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