In the previous LLVM assignment, you have used the interface LLVM provided. From this assignment on, we are starting to do a loop parallelization term project which is divided into 3 assignments: (1) Loop detection. (2) Dependence analysis and induction variable analysis. (3) Parallelization.

RUST may also be used if there are enough interests.  Email Jacob Bisnett if you are interested.

IMPORTANT NOTES: As we are doing term project from this assignment on, the problem we are going to solve is more close to the real-world compiler development.   The assignment may have missing information and you may encounter problems not covered by the textbooks or the lectures, part of the project experience is to take initiative, formulate these problems, seek help from others (teaching staff, classmates, and online resources), and solve these problems .

The deadline is 11:59pm Friday March 10th. 

For this assignment, you need to use data flow analysis to find loops in the LLVM IR code.

The definition for a loop in the flow graph can be find in the dragon book Chapter 8.4.5 P531. The loop identification approach can be found in these slides from CMU .

For implementation, three steps described in the slides are needed as follows.  Each step generates an output which will be used for grading.

(1) Calculate Dominance relation for basic blocks by data flow analysis.  Provide a function named dump to output the dominance relation.  (Do NOT use the dominator analysis in the LLVM compiler.)

• To calculate Dominance, you need to traverse CFG.  Take a look at the class reference for functions and basic blocks to see how to find the entry block and how to find the successors or predecessors for a given basic block;
• You also need to know about some C++ data structures, such as vectors, map, pair, stack, queue. That will simply your implementation.
• To find the name of basic blocks, look at the APIs such as hasName(), getValueName(), setValueName() provided in value class.

(2) Find back edges; Provide a dump function to output all back edges.

(3) Find natural Loops. Provide a dump function to dump the set of basic blocks in the loop.

The output should first give the number of loops, the dominance relation and all back edges. For each loop, output a set of basic blocks in the loop. For example:

======================

Number of loops: 1

Dominance relation: BB1 -> BB2, BB1->BB3, BB2->BB3

Back edge: BB3 -> BB1

Basic blocks in the loop 1: BB1, BB2, BB3

=======================

Write at least two test programs with at least one loop in each program. Provide detailed README file to describe the design and limitations, including what types of loops can be detected and what types of loops can not.

Extra credit (10%):

LLVM built-in analysis may be useful for loop detection, for example the dominator analysis in the LLVM compiler?  Implement a second loop detection pass which you can use any LLVM API for loop detection. Compare different implementations and write down the detection coverage for different loop structures.