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   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 Optimizater";
  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     void UpdateTerminator(MachineBasicBlock *MBB);
  60     bool OptimizeIntraLoopEdges(MachineFunction &MF);
  61     bool OptimizeIntraLoopEdgesInLoop(MachineFunction &MF, MachineLoop *L);
  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 /// 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   // Ignore blocks which look like they might have EH-related control flow.
 103   // At the time of this writing, there are blocks which AnalyzeBranch
 104   // thinks end in single uncoditional branches, yet which have two CFG
 105   // successors. Code in this file is not prepared to reason about such things.
 106   if (!MBB->empty() && MBB->back().getOpcode() == TargetInstrInfo::EH_LABEL)
 107     return false;
 108
 109   // Aggressively handle return blocks and similar constructs.
 110   if (MBB->succ_empty()) return true;
 111
 112   // Ask the target's AnalyzeBranch if it can handle this block.
 113   MachineBasicBlock *TBB = 0, *FBB = 0;
 114   SmallVector<MachineOperand, 4> Cond;
 115   // Make the the terminator is understood.
 116   if (TII->AnalyzeBranch(*MBB, TBB, FBB, Cond))
 117     return false;
 118   // Make sure we have the option of reversing the condition.
 119   if (!Cond.empty() && TII->ReverseBranchCondition(Cond))
 120     return false;
 121   return true;
 122 }
 123
 124 /// Splice - Move the sequence of instructions [Begin,End) to just before
 125 /// InsertPt. Update branch instructions as needed to account for broken
 126 /// fallthrough edges and to take advantage of newly exposed fallthrough
 127 /// opportunities.
 128 ///
 129 void CodePlacementOpt::Splice(MachineFunction &MF,
 130                               MachineFunction::iterator InsertPt,
 131                               MachineFunction::iterator Begin,
 132                               MachineFunction::iterator End) {
 133   assert(Begin != MF.begin() && End != MF.begin() && InsertPt != MF.begin() &&
 134          "Splice can't change the entry block!");
 135   MachineFunction::iterator OldBeginPrior = prior(Begin);
 136   MachineFunction::iterator OldEndPrior = prior(End);
 137
 138   MF.splice(InsertPt, Begin, End);
 139
 140   UpdateTerminator(prior(Begin));
 141   UpdateTerminator(OldBeginPrior);
 142   UpdateTerminator(OldEndPrior);
 143 }
 144
 145 /// UpdateTerminator - Update the terminator instructions in MBB to account
 146 /// for changes to the layout. If the block previously used a fallthrough,
 147 /// it may now need a branch, and if it previously used branching it may now
 148 /// be able to use a fallthrough.
 149 ///
 150 void CodePlacementOpt::UpdateTerminator(MachineBasicBlock *MBB) {
 151   // A block with no successors has no concerns with fall-through edges.
 152   if (MBB->succ_empty()) return;
 153
 154   MachineBasicBlock *TBB = 0, *FBB = 0;
 155   SmallVector<MachineOperand, 4> Cond;
 156   bool B = TII->AnalyzeBranch(*MBB, TBB, FBB, Cond);
 157   assert(!B && "UpdateTerminators requires analyzable predecessors!");
 158   if (Cond.empty()) {
 159     if (TBB) {
 160       // The block has an unconditional branch. If its successor is now
 161       // its layout successor, delete the branch.
 162       if (MBB->isLayoutSuccessor(TBB))
 163         TII->RemoveBranch(*MBB);
 164     } else {
 165       // The block has an unconditional fallthrough. If its successor is not
 166       // its layout successor, insert a branch.
 167       TBB = *MBB->succ_begin();
 168       if (!MBB->isLayoutSuccessor(TBB))
 169         TII->InsertBranch(*MBB, TBB, 0, Cond);
 170     }
 171   } else {
 172     if (FBB) {
 173       // The block has a non-fallthrough conditional branch. If one of its
 174       // successors is its layout successor, rewrite it to a fallthrough
 175       // conditional branch.
 176       if (MBB->isLayoutSuccessor(TBB)) {
 177         TII->RemoveBranch(*MBB);
 178         TII->ReverseBranchCondition(Cond);
 179         TII->InsertBranch(*MBB, FBB, 0, Cond);
 180       } else if (MBB->isLayoutSuccessor(FBB)) {
 181         TII->RemoveBranch(*MBB);
 182         TII->InsertBranch(*MBB, TBB, 0, Cond);
 183       }
 184     } else {
 185       // The block has a fallthrough conditional branch.
 186       MachineBasicBlock *MBBA = *MBB->succ_begin();
 187       MachineBasicBlock *MBBB = *next(MBB->succ_begin());
 188       if (MBBA == TBB) std::swap(MBBB, MBBA);
 189       if (MBB->isLayoutSuccessor(TBB)) {
 190         TII->RemoveBranch(*MBB);
 191         TII->ReverseBranchCondition(Cond);
 192         TII->InsertBranch(*MBB, MBBA, 0, Cond);
 193       } else if (!MBB->isLayoutSuccessor(MBBA)) {
 194         TII->RemoveBranch(*MBB);
 195         TII->InsertBranch(*MBB, TBB, MBBA, Cond);
 196       }
 197     }
 198   }
 199 }
 200
 201 /// OptimizeIntraLoopEdges - Reposition loop blocks to minimize
 202 /// intra-loop branching and to form contiguous loops.
 203 ///
 204 bool CodePlacementOpt::OptimizeIntraLoopEdges(MachineFunction &MF) {
 205   bool Changed = false;
 206
 207   if (!TLI->shouldOptimizeCodePlacement())
 208     return Changed;
 209
 210   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 211        I != E; ++I)
 212     Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
 213
 214   return Changed;
 215 }
 216
 217 /// OptimizeIntraLoopEdgesInLoop - Reposition loop blocks to minimize
 218 /// intra-loop branching and to form contiguous loops.
 219 ///
 220 /// This code takes the approach of making minor changes to the existing
 221 /// layout to fix specific loop-oriented problems. Also, it depends on
 222 /// AnalyzeBranch, which can't understand complex control instructions.
 223 ///
 224 bool CodePlacementOpt::OptimizeIntraLoopEdgesInLoop(MachineFunction &MF,
 225                                                     MachineLoop *L) {
 226   bool Changed = false;
 227
 228   // Do optimization for nested loops.
 229   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 230     Changed |= OptimizeIntraLoopEdgesInLoop(MF, *I);
 231
 232   // Keep a record of which blocks are in the portion of the loop contiguous
 233   // with the loop header.
 234   SmallPtrSet<MachineBasicBlock *, 8> ContiguousBlocks;
 235   ContiguousBlocks.insert(L->getHeader());
 236
 237   // Find the loop "top", ignoring any discontiguous parts.
 238   MachineBasicBlock *TopMBB = L->getHeader();
 239   if (TopMBB != MF.begin()) {
 240     MachineBasicBlock *PriorMBB = prior(MachineFunction::iterator(TopMBB));
 241     while (L->contains(PriorMBB)) {
 242       ContiguousBlocks.insert(PriorMBB);
 243       TopMBB = PriorMBB;
 244       if (TopMBB == MF.begin()) break;
 245       PriorMBB = prior(MachineFunction::iterator(TopMBB));
 246     }
 247   }
 248
 249   // Find the loop "bottom", ignoring any discontiguous parts.
 250   MachineBasicBlock *BotMBB = L->getHeader();
 251   if (BotMBB != prior(MF.end())) {
 252     MachineBasicBlock *NextMBB = next(MachineFunction::iterator(BotMBB));
 253     while (L->contains(NextMBB)) {
 254       ContiguousBlocks.insert(NextMBB);
 255       BotMBB = NextMBB;
 256       if (BotMBB == next(MachineFunction::iterator(BotMBB))) break;
 257       NextMBB = next(MachineFunction::iterator(BotMBB));
 258     }
 259   }
 260
 261   // First, move blocks which unconditionally jump to the loop top to the
 262   // top of the loop so that they have a fall through. This can introduce a
 263   // branch on entry to the loop, but it can eliminate a branch within the
 264   // loop. See the @simple case in test/CodeGen/X86/loop_blocks.ll for an
 265   // example of this.
 266
 267   bool BotHasFallthrough = HasFallthrough(BotMBB);
 268
 269   if (TopMBB == MF.begin() ||
 270       HasAnalyzableTerminator(prior(MachineFunction::iterator(TopMBB)))) {
 271   new_top:
 272     for (MachineBasicBlock::pred_iterator PI = TopMBB->pred_begin(),
 273          PE = TopMBB->pred_end(); PI != PE; ++PI) {
 274       MachineBasicBlock *Pred = *PI;
 275       if (Pred == TopMBB) continue;
 276       if (HasFallthrough(Pred)) continue;
 277       if (!L->contains(Pred)) continue;
 278
 279       // Verify that we can analyze all the loop entry edges before beginning
 280       // any changes which will require us to be able to analyze them.
 281       if (Pred == MF.begin())
 282         continue;
 283       if (!HasAnalyzableTerminator(Pred))
 284         continue;
 285       if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Pred))))
 286         continue;
 287
 288       // Move the block.
 289       Changed = true;
 290       ContiguousBlocks.insert(Pred);
 291
 292       // Move it and all the blocks that can reach it via fallthrough edges
 293       // exclusively, to keep existing fallthrough-edges intact.
 294       MachineFunction::iterator Begin = Pred;
 295       MachineFunction::iterator End = next(Begin);
 296       while (Begin != MF.begin()) {
 297         MachineFunction::iterator Prior = prior(Begin);
 298         if (Prior == MF.begin())
 299           break;
 300         // Stop when a non-fallthrough edge is found.
 301         if (!HasFallthrough(Prior))
 302           break;
 303         // Stop if a block which could fall-through out of the loop is found.
 304         if (Prior->isSuccessor(End))
 305           break;
 306         // If we've reached the top, stop scanning.
 307         if (Prior == MachineFunction::iterator(TopMBB)) {
 308           // We know top currently has a fall through (because we just checked
 309           // it) which would be lost if we do the transformation, so it isn't
 310           // worthwhile to do the transformation unless it would expose a new
 311           // fallthrough edge.
 312           if (!Prior->isSuccessor(End))
 313             goto next_pred;
 314           // Otherwise we can stop scanning and procede to move the blocks.
 315           break;
 316         }
 317         // If we hit a switch or something complicated, don't move anything
 318         // for this predecessor.
 319         if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(Prior))))
 320           break;
 321         Begin = Prior;
 322         ContiguousBlocks.insert(Begin);
 323         ++NumIntraMoved;
 324       }
 325
 326       // Update BotMBB, before moving Begin/End around and forgetting where
 327       // the new bottom is.
 328       if (BotMBB == prior(End))
 329         BotMBB = prior(Begin);
 330
 331       // Move the blocks.
 332       Splice(MF, TopMBB, Begin, End);
 333
 334       // Update TopMBB, now that all the updates requiring the old top are
 335       // complete.
 336       TopMBB = Begin;
 337
 338       // We have a new loop top. Iterate on it. We shouldn't have to do this
 339       // too many times if BranchFolding has done a reasonable job.
 340       goto new_top;
 341     next_pred:;
 342     }
 343   }
 344
 345   // If the loop previously didn't exit with a fall-through and it now does,
 346   // we eliminated a branch.
 347   if (!BotHasFallthrough && HasFallthrough(BotMBB)) {
 348     ++NumIntraElim;
 349     BotHasFallthrough = true;
 350   }
 351
 352   // Next, move any loop blocks that are not in the portion of the loop
 353   // contiguous with the header. This makes the loop contiguous, provided that
 354   // AnalyzeBranch can handle all the relevant branching. See the @cfg_islands
 355   // case in test/CodeGen/X86/loop_blocks.ll for an example of this.
 356
 357   // Determine a position to move orphaned loop blocks to. If TopMBB is not
 358   // entered via fallthrough and BotMBB is exited via fallthrough, prepend them
 359   // to the top of the loop to avoid loosing that fallthrough. Otherwise append
 360   // them to the bottom, even if it previously had a fallthrough, on the theory
 361   // that it's worth an extra branch to keep the loop contiguous.
 362   MachineFunction::iterator InsertPt = next(MachineFunction::iterator(BotMBB));
 363   bool InsertAtTop = false;
 364   if (TopMBB != MF.begin() &&
 365       !HasFallthrough(prior(MachineFunction::iterator(TopMBB))) &&
 366       HasFallthrough(BotMBB)) {
 367     InsertPt = TopMBB;
 368     InsertAtTop = true;
 369   }
 370
 371   // Find non-contigous blocks and fix them.
 372   if (InsertPt != MF.begin() && HasAnalyzableTerminator(prior(InsertPt)))
 373     for (MachineLoop::block_iterator BI = L->block_begin(), BE = L->block_end();
 374          BI != BE; ++BI) {
 375       MachineBasicBlock *BB = *BI;
 376
 377       // Verify that we can analyze all the loop entry edges before beginning
 378       // any changes which will require us to be able to analyze them.
 379       if (!HasAnalyzableTerminator(BB))
 380         continue;
 381       if (!HasAnalyzableTerminator(prior(MachineFunction::iterator(BB))))
 382         continue;
 383
 384       // If the layout predecessor is part of the loop, this block will be
 385       // processed along with it. This keeps them in their relative order.
 386       if (BB != MF.begin() &&
 387           L->contains(prior(MachineFunction::iterator(BB))))
 388         continue;
 389
 390       // Check to see if this block is already contiguous with the main
 391       // portion of the loop.
 392       if (!ContiguousBlocks.insert(BB))
 393         continue;
 394
 395       // Move the block.
 396       Changed = true;
 397
 398       // Process this block and all loop blocks contiguous with it, to keep
 399       // them in their relative order.
 400       MachineFunction::iterator Begin = BB;
 401       MachineFunction::iterator End = next(MachineFunction::iterator(BB));
 402       for (; End != MF.end(); ++End) {
 403         if (!L->contains(End)) break;
 404         if (!HasAnalyzableTerminator(End)) break;
 405         ContiguousBlocks.insert(End);
 406         ++NumIntraMoved;
 407       }
 408
 409       // Update BotMBB.
 410       if (!InsertAtTop)
 411         BotMBB = prior(End);
 412
 413       // If we're inserting at the bottom of the loop, and the code we're
 414       // moving originally had fall-through successors, bring the sucessors
 415       // up with the loop blocks to preserve the fall-through edges.
 416       if (!InsertAtTop)
 417         for (; End != MF.end(); ++End) {
 418           if (L->contains(End)) break;
 419           if (!HasAnalyzableTerminator(End)) break;
 420           if (!HasFallthrough(prior(End))) break;
 421         }
 422
 423       // Move the blocks.
 424       Splice(MF, InsertPt, Begin, End);
 425
 426       // Update TopMBB.
 427       if (InsertAtTop)
 428         TopMBB = Begin;
 429     }
 430
 431   return Changed;
 432 }
 433
 434 /// AlignLoops - Align loop headers to target preferred alignments.
 435 ///
 436 bool CodePlacementOpt::AlignLoops(MachineFunction &MF) {
 437   const Function *F = MF.getFunction();
 438   if (F->hasFnAttr(Attribute::OptimizeForSize))
 439     return false;
 440
 441   unsigned Align = TLI->getPrefLoopAlignment();
 442   if (!Align)
 443     return false;  // Don't care about loop alignment.
 444
 445   bool Changed = false;
 446
 447   for (MachineLoopInfo::iterator I = MLI->begin(), E = MLI->end();
 448        I != E; ++I)
 449     Changed |= AlignLoop(MF, *I, Align);
 450
 451   return Changed;
 452 }
 453
 454 /// AlignLoop - Align loop headers to target preferred alignments.
 455 ///
 456 bool CodePlacementOpt::AlignLoop(MachineFunction &MF, MachineLoop *L,
 457                                  unsigned Align) {
 458   bool Changed = false;
 459
 460   // Do alignment for nested loops.
 461   for (MachineLoop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 462     Changed |= AlignLoop(MF, *I, Align);
 463
 464   MachineBasicBlock *TopMBB = L->getHeader();
 465   if (TopMBB != MF.begin()) {
 466     MachineBasicBlock *PredMBB = prior(MachineFunction::iterator(TopMBB));
 467     while (L->contains(PredMBB)) {
 468       TopMBB = PredMBB;
 469       if (TopMBB == MF.begin()) break;
 470       PredMBB = prior(MachineFunction::iterator(TopMBB));
 471     }
 472   }
 473
 474   TopMBB->setAlignment(Align);
 475   Changed = true;
 476   ++NumLoopsAligned;
 477
 478   return Changed;
 479 }
 480
 481 bool CodePlacementOpt::runOnMachineFunction(MachineFunction &MF) {
 482   MLI = &getAnalysis<MachineLoopInfo>();
 483   if (MLI->empty())
 484     return false;  // No loops.
 485
 486   TLI = MF.getTarget().getTargetLowering();
 487   TII = MF.getTarget().getInstrInfo();
 488
 489   bool Changed = OptimizeIntraLoopEdges(MF);
 490
 491   Changed |= AlignLoops(MF);
 492
 493   return Changed;
 494 }