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