LLVM API Documentation
00001 //===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the pass that optimize code placement and align loop 00011 // headers to target specific alignment boundary. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "code-placement" 00016 #include "llvm/CodeGen/MachineLoopInfo.h" 00017 #include "llvm/CodeGen/MachineFunctionPass.h" 00018 #include "llvm/CodeGen/Passes.h" 00019 #include "llvm/Target/TargetInstrInfo.h" 00020 #include "llvm/Target/TargetLowering.h" 00021 #include "llvm/Target/TargetMachine.h" 00022 #include "llvm/Support/Compiler.h" 00023 #include "llvm/Support/Debug.h" 00024 #include "llvm/ADT/Statistic.h" 00025 using namespace llvm; 00026 00027 STATISTIC(NumHeaderAligned, "Number of loop header aligned"); 00028 STATISTIC(NumIntraElim, "Number of intra loop branches eliminated"); 00029 STATISTIC(NumIntraMoved, "Number of intra loop branches moved"); 00030 00031 namespace { 00032 class CodePlacementOpt : public MachineFunctionPass { 00033 const MachineLoopInfo *MLI; 00034 const TargetInstrInfo *TII; 00035 const TargetLowering *TLI; 00036 00037 /// ChangedMBBs - BBs which are modified by OptimizeIntraLoopEdges. 00038 SmallPtrSet<MachineBasicBlock*, 8> ChangedMBBs; 00039 00040 /// UncondJmpMBBs - A list of BBs which are in loops and end with 00041 /// unconditional branches. 00042 SmallVector<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 4> 00043 UncondJmpMBBs; 00044 00045 /// LoopHeaders - A list of BBs which are loop headers. 00046 SmallVector<MachineBasicBlock*, 4> LoopHeaders; 00047 00048 public: 00049 static char ID; 00050 CodePlacementOpt() : MachineFunctionPass(&ID) {} 00051 00052 virtual bool runOnMachineFunction(MachineFunction &MF); 00053 virtual const char *getPassName() const { 00054 return "Code Placement Optimizater"; 00055 } 00056 00057 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00058 AU.addRequired<MachineLoopInfo>(); 00059 AU.addPreservedID(MachineDominatorsID); 00060 MachineFunctionPass::getAnalysisUsage(AU); 00061 } 00062 00063 private: 00064 bool OptimizeIntraLoopEdges(); 00065 bool HeaderShouldBeAligned(MachineBasicBlock *MBB, MachineLoop *L, 00066 SmallPtrSet<MachineBasicBlock*, 4> &DoNotAlign); 00067 bool AlignLoops(MachineFunction &MF); 00068 }; 00069 00070 char CodePlacementOpt::ID = 0; 00071 } // end anonymous namespace 00072 00073 FunctionPass *llvm::createCodePlacementOptPass() { 00074 return new CodePlacementOpt(); 00075 } 00076 00077 /// OptimizeBackEdges - Place loop back edges to move unconditional branches 00078 /// out of the loop. 00079 /// 00080 /// A: 00081 /// ... 00082 /// <fallthrough to B> 00083 /// 00084 /// B: --> loop header 00085 /// ... 00086 /// jcc <cond> C, [exit] 00087 /// 00088 /// C: 00089 /// ... 00090 /// jmp B 00091 /// 00092 /// ==> 00093 /// 00094 /// A: 00095 /// ... 00096 /// jmp B 00097 /// 00098 /// C: --> new loop header 00099 /// ... 00100 /// <fallthough to B> 00101 /// 00102 /// B: 00103 /// ... 00104 /// jcc <cond> C, [exit] 00105 /// 00106 bool CodePlacementOpt::OptimizeIntraLoopEdges() { 00107 if (!TLI->shouldOptimizeCodePlacement()) 00108 return false; 00109 00110 bool Changed = false; 00111 for (unsigned i = 0, e = UncondJmpMBBs.size(); i != e; ++i) { 00112 MachineBasicBlock *MBB = UncondJmpMBBs[i].first; 00113 MachineBasicBlock *SuccMBB = UncondJmpMBBs[i].second; 00114 MachineLoop *L = MLI->getLoopFor(MBB); 00115 assert(L && "BB is expected to be in a loop!"); 00116 00117 if (ChangedMBBs.count(MBB)) { 00118 // BB has been modified, re-analyze. 00119 MachineBasicBlock *TBB = 0, *FBB = 0; 00120 SmallVector<MachineOperand, 4> Cond; 00121 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty()) 00122 continue; 00123 if (MLI->getLoopFor(TBB) != L || TBB->isLandingPad()) 00124 continue; 00125 SuccMBB = TBB; 00126 } else { 00127 assert(MLI->getLoopFor(SuccMBB) == L && 00128 "Successor is not in the same loop!"); 00129 } 00130 00131 if (MBB->isLayoutSuccessor(SuccMBB)) { 00132 // Successor is right after MBB, just eliminate the unconditional jmp. 00133 // Can this happen? 00134 TII->RemoveBranch(*MBB); 00135 ChangedMBBs.insert(MBB); 00136 ++NumIntraElim; 00137 Changed = true; 00138 continue; 00139 } 00140 00141 // Now check if the predecessor is fallthrough from any BB. If there is, 00142 // that BB should be from outside the loop since edge will become a jmp. 00143 bool OkToMove = true; 00144 MachineBasicBlock *FtMBB = 0, *FtTBB = 0, *FtFBB = 0; 00145 SmallVector<MachineOperand, 4> FtCond; 00146 for (MachineBasicBlock::pred_iterator PI = SuccMBB->pred_begin(), 00147 PE = SuccMBB->pred_end(); PI != PE; ++PI) { 00148 MachineBasicBlock *PredMBB = *PI; 00149 if (PredMBB->isLayoutSuccessor(SuccMBB)) { 00150 if (TII->AnalyzeBranch(*PredMBB, FtTBB, FtFBB, FtCond)) { 00151 OkToMove = false; 00152 break; 00153 } 00154 if (!FtTBB) 00155 FtTBB = SuccMBB; 00156 else if (!FtFBB) { 00157 assert(FtFBB != SuccMBB && "Unexpected control flow!"); 00158 FtFBB = SuccMBB; 00159 } 00160 00161 // A fallthrough. 00162 FtMBB = PredMBB; 00163 MachineLoop *PL = MLI->getLoopFor(PredMBB); 00164 if (PL && (PL == L || PL->getLoopDepth() >= L->getLoopDepth())) 00165 OkToMove = false; 00166 00167 break; 00168 } 00169 } 00170 00171 if (!OkToMove) 00172 continue; 00173 00174 // Is it profitable? If SuccMBB can fallthrough itself, that can be changed 00175 // into a jmp. 00176 MachineBasicBlock *TBB = 0, *FBB = 0; 00177 SmallVector<MachineOperand, 4> Cond; 00178 if (TII->AnalyzeBranch(*SuccMBB, TBB, FBB, Cond)) 00179 continue; 00180 if (!TBB && Cond.empty()) 00181 TBB = next(MachineFunction::iterator(SuccMBB)); 00182 else if (!FBB && !Cond.empty()) 00183 FBB = next(MachineFunction::iterator(SuccMBB)); 00184 00185 // This calculate the cost of the transformation. Also, it finds the *only* 00186 // intra-loop edge if there is one. 00187 int Cost = 0; 00188 bool HasOneIntraSucc = true; 00189 MachineBasicBlock *IntraSucc = 0; 00190 for (MachineBasicBlock::succ_iterator SI = SuccMBB->succ_begin(), 00191 SE = SuccMBB->succ_end(); SI != SE; ++SI) { 00192 MachineBasicBlock *SSMBB = *SI; 00193 if (MLI->getLoopFor(SSMBB) == L) { 00194 if (!IntraSucc) 00195 IntraSucc = SSMBB; 00196 else 00197 HasOneIntraSucc = false; 00198 } 00199 00200 if (SuccMBB->isLayoutSuccessor(SSMBB)) 00201 // This will become a jmp. 00202 ++Cost; 00203 else if (MBB->isLayoutSuccessor(SSMBB)) { 00204 // One of the successor will become the new fallthrough. 00205 if (SSMBB == FBB) { 00206 FBB = 0; 00207 --Cost; 00208 } else if (!FBB && SSMBB == TBB && Cond.empty()) { 00209 TBB = 0; 00210 --Cost; 00211 } else if (!Cond.empty() && !TII->ReverseBranchCondition(Cond)) { 00212 assert(SSMBB == TBB); 00213 TBB = FBB; 00214 FBB = 0; 00215 --Cost; 00216 } 00217 } 00218 } 00219 if (Cost) 00220 continue; 00221 00222 // Now, let's move the successor to below the BB to eliminate the jmp. 00223 SuccMBB->moveAfter(MBB); 00224 TII->RemoveBranch(*MBB); 00225 TII->RemoveBranch(*SuccMBB); 00226 if (TBB) 00227 TII->InsertBranch(*SuccMBB, TBB, FBB, Cond); 00228 ChangedMBBs.insert(MBB); 00229 ChangedMBBs.insert(SuccMBB); 00230 if (FtMBB) { 00231 TII->RemoveBranch(*FtMBB); 00232 TII->InsertBranch(*FtMBB, FtTBB, FtFBB, FtCond); 00233 ChangedMBBs.insert(FtMBB); 00234 } 00235 Changed = true; 00236 00237 // If BB is the loop latch, we may have a new loop headr. 00238 if (MBB == L->getLoopLatch()) { 00239 assert(MLI->isLoopHeader(SuccMBB) && 00240 "Only succ of loop latch is not the header?"); 00241 if (HasOneIntraSucc && IntraSucc) 00242 std::replace(LoopHeaders.begin(),LoopHeaders.end(), SuccMBB, IntraSucc); 00243 } 00244 } 00245 00246 ++NumIntraMoved; 00247 return Changed; 00248 } 00249 00250 /// HeaderShouldBeAligned - Return true if the specified loop header block 00251 /// should be aligned. For now, we will not align it if all the predcessors 00252 /// (i.e. loop back edges) are laid out above the header. FIXME: Do not 00253 /// align small loops. 00254 bool 00255 CodePlacementOpt::HeaderShouldBeAligned(MachineBasicBlock *MBB, MachineLoop *L, 00256 SmallPtrSet<MachineBasicBlock*, 4> &DoNotAlign) { 00257 if (DoNotAlign.count(MBB)) 00258 return false; 00259 00260 bool BackEdgeBelow = false; 00261 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(), 00262 PE = MBB->pred_end(); PI != PE; ++PI) { 00263 MachineBasicBlock *PredMBB = *PI; 00264 if (PredMBB == MBB || PredMBB->getNumber() > MBB->getNumber()) { 00265 BackEdgeBelow = true; 00266 break; 00267 } 00268 } 00269 00270 if (!BackEdgeBelow) 00271 return false; 00272 00273 // Ok, we are going to align this loop header. If it's an inner loop, 00274 // do not align its outer loop. 00275 MachineBasicBlock *PreHeader = L->getLoopPreheader(); 00276 if (PreHeader) { 00277 MachineLoop *L = MLI->getLoopFor(PreHeader); 00278 if (L) { 00279 MachineBasicBlock *HeaderBlock = L->getHeader(); 00280 HeaderBlock->setAlignment(0); 00281 DoNotAlign.insert(HeaderBlock); 00282 } 00283 } 00284 return true; 00285 } 00286 00287 /// AlignLoops - Align loop headers to target preferred alignments. 00288 /// 00289 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) { 00290 const Function *F = MF.getFunction(); 00291 if (F->hasFnAttr(Attribute::OptimizeForSize)) 00292 return false; 00293 00294 unsigned Align = TLI->getPrefLoopAlignment(); 00295 if (!Align) 00296 return false; // Don't care about loop alignment. 00297 00298 // Make sure blocks are numbered in order 00299 MF.RenumberBlocks(); 00300 00301 bool Changed = false; 00302 SmallPtrSet<MachineBasicBlock*, 4> DoNotAlign; 00303 for (unsigned i = 0, e = LoopHeaders.size(); i != e; ++i) { 00304 MachineBasicBlock *HeaderMBB = LoopHeaders[i]; 00305 MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(HeaderMBB)); 00306 MachineLoop *L = MLI->getLoopFor(HeaderMBB); 00307 if (L == MLI->getLoopFor(PredMBB)) 00308 // If previously BB is in the same loop, don't align this BB. We want 00309 // to prevent adding noop's inside a loop. 00310 continue; 00311 if (HeaderShouldBeAligned(HeaderMBB, L, DoNotAlign)) { 00312 HeaderMBB->setAlignment(Align); 00313 Changed = true; 00314 ++NumHeaderAligned; 00315 } 00316 } 00317 00318 return Changed; 00319 } 00320 00321 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) { 00322 MLI = &getAnalysis<MachineLoopInfo>(); 00323 if (MLI->empty()) 00324 return false; // No loops. 00325 00326 TLI = MF.getTarget().getTargetLowering(); 00327 TII = MF.getTarget().getInstrInfo(); 00328 00329 // Analyze the BBs first and keep track of loop headers and BBs that 00330 // end with an unconditional jmp to another block in the same loop. 00331 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 00332 MachineBasicBlock *MBB = I; 00333 if (MBB->isLandingPad()) 00334 continue; 00335 MachineLoop *L = MLI->getLoopFor(MBB); 00336 if (!L) 00337 continue; 00338 if (MLI->isLoopHeader(MBB)) 00339 LoopHeaders.push_back(MBB); 00340 00341 MachineBasicBlock *TBB = 0, *FBB = 0; 00342 SmallVector<MachineOperand, 4> Cond; 00343 if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty()) 00344 continue; 00345 if (MLI->getLoopFor(TBB) == L && !TBB->isLandingPad()) 00346 UncondJmpMBBs.push_back(std::make_pair(MBB, TBB)); 00347 } 00348 00349 bool Changed = OptimizeIntraLoopEdges(); 00350 00351 Changed |= AlignLoops(MF); 00352 00353 ChangedMBBs.clear(); 00354 UncondJmpMBBs.clear(); 00355 LoopHeaders.clear(); 00356 00357 return Changed; 00358 }