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 optimizes code placement and aligns loop
  11 // headers to target-specific alignment boundaries.
  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   public:
  38     static char ID;
  39     CodePlacementOpt() : MachineFunctionPass(ID) {}
  40
  41     virtual bool runOnMachineFunction(MachineFunction &MF);
  42     virtual const char *getPassName() const {
  43       return "Code Placement Optimizer";
  44     }
  45
  46     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  47       AU.addRequired<MachineLoopInfo>();
  48       AU.addPreservedID(MachineDominatorsID);
  49       MachineFunctionPass::getAnalysisUsage(AU);
  50     }
  51
  52   private:
  53     bool HasFallthrough(MachineBasicBlock *MBB);
  54     bool HasAnalyzableTerminator(MachineBasicBlock *MBB);
  55     void Splice(MachineFunction &MF,
  56                 MachineFunction::iterator InsertPt,
  57                 MachineFunction::iterator Begin,
  58                 MachineFunction::iterator End);
  59     bool EliminateUnconditionalJumpsToTop(MachineFunction &MF,
  60                                           MachineLoop *L);
  61     bool MoveDiscontiguousLoopBlocks(MachineFunction &MF,
  62                                      MachineLoop *L);
  63     bool OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF, MachineLoop *L);
  64     bool OptimizeIntraLoopEdges(MachineFunction &MF);
  65     bool AlignLoops(MachineFunction &MF);
  66     bool AlignLoop(MachineFunction &MF, MachineLoop *L, unsigned Align);
  67   };
  68
  69   char CodePlacementOpt::ID = 0;
  70 } // end anonymous namespace
  71
  72 FunctionPass *llvm::createCodePlacementOptPass() {
  73   return new CodePlacementOpt();
  74 }
  75
  76 /// HasFallthrough - Test whether the given branch has a fallthrough, either as
  77 /// a plain fallthrough or as a fallthrough case of a conditional branch.
  78 ///
  79 bool CodePlacementOpt::HasFallthrough(MachineBasicBlock *MBB) {
  80   MachineBasicBlock *TBB = 0, *FBB = 0;
  81   SmallVector<MachineOperand, 4> Cond;
  82   if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
  83     return false;
  84   // This conditional branch has no fallthrough.
  85   if (FBB)
  86     return false;
  87   // An unconditional branch has no fallthrough.
  88   if (Cond.empty() && TBB)
  89     return false;
  90   // It has a fallthrough.
  91   return true;
  92 }
  93
  94 /// HasAnalyzableTerminator - Test whether AnalyzeBranch will succeed on MBB.
  95 /// This is called before major changes are begun to test whether it will be
  96 /// possible to complete the changes.
  97 ///
  98 /// Target-specific code is hereby encouraged to make AnalyzeBranch succeed
  99 /// whenever possible.
 100 ///
 101 bool CodePlacementOpt::HasAnalyzableTerminator(MachineBasicBlock *MBB) {
 102   // Conservatively ignore EH landing pads.
 103   if (MBB->isLandingPad()) return false;
 104
 105   // Aggressively handle return blocks and similar constructs.
 106   if (MBB->succ_empty()) return true;
 107
 108   // Ask the target's AnalyzeBranch if it can handle this block.
 109   MachineBasicBlock *TBB = 0, *FBB = 0;
 110   SmallVector<MachineOperand, 4> Cond;
 111   // Make sure the terminator is understood.
 112   if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
 113     return false;
 114    // Ignore blocks which look like they might have EH-related control flow.
 115    // AnalyzeBranch thinks it knows how to analyze such things, but it doesn't
 116    // recognize the possibility of a control transfer through an unwind.
 117    // Such blocks contain EH_LABEL instructions, however they may be in the
 118    // middle of the block. Instead of searching for them, just check to see
 119    // if the CFG disagrees with AnalyzeBranch.
 120   if (1u + !Cond.empty() != MBB->succ_size())
 121     return false;
 122   // Make sure we have the option of reversing the condition.
 123   if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
 124     return false;
 125   return true;
 126 }
 127
 128 /// Splice - Move the sequence of instructions [Begin,End) to just before
 129 /// InsertPt. Update branch instructions as needed to account for broken
 130 /// fallthrough edges and to take advantage of newly exposed fallthrough
 131 /// opportunities.
 132 ///
 133 void CodePlacementOpt::Splice(MachineFunction &MF,
 134                               MachineFunction::iterator InsertPt,
 135                               MachineFunction::iterator Begin,
 136                               MachineFunction::iterator End) {
 137   assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
 138          "Splice can't change the entry block!");
 139   MachineFunction::iterator OldBeginPrior = prior(Begin);
 140   MachineFunction::iterator OldEndPrior = prior(End);
 141
 142   MF.splice(InsertPt, Begin, End);
 143
 144   prior(Begin)->updateTerminator();
 145   OldBeginPrior->updateTerminator();
 146   OldEndPrior->updateTerminator();
 147 }
 148
 149 /// EliminateUnconditionalJumpsToTop - Move blocks which unconditionally jump
 150 /// to the loop top to the top of the loop so that they have a fall through.
 151 /// This can introduce a branch on entry to the loop, but it can eliminate a
 152 /// branch within the loop. See the @simple case in
 153 /// test/CodeGen/X86/loop_blocks.ll for an example of this.
 154 bool CodePlacementOpt::EliminateUnconditionalJumpsToTop(MachineFunction &MF,
 155                                                         MachineLoop *L) {
 156   bool Changed = false;
 157   MachineBasicBlock *TopMBB = L->getTopBlock();
 158
 159   bool BotHasFallthrough = HasFallthrough(L->getBottomBlock());
 160
 161   if (TopMBB == MF.begin() ||
 162       HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
 163   new_top:
 164     for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
 165          PE = TopMBB->pred_end(); PI != PE; ++PI) {
 166       MachineBasicBlock *Pred = *PI;
 167       if (Pred == TopMBB) continue;
 168       if (HasFallthrough(Pred)) continue;
 169       if (!L->contains(Pred)) continue;
 170
 171       // Verify that we can analyze all the loop entry edges before beginning
 172       // any changes which will require us to be able to analyze them.
 173       if (Pred == MF.begin())
 174         continue;
 175       if (!HasAnalyzableTerminator(Pred))
 176         continue;
 177       if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
 178         continue;
 179
 180       // Move the block.
 181       DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << Pred->getNumber()
 182                    << " to top of loop.\n");
 183       Changed = true;
 184
 185       // Move it and all the blocks that can reach it via fallthrough edges
 186       // exclusively, to keep existing fallthrough edges intact.
 187       MachineFunction::iterator Begin = Pred;
 188       MachineFunction::iterator End = llvm::next(Begin);
 189       while (Begin != MF.begin()) {
 190         MachineFunction::iterator Prior = prior(Begin);
 191         if (Prior == MF.begin())
 192           break;
 193         // Stop when a non-fallthrough edge is found.
 194         if (!HasFallthrough(Prior))
 195           break;
 196         // Stop if a block which could fall-through out of the loop is found.
 197         if (Prior->isSuccessor(End))
 198           break;
 199         // If we've reached the top, stop scanning.
 200         if (Prior == MachineFunction::iterator(TopMBB)) {
 201           // We know top currently has a fall through (because we just checked
 202           // it) which would be lost if we do the transformation, so it isn't
 203           // worthwhile to do the transformation unless it would expose a new
 204           // fallthrough edge.
 205           if (!Prior->isSuccessor(End))
 206             goto next_pred;
 207           // Otherwise we can stop scanning and procede to move the blocks.
 208           break;
 209         }
 210         // If we hit a switch or something complicated, don't move anything
 211         // for this predecessor.
 212         if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
 213           break;
 214         // Ok, the block prior to Begin will be moved along with the rest.
 215         // Extend the range to include it.
 216         Begin = Prior;
 217         ++NumIntraMoved;
 218       }
 219
 220       // Move the blocks.
 221       Splice(MF, TopMBB, Begin, End);
 222
 223       // Update TopMBB.
 224       TopMBB = L->getTopBlock();
 225
 226       // We have a new loop top. Iterate on it. We shouldn't have to do this
 227       // too many times if BranchFolding has done a reasonable job.
 228       goto new_top;
 229     next_pred:;
 230     }
 231   }
 232
 233   // If the loop previously didn't exit with a fall-through and it now does,
 234   // we eliminated a branch.
 235   if (Changed &&
 236       !BotHasFallthrough &&
 237       HasFallthrough(L->getBottomBlock())) {
 238     ++NumIntraElim;
 239   }
 240
 241   return Changed;
 242 }
 243
 244 /// MoveDiscontiguousLoopBlocks - Move any loop blocks that are not in the
 245 /// portion of the loop contiguous with the header. This usually makes the loop
 246 /// contiguous, provided that AnalyzeBranch can handle all the relevant
 247 /// branching. See the @cfg_islands case in test/CodeGen/X86/loop_blocks.ll
 248 /// for an example of this.
 249 bool CodePlacementOpt::MoveDiscontiguousLoopBlocks(MachineFunction &MF,
 250                                                    MachineLoop *L) {
 251   bool Changed = false;
 252   MachineBasicBlock *TopMBB = L->getTopBlock();
 253   MachineBasicBlock *BotMBB = L->getBottomBlock();
 254
 255   // Determine a position to move orphaned loop blocks to. If TopMBB is not
 256   // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
 257   // to the top of the loop to avoid losing that fallthrough. Otherwise append
 258   // them to the bottom, even if it previously had a fallthrough, on the theory
 259   // that it's worth an extra branch to keep the loop contiguous.
 260   MachineFunction::iterator InsertPt =
 261     llvm::next(MachineFunction::iterator(BotMBB));
 262   bool InsertAtTop = false;
 263   if (TopMBB != MF.begin() &&
 264       !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
 265       HasFallthrough(BotMBB)) {
 266     InsertPt = TopMBB;
 267     InsertAtTop = true;
 268   }
 269
 270   // Keep a record of which blocks are in the portion of the loop contiguous
 271   // with the loop header.
 272   SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
 273   for (MachineFunction::iterator I = TopMBB,
 274        E = llvm::next(MachineFunction::iterator(BotMBB)); I != E; ++I)
 275     ContiguousBlocks.insert(I);
 276
 277   // Find non-contigous blocks and fix them.
 278   if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
 279     for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
 280          BI != BE; ++BI) {
 281       MachineBasicBlock *BB = *BI;
 282
 283       // Verify that we can analyze all the loop entry edges before beginning
 284       // any changes which will require us to be able to analyze them.
 285       if (!HasAnalyzableTerminator(BB))
 286         continue;
 287       if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
 288         continue;
 289
 290       // If the layout predecessor is part of the loop, this block will be
 291       // processed along with it. This keeps them in their relative order.
 292       if (BB != MF.begin() &&
 293           L->contains(prior(MachineFunction::iterator(BB))))
 294         continue;
 295
 296       // Check to see if this block is already contiguous with the main
 297       // portion of the loop.
 298       if (!ContiguousBlocks.insert(BB))
 299         continue;
 300
 301       // Move the block.
 302       DEBUG(dbgs() << "CGP: Moving blocks starting at BB#" << BB->getNumber()
 303                    << " to be contiguous with loop.\n");
 304       Changed = true;
 305
 306       // Process this block and all loop blocks contiguous with it, to keep
 307       // them in their relative order.
 308       MachineFunction::iterator Begin = BB;
 309       MachineFunction::iterator End = llvm::next(MachineFunction::iterator(BB));
 310       for (; End != MF.end(); ++End) {
 311         if (!L->contains(End)) break;
 312         if (!HasAnalyzableTerminator(End)) break;
 313         ContiguousBlocks.insert(End);
 314         ++NumIntraMoved;
 315       }
 316
 317       // If we're inserting at the bottom of the loop, and the code we're
 318       // moving originally had fall-through successors, bring the sucessors
 319       // up with the loop blocks to preserve the fall-through edges.
 320       if (!InsertAtTop)
 321         for (; End != MF.end(); ++End) {
 322           if (L->contains(End)) break;
 323           if (!HasAnalyzableTerminator(End)) break;
 324           if (!HasFallthrough(prior(End))) break;
 325         }
 326
 327       // Move the blocks. This may invalidate TopMBB and/or BotMBB, but
 328       // we don't need them anymore at this point.
 329       Splice(MF, InsertPt, Begin, End);
 330     }
 331
 332   return Changed;
 333 }
 334
 335 /// OptimizeIntraLoopEdgesInLoopNest - Reposition loop blocks to minimize
 336 /// intra-loop branching and to form contiguous loops.
 337 ///
 338 /// This code takes the approach of making minor changes to the existing
 339 /// layout to fix specific loop-oriented problems. Also, it depends on
 340 /// AnalyzeBranch, which can't understand complex control instructions.
 341 ///
 342 bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoopNest(MachineFunction &MF,
 343                                                         MachineLoop *L) {
 344   bool Changed = false;
 345
 346   // Do optimization for nested loops.
 347   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 348     Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
 349
 350   // Do optimization for this loop.
 351   Changed |= EliminateUnconditionalJumpsToTop(MF, L);
 352   Changed |= MoveDiscontiguousLoopBlocks(MF, L);
 353
 354   return Changed;
 355 }
 356
 357 /// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
 358 /// intra-loop branching and to form contiguous loops.
 359 ///
 360 bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
 361   bool Changed = false;
 362
 363   if (!TLI->shouldOptimizeCodePlacement())
 364     return Changed;
 365
 366   // Do optimization for each loop in the function.
 367   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 368        I != E; ++I)
 369     if (!(*I)->getParentLoop())
 370       Changed |= OptimizeIntraLoopEdgesInLoopNest(MF, *I);
 371
 372   return Changed;
 373 }
 374
 375 /// AlignLoops - Align loop headers to target preferred alignments.
 376 ///
 377 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
 378   const Function *F = MF.getFunction();
 379   if (F->hasFnAttr(Attribute::OptimizeForSize))
 380     return false;
 381
 382   unsigned Align = TLI->getPrefLoopAlignment();
 383   if (!Align)
 384     return false;  // Don't care about loop alignment.
 385
 386   bool Changed = false;
 387
 388   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 389        I != E; ++I)
 390     Changed |= AlignLoop(MF, *I, Align);
 391
 392   return Changed;
 393 }
 394
 395 /// AlignLoop - Align loop headers to target preferred alignments.
 396 ///
 397 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
 398                                  unsigned Align) {
 399   bool Changed = false;
 400
 401   // Do alignment for nested loops.
 402   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 403     Changed |= AlignLoop(MF, *I, Align);
 404
 405   L->getTopBlock()->setAlignment(Align);
 406   Changed = true;
 407   ++NumLoopsAligned;
 408
 409   return Changed;
 410 }
 411
 412 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
 413   MLI = &getAnalysis<MachineLoopInfo>();
 414   if (MLI->empty())
 415     return false;  // No loops.
 416
 417   TLI = MF.getTarget().getTargetLowering();
 418   TII = MF.getTarget().getInstrInfo();
 419
 420   bool Changed = OptimizeIntraLoopEdges(MF);
 421
 422   Changed |= AlignLoops(MF);
 423
 424   return Changed;
 425 }