blob: 56a20730b78a2efb4cbb0659c52df6766b0b2a20 [file] [log] [blame]
Chris Lattnercf3056d2003-10-13 03:32:08 +00001//===-- InstLoops.cpp -----------------------------------------------------===//
John Criswellb576c942003-10-20 19:43:21 +00002//
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 Lattnercf3056d2003-10-13 03:32:08 +00009//
Brian Gaekecc9620c2004-05-14 21:21:52 +000010// 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 Lattnercf3056d2003-10-13 03:32:08 +000014//
Anand Shukla93d545e2002-11-03 01:45:20 +000015//===----------------------------------------------------------------------===//
16
Anand Shukla666ff522003-07-10 21:55:57 +000017#include "llvm/Analysis/Dominators.h"
Anand Shukla93d545e2002-11-03 01:45:20 +000018#include "llvm/Support/CFG.h"
Misha Brukman47b14a42004-07-29 17:30:56 +000019#include "llvm/Instructions.h"
Anand Shukla93d545e2002-11-03 01:45:20 +000020#include "llvm/Module.h"
Anand Shukla93d545e2002-11-03 01:45:20 +000021#include "llvm/Pass.h"
Misha Brukman47b14a42004-07-29 17:30:56 +000022#include "llvm/Type.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000023#include "llvm/Support/Debug.h"
Brian Gaekecc9620c2004-05-14 21:21:52 +000024#include "../ProfilingUtils.h"
Anand Shukla93d545e2002-11-03 01:45:20 +000025
Brian Gaeked0fde302003-11-11 22:41:34 +000026namespace llvm {
27
Anand Shukla93d545e2002-11-03 01:45:20 +000028//this is used to color vertices
29//during DFS
30
31enum Color{
32 WHITE,
33 GREY,
34 BLACK
35};
36
Chris Lattnercf3056d2003-10-13 03:32:08 +000037namespace {
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000038 typedef std::map<BasicBlock *, BasicBlock *> BBMap;
Anand Shukla666ff522003-07-10 21:55:57 +000039 struct InstLoops : public FunctionPass {
40 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
41 AU.addRequired<DominatorSet>();
42 }
43 private:
Brian Gaekecc9620c2004-05-14 21:21:52 +000044 Function *inCountMth;
Anand Shukla666ff522003-07-10 21:55:57 +000045 DominatorSet *DS;
46 void getBackEdgesVisit(BasicBlock *u,
47 std::map<BasicBlock *, Color > &color,
48 std::map<BasicBlock *, int > &d,
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000049 int &time, BBMap &be);
50 void removeRedundant(BBMap &be);
51 void findAndInstrumentBackEdges(Function &F);
Anand Shukla666ff522003-07-10 21:55:57 +000052 public:
Brian Gaekecc9620c2004-05-14 21:21:52 +000053 bool doInitialization(Module &M);
Anand Shukla666ff522003-07-10 21:55:57 +000054 bool runOnFunction(Function &F);
55 };
56
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000057 RegisterOpt<InstLoops> X("instloops", "Instrument backedges for profiling");
Anand Shukla666ff522003-07-10 21:55:57 +000058}
Anand Shukla93d545e2002-11-03 01:45:20 +000059
Anand Shukla93d545e2002-11-03 01:45:20 +000060//helper function to get back edges: it is called by
61//the "getBackEdges" function below
Anand Shukla666ff522003-07-10 21:55:57 +000062void InstLoops::getBackEdgesVisit(BasicBlock *u,
Anand Shukla93d545e2002-11-03 01:45:20 +000063 std::map<BasicBlock *, Color > &color,
64 std::map<BasicBlock *, int > &d,
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000065 int &time, BBMap &be) {
Anand Shukla93d545e2002-11-03 01:45:20 +000066 color[u]=GREY;
67 time++;
68 d[u]=time;
69
Chris Lattnerf8b5b6d2003-09-24 22:06:25 +000070 for(succ_iterator vl = succ_begin(u), ve = succ_end(u); vl != ve; ++vl){
Anand Shukla93d545e2002-11-03 01:45:20 +000071 BasicBlock *BB = *vl;
72
73 if(color[BB]!=GREY && color[BB]!=BLACK){
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000074 getBackEdgesVisit(BB, color, d, time, be);
Anand Shukla93d545e2002-11-03 01:45:20 +000075 }
76
77 //now checking for d and f vals
Anand Shukla666ff522003-07-10 21:55:57 +000078 else if(color[BB]==GREY){
Anand Shukla93d545e2002-11-03 01:45:20 +000079 //so v is ancestor of u if time of u > time of v
80 if(d[u] >= d[BB]){
Anand Shukla666ff522003-07-10 21:55:57 +000081 //u->BB is a backedge
82 be[u] = BB;
Anand Shukla93d545e2002-11-03 01:45:20 +000083 }
84 }
85 }
86 color[u]=BLACK;//done with visiting the node and its neighbors
87}
88
Anand Shukla666ff522003-07-10 21:55:57 +000089//look at all BEs, and remove all BEs that are dominated by other BE's in the
90//set
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000091void InstLoops::removeRedundant(BBMap &be) {
Anand Shukla666ff522003-07-10 21:55:57 +000092 std::vector<BasicBlock *> toDelete;
93 for(std::map<BasicBlock *, BasicBlock *>::iterator MI = be.begin(),
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000094 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 Shukla666ff522003-07-10 21:55:57 +000097 toDelete.push_back(MMI->first);
Brian Gaekeaee2fdf2003-08-12 22:00:24 +000098 // Remove all the back-edges we found from be.
Anand Shukla666ff522003-07-10 21:55:57 +000099 for(std::vector<BasicBlock *>::iterator VI = toDelete.begin(),
Brian Gaekeaee2fdf2003-08-12 22:00:24 +0000100 VE = toDelete.end(); VI != VE; ++VI)
Anand Shukla666ff522003-07-10 21:55:57 +0000101 be.erase(*VI);
Anand Shukla666ff522003-07-10 21:55:57 +0000102}
Anand Shukla93d545e2002-11-03 01:45:20 +0000103
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 Gaekeaee2fdf2003-08-12 22:00:24 +0000115void InstLoops::findAndInstrumentBackEdges(Function &F){
Anand Shukla93d545e2002-11-03 01:45:20 +0000116 std::map<BasicBlock *, Color > color;
117 std::map<BasicBlock *, int> d;
Brian Gaekeaee2fdf2003-08-12 22:00:24 +0000118 BBMap be;
Anand Shukla93d545e2002-11-03 01:45:20 +0000119 int time=0;
Brian Gaekeaee2fdf2003-08-12 22:00:24 +0000120 getBackEdgesVisit(F.begin(), color, d, time, be);
Anand Shukla666ff522003-07-10 21:55:57 +0000121
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 Gaekecc9620c2004-05-14 21:21:52 +0000128 // 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 Shukla666ff522003-07-10 21:55:57 +0000134 BranchInst *ti = cast<BranchInst>(u->getTerminator());
Brian Gaekecc9620c2004-05-14 21:21:52 +0000135 unsigned char index = ((ti->getSuccessor(0) == BB) ? 0 : 1);
136
Anand Shukla666ff522003-07-10 21:55:57 +0000137 assert(ti->getNumSuccessors() > index && "Not enough successors!");
138 ti->setSuccessor(index, newBB);
139
140 BasicBlock::InstListType &lt = newBB->getInstList();
Chris Lattnerf8485c62003-11-20 18:25:24 +0000141 lt.push_back(new CallInst(inCountMth));
142 new BranchInst(BB, newBB);
Anand Shukla666ff522003-07-10 21:55:57 +0000143
Brian Gaekecc9620c2004-05-14 21:21:52 +0000144 // Now, set the sources of Phi nodes corresponding to the back-edge
145 // in BB to come from the instrumentation block instead.
Anand Shukla666ff522003-07-10 21:55:57 +0000146 for(BasicBlock::iterator BB2Inst = BB->begin(), BBend = BB->end();
Brian Gaekecc9620c2004-05-14 21:21:52 +0000147 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 Shukla666ff522003-07-10 21:55:57 +0000152 }
153 }
154 }
Anand Shukla93d545e2002-11-03 01:45:20 +0000155}
156
Brian Gaekecc9620c2004-05-14 21:21:52 +0000157bool 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 Gaekeaee2fdf2003-08-12 22:00:24 +0000164///
Anand Shukla93d545e2002-11-03 01:45:20 +0000165bool InstLoops::runOnFunction(Function &F){
Brian Gaekecc9620c2004-05-14 21:21:52 +0000166 if (F.isExternal ())
Anand Shukla666ff522003-07-10 21:55:57 +0000167 return false;
Brian Gaekecc9620c2004-05-14 21:21:52 +0000168
169 DS = &getAnalysis<DominatorSet> ();
170
Brian Gaekeaee2fdf2003-08-12 22:00:24 +0000171 // Add a call to reoptimizerInitialize() to beginning of function named main.
Brian Gaekecc9620c2004-05-14 21:21:52 +0000172 if (F.getName() == "main")
173 InsertProfilingInitCall (&F, "reoptimizerInitialize");
174
Brian Gaekeaee2fdf2003-08-12 22:00:24 +0000175 findAndInstrumentBackEdges(F);
176 return true; // Function was modified.
Anand Shukla93d545e2002-11-03 01:45:20 +0000177}
Brian Gaeked0fde302003-11-11 22:41:34 +0000178
179} // End llvm namespace