LLVM API Documentation

CodePlacementOpt.cpp

Go to the documentation of this file.
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 }