Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 1 | //===-- InstLoops.cpp -----------------------------------------------------===// |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 9 | // |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 10 | // This is the first-level instrumentation pass for the Reoptimizer. It |
| 11 | // instrument the back-edges of loops by inserting a basic block |
| 12 | // containing a call to llvm_first_trigger (the first-level trigger function), |
| 13 | // and inserts an initialization call to the main() function. |
Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 14 | // |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 15 | //===----------------------------------------------------------------------===// |
| 16 | |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 17 | #include "llvm/Analysis/Dominators.h" |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 18 | #include "llvm/Support/CFG.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 19 | #include "llvm/Instructions.h" |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 20 | #include "llvm/Module.h" |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 21 | #include "llvm/Pass.h" |
Misha Brukman | 47b14a4 | 2004-07-29 17:30:56 +0000 | [diff] [blame] | 22 | #include "llvm/Type.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame^] | 23 | #include "llvm/Support/Debug.h" |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 24 | #include "../ProfilingUtils.h" |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 25 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 26 | namespace llvm { |
| 27 | |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 28 | //this is used to color vertices |
| 29 | //during DFS |
| 30 | |
| 31 | enum Color{ |
| 32 | WHITE, |
| 33 | GREY, |
| 34 | BLACK |
| 35 | }; |
| 36 | |
Chris Lattner | cf3056d | 2003-10-13 03:32:08 +0000 | [diff] [blame] | 37 | namespace { |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 38 | typedef std::map<BasicBlock *, BasicBlock *> BBMap; |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 39 | struct InstLoops : public FunctionPass { |
| 40 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 41 | AU.addRequired<DominatorSet>(); |
| 42 | } |
| 43 | private: |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 44 | Function *inCountMth; |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 45 | DominatorSet *DS; |
| 46 | void getBackEdgesVisit(BasicBlock *u, |
| 47 | std::map<BasicBlock *, Color > &color, |
| 48 | std::map<BasicBlock *, int > &d, |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 49 | int &time, BBMap &be); |
| 50 | void removeRedundant(BBMap &be); |
| 51 | void findAndInstrumentBackEdges(Function &F); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 52 | public: |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 53 | bool doInitialization(Module &M); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 54 | bool runOnFunction(Function &F); |
| 55 | }; |
| 56 | |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 57 | RegisterOpt<InstLoops> X("instloops", "Instrument backedges for profiling"); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 58 | } |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 59 | |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 60 | //helper function to get back edges: it is called by |
| 61 | //the "getBackEdges" function below |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 62 | void InstLoops::getBackEdgesVisit(BasicBlock *u, |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 63 | std::map<BasicBlock *, Color > &color, |
| 64 | std::map<BasicBlock *, int > &d, |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 65 | int &time, BBMap &be) { |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 66 | color[u]=GREY; |
| 67 | time++; |
| 68 | d[u]=time; |
| 69 | |
Chris Lattner | f8b5b6d | 2003-09-24 22:06:25 +0000 | [diff] [blame] | 70 | for(succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){ |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 71 | BasicBlock *BB = *vl; |
| 72 | |
| 73 | if(color[BB]!=GREY && color[BB]!=BLACK){ |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 74 | getBackEdgesVisit(BB, color, d, time, be); |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 75 | } |
| 76 | |
| 77 | //now checking for d and f vals |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 78 | else if(color[BB]==GREY){ |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 79 | //so v is ancestor of u if time of u > time of v |
| 80 | if(d[u] >= d[BB]){ |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 81 | //u->BB is a backedge |
| 82 | be[u] = BB; |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 83 | } |
| 84 | } |
| 85 | } |
| 86 | color[u]=BLACK;//done with visiting the node and its neighbors |
| 87 | } |
| 88 | |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 89 | //look at all BEs, and remove all BEs that are dominated by other BE's in the |
| 90 | //set |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 91 | void InstLoops::removeRedundant(BBMap &be) { |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 92 | std::vector<BasicBlock *> toDelete; |
| 93 | for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 94 | ME = be.end(); MI != ME; ++MI) |
| 95 | for(BBMap::iterator MMI = be.begin(), MME = be.end(); MMI != MME; ++MMI) |
| 96 | if(DS->properlyDominates(MI->first, MMI->first)) |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 97 | toDelete.push_back(MMI->first); |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 98 | // Remove all the back-edges we found from be. |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 99 | for(std::vector<BasicBlock *>::iterator VI = toDelete.begin(), |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 100 | VE = toDelete.end(); VI != VE; ++VI) |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 101 | be.erase(*VI); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 102 | } |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 103 | |
| 104 | //getting the backedges in a graph |
| 105 | //Its a variation of DFS to get the backedges in the graph |
| 106 | //We get back edges by associating a time |
| 107 | //and a color with each vertex. |
| 108 | //The time of a vertex is the time when it was first visited |
| 109 | //The color of a vertex is initially WHITE, |
| 110 | //Changes to GREY when it is first visited, |
| 111 | //and changes to BLACK when ALL its neighbors |
| 112 | //have been visited |
| 113 | //So we have a back edge when we meet a successor of |
| 114 | //a node with smaller time, and GREY color |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 115 | void InstLoops::findAndInstrumentBackEdges(Function &F){ |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 116 | std::map<BasicBlock *, Color > color; |
| 117 | std::map<BasicBlock *, int> d; |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 118 | BBMap be; |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 119 | int time=0; |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 120 | getBackEdgesVisit(F.begin(), color, d, time, be); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 121 | |
| 122 | removeRedundant(be); |
| 123 | |
| 124 | for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(), |
| 125 | ME = be.end(); MI != ME; ++MI){ |
| 126 | BasicBlock *u = MI->first; |
| 127 | BasicBlock *BB = MI->second; |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 128 | // We have a back-edge from BB --> u. |
| 129 | DEBUG (std::cerr << "Instrumenting back-edge from " << BB->getName () |
| 130 | << "-->" << u->getName () << "\n"); |
| 131 | // Split the back-edge, inserting a new basic block on it, and modify the |
| 132 | // source BB's terminator accordingly. |
| 133 | BasicBlock *newBB = new BasicBlock("backEdgeInst", u->getParent()); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 134 | BranchInst *ti = cast<BranchInst>(u->getTerminator()); |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 135 | unsigned char index = ((ti->getSuccessor(0) == BB) ? 0 : 1); |
| 136 | |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 137 | assert(ti->getNumSuccessors() > index && "Not enough successors!"); |
| 138 | ti->setSuccessor(index, newBB); |
| 139 | |
| 140 | BasicBlock::InstListType < = newBB->getInstList(); |
Chris Lattner | f8485c6 | 2003-11-20 18:25:24 +0000 | [diff] [blame] | 141 | lt.push_back(new CallInst(inCountMth)); |
| 142 | new BranchInst(BB, newBB); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 143 | |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 144 | // Now, set the sources of Phi nodes corresponding to the back-edge |
| 145 | // in BB to come from the instrumentation block instead. |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 146 | for(BasicBlock::iterator BB2Inst = BB->begin(), BBend = BB->end(); |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 147 | BB2Inst != BBend; ++BB2Inst) { |
| 148 | if (PHINode *phiInst = dyn_cast<PHINode>(BB2Inst)) { |
| 149 | int bbIndex = phiInst->getBasicBlockIndex(u); |
| 150 | if (bbIndex>=0) |
| 151 | phiInst->setIncomingBlock(bbIndex, newBB); |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 152 | } |
| 153 | } |
| 154 | } |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 155 | } |
| 156 | |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 157 | bool InstLoops::doInitialization (Module &M) { |
| 158 | inCountMth = M.getOrInsertFunction("llvm_first_trigger", Type::VoidTy, 0); |
| 159 | return true; // Module was modified. |
| 160 | } |
| 161 | |
| 162 | /// runOnFunction - Entry point for FunctionPass that inserts calls to |
| 163 | /// trigger function. |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 164 | /// |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 165 | bool InstLoops::runOnFunction(Function &F){ |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 166 | if (F.isExternal ()) |
Anand Shukla | 666ff52 | 2003-07-10 21:55:57 +0000 | [diff] [blame] | 167 | return false; |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 168 | |
| 169 | DS = &getAnalysis<DominatorSet> (); |
| 170 | |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 171 | // Add a call to reoptimizerInitialize() to beginning of function named main. |
Brian Gaeke | cc9620c | 2004-05-14 21:21:52 +0000 | [diff] [blame] | 172 | if (F.getName() == "main") |
| 173 | InsertProfilingInitCall (&F, "reoptimizerInitialize"); |
| 174 | |
Brian Gaeke | aee2fdf | 2003-08-12 22:00:24 +0000 | [diff] [blame] | 175 | findAndInstrumentBackEdges(F); |
| 176 | return true; // Function was modified. |
Anand Shukla | 93d545e | 2002-11-03 01:45:20 +0000 | [diff] [blame] | 177 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 178 | |
| 179 | } // End llvm namespace |