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 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 procede 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->hasFnAttr(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 } 423