lib/CodeGen/CodePlacementOpt.cpp

   1 //===-- CodePlacementOpt.cpp - Code Placement pass. -----------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the pass that optimize code placement and align loop
  11 // headers to target specific alignment boundary.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "code-placement"
  16 #include "llvm/CodeGen/MachineLoopInfo.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/CodeGen/Passes.h"
  19 #include "llvm/Target/TargetInstrInfo.h"
  20 #include "llvm/Target/TargetLowering.h"
  21 #include "llvm/Target/TargetMachine.h"
  22 #include "llvm/Support/Compiler.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/ADT/Statistic.h"
  25 using namespace llvm;
  26
  27 STATISTIC(NumHeaderAligned, "Number of loop header aligned");
  28 STATISTIC(NumIntraElim,     "Number of intra loop branches eliminated");
  29 STATISTIC(NumIntraMoved,    "Number of intra loop branches moved");
  30
  31 namespace {
  32   class CodePlacementOpt : public MachineFunctionPass {
  33     const MachineLoopInfo *MLI;
  34     const TargetInstrInfo *TII;
  35     const TargetLowering  *TLI;
  36
  37     /// ChangedMBBs - BBs which are modified by OptimizeIntraLoopEdges.
  38     SmallPtrSet<MachineBasicBlock*, 8> ChangedMBBs;
  39
  40     /// UncondJmpMBBs - A list of BBs which are in loops and end with
  41     /// unconditional branches.
  42     SmallVector<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 4>
  43     UncondJmpMBBs;
  44
  45     /// LoopHeaders - A list of BBs which are loop headers.
  46     SmallVector<MachineBasicBlock*, 4> LoopHeaders;
  47
  48   public:
  49     static char ID;
  50     CodePlacementOpt() : MachineFunctionPass(&ID) {}
  51
  52     virtual bool runOnMachineFunction(MachineFunction &MF);
  53     virtual const char *getPassName() const {
  54       return "Code Placement Optimizater";
  55     }
  56
  57     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  58       AU.addRequired<MachineLoopInfo>();
  59       AU.addPreservedID(MachineDominatorsID);
  60       MachineFunctionPass::getAnalysisUsage(AU);
  61     }
  62
  63   private:
  64     bool OptimizeIntraLoopEdges();
  65     bool HeaderShouldBeAligned(MachineBasicBlock *MBB, MachineLoop *L,
  66                                SmallPtrSet<MachineBasicBlock*, 4> &DoNotAlign);
  67     bool AlignLoops(MachineFunction &MF);
  68   };
  69
  70   char CodePlacementOpt::ID = 0;
  71 } // end anonymous namespace
  72
  73 FunctionPass *llvm::createCodePlacementOptPass() {
  74   return new CodePlacementOpt();
  75 }
  76
  77 /// OptimizeBackEdges - Place loop back edges to move unconditional branches
  78 /// out of the loop.
  79 ///
  80 ///       A:
  81 ///       ...
  82 ///       <fallthrough to B>
  83 ///
  84 ///       B:  --> loop header
  85 ///       ...
  86 ///       jcc <cond> C, [exit]
  87 ///
  88 ///       C:
  89 ///       ...
  90 ///       jmp B
  91 ///
  92 /// ==>
  93 ///
  94 ///       A:
  95 ///       ...
  96 ///       jmp B
  97 ///
  98 ///       C:  --> new loop header
  99 ///       ...
 100 ///       <fallthough to B>
 101 ///
 102 ///       B:
 103 ///       ...
 104 ///       jcc <cond> C, [exit]
 105 ///
 106 bool CodePlacementOpt::OptimizeIntraLoopEdges() {
 107   if (!TLI->shouldOptimizeCodePlacement())
 108     return false;
 109
 110   bool Changed = false;
 111   for (unsigned i = 0, e = UncondJmpMBBs.size(); i != e; ++i) {
 112     MachineBasicBlock *MBB = UncondJmpMBBs[i].first;
 113     MachineBasicBlock *SuccMBB = UncondJmpMBBs[i].second;
 114     MachineLoop *L = MLI->getLoopFor(MBB);
 115     assert(L && "BB is expected to be in a loop!");
 116
 117     if (ChangedMBBs.count(MBB)) {
 118       // BB has been modified, re-analyze.
 119       MachineBasicBlock *TBB = 0, *FBB = 0;
 120       SmallVector<MachineOperand, 4> Cond;
 121       if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
 122         continue;
 123       if (MLI->getLoopFor(TBB) != L || TBB->isLandingPad())
 124         continue;
 125       SuccMBB = TBB;
 126     } else {
 127       assert(MLI->getLoopFor(SuccMBB) == L &&
 128              "Successor is not in the same loop!");
 129     }
 130
 131     if (MBB->isLayoutSuccessor(SuccMBB)) {
 132       // Successor is right after MBB, just eliminate the unconditional jmp.
 133       // Can this happen?
 134       TII->RemoveBranch(*MBB);
 135       ChangedMBBs.insert(MBB);
 136       ++NumIntraElim;
 137       Changed = true;
 138       continue;
 139     }
 140
 141     // Now check if the predecessor is fallthrough from any BB. If there is,
 142     // that BB should be from outside the loop since edge will become a jmp.
 143     bool OkToMove = true;
 144     MachineBasicBlock *FtMBB = 0, *FtTBB = 0, *FtFBB = 0;
 145     SmallVector<MachineOperand, 4> FtCond;
 146     for (MachineBasicBlock::pred_iterator PI = SuccMBB->pred_begin(),
 147            PE = SuccMBB->pred_end(); PI != PE; ++PI) {
 148       MachineBasicBlock *PredMBB = *PI;
 149       if (PredMBB->isLayoutSuccessor(SuccMBB)) {
 150         if (TII->AnalyzeBranch(*PredMBB, FtTBB, FtFBB, FtCond)) {
 151           OkToMove = false;
 152           break;
 153         }
 154         if (!FtTBB)
 155           FtTBB = SuccMBB;
 156         else if (!FtFBB) {
 157           assert(FtFBB != SuccMBB && "Unexpected control flow!");
 158           FtFBB = SuccMBB;
 159         }
 160
 161         // A fallthrough.
 162         FtMBB = PredMBB;
 163         MachineLoop *PL = MLI->getLoopFor(PredMBB);
 164         if (PL && (PL == L || PL->getLoopDepth() >= L->getLoopDepth()))
 165           OkToMove = false;
 166
 167         break;
 168       }
 169     }
 170
 171     if (!OkToMove)
 172       continue;
 173
 174     // Is it profitable? If SuccMBB can fallthrough itself, that can be changed
 175     // into a jmp.
 176     MachineBasicBlock *TBB = 0, *FBB = 0;
 177     SmallVector<MachineOperand, 4> Cond;
 178     if (TII->AnalyzeBranch(*SuccMBB, TBB, FBB, Cond))
 179       continue;
 180     if (!TBB && Cond.empty())
 181       TBB = next(MachineFunction::iterator(SuccMBB));
 182     else if (!FBB && !Cond.empty())
 183       FBB = next(MachineFunction::iterator(SuccMBB));
 184
 185     // This calculate the cost of the transformation. Also, it finds the *only*
 186     // intra-loop edge if there is one.
 187     int Cost = 0;
 188     bool HasOneIntraSucc = true;
 189     MachineBasicBlock *IntraSucc = 0;
 190     for (MachineBasicBlock::succ_iterator SI = SuccMBB->succ_begin(),
 191            SE = SuccMBB->succ_end(); SI != SE; ++SI) {
 192       MachineBasicBlock *SSMBB = *SI;
 193       if (MLI->getLoopFor(SSMBB) == L) {
 194         if (!IntraSucc)
 195           IntraSucc = SSMBB;
 196         else
 197           HasOneIntraSucc = false;
 198       }
 199
 200       if (SuccMBB->isLayoutSuccessor(SSMBB))
 201         // This will become a jmp.
 202         ++Cost;
 203       else if (MBB->isLayoutSuccessor(SSMBB)) {
 204         // One of the successor will become the new fallthrough.
 205         if (SSMBB == FBB) {
 206           FBB = 0;
 207           --Cost;
 208         } else if (!FBB && SSMBB == TBB && Cond.empty()) {
 209           TBB = 0;
 210           --Cost;
 211         } else if (!Cond.empty() && !TII->ReverseBranchCondition(Cond)) {
 212           assert(SSMBB == TBB);
 213           TBB = FBB;
 214           FBB = 0;
 215           --Cost;
 216         }
 217       }
 218     }
 219     if (Cost)
 220       continue;
 221
 222     // Now, let's move the successor to below the BB to eliminate the jmp.
 223     SuccMBB->moveAfter(MBB);
 224     TII->RemoveBranch(*MBB);
 225     TII->RemoveBranch(*SuccMBB);
 226     if (TBB)
 227       TII->InsertBranch(*SuccMBB, TBB, FBB, Cond);
 228     ChangedMBBs.insert(MBB);
 229     ChangedMBBs.insert(SuccMBB);
 230     if (FtMBB) {
 231       TII->RemoveBranch(*FtMBB);
 232       TII->InsertBranch(*FtMBB, FtTBB, FtFBB, FtCond);
 233       ChangedMBBs.insert(FtMBB);
 234     }
 235     Changed = true;
 236
 237     // If BB is the loop latch, we may have a new loop headr.
 238     if (MBB == L->getLoopLatch()) {
 239       assert(MLI->isLoopHeader(SuccMBB) &&
 240              "Only succ of loop latch is not the header?");
 241       if (HasOneIntraSucc && IntraSucc)
 242         std::replace(LoopHeaders.begin(),LoopHeaders.end(), SuccMBB, IntraSucc);
 243     }
 244   }
 245
 246   ++NumIntraMoved;
 247   return Changed;
 248 }
 249
 250 /// HeaderShouldBeAligned - Return true if the specified loop header block
 251 /// should be aligned. For now, we will not align it if all the predcessors
 252 /// (i.e. loop back edges) are laid out above the header. FIXME: Do not
 253 /// align small loops.
 254 bool
 255 CodePlacementOpt::HeaderShouldBeAligned(MachineBasicBlock *MBB, MachineLoop *L,
 256                                SmallPtrSet<MachineBasicBlock*, 4> &DoNotAlign) {
 257   if (DoNotAlign.count(MBB))
 258     return false;
 259
 260   bool BackEdgeBelow = false;
 261   for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
 262          PE = MBB->pred_end(); PI != PE; ++PI) {
 263     MachineBasicBlock *PredMBB = *PI;
 264     if (PredMBB == MBB || PredMBB->getNumber() > MBB->getNumber()) {
 265       BackEdgeBelow = true;
 266       break;
 267     }
 268   }
 269
 270   if (!BackEdgeBelow)
 271     return false;
 272
 273   // Ok, we are going to align this loop header. If it's an inner loop,
 274   // do not align its outer loop.
 275   MachineBasicBlock *PreHeader = L->getLoopPreheader();
 276   if (PreHeader) {
 277     MachineLoop *L = MLI->getLoopFor(PreHeader);
 278     if (L) {
 279       MachineBasicBlock *HeaderBlock = L->getHeader();
 280       HeaderBlock->setAlignment(0);
 281       DoNotAlign.insert(HeaderBlock);
 282     }
 283   }
 284   return true;
 285 }
 286
 287 /// AlignLoops - Align loop headers to target preferred alignments.
 288 ///
 289 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
 290   const Function *F = MF.getFunction();
 291   if (F->hasFnAttr(Attribute::OptimizeForSize))
 292     return false;
 293
 294   unsigned Align = TLI->getPrefLoopAlignment();
 295   if (!Align)
 296     return false;  // Don't care about loop alignment.
 297
 298   // Make sure blocks are numbered in order
 299   MF.RenumberBlocks();
 300
 301   bool Changed = false;
 302   SmallPtrSet<MachineBasicBlock*, 4> DoNotAlign;
 303   for (unsigned i = 0, e = LoopHeaders.size(); i != e; ++i) {
 304     MachineBasicBlock *HeaderMBB = LoopHeaders[i];
 305     MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(HeaderMBB));
 306     MachineLoop *L = MLI->getLoopFor(HeaderMBB);
 307     if (L == MLI->getLoopFor(PredMBB))
 308       // If previously BB is in the same loop, don't align this BB. We want
 309       // to prevent adding noop's inside a loop.
 310       continue;
 311     if (HeaderShouldBeAligned(HeaderMBB, L, DoNotAlign)) {
 312       HeaderMBB->setAlignment(Align);
 313       Changed = true;
 314       ++NumHeaderAligned;
 315     }
 316   }
 317
 318   return Changed;
 319 }
 320
 321 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
 322   MLI = &getAnalysis<MachineLoopInfo>();
 323   if (MLI->empty())
 324     return false;  // No loops.
 325
 326   TLI = MF.getTarget().getTargetLowering();
 327   TII = MF.getTarget().getInstrInfo();
 328
 329   // Analyze the BBs first and keep track of loop headers and BBs that
 330   // end with an unconditional jmp to another block in the same loop.
 331   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
 332     MachineBasicBlock *MBB = I;
 333     if (MBB->isLandingPad())
 334       continue;
 335     MachineLoop *L = MLI->getLoopFor(MBB);
 336     if (!L)
 337       continue;
 338     if (MLI->isLoopHeader(MBB))
 339       LoopHeaders.push_back(MBB);
 340
 341     MachineBasicBlock *TBB = 0, *FBB = 0;
 342     SmallVector<MachineOperand, 4> Cond;
 343     if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond) || !Cond.empty())
 344       continue;
 345     if (MLI->getLoopFor(TBB) == L && !TBB->isLandingPad())
 346       UncondJmpMBBs.push_back(std::make_pair(MBB, TBB));
 347   }
 348
 349   bool Changed = OptimizeIntraLoopEdges();
 350
 351   Changed |= AlignLoops(MF);
 352
 353   ChangedMBBs.clear();
 354   UncondJmpMBBs.clear();
 355   LoopHeaders.clear();
 356
 357   return Changed;
 358 }