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