LoopUnswitch.cpp revision 708e1a5c9c5f10879295172ec382f064b0443733
1//===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass transforms loops that contain branches on loop-invariant conditions 11// to have multiple loops. For example, it turns the left into the right code: 12// 13// for (...) if (lic) 14// A for (...) 15// if (lic) A; B; C 16// B else 17// C for (...) 18// A; C 19// 20// This can increase the size of the code exponentially (doubling it every time 21// a loop is unswitched) so we only unswitch if the resultant code will be 22// smaller than a threshold. 23// 24// This pass expects LICM to be run before it to hoist invariant conditions out 25// of the loop, to make the unswitching opportunity obvious. 26// 27//===----------------------------------------------------------------------===// 28 29#define DEBUG_TYPE "loop-unswitch" 30#include "llvm/Transforms/Scalar.h" 31#include "llvm/Constants.h" 32#include "llvm/Function.h" 33#include "llvm/Instructions.h" 34#include "llvm/Analysis/LoopInfo.h" 35#include "llvm/Transforms/Utils/Cloning.h" 36#include "llvm/Transforms/Utils/Local.h" 37#include "llvm/ADT/Statistic.h" 38#include "llvm/Support/Debug.h" 39#include "llvm/Support/CommandLine.h" 40#include <algorithm> 41#include <iostream> 42#include <set> 43using namespace llvm; 44 45namespace { 46 Statistic<> NumUnswitched("loop-unswitch", "Number of loops unswitched"); 47 cl::opt<unsigned> 48 Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), 49 cl::init(10), cl::Hidden); 50 51 class LoopUnswitch : public FunctionPass { 52 LoopInfo *LI; // Loop information 53 public: 54 virtual bool runOnFunction(Function &F); 55 bool visitLoop(Loop *L); 56 57 /// This transformation requires natural loop information & requires that 58 /// loop preheaders be inserted into the CFG... 59 /// 60 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 61 AU.addRequiredID(LoopSimplifyID); 62 AU.addPreservedID(LoopSimplifyID); 63 AU.addRequired<LoopInfo>(); 64 AU.addPreserved<LoopInfo>(); 65 } 66 67 private: 68 unsigned getLoopUnswitchCost(Loop *L, Value *LIC); 69 void VersionLoop(Value *LIC, Loop *L, Loop *&Out1, Loop *&Out2); 70 BasicBlock *SplitBlock(BasicBlock *BB, bool SplitAtTop); 71 void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, bool Val); 72 void UnswitchTrivialCondition(Loop *L, Value *Cond, bool EntersLoopOnCond, 73 BasicBlock *ExitBlock); 74 }; 75 RegisterOpt<LoopUnswitch> X("loop-unswitch", "Unswitch loops"); 76} 77 78FunctionPass *llvm::createLoopUnswitchPass() { return new LoopUnswitch(); } 79 80bool LoopUnswitch::runOnFunction(Function &F) { 81 bool Changed = false; 82 LI = &getAnalysis<LoopInfo>(); 83 84 // Transform all the top-level loops. Copy the loop list so that the child 85 // can update the loop tree if it needs to delete the loop. 86 std::vector<Loop*> SubLoops(LI->begin(), LI->end()); 87 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 88 Changed |= visitLoop(SubLoops[i]); 89 90 return Changed; 91} 92 93 94/// LoopValuesUsedOutsideLoop - Return true if there are any values defined in 95/// the loop that are used by instructions outside of it. 96static bool LoopValuesUsedOutsideLoop(Loop *L) { 97 // We will be doing lots of "loop contains block" queries. Loop::contains is 98 // linear time, use a set to speed this up. 99 std::set<BasicBlock*> LoopBlocks; 100 101 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 102 BB != E; ++BB) 103 LoopBlocks.insert(*BB); 104 105 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 106 BB != E; ++BB) { 107 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 108 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 109 ++UI) { 110 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 111 if (!LoopBlocks.count(UserBB)) 112 return true; 113 } 114 } 115 return false; 116} 117 118/// FindTrivialLoopExitBlock - We know that we have a branch from the loop 119/// header to the specified latch block. See if one of the successors of the 120/// latch block is an exit, and if so what block it is. 121static BasicBlock *FindTrivialLoopExitBlock(Loop *L, BasicBlock *Latch) { 122 BasicBlock *Header = L->getHeader(); 123 BranchInst *LatchBranch = dyn_cast<BranchInst>(Latch->getTerminator()); 124 if (!LatchBranch || !LatchBranch->isConditional()) return 0; 125 126 // Simple case, the latch block is a conditional branch. The target that 127 // doesn't go to the loop header is our block if it is not in the loop. 128 if (LatchBranch->getSuccessor(0) == Header) { 129 if (L->contains(LatchBranch->getSuccessor(1))) return false; 130 return LatchBranch->getSuccessor(1); 131 } else { 132 assert(LatchBranch->getSuccessor(1) == Header); 133 if (L->contains(LatchBranch->getSuccessor(0))) return false; 134 return LatchBranch->getSuccessor(0); 135 } 136} 137 138 139/// IsTrivialUnswitchCondition - Check to see if this unswitch condition is 140/// trivial: that is, that the condition controls whether or not the loop does 141/// anything at all. If this is a trivial condition, unswitching produces no 142/// code duplications (equivalently, it produces a simpler loop and a new empty 143/// loop, which gets deleted). 144/// 145/// If this is a trivial condition, return ConstantBool::True if the loop body 146/// runs when the condition is true, False if the loop body executes when the 147/// condition is false. Otherwise, return null to indicate a complex condition. 148static bool IsTrivialUnswitchCondition(Loop *L, Value *Cond, 149 bool *CondEntersLoop = 0, 150 BasicBlock **LoopExit = 0) { 151 BasicBlock *Header = L->getHeader(); 152 BranchInst *HeaderTerm = dyn_cast<BranchInst>(Header->getTerminator()); 153 154 // If the header block doesn't end with a conditional branch on Cond, we can't 155 // handle it. 156 if (!HeaderTerm || !HeaderTerm->isConditional() || 157 HeaderTerm->getCondition() != Cond) 158 return false; 159 160 // Check to see if the conditional branch goes to the latch block. If not, 161 // it's not trivial. This also determines the value of Cond that will execute 162 // the loop. 163 BasicBlock *Latch = L->getLoopLatch(); 164 if (HeaderTerm->getSuccessor(1) == Latch) { 165 if (CondEntersLoop) *CondEntersLoop = true; 166 } else if (HeaderTerm->getSuccessor(0) == Latch) 167 if (CondEntersLoop) *CondEntersLoop = false; 168 else 169 return false; // Doesn't branch to latch block. 170 171 // The latch block must end with a conditional branch where one edge goes to 172 // the header (this much we know) and one edge goes OUT of the loop. 173 BasicBlock *LoopExitBlock = FindTrivialLoopExitBlock(L, Latch); 174 if (!LoopExitBlock) return 0; 175 if (LoopExit) *LoopExit = LoopExitBlock; 176 177 // We already know that nothing uses any scalar values defined inside of this 178 // loop. As such, we just have to check to see if this loop will execute any 179 // side-effecting instructions (e.g. stores, calls, volatile loads) in the 180 // part of the loop that the code *would* execute. 181 for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I) 182 if (I->mayWriteToMemory()) 183 return false; 184 for (BasicBlock::iterator I = Latch->begin(), E = Latch->end(); I != E; ++I) 185 if (I->mayWriteToMemory()) 186 return false; 187 return true; 188} 189 190/// getLoopUnswitchCost - Return the cost (code size growth) that will happen if 191/// we choose to unswitch the specified loop on the specified value. 192/// 193unsigned LoopUnswitch::getLoopUnswitchCost(Loop *L, Value *LIC) { 194 // If the condition is trivial, always unswitch. There is no code growth for 195 // this case. 196 if (IsTrivialUnswitchCondition(L, LIC)) 197 return 0; 198 199 unsigned Cost = 0; 200 // FIXME: this is brain dead. It should take into consideration code 201 // shrinkage. 202 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 203 I != E; ++I) { 204 BasicBlock *BB = *I; 205 // Do not include empty blocks in the cost calculation. This happen due to 206 // loop canonicalization and will be removed. 207 if (BB->begin() == BasicBlock::iterator(BB->getTerminator())) 208 continue; 209 210 // Count basic blocks. 211 ++Cost; 212 } 213 214 return Cost; 215} 216 217/// FindLIVLoopCondition - Cond is a condition that occurs in L. If it is 218/// invariant in the loop, or has an invariant piece, return the invariant. 219/// Otherwise, return null. 220static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { 221 // Constants should be folded, not unswitched on! 222 if (isa<Constant>(Cond)) return false; 223 224 // TODO: Handle: br (VARIANT|INVARIANT). 225 // TODO: Hoist simple expressions out of loops. 226 if (L->isLoopInvariant(Cond)) return Cond; 227 228 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond)) 229 if (BO->getOpcode() == Instruction::And || 230 BO->getOpcode() == Instruction::Or) { 231 // If either the left or right side is invariant, we can unswitch on this, 232 // which will cause the branch to go away in one loop and the condition to 233 // simplify in the other one. 234 if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed)) 235 return LHS; 236 if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) 237 return RHS; 238 } 239 240 return 0; 241} 242 243bool LoopUnswitch::visitLoop(Loop *L) { 244 bool Changed = false; 245 246 // Recurse through all subloops before we process this loop. Copy the loop 247 // list so that the child can update the loop tree if it needs to delete the 248 // loop. 249 std::vector<Loop*> SubLoops(L->begin(), L->end()); 250 for (unsigned i = 0, e = SubLoops.size(); i != e; ++i) 251 Changed |= visitLoop(SubLoops[i]); 252 253 // Loop over all of the basic blocks in the loop. If we find an interior 254 // block that is branching on a loop-invariant condition, we can unswitch this 255 // loop. 256 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 257 I != E; ++I) { 258 TerminatorInst *TI = (*I)->getTerminator(); 259 // FIXME: Handle invariant select instructions. 260 261 if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 262 if (!isa<Constant>(SI) && L->isLoopInvariant(SI->getCondition())) 263 DEBUG(std::cerr << "TODO: Implement unswitching 'switch' loop %" 264 << L->getHeader()->getName() << ", cost = " 265 << L->getBlocks().size() << "\n" << **I); 266 continue; 267 } 268 269 BranchInst *BI = dyn_cast<BranchInst>(TI); 270 if (!BI) continue; 271 272 // If this isn't branching on an invariant condition, we can't unswitch it. 273 if (!BI->isConditional()) 274 continue; 275 276 // See if this, or some part of it, is loop invariant. If so, we can 277 // unswitch on it if we desire. 278 Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), L, Changed); 279 if (LoopCond == 0) continue; 280 281 // Check to see if it would be profitable to unswitch this loop. 282 if (getLoopUnswitchCost(L, LoopCond) > Threshold) { 283 // FIXME: this should estimate growth by the amount of code shared by the 284 // resultant unswitched loops. This should have no code growth: 285 // for () { if (iv) {...} } 286 // as one copy of the loop will be empty. 287 // 288 DEBUG(std::cerr << "NOT unswitching loop %" 289 << L->getHeader()->getName() << ", cost too high: " 290 << L->getBlocks().size() << "\n"); 291 continue; 292 } 293 294 // If this loop has live-out values, we can't unswitch it. We need something 295 // like loop-closed SSA form in order to know how to insert PHI nodes for 296 // these values. 297 if (LoopValuesUsedOutsideLoop(L)) { 298 DEBUG(std::cerr << "NOT unswitching loop %" 299 << L->getHeader()->getName() 300 << ", a loop value is used outside loop!\n"); 301 continue; 302 } 303 304 //std::cerr << "BEFORE:\n"; LI->dump(); 305 Loop *NewLoop1 = 0, *NewLoop2 = 0; 306 307 // If this is a trivial condition to unswitch (which results in no code 308 // duplication), do it now. 309 bool EntersLoopOnCond; 310 BasicBlock *ExitBlock; 311 if (IsTrivialUnswitchCondition(L, LoopCond, &EntersLoopOnCond, &ExitBlock)){ 312 UnswitchTrivialCondition(L, LoopCond, EntersLoopOnCond, ExitBlock); 313 NewLoop1 = L; 314 } else { 315 VersionLoop(LoopCond, L, NewLoop1, NewLoop2); 316 } 317 318 //std::cerr << "AFTER:\n"; LI->dump(); 319 320 // Try to unswitch each of our new loops now! 321 if (NewLoop1) visitLoop(NewLoop1); 322 if (NewLoop2) visitLoop(NewLoop2); 323 return true; 324 } 325 326 return Changed; 327} 328 329/// SplitBlock - Split the specified basic block into two pieces. If SplitAtTop 330/// is false, this splits the block so the second half only has an unconditional 331/// branch. If SplitAtTop is true, it makes it so the first half of the block 332/// only has an unconditional branch in it. 333/// 334/// This method updates the LoopInfo for this function to correctly reflect the 335/// CFG changes made. 336/// 337/// This routine returns the new basic block that was inserted, which is always 338/// the later part of the block. 339BasicBlock *LoopUnswitch::SplitBlock(BasicBlock *BB, bool SplitAtTop) { 340 BasicBlock::iterator SplitPoint; 341 if (!SplitAtTop) 342 SplitPoint = BB->getTerminator(); 343 else { 344 SplitPoint = BB->begin(); 345 while (isa<PHINode>(SplitPoint)) ++SplitPoint; 346 } 347 348 BasicBlock *New = BB->splitBasicBlock(SplitPoint, BB->getName()+".tail"); 349 // New now lives in whichever loop that BB used to. 350 if (Loop *L = LI->getLoopFor(BB)) 351 L->addBasicBlockToLoop(New, *LI); 352 return New; 353} 354 355 356// RemapInstruction - Convert the instruction operands from referencing the 357// current values into those specified by ValueMap. 358// 359static inline void RemapInstruction(Instruction *I, 360 std::map<const Value *, Value*> &ValueMap) { 361 for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { 362 Value *Op = I->getOperand(op); 363 std::map<const Value *, Value*>::iterator It = ValueMap.find(Op); 364 if (It != ValueMap.end()) Op = It->second; 365 I->setOperand(op, Op); 366 } 367} 368 369/// CloneLoop - Recursively clone the specified loop and all of its children, 370/// mapping the blocks with the specified map. 371static Loop *CloneLoop(Loop *L, Loop *PL, std::map<const Value*, Value*> &VM, 372 LoopInfo *LI) { 373 Loop *New = new Loop(); 374 375 if (PL) 376 PL->addChildLoop(New); 377 else 378 LI->addTopLevelLoop(New); 379 380 // Add all of the blocks in L to the new loop. 381 for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); 382 I != E; ++I) 383 if (LI->getLoopFor(*I) == L) 384 New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); 385 386 // Add all of the subloops to the new loop. 387 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 388 CloneLoop(*I, New, VM, LI); 389 390 return New; 391} 392 393/// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable 394/// condition in it (a cond branch from its header block to its latch block, 395/// where the path through the loop that doesn't execute its body has no 396/// side-effects), unswitch it. This doesn't involve any code duplication, just 397/// moving the conditional branch outside of the loop and updating loop info. 398void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, 399 bool EnterOnCond, 400 BasicBlock *ExitBlock) { 401 DEBUG(std::cerr << "loop-unswitch: Trivial-Unswitch loop %" 402 << L->getHeader()->getName() << " [" << L->getBlocks().size() 403 << " blocks] in Function " << L->getHeader()->getParent()->getName() 404 << " on cond:" << *Cond << "\n"); 405 406 // First step, split the preahder, so that we know that there is a safe place 407 // to insert the conditional branch. We will change 'OrigPH' to have a 408 // conditional branch on Cond. 409 BasicBlock *OrigPH = L->getLoopPreheader(); 410 BasicBlock *NewPH = SplitBlock(OrigPH, false); 411 412 // Now that we have a place to insert the conditional branch, create a place 413 // to branch to: this is the exit block out of the loop that we should 414 // short-circuit to. 415 416 // Split this block now, so that the loop maintains its exit block. 417 assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); 418 BasicBlock *NewExit = SplitBlock(ExitBlock, true); 419 420 // Okay, now we have a position to branch from and a position to branch to, 421 // insert the new conditional branch. 422 new BranchInst(EnterOnCond ? NewPH : NewExit, EnterOnCond ? NewExit : NewPH, 423 Cond, OrigPH->getTerminator()); 424 OrigPH->getTerminator()->eraseFromParent(); 425 426 // Now that we know that the loop is never entered when this condition is a 427 // particular value, rewrite the loop with this info. We know that this will 428 // at least eliminate the old branch. 429 RewriteLoopBodyWithConditionConstant(L, Cond, EnterOnCond); 430 431 ++NumUnswitched; 432} 433 434 435/// VersionLoop - We determined that the loop is profitable to unswitch and 436/// contains a branch on a loop invariant condition. Split it into loop 437/// versions and test the condition outside of either loop. Return the loops 438/// created as Out1/Out2. 439void LoopUnswitch::VersionLoop(Value *LIC, Loop *L, Loop *&Out1, Loop *&Out2) { 440 Function *F = L->getHeader()->getParent(); 441 442 DEBUG(std::cerr << "loop-unswitch: Unswitching loop %" 443 << L->getHeader()->getName() << " [" << L->getBlocks().size() 444 << " blocks] in Function " << F->getName() 445 << " on cond:" << *LIC << "\n"); 446 447 std::vector<BasicBlock*> LoopBlocks; 448 449 // First step, split the preheader and exit blocks, and add these blocks to 450 // the LoopBlocks list. 451 BasicBlock *OrigPreheader = L->getLoopPreheader(); 452 LoopBlocks.push_back(SplitBlock(OrigPreheader, false)); 453 454 // We want the loop to come after the preheader, but before the exit blocks. 455 LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); 456 457 std::vector<BasicBlock*> ExitBlocks; 458 L->getExitBlocks(ExitBlocks); 459 std::sort(ExitBlocks.begin(), ExitBlocks.end()); 460 ExitBlocks.erase(std::unique(ExitBlocks.begin(), ExitBlocks.end()), 461 ExitBlocks.end()); 462 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { 463 SplitBlock(ExitBlocks[i], true); 464 LoopBlocks.push_back(ExitBlocks[i]); 465 } 466 467 // Next step, clone all of the basic blocks that make up the loop (including 468 // the loop preheader and exit blocks), keeping track of the mapping between 469 // the instructions and blocks. 470 std::vector<BasicBlock*> NewBlocks; 471 NewBlocks.reserve(LoopBlocks.size()); 472 std::map<const Value*, Value*> ValueMap; 473 for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { 474 NewBlocks.push_back(CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F)); 475 ValueMap[LoopBlocks[i]] = NewBlocks.back(); // Keep the BB mapping. 476 } 477 478 // Splice the newly inserted blocks into the function right before the 479 // original preheader. 480 F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(), 481 NewBlocks[0], F->end()); 482 483 // Now we create the new Loop object for the versioned loop. 484 Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI); 485 if (Loop *Parent = L->getParentLoop()) { 486 // Make sure to add the cloned preheader and exit blocks to the parent loop 487 // as well. 488 Parent->addBasicBlockToLoop(NewBlocks[0], *LI); 489 for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 490 Parent->addBasicBlockToLoop(cast<BasicBlock>(ValueMap[ExitBlocks[i]]), 491 *LI); 492 } 493 494 // Rewrite the code to refer to itself. 495 for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) 496 for (BasicBlock::iterator I = NewBlocks[i]->begin(), 497 E = NewBlocks[i]->end(); I != E; ++I) 498 RemapInstruction(I, ValueMap); 499 500 // Rewrite the original preheader to select between versions of the loop. 501 assert(isa<BranchInst>(OrigPreheader->getTerminator()) && 502 cast<BranchInst>(OrigPreheader->getTerminator())->isUnconditional() && 503 OrigPreheader->getTerminator()->getSuccessor(0) == LoopBlocks[0] && 504 "Preheader splitting did not work correctly!"); 505 // Remove the unconditional branch to LoopBlocks[0]. 506 OrigPreheader->getInstList().pop_back(); 507 508 // Insert a conditional branch on LIC to the two preheaders. The original 509 // code is the true version and the new code is the false version. 510 new BranchInst(LoopBlocks[0], NewBlocks[0], LIC, OrigPreheader); 511 512 // Now we rewrite the original code to know that the condition is true and the 513 // new code to know that the condition is false. 514 RewriteLoopBodyWithConditionConstant(L, LIC, true); 515 RewriteLoopBodyWithConditionConstant(NewLoop, LIC, false); 516 ++NumUnswitched; 517 Out1 = L; 518 Out2 = NewLoop; 519} 520 521// RewriteLoopBodyWithConditionConstant - We know that the boolean value LIC has 522// the value specified by Val in the specified loop. Rewrite any uses of LIC or 523// of properties correlated to it. 524void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, 525 bool Val) { 526 assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?"); 527 // FIXME: Support correlated properties, like: 528 // for (...) 529 // if (li1 < li2) 530 // ... 531 // if (li1 > li2) 532 // ... 533 ConstantBool *BoolVal = ConstantBool::get(Val); 534 535 // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, 536 // selects, switches. 537 std::vector<User*> Users(LIC->use_begin(), LIC->use_end()); 538 for (unsigned i = 0, e = Users.size(); i != e; ++i) 539 if (Instruction *U = cast<Instruction>(Users[i])) 540 if (L->contains(U->getParent())) 541 U->replaceUsesOfWith(LIC, BoolVal); 542} 543