Here's a list of projects that I would like to suggest for cs715. It is strongly recommended that the projects be done in groups of two. However, I don't want to make it mandatory; so if you want do a project alone that is fine by me but I would like this to be discussed clearly so that you are aware of what you are getting into.
Implementing gdfa
for RTL (preferably for gcc-4.4.2 or even gcc-4.4.3). At the moment,
gdfa performs data flow analysis on gimple representation rather than
RTL representation. This project basically involves providing an
alternate set of APIs that read RTL IR instead of gimple IR.
Providing support for specification of transformations in gdfa. This could be on gimple in gcc-4.3.0 for simplicity. Currently, gdfa supports only analysis but no transformation. For example, one could specify available expressions analysis and perform it using gdfa. However, one still needs to write a C code that will use the result of available expressions analysis and perform the actual transformation of common subexpression elimination.
Providing support for functional method of interprocedural data flow analysis using reductions of compositions and meets of flow functions in gdfa. This could be on gcc-4.3.0 for simplicity.
Providing support for functional method of interprocedural data flow analysis using the tabulation method in gdfa. This could be on gcc-4.3.0 for simplicity. A tabulation method of functional approach remembers the pairs (in,out) for each procedure p where in is a particular data flow value reaching the entry of procedure p and out is the corresponding data flow value reaching the exit of p discovered after analyzing p. The analysis of p is performed iteratively. If a new value in2 reaches the entry of p, the procedure is analyzed once again and the corresponding out2 value is remembered. Under the assumption that the lattice of data flow values is finite, the termination of this method is guaranteed. This method is functional because when a procedural call is encountered, the input-output table for that procedure is consulted to explore the possibility of directly using the out value and avoiding re-analysis of the procedure being called. This method avoids the need of reducing compositions and meets of flow functions.
Efficient interprocedural analysis using k-lengh suffix call
strings method in gcc-4.4.2. In the presence of cycles formed by interprocedurally
invalid control flow paths, the fixed length suffix based approximate
call strings method for interprocedural data flow analysis
becomes inefficient. This problem arises because the length of
these paths (in terms of call sites) is typically larger
than the practically chosen length of suffixes of call strings retained
in the approximate call strings method. As a consequence, data flow
value propagation along these cyclic paths gets performed iteratively
until a fixed point is reached. If longer call strings are maintained,
interprocedurally invalid cyclic paths would be avoided automatically.
This is a curious situation where approximation introduced for
efficiency actually causes inefficiency! There is an intersting
approach which shows that a significant amount of efficiency can be
achieved by a minor variation in the algorithm. This project involves
implementing this approach for call strings for k from 1 to 3.
Implementing cilk in gcc (taken up by Prathmesh Prabhu).
Implemeting call strings based points-to analysis in GCC 4.4.2 (taken up by Prashant Singh Rawat).
Rewriting one of the following groups of instructions in i386
machine description using the new constructs proposed by Sagar. Please see this for more details
about the overall approach.
Arithmetic Instructions: Add, Subtract, Multiply, SSE5 scalar multiply/add (defined in sse.md), Divide, and Remainder instructions.
Control flow related instructions: Move, Conditional Move, Push/pop, Store-flag, Conditional jump, Unconditional jump (and variants), Call, Prologue and epilogue, Block operation instructions.
Logical and Relational Instructions: AND, OR (inclusive), XOR, Nagation, Compare, One's Complement instructions. Instructions to convert (a) HImode/SImode test with immediate to QImode ones and (b) wide AND instructions with immediate operand to shorter QImode.
Shift & Rotate Instructions: Arithmetic shift, logical shift, Rotate, Bit set/test, Zero/Sign extension instructions. Instructions to implement rotation using two double-precision shift instructions and to implement rotation using two double-precision shift instructions.