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