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