Things todo

[zalex11]

1. implement the methods to detect loops and Dominator trees/sets
2. Compute minimum dominator set with a back edge which will give the innermost loop.
3. implement algorithm to compute edge weights on paths
4. Identify the chordal edges(Not part of the minimum spanning tree)
5. Assign Inc(c) function to each chordal edge.[Placing Instrumentation]
6. Determine the path execution information from the instrumentation profile.

add what ever else you think of or add more detail.

[zalex11]

http://llvm.org/docs/ProgrammersManual.html#iterating-over-the-basicblock-in-a-function
so it looks like we can iterate over all the basic blocks in a function with this iterator and choose to go backwards for implementing the algorithm http://www.cplusplus.com/reference/iterator/reverse_iterator/

[aditya23788]

I found a simple implementation for basic block labeling. Don't know how useful it is. I am going through the Programmers Manual right now...
https://github.com/liuml07/giri/blob/master/lib/Utility/BasicBlockNumbering.cpp

[zalex11]

http://llvm.org/docs/doxygen/html/Dominators_8cpp_source.html would the fucntion bool DominatorTree::dominates be similar to what we want?

[aditya23788]

I don't know whether we are allowed to use utilities from the Dominator class. TA said that we have to compute the dominator info it seems but I am not sure.

[zalex11]

i know we cant like #include dominators.cpp but we can use their logic to implement our own.

[aditya23788]

One doubt that I had: Do we need to path profile only the innermost loop or the whole loop structure within a function?

[zalex11]

from the assignment page sample example

foreach Module M:
    foreach Funcion f in M:
      foreach BasicBlock b in F:
        Add code to increment bbCounter;

maybe we should

foreach Module M:
    foreach Funcion f in M:
      foreach BasicBlock b in F:
        calculate dominator set
      foreach BasicBlock b inreverse F:
        calculate edge weights with algorithm

I think the dominators can be calculated with a dfs
http://www.boost.org/doc/libs/1_38_0/boost/graph/dominator_tree.hpp another dominator tree implementation http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/lengauer_tarjan_dominator.htm

[aditya23788]

By finding dominator tree how are we going to determine the back edges... The algorithm discussed in class in not clear on that. I mean we can determine back edges by DFS but I am not clear on how to determine it using the dominator sets computed for each node. Do you have any idea on that?

[zalex11]

http://eli.thegreenplace.net/2013/09/16/analyzing-function-cfgs-with-llvm
This might be why some people were doing graph coloring.

[zalex11]

void BasicBlocksDemo::updateArray(BasicBlock &bb)
{
    IRBuilder<> IRB(bb.getFirstInsertionPt());
    Value *loadAddr = IRB.CreateLoad(bbCounter);
    Value *pathAddr = IRB.CreateLoad(pathctr);
    Value *pathCtr = IRB.CreateExtractElement(pathAddr,loadAddr);
    Value *pathUpdateValue = IRB.CreateAdd(ConstantInt::get(Type::getInt32Ty(*Context), 1),pathCtr);
    IRB.CreateInsertElement(pathAddr,pathUpdateValue,loadAddr);
    }