Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 1 | //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 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. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 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" |
Reid Spencer | c103057 | 2007-01-19 21:13:56 +0000 | [diff] [blame] | 32 | #include "llvm/DerivedTypes.h" |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 33 | #include "llvm/Function.h" |
| 34 | #include "llvm/Instructions.h" |
Chris Lattner | 79066fa | 2007-01-30 23:46:24 +0000 | [diff] [blame] | 35 | #include "llvm/Analysis/ConstantFolding.h" |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 36 | #include "llvm/Analysis/LoopInfo.h" |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 37 | #include "llvm/Analysis/LoopPass.h" |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 38 | #include "llvm/Transforms/Utils/Cloning.h" |
| 39 | #include "llvm/Transforms/Utils/Local.h" |
Chris Lattner | 81be2e9 | 2006-02-10 19:08:15 +0000 | [diff] [blame] | 40 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 41 | #include "llvm/ADT/Statistic.h" |
Devang Patel | fb688d4 | 2007-02-26 20:22:50 +0000 | [diff] [blame] | 42 | #include "llvm/ADT/SmallPtrSet.h" |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 43 | #include "llvm/ADT/PostOrderIterator.h" |
Chris Lattner | e487abb | 2006-02-09 20:15:48 +0000 | [diff] [blame] | 44 | #include "llvm/Support/CommandLine.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 45 | #include "llvm/Support/Compiler.h" |
| 46 | #include "llvm/Support/Debug.h" |
Alkis Evlogimenos | 20aa474 | 2004-09-03 18:19:51 +0000 | [diff] [blame] | 47 | #include <algorithm> |
Chris Lattner | 2f4b898 | 2006-02-09 19:14:52 +0000 | [diff] [blame] | 48 | #include <set> |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 49 | using namespace llvm; |
| 50 | |
Chris Lattner | 0e5f499 | 2006-12-19 21:40:18 +0000 | [diff] [blame] | 51 | STATISTIC(NumBranches, "Number of branches unswitched"); |
| 52 | STATISTIC(NumSwitches, "Number of switches unswitched"); |
| 53 | STATISTIC(NumSelects , "Number of selects unswitched"); |
| 54 | STATISTIC(NumTrivial , "Number of unswitches that are trivial"); |
| 55 | STATISTIC(NumSimplify, "Number of simplifications of unswitched code"); |
| 56 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 57 | namespace { |
Chris Lattner | e487abb | 2006-02-09 20:15:48 +0000 | [diff] [blame] | 58 | cl::opt<unsigned> |
| 59 | Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), |
| 60 | cl::init(10), cl::Hidden); |
| 61 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 62 | class VISIBILITY_HIDDEN LoopUnswitch : public LoopPass { |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 63 | LoopInfo *LI; // Loop information |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 64 | LPPassManager *LPM; |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 65 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 66 | // LoopProcessWorklist - Used to check if second loop needs processing |
| 67 | // after RewriteLoopBodyWithConditionConstant rewrites first loop. |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 68 | std::vector<Loop*> LoopProcessWorklist; |
Devang Patel | fb688d4 | 2007-02-26 20:22:50 +0000 | [diff] [blame] | 69 | SmallPtrSet<Value *,8> UnswitchedVals; |
Devang Patel | 5295692 | 2007-02-26 19:31:58 +0000 | [diff] [blame] | 70 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 71 | public: |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 72 | static char ID; // Pass ID, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 73 | LoopUnswitch() : LoopPass((intptr_t)&ID) {} |
| 74 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 75 | bool runOnLoop(Loop *L, LPPassManager &LPM); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 76 | |
| 77 | /// This transformation requires natural loop information & requires that |
| 78 | /// loop preheaders be inserted into the CFG... |
| 79 | /// |
| 80 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 81 | AU.addRequiredID(LoopSimplifyID); |
Chris Lattner | f4f5f4e | 2006-02-09 22:15:42 +0000 | [diff] [blame] | 82 | AU.addPreservedID(LoopSimplifyID); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 83 | AU.addRequired<LoopInfo>(); |
| 84 | AU.addPreserved<LoopInfo>(); |
Owen Anderson | 6edf399 | 2006-06-12 21:49:21 +0000 | [diff] [blame] | 85 | AU.addRequiredID(LCSSAID); |
| 86 | AU.addPreservedID(LCSSAID); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | private: |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 90 | /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist, |
| 91 | /// remove it. |
| 92 | void RemoveLoopFromWorklist(Loop *L) { |
| 93 | std::vector<Loop*>::iterator I = std::find(LoopProcessWorklist.begin(), |
| 94 | LoopProcessWorklist.end(), L); |
| 95 | if (I != LoopProcessWorklist.end()) |
| 96 | LoopProcessWorklist.erase(I); |
| 97 | } |
| 98 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 99 | bool UnswitchIfProfitable(Value *LoopCond, Constant *Val,Loop *L); |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 100 | unsigned getLoopUnswitchCost(Loop *L, Value *LIC); |
Chris Lattner | f4412d8 | 2006-02-18 01:27:45 +0000 | [diff] [blame] | 101 | void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 102 | BasicBlock *ExitBlock); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 103 | void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 104 | BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To); |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 105 | BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 106 | |
| 107 | void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, |
| 108 | Constant *Val, bool isEqual); |
| 109 | |
| 110 | void SimplifyCode(std::vector<Instruction*> &Worklist); |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 111 | void RemoveBlockIfDead(BasicBlock *BB, |
| 112 | std::vector<Instruction*> &Worklist); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 113 | void RemoveLoopFromHierarchy(Loop *L); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 114 | }; |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 115 | char LoopUnswitch::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 116 | RegisterPass<LoopUnswitch> X("loop-unswitch", "Unswitch loops"); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 117 | } |
| 118 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 119 | LoopPass *llvm::createLoopUnswitchPass() { return new LoopUnswitch(); } |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 120 | |
| 121 | /// FindLIVLoopCondition - Cond is a condition that occurs in L. If it is |
| 122 | /// invariant in the loop, or has an invariant piece, return the invariant. |
| 123 | /// Otherwise, return null. |
| 124 | static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { |
| 125 | // Constants should be folded, not unswitched on! |
| 126 | if (isa<Constant>(Cond)) return false; |
| 127 | |
| 128 | // TODO: Handle: br (VARIANT|INVARIANT). |
| 129 | // TODO: Hoist simple expressions out of loops. |
| 130 | if (L->isLoopInvariant(Cond)) return Cond; |
| 131 | |
| 132 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond)) |
| 133 | if (BO->getOpcode() == Instruction::And || |
| 134 | BO->getOpcode() == Instruction::Or) { |
| 135 | // If either the left or right side is invariant, we can unswitch on this, |
| 136 | // which will cause the branch to go away in one loop and the condition to |
| 137 | // simplify in the other one. |
| 138 | if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed)) |
| 139 | return LHS; |
| 140 | if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) |
| 141 | return RHS; |
| 142 | } |
| 143 | |
| 144 | return 0; |
| 145 | } |
| 146 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 147 | bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { |
Owen Anderson | 6edf399 | 2006-06-12 21:49:21 +0000 | [diff] [blame] | 148 | assert(L->isLCSSAForm()); |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 149 | LI = &getAnalysis<LoopInfo>(); |
| 150 | LPM = &LPM_Ref; |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 151 | bool Changed = false; |
| 152 | |
| 153 | // Loop over all of the basic blocks in the loop. If we find an interior |
| 154 | // block that is branching on a loop-invariant condition, we can unswitch this |
| 155 | // loop. |
| 156 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 157 | I != E; ++I) { |
| 158 | TerminatorInst *TI = (*I)->getTerminator(); |
| 159 | if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { |
| 160 | // If this isn't branching on an invariant condition, we can't unswitch |
| 161 | // it. |
| 162 | if (BI->isConditional()) { |
| 163 | // See if this, or some part of it, is loop invariant. If so, we can |
| 164 | // unswitch on it if we desire. |
| 165 | Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), L, Changed); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 166 | if (LoopCond && UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(), |
Chris Lattner | 47811b7 | 2006-09-28 23:35:22 +0000 | [diff] [blame] | 167 | L)) { |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 168 | ++NumBranches; |
| 169 | return true; |
| 170 | } |
| 171 | } |
| 172 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { |
| 173 | Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), L, Changed); |
| 174 | if (LoopCond && SI->getNumCases() > 1) { |
| 175 | // Find a value to unswitch on: |
| 176 | // FIXME: this should chose the most expensive case! |
| 177 | Constant *UnswitchVal = SI->getCaseValue(1); |
Devang Patel | 5295692 | 2007-02-26 19:31:58 +0000 | [diff] [blame] | 178 | // Do not process same value again and again. |
Devang Patel | fb688d4 | 2007-02-26 20:22:50 +0000 | [diff] [blame] | 179 | if (!UnswitchedVals.insert(UnswitchVal)) |
Devang Patel | 5295692 | 2007-02-26 19:31:58 +0000 | [diff] [blame] | 180 | continue; |
Devang Patel | 5295692 | 2007-02-26 19:31:58 +0000 | [diff] [blame] | 181 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 182 | if (UnswitchIfProfitable(LoopCond, UnswitchVal, L)) { |
| 183 | ++NumSwitches; |
| 184 | return true; |
| 185 | } |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | // Scan the instructions to check for unswitchable values. |
| 190 | for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); |
| 191 | BBI != E; ++BBI) |
| 192 | if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) { |
| 193 | Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), L, Changed); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 194 | if (LoopCond && UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(), |
Chris Lattner | 47811b7 | 2006-09-28 23:35:22 +0000 | [diff] [blame] | 195 | L)) { |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 196 | ++NumSelects; |
| 197 | return true; |
| 198 | } |
| 199 | } |
| 200 | } |
Owen Anderson | 6edf399 | 2006-06-12 21:49:21 +0000 | [diff] [blame] | 201 | |
| 202 | assert(L->isLCSSAForm()); |
| 203 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 204 | return Changed; |
| 205 | } |
| 206 | |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 207 | /// isTrivialLoopExitBlock - Check to see if all paths from BB either: |
| 208 | /// 1. Exit the loop with no side effects. |
| 209 | /// 2. Branch to the latch block with no side-effects. |
| 210 | /// |
| 211 | /// If these conditions are true, we return true and set ExitBB to the block we |
| 212 | /// exit through. |
| 213 | /// |
| 214 | static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, |
| 215 | BasicBlock *&ExitBB, |
| 216 | std::set<BasicBlock*> &Visited) { |
Chris Lattner | 0017d48 | 2006-02-17 06:39:56 +0000 | [diff] [blame] | 217 | if (!Visited.insert(BB).second) { |
| 218 | // Already visited and Ok, end of recursion. |
| 219 | return true; |
| 220 | } else if (!L->contains(BB)) { |
| 221 | // Otherwise, this is a loop exit, this is fine so long as this is the |
| 222 | // first exit. |
| 223 | if (ExitBB != 0) return false; |
| 224 | ExitBB = BB; |
| 225 | return true; |
| 226 | } |
| 227 | |
| 228 | // Otherwise, this is an unvisited intra-loop node. Check all successors. |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 229 | for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) { |
Chris Lattner | 0017d48 | 2006-02-17 06:39:56 +0000 | [diff] [blame] | 230 | // Check to see if the successor is a trivial loop exit. |
| 231 | if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited)) |
| 232 | return false; |
Chris Lattner | 708e1a5 | 2006-02-10 02:30:37 +0000 | [diff] [blame] | 233 | } |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 234 | |
| 235 | // Okay, everything after this looks good, check to make sure that this block |
| 236 | // doesn't include any side effects. |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 237 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 238 | if (I->mayWriteToMemory()) |
| 239 | return false; |
| 240 | |
| 241 | return true; |
Chris Lattner | 708e1a5 | 2006-02-10 02:30:37 +0000 | [diff] [blame] | 242 | } |
| 243 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 244 | /// isTrivialLoopExitBlock - Return true if the specified block unconditionally |
| 245 | /// leads to an exit from the specified loop, and has no side-effects in the |
| 246 | /// process. If so, return the block that is exited to, otherwise return null. |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 247 | static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { |
| 248 | std::set<BasicBlock*> Visited; |
| 249 | Visited.insert(L->getHeader()); // Branches to header are ok. |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 250 | BasicBlock *ExitBB = 0; |
| 251 | if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited)) |
| 252 | return ExitBB; |
| 253 | return 0; |
| 254 | } |
Chris Lattner | 708e1a5 | 2006-02-10 02:30:37 +0000 | [diff] [blame] | 255 | |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 256 | /// IsTrivialUnswitchCondition - Check to see if this unswitch condition is |
| 257 | /// trivial: that is, that the condition controls whether or not the loop does |
| 258 | /// anything at all. If this is a trivial condition, unswitching produces no |
| 259 | /// code duplications (equivalently, it produces a simpler loop and a new empty |
| 260 | /// loop, which gets deleted). |
| 261 | /// |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 262 | /// If this is a trivial condition, return true, otherwise return false. When |
| 263 | /// returning true, this sets Cond and Val to the condition that controls the |
| 264 | /// trivial condition: when Cond dynamically equals Val, the loop is known to |
| 265 | /// exit. Finally, this sets LoopExit to the BB that the loop exits to when |
| 266 | /// Cond == Val. |
| 267 | /// |
| 268 | static bool IsTrivialUnswitchCondition(Loop *L, Value *Cond, Constant **Val = 0, |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 269 | BasicBlock **LoopExit = 0) { |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 270 | BasicBlock *Header = L->getHeader(); |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 271 | TerminatorInst *HeaderTerm = Header->getTerminator(); |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 272 | |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 273 | BasicBlock *LoopExitBB = 0; |
| 274 | if (BranchInst *BI = dyn_cast<BranchInst>(HeaderTerm)) { |
| 275 | // If the header block doesn't end with a conditional branch on Cond, we |
| 276 | // can't handle it. |
| 277 | if (!BI->isConditional() || BI->getCondition() != Cond) |
| 278 | return false; |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 279 | |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 280 | // Check to see if a successor of the branch is guaranteed to go to the |
| 281 | // latch block or exit through a one exit block without having any |
| 282 | // side-effects. If so, determine the value of Cond that causes it to do |
| 283 | // this. |
| 284 | if ((LoopExitBB = isTrivialLoopExitBlock(L, BI->getSuccessor(0)))) { |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 285 | if (Val) *Val = ConstantInt::getTrue(); |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 286 | } else if ((LoopExitBB = isTrivialLoopExitBlock(L, BI->getSuccessor(1)))) { |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 287 | if (Val) *Val = ConstantInt::getFalse(); |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 288 | } |
| 289 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(HeaderTerm)) { |
| 290 | // If this isn't a switch on Cond, we can't handle it. |
| 291 | if (SI->getCondition() != Cond) return false; |
| 292 | |
| 293 | // Check to see if a successor of the switch is guaranteed to go to the |
| 294 | // latch block or exit through a one exit block without having any |
| 295 | // side-effects. If so, determine the value of Cond that causes it to do |
| 296 | // this. Note that we can't trivially unswitch on the default case. |
| 297 | for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) |
| 298 | if ((LoopExitBB = isTrivialLoopExitBlock(L, SI->getSuccessor(i)))) { |
| 299 | // Okay, we found a trivial case, remember the value that is trivial. |
| 300 | if (Val) *Val = SI->getCaseValue(i); |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 301 | break; |
| 302 | } |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 303 | } |
| 304 | |
Chris Lattner | f8bf116 | 2006-02-22 23:55:00 +0000 | [diff] [blame] | 305 | // If we didn't find a single unique LoopExit block, or if the loop exit block |
| 306 | // contains phi nodes, this isn't trivial. |
| 307 | if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 308 | return false; // Can't handle this. |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 309 | |
Chris Lattner | a48654e | 2006-02-15 22:52:05 +0000 | [diff] [blame] | 310 | if (LoopExit) *LoopExit = LoopExitBB; |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 311 | |
| 312 | // We already know that nothing uses any scalar values defined inside of this |
| 313 | // loop. As such, we just have to check to see if this loop will execute any |
| 314 | // side-effecting instructions (e.g. stores, calls, volatile loads) in the |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 315 | // part of the loop that the code *would* execute. We already checked the |
| 316 | // tail, check the header now. |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 317 | for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E; ++I) |
| 318 | if (I->mayWriteToMemory()) |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 319 | return false; |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 320 | return true; |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 321 | } |
| 322 | |
| 323 | /// getLoopUnswitchCost - Return the cost (code size growth) that will happen if |
| 324 | /// we choose to unswitch the specified loop on the specified value. |
| 325 | /// |
| 326 | unsigned LoopUnswitch::getLoopUnswitchCost(Loop *L, Value *LIC) { |
| 327 | // If the condition is trivial, always unswitch. There is no code growth for |
| 328 | // this case. |
| 329 | if (IsTrivialUnswitchCondition(L, LIC)) |
| 330 | return 0; |
| 331 | |
Owen Anderson | 372994b | 2006-06-28 17:47:50 +0000 | [diff] [blame] | 332 | // FIXME: This is really overly conservative. However, more liberal |
| 333 | // estimations have thus far resulted in excessive unswitching, which is bad |
| 334 | // both in compile time and in code size. This should be replaced once |
| 335 | // someone figures out how a good estimation. |
| 336 | return L->getBlocks().size(); |
Chris Lattner | daa2bf9 | 2006-06-28 16:38:55 +0000 | [diff] [blame] | 337 | |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 338 | unsigned Cost = 0; |
| 339 | // FIXME: this is brain dead. It should take into consideration code |
| 340 | // shrinkage. |
| 341 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 342 | I != E; ++I) { |
| 343 | BasicBlock *BB = *I; |
| 344 | // Do not include empty blocks in the cost calculation. This happen due to |
| 345 | // loop canonicalization and will be removed. |
| 346 | if (BB->begin() == BasicBlock::iterator(BB->getTerminator())) |
| 347 | continue; |
| 348 | |
| 349 | // Count basic blocks. |
| 350 | ++Cost; |
| 351 | } |
| 352 | |
| 353 | return Cost; |
| 354 | } |
| 355 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 356 | /// UnswitchIfProfitable - We have found that we can unswitch L when |
| 357 | /// LoopCond == Val to simplify the loop. If we decide that this is profitable, |
| 358 | /// unswitch the loop, reprocess the pieces, then return true. |
| 359 | bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,Loop *L){ |
| 360 | // Check to see if it would be profitable to unswitch this loop. |
Chris Lattner | 0f862e5 | 2006-03-24 07:14:00 +0000 | [diff] [blame] | 361 | unsigned Cost = getLoopUnswitchCost(L, LoopCond); |
| 362 | if (Cost > Threshold) { |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 363 | // FIXME: this should estimate growth by the amount of code shared by the |
| 364 | // resultant unswitched loops. |
| 365 | // |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 366 | DOUT << "NOT unswitching loop %" |
| 367 | << L->getHeader()->getName() << ", cost too high: " |
| 368 | << L->getBlocks().size() << "\n"; |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 369 | return false; |
| 370 | } |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 371 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 372 | // If this is a trivial condition to unswitch (which results in no code |
| 373 | // duplication), do it now. |
Chris Lattner | 6d9d13d | 2006-02-15 01:44:42 +0000 | [diff] [blame] | 374 | Constant *CondVal; |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 375 | BasicBlock *ExitBlock; |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 376 | if (IsTrivialUnswitchCondition(L, LoopCond, &CondVal, &ExitBlock)) { |
| 377 | UnswitchTrivialCondition(L, LoopCond, CondVal, ExitBlock); |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 378 | } else { |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 379 | UnswitchNontrivialCondition(LoopCond, Val, L); |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 380 | } |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 381 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 382 | return true; |
| 383 | } |
| 384 | |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 385 | /// SplitBlock - Split the specified block at the specified instruction - every |
| 386 | /// thing before SplitPt stays in Old and everything starting with SplitPt moves |
| 387 | /// to a new block. The two blocks are joined by an unconditional branch and |
| 388 | /// the loop info is updated. |
| 389 | /// |
| 390 | BasicBlock *LoopUnswitch::SplitBlock(BasicBlock *Old, Instruction *SplitPt) { |
Chris Lattner | 10cd9bb | 2006-02-16 19:36:22 +0000 | [diff] [blame] | 391 | BasicBlock::iterator SplitIt = SplitPt; |
| 392 | while (isa<PHINode>(SplitIt)) |
| 393 | ++SplitIt; |
| 394 | BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split"); |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 395 | |
| 396 | // The new block lives in whichever loop the old one did. |
| 397 | if (Loop *L = LI->getLoopFor(Old)) |
| 398 | L->addBasicBlockToLoop(New, *LI); |
| 399 | |
| 400 | return New; |
| 401 | } |
| 402 | |
| 403 | |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 404 | BasicBlock *LoopUnswitch::SplitEdge(BasicBlock *BB, BasicBlock *Succ) { |
| 405 | TerminatorInst *LatchTerm = BB->getTerminator(); |
| 406 | unsigned SuccNum = 0; |
| 407 | for (unsigned i = 0, e = LatchTerm->getNumSuccessors(); ; ++i) { |
| 408 | assert(i != e && "Didn't find edge?"); |
| 409 | if (LatchTerm->getSuccessor(i) == Succ) { |
| 410 | SuccNum = i; |
| 411 | break; |
| 412 | } |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 413 | } |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 414 | |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 415 | // If this is a critical edge, let SplitCriticalEdge do it. |
| 416 | if (SplitCriticalEdge(BB->getTerminator(), SuccNum, this)) |
| 417 | return LatchTerm->getSuccessor(SuccNum); |
| 418 | |
| 419 | // If the edge isn't critical, then BB has a single successor or Succ has a |
| 420 | // single pred. Split the block. |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 421 | BasicBlock::iterator SplitPoint; |
| 422 | if (BasicBlock *SP = Succ->getSinglePredecessor()) { |
| 423 | // If the successor only has a single pred, split the top of the successor |
| 424 | // block. |
| 425 | assert(SP == BB && "CFG broken"); |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 426 | return SplitBlock(Succ, Succ->begin()); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 427 | } else { |
| 428 | // Otherwise, if BB has a single successor, split it at the bottom of the |
| 429 | // block. |
| 430 | assert(BB->getTerminator()->getNumSuccessors() == 1 && |
| 431 | "Should have a single succ!"); |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 432 | return SplitBlock(BB, BB->getTerminator()); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 433 | } |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 434 | } |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 435 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 436 | |
| 437 | |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 438 | // RemapInstruction - Convert the instruction operands from referencing the |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 439 | // current values into those specified by ValueMap. |
| 440 | // |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 441 | static inline void RemapInstruction(Instruction *I, |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 442 | DenseMap<const Value *, Value*> &ValueMap) { |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 443 | for (unsigned op = 0, E = I->getNumOperands(); op != E; ++op) { |
| 444 | Value *Op = I->getOperand(op); |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 445 | DenseMap<const Value *, Value*>::iterator It = ValueMap.find(Op); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 446 | if (It != ValueMap.end()) Op = It->second; |
| 447 | I->setOperand(op, Op); |
| 448 | } |
| 449 | } |
| 450 | |
| 451 | /// CloneLoop - Recursively clone the specified loop and all of its children, |
| 452 | /// mapping the blocks with the specified map. |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 453 | static Loop *CloneLoop(Loop *L, Loop *PL, DenseMap<const Value*, Value*> &VM, |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 454 | LoopInfo *LI, LPPassManager *LPM) { |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 455 | Loop *New = new Loop(); |
| 456 | |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 457 | LPM->insertLoop(New, PL); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 458 | |
| 459 | // Add all of the blocks in L to the new loop. |
| 460 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 461 | I != E; ++I) |
| 462 | if (LI->getLoopFor(*I) == L) |
| 463 | New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); |
| 464 | |
| 465 | // Add all of the subloops to the new loop. |
| 466 | for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 467 | CloneLoop(*I, New, VM, LI, LPM); |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 468 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 469 | return New; |
| 470 | } |
| 471 | |
Chris Lattner | fed5d9d | 2006-02-15 00:07:43 +0000 | [diff] [blame] | 472 | /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values |
| 473 | /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the |
| 474 | /// code immediately before InsertPt. |
| 475 | static void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, |
| 476 | BasicBlock *TrueDest, |
| 477 | BasicBlock *FalseDest, |
| 478 | Instruction *InsertPt) { |
| 479 | // Insert a conditional branch on LIC to the two preheaders. The original |
| 480 | // code is the true version and the new code is the false version. |
| 481 | Value *BranchVal = LIC; |
Reid Spencer | c103057 | 2007-01-19 21:13:56 +0000 | [diff] [blame] | 482 | if (!isa<ConstantInt>(Val) || Val->getType() != Type::Int1Ty) |
Reid Spencer | e4d87aa | 2006-12-23 06:05:41 +0000 | [diff] [blame] | 483 | BranchVal = new ICmpInst(ICmpInst::ICMP_EQ, LIC, Val, "tmp", InsertPt); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 484 | else if (Val != ConstantInt::getTrue()) |
Chris Lattner | fed5d9d | 2006-02-15 00:07:43 +0000 | [diff] [blame] | 485 | // We want to enter the new loop when the condition is true. |
| 486 | std::swap(TrueDest, FalseDest); |
Chris Lattner | fed5d9d | 2006-02-15 00:07:43 +0000 | [diff] [blame] | 487 | |
| 488 | // Insert the new branch. |
| 489 | new BranchInst(TrueDest, FalseDest, BranchVal, InsertPt); |
| 490 | } |
| 491 | |
| 492 | |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 493 | /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable |
| 494 | /// condition in it (a cond branch from its header block to its latch block, |
| 495 | /// where the path through the loop that doesn't execute its body has no |
| 496 | /// side-effects), unswitch it. This doesn't involve any code duplication, just |
| 497 | /// moving the conditional branch outside of the loop and updating loop info. |
| 498 | void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 499 | Constant *Val, |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 500 | BasicBlock *ExitBlock) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 501 | DOUT << "loop-unswitch: Trivial-Unswitch loop %" |
| 502 | << L->getHeader()->getName() << " [" << L->getBlocks().size() |
| 503 | << " blocks] in Function " << L->getHeader()->getParent()->getName() |
| 504 | << " on cond: " << *Val << " == " << *Cond << "\n"; |
Chris Lattner | 4d1ca94 | 2006-02-10 01:36:35 +0000 | [diff] [blame] | 505 | |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 506 | // First step, split the preheader, so that we know that there is a safe place |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 507 | // to insert the conditional branch. We will change 'OrigPH' to have a |
| 508 | // conditional branch on Cond. |
| 509 | BasicBlock *OrigPH = L->getLoopPreheader(); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 510 | BasicBlock *NewPH = SplitEdge(OrigPH, L->getHeader()); |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 511 | |
| 512 | // Now that we have a place to insert the conditional branch, create a place |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 513 | // to branch to: this is the exit block out of the loop that we should |
| 514 | // short-circuit to. |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 515 | |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 516 | // Split this block now, so that the loop maintains its exit block, and so |
| 517 | // that the jump from the preheader can execute the contents of the exit block |
| 518 | // without actually branching to it (the exit block should be dominated by the |
| 519 | // loop header, not the preheader). |
Chris Lattner | dd3ee6d | 2006-02-10 02:01:22 +0000 | [diff] [blame] | 520 | assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); |
Chris Lattner | 4e13239 | 2006-02-15 22:03:36 +0000 | [diff] [blame] | 521 | BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin()); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 522 | |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 523 | // Okay, now we have a position to branch from and a position to branch to, |
| 524 | // insert the new conditional branch. |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 525 | EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, |
| 526 | OrigPH->getTerminator()); |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 527 | OrigPH->getTerminator()->eraseFromParent(); |
| 528 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 529 | // We need to reprocess this loop, it could be unswitched again. |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 530 | LPM->redoLoop(L); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 531 | |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 532 | // Now that we know that the loop is never entered when this condition is a |
| 533 | // particular value, rewrite the loop with this info. We know that this will |
| 534 | // at least eliminate the old branch. |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 535 | RewriteLoopBodyWithConditionConstant(L, Cond, Val, false); |
Chris Lattner | 3dd4c40 | 2006-02-14 01:01:41 +0000 | [diff] [blame] | 536 | ++NumTrivial; |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 537 | } |
| 538 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 539 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 540 | /// VersionLoop - We determined that the loop is profitable to unswitch when LIC |
| 541 | /// equal Val. Split it into loop versions and test the condition outside of |
| 542 | /// either loop. Return the loops created as Out1/Out2. |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 543 | void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, |
| 544 | Loop *L) { |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 545 | Function *F = L->getHeader()->getParent(); |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 546 | DOUT << "loop-unswitch: Unswitching loop %" |
| 547 | << L->getHeader()->getName() << " [" << L->getBlocks().size() |
| 548 | << " blocks] in Function " << F->getName() |
| 549 | << " when '" << *Val << "' == " << *LIC << "\n"; |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 550 | |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 551 | // LoopBlocks contains all of the basic blocks of the loop, including the |
| 552 | // preheader of the loop, the body of the loop, and the exit blocks of the |
| 553 | // loop, in that order. |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 554 | std::vector<BasicBlock*> LoopBlocks; |
| 555 | |
| 556 | // First step, split the preheader and exit blocks, and add these blocks to |
| 557 | // the LoopBlocks list. |
| 558 | BasicBlock *OrigPreheader = L->getLoopPreheader(); |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 559 | LoopBlocks.push_back(SplitEdge(OrigPreheader, L->getHeader())); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 560 | |
| 561 | // We want the loop to come after the preheader, but before the exit blocks. |
| 562 | LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); |
| 563 | |
| 564 | std::vector<BasicBlock*> ExitBlocks; |
Devang Patel | 4b8f36f | 2006-08-29 22:29:16 +0000 | [diff] [blame] | 565 | L->getUniqueExitBlocks(ExitBlocks); |
| 566 | |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 567 | // Split all of the edges from inside the loop to their exit blocks. Update |
| 568 | // the appropriate Phi nodes as we do so. |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 569 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 570 | BasicBlock *ExitBlock = ExitBlocks[i]; |
| 571 | std::vector<BasicBlock*> Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); |
| 572 | |
| 573 | for (unsigned j = 0, e = Preds.size(); j != e; ++j) { |
| 574 | assert(L->contains(Preds[j]) && |
| 575 | "All preds of loop exit blocks must be the same loop!"); |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 576 | BasicBlock* MiddleBlock = SplitEdge(Preds[j], ExitBlock); |
| 577 | BasicBlock* StartBlock = Preds[j]; |
| 578 | BasicBlock* EndBlock; |
| 579 | if (MiddleBlock->getSinglePredecessor() == ExitBlock) { |
| 580 | EndBlock = MiddleBlock; |
| 581 | MiddleBlock = EndBlock->getSinglePredecessor();; |
| 582 | } else { |
| 583 | EndBlock = ExitBlock; |
| 584 | } |
| 585 | |
| 586 | std::set<PHINode*> InsertedPHIs; |
| 587 | PHINode* OldLCSSA = 0; |
| 588 | for (BasicBlock::iterator I = EndBlock->begin(); |
| 589 | (OldLCSSA = dyn_cast<PHINode>(I)); ++I) { |
| 590 | Value* OldValue = OldLCSSA->getIncomingValueForBlock(MiddleBlock); |
| 591 | PHINode* NewLCSSA = new PHINode(OldLCSSA->getType(), |
| 592 | OldLCSSA->getName() + ".us-lcssa", |
| 593 | MiddleBlock->getTerminator()); |
| 594 | NewLCSSA->addIncoming(OldValue, StartBlock); |
| 595 | OldLCSSA->setIncomingValue(OldLCSSA->getBasicBlockIndex(MiddleBlock), |
| 596 | NewLCSSA); |
| 597 | InsertedPHIs.insert(NewLCSSA); |
| 598 | } |
| 599 | |
Owen Anderson | db5b9cf | 2006-07-19 03:51:48 +0000 | [diff] [blame] | 600 | BasicBlock::iterator InsertPt = EndBlock->begin(); |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 601 | while (dyn_cast<PHINode>(InsertPt)) ++InsertPt; |
| 602 | for (BasicBlock::iterator I = MiddleBlock->begin(); |
| 603 | (OldLCSSA = dyn_cast<PHINode>(I)) && InsertedPHIs.count(OldLCSSA) == 0; |
| 604 | ++I) { |
| 605 | PHINode *NewLCSSA = new PHINode(OldLCSSA->getType(), |
| 606 | OldLCSSA->getName() + ".us-lcssa", |
| 607 | InsertPt); |
| 608 | OldLCSSA->replaceAllUsesWith(NewLCSSA); |
| 609 | NewLCSSA->addIncoming(OldLCSSA, MiddleBlock); |
| 610 | } |
| 611 | } |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 612 | } |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 613 | |
| 614 | // The exit blocks may have been changed due to edge splitting, recompute. |
| 615 | ExitBlocks.clear(); |
Devang Patel | 4b8f36f | 2006-08-29 22:29:16 +0000 | [diff] [blame] | 616 | L->getUniqueExitBlocks(ExitBlocks); |
| 617 | |
Chris Lattner | b2bc315 | 2006-02-10 23:16:39 +0000 | [diff] [blame] | 618 | // Add exit blocks to the loop blocks. |
| 619 | LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end()); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 620 | |
| 621 | // Next step, clone all of the basic blocks that make up the loop (including |
| 622 | // the loop preheader and exit blocks), keeping track of the mapping between |
| 623 | // the instructions and blocks. |
| 624 | std::vector<BasicBlock*> NewBlocks; |
| 625 | NewBlocks.reserve(LoopBlocks.size()); |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 626 | DenseMap<const Value*, Value*> ValueMap; |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 627 | for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { |
Chris Lattner | 3dd4c40 | 2006-02-14 01:01:41 +0000 | [diff] [blame] | 628 | BasicBlock *New = CloneBasicBlock(LoopBlocks[i], ValueMap, ".us", F); |
| 629 | NewBlocks.push_back(New); |
| 630 | ValueMap[LoopBlocks[i]] = New; // Keep the BB mapping. |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 631 | } |
| 632 | |
| 633 | // Splice the newly inserted blocks into the function right before the |
| 634 | // original preheader. |
| 635 | F->getBasicBlockList().splice(LoopBlocks[0], F->getBasicBlockList(), |
| 636 | NewBlocks[0], F->end()); |
| 637 | |
| 638 | // Now we create the new Loop object for the versioned loop. |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 639 | Loop *NewLoop = CloneLoop(L, L->getParentLoop(), ValueMap, LI, LPM); |
Chris Lattner | e825593 | 2006-02-10 23:26:14 +0000 | [diff] [blame] | 640 | Loop *ParentLoop = L->getParentLoop(); |
| 641 | if (ParentLoop) { |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 642 | // Make sure to add the cloned preheader and exit blocks to the parent loop |
| 643 | // as well. |
Chris Lattner | e825593 | 2006-02-10 23:26:14 +0000 | [diff] [blame] | 644 | ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); |
| 645 | } |
| 646 | |
| 647 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { |
| 648 | BasicBlock *NewExit = cast<BasicBlock>(ValueMap[ExitBlocks[i]]); |
Chris Lattner | 25cae0f | 2006-02-18 00:55:32 +0000 | [diff] [blame] | 649 | // The new exit block should be in the same loop as the old one. |
| 650 | if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) |
| 651 | ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); |
Chris Lattner | e825593 | 2006-02-10 23:26:14 +0000 | [diff] [blame] | 652 | |
| 653 | assert(NewExit->getTerminator()->getNumSuccessors() == 1 && |
| 654 | "Exit block should have been split to have one successor!"); |
| 655 | BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); |
| 656 | |
| 657 | // If the successor of the exit block had PHI nodes, add an entry for |
| 658 | // NewExit. |
| 659 | PHINode *PN; |
| 660 | for (BasicBlock::iterator I = ExitSucc->begin(); |
| 661 | (PN = dyn_cast<PHINode>(I)); ++I) { |
| 662 | Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]); |
Chris Lattner | 5e665f5 | 2007-02-03 00:08:31 +0000 | [diff] [blame] | 663 | DenseMap<const Value *, Value*>::iterator It = ValueMap.find(V); |
Chris Lattner | e825593 | 2006-02-10 23:26:14 +0000 | [diff] [blame] | 664 | if (It != ValueMap.end()) V = It->second; |
| 665 | PN->addIncoming(V, NewExit); |
| 666 | } |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 667 | } |
| 668 | |
| 669 | // Rewrite the code to refer to itself. |
| 670 | for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) |
| 671 | for (BasicBlock::iterator I = NewBlocks[i]->begin(), |
| 672 | E = NewBlocks[i]->end(); I != E; ++I) |
| 673 | RemapInstruction(I, ValueMap); |
Chris Lattner | 2f4b898 | 2006-02-09 19:14:52 +0000 | [diff] [blame] | 674 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 675 | // Rewrite the original preheader to select between versions of the loop. |
Chris Lattner | fed5d9d | 2006-02-15 00:07:43 +0000 | [diff] [blame] | 676 | BranchInst *OldBR = cast<BranchInst>(OrigPreheader->getTerminator()); |
| 677 | assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 678 | "Preheader splitting did not work correctly!"); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 679 | |
Chris Lattner | fed5d9d | 2006-02-15 00:07:43 +0000 | [diff] [blame] | 680 | // Emit the new branch that selects between the two versions of this loop. |
| 681 | EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR); |
| 682 | OldBR->eraseFromParent(); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 683 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 684 | LoopProcessWorklist.push_back(NewLoop); |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 685 | LPM->redoLoop(L); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 686 | |
| 687 | // Now we rewrite the original code to know that the condition is true and the |
| 688 | // new code to know that the condition is false. |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 689 | RewriteLoopBodyWithConditionConstant(L , LIC, Val, false); |
| 690 | |
| 691 | // It's possible that simplifying one loop could cause the other to be |
| 692 | // deleted. If so, don't simplify it. |
| 693 | if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop) |
| 694 | RewriteLoopBodyWithConditionConstant(NewLoop, LIC, Val, true); |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 695 | } |
| 696 | |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 697 | /// RemoveFromWorklist - Remove all instances of I from the worklist vector |
| 698 | /// specified. |
| 699 | static void RemoveFromWorklist(Instruction *I, |
| 700 | std::vector<Instruction*> &Worklist) { |
| 701 | std::vector<Instruction*>::iterator WI = std::find(Worklist.begin(), |
| 702 | Worklist.end(), I); |
| 703 | while (WI != Worklist.end()) { |
| 704 | unsigned Offset = WI-Worklist.begin(); |
| 705 | Worklist.erase(WI); |
| 706 | WI = std::find(Worklist.begin()+Offset, Worklist.end(), I); |
| 707 | } |
| 708 | } |
| 709 | |
| 710 | /// ReplaceUsesOfWith - When we find that I really equals V, remove I from the |
| 711 | /// program, replacing all uses with V and update the worklist. |
| 712 | static void ReplaceUsesOfWith(Instruction *I, Value *V, |
| 713 | std::vector<Instruction*> &Worklist) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 714 | DOUT << "Replace with '" << *V << "': " << *I; |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 715 | |
| 716 | // Add uses to the worklist, which may be dead now. |
| 717 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 718 | if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) |
| 719 | Worklist.push_back(Use); |
| 720 | |
| 721 | // Add users to the worklist which may be simplified now. |
| 722 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); |
| 723 | UI != E; ++UI) |
| 724 | Worklist.push_back(cast<Instruction>(*UI)); |
| 725 | I->replaceAllUsesWith(V); |
| 726 | I->eraseFromParent(); |
| 727 | RemoveFromWorklist(I, Worklist); |
| 728 | ++NumSimplify; |
| 729 | } |
| 730 | |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 731 | /// RemoveBlockIfDead - If the specified block is dead, remove it, update loop |
| 732 | /// information, and remove any dead successors it has. |
| 733 | /// |
| 734 | void LoopUnswitch::RemoveBlockIfDead(BasicBlock *BB, |
| 735 | std::vector<Instruction*> &Worklist) { |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 736 | if (pred_begin(BB) != pred_end(BB)) { |
| 737 | // This block isn't dead, since an edge to BB was just removed, see if there |
| 738 | // are any easy simplifications we can do now. |
| 739 | if (BasicBlock *Pred = BB->getSinglePredecessor()) { |
| 740 | // If it has one pred, fold phi nodes in BB. |
| 741 | while (isa<PHINode>(BB->begin())) |
| 742 | ReplaceUsesOfWith(BB->begin(), |
| 743 | cast<PHINode>(BB->begin())->getIncomingValue(0), |
| 744 | Worklist); |
| 745 | |
| 746 | // If this is the header of a loop and the only pred is the latch, we now |
| 747 | // have an unreachable loop. |
| 748 | if (Loop *L = LI->getLoopFor(BB)) |
| 749 | if (L->getHeader() == BB && L->contains(Pred)) { |
| 750 | // Remove the branch from the latch to the header block, this makes |
| 751 | // the header dead, which will make the latch dead (because the header |
| 752 | // dominates the latch). |
| 753 | Pred->getTerminator()->eraseFromParent(); |
| 754 | new UnreachableInst(Pred); |
| 755 | |
| 756 | // The loop is now broken, remove it from LI. |
| 757 | RemoveLoopFromHierarchy(L); |
| 758 | |
| 759 | // Reprocess the header, which now IS dead. |
| 760 | RemoveBlockIfDead(BB, Worklist); |
| 761 | return; |
| 762 | } |
| 763 | |
| 764 | // If pred ends in a uncond branch, add uncond branch to worklist so that |
| 765 | // the two blocks will get merged. |
| 766 | if (BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator())) |
| 767 | if (BI->isUnconditional()) |
| 768 | Worklist.push_back(BI); |
| 769 | } |
| 770 | return; |
| 771 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 772 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 773 | DOUT << "Nuking dead block: " << *BB; |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 774 | |
| 775 | // Remove the instructions in the basic block from the worklist. |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 776 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 777 | RemoveFromWorklist(I, Worklist); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 778 | |
| 779 | // Anything that uses the instructions in this basic block should have their |
| 780 | // uses replaced with undefs. |
| 781 | if (!I->use_empty()) |
| 782 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 783 | } |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 784 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 785 | // If this is the edge to the header block for a loop, remove the loop and |
| 786 | // promote all subloops. |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 787 | if (Loop *BBLoop = LI->getLoopFor(BB)) { |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 788 | if (BBLoop->getLoopLatch() == BB) |
| 789 | RemoveLoopFromHierarchy(BBLoop); |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 790 | } |
| 791 | |
| 792 | // Remove the block from the loop info, which removes it from any loops it |
| 793 | // was in. |
| 794 | LI->removeBlock(BB); |
| 795 | |
| 796 | |
| 797 | // Remove phi node entries in successors for this block. |
| 798 | TerminatorInst *TI = BB->getTerminator(); |
| 799 | std::vector<BasicBlock*> Succs; |
| 800 | for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { |
| 801 | Succs.push_back(TI->getSuccessor(i)); |
| 802 | TI->getSuccessor(i)->removePredecessor(BB); |
Chris Lattner | f4412d8 | 2006-02-18 01:27:45 +0000 | [diff] [blame] | 803 | } |
| 804 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 805 | // Unique the successors, remove anything with multiple uses. |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 806 | std::sort(Succs.begin(), Succs.end()); |
| 807 | Succs.erase(std::unique(Succs.begin(), Succs.end()), Succs.end()); |
| 808 | |
| 809 | // Remove the basic block, including all of the instructions contained in it. |
| 810 | BB->eraseFromParent(); |
| 811 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 812 | // Remove successor blocks here that are not dead, so that we know we only |
| 813 | // have dead blocks in this list. Nondead blocks have a way of becoming dead, |
| 814 | // then getting removed before we revisit them, which is badness. |
| 815 | // |
| 816 | for (unsigned i = 0; i != Succs.size(); ++i) |
| 817 | if (pred_begin(Succs[i]) != pred_end(Succs[i])) { |
| 818 | // One exception is loop headers. If this block was the preheader for a |
| 819 | // loop, then we DO want to visit the loop so the loop gets deleted. |
| 820 | // We know that if the successor is a loop header, that this loop had to |
| 821 | // be the preheader: the case where this was the latch block was handled |
| 822 | // above and headers can only have two predecessors. |
| 823 | if (!LI->isLoopHeader(Succs[i])) { |
| 824 | Succs.erase(Succs.begin()+i); |
| 825 | --i; |
| 826 | } |
| 827 | } |
| 828 | |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 829 | for (unsigned i = 0, e = Succs.size(); i != e; ++i) |
| 830 | RemoveBlockIfDead(Succs[i], Worklist); |
Chris Lattner | f4412d8 | 2006-02-18 01:27:45 +0000 | [diff] [blame] | 831 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 832 | |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 833 | /// RemoveLoopFromHierarchy - We have discovered that the specified loop has |
| 834 | /// become unwrapped, either because the backedge was deleted, or because the |
| 835 | /// edge into the header was removed. If the edge into the header from the |
| 836 | /// latch block was removed, the loop is unwrapped but subloops are still alive, |
| 837 | /// so they just reparent loops. If the loops are actually dead, they will be |
| 838 | /// removed later. |
| 839 | void LoopUnswitch::RemoveLoopFromHierarchy(Loop *L) { |
Devang Patel | 1bc8936 | 2007-03-07 00:26:10 +0000 | [diff] [blame] | 840 | LPM->deleteLoopFromQueue(L); |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 841 | RemoveLoopFromWorklist(L); |
| 842 | } |
| 843 | |
| 844 | |
| 845 | |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 846 | // RewriteLoopBodyWithConditionConstant - We know either that the value LIC has |
| 847 | // the value specified by Val in the specified loop, or we know it does NOT have |
| 848 | // that value. Rewrite any uses of LIC or of properties correlated to it. |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 849 | void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 850 | Constant *Val, |
| 851 | bool IsEqual) { |
Chris Lattner | 4c41d49 | 2006-02-10 01:24:09 +0000 | [diff] [blame] | 852 | assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?"); |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 853 | |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 854 | // FIXME: Support correlated properties, like: |
| 855 | // for (...) |
| 856 | // if (li1 < li2) |
| 857 | // ... |
| 858 | // if (li1 > li2) |
| 859 | // ... |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 860 | |
Chris Lattner | 708e1a5 | 2006-02-10 02:30:37 +0000 | [diff] [blame] | 861 | // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, |
| 862 | // selects, switches. |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 863 | std::vector<User*> Users(LIC->use_begin(), LIC->use_end()); |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 864 | std::vector<Instruction*> Worklist; |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 865 | |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 866 | // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC |
| 867 | // in the loop with the appropriate one directly. |
Reid Spencer | 4fe16d6 | 2007-01-11 18:21:29 +0000 | [diff] [blame] | 868 | if (IsEqual || (isa<ConstantInt>(Val) && Val->getType() == Type::Int1Ty)) { |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 869 | Value *Replacement; |
| 870 | if (IsEqual) |
| 871 | Replacement = Val; |
| 872 | else |
Reid Spencer | 579dca1 | 2007-01-12 04:24:46 +0000 | [diff] [blame] | 873 | Replacement = ConstantInt::get(Type::Int1Ty, |
| 874 | !cast<ConstantInt>(Val)->getZExtValue()); |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 875 | |
| 876 | for (unsigned i = 0, e = Users.size(); i != e; ++i) |
| 877 | if (Instruction *U = cast<Instruction>(Users[i])) { |
| 878 | if (!L->contains(U->getParent())) |
| 879 | continue; |
| 880 | U->replaceUsesOfWith(LIC, Replacement); |
| 881 | Worklist.push_back(U); |
| 882 | } |
| 883 | } else { |
| 884 | // Otherwise, we don't know the precise value of LIC, but we do know that it |
| 885 | // is certainly NOT "Val". As such, simplify any uses in the loop that we |
| 886 | // can. This case occurs when we unswitch switch statements. |
| 887 | for (unsigned i = 0, e = Users.size(); i != e; ++i) |
| 888 | if (Instruction *U = cast<Instruction>(Users[i])) { |
| 889 | if (!L->contains(U->getParent())) |
| 890 | continue; |
| 891 | |
| 892 | Worklist.push_back(U); |
| 893 | |
Chris Lattner | 10cd9bb | 2006-02-16 19:36:22 +0000 | [diff] [blame] | 894 | // If we know that LIC is not Val, use this info to simplify code. |
| 895 | if (SwitchInst *SI = dyn_cast<SwitchInst>(U)) { |
| 896 | for (unsigned i = 1, e = SI->getNumCases(); i != e; ++i) { |
| 897 | if (SI->getCaseValue(i) == Val) { |
| 898 | // Found a dead case value. Don't remove PHI nodes in the |
| 899 | // successor if they become single-entry, those PHI nodes may |
| 900 | // be in the Users list. |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 901 | |
| 902 | // FIXME: This is a hack. We need to keep the successor around |
| 903 | // and hooked up so as to preserve the loop structure, because |
| 904 | // trying to update it is complicated. So instead we preserve the |
| 905 | // loop structure and put the block on an dead code path. |
| 906 | |
| 907 | BasicBlock* Old = SI->getParent(); |
| 908 | BasicBlock* Split = SplitBlock(Old, SI); |
| 909 | |
| 910 | Instruction* OldTerm = Old->getTerminator(); |
Reid Spencer | 3ed469c | 2006-11-02 20:25:50 +0000 | [diff] [blame] | 911 | new BranchInst(Split, SI->getSuccessor(i), |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 912 | ConstantInt::getTrue(), OldTerm); |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 913 | |
| 914 | Old->getTerminator()->eraseFromParent(); |
| 915 | |
Owen Anderson | bef8508 | 2006-06-27 22:26:09 +0000 | [diff] [blame] | 916 | |
| 917 | PHINode *PN; |
| 918 | for (BasicBlock::iterator II = SI->getSuccessor(i)->begin(); |
| 919 | (PN = dyn_cast<PHINode>(II)); ++II) { |
| 920 | Value *InVal = PN->removeIncomingValue(Split, false); |
| 921 | PN->addIncoming(InVal, Old); |
Owen Anderson | 2b67f07 | 2006-06-26 07:44:36 +0000 | [diff] [blame] | 922 | } |
| 923 | |
Chris Lattner | 10cd9bb | 2006-02-16 19:36:22 +0000 | [diff] [blame] | 924 | SI->removeCase(i); |
| 925 | break; |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 926 | } |
| 927 | } |
Chris Lattner | c235809 | 2006-02-11 00:43:37 +0000 | [diff] [blame] | 928 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 929 | |
| 930 | // TODO: We could do other simplifications, for example, turning |
| 931 | // LIC == Val -> false. |
Chris Lattner | 10cd9bb | 2006-02-16 19:36:22 +0000 | [diff] [blame] | 932 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 933 | } |
Chris Lattner | a6fc94b | 2006-02-18 07:57:38 +0000 | [diff] [blame] | 934 | |
| 935 | SimplifyCode(Worklist); |
| 936 | } |
| 937 | |
| 938 | /// SimplifyCode - Okay, now that we have simplified some instructions in the |
| 939 | /// loop, walk over it and constant prop, dce, and fold control flow where |
| 940 | /// possible. Note that this is effectively a very simple loop-structure-aware |
| 941 | /// optimizer. During processing of this loop, L could very well be deleted, so |
| 942 | /// it must not be used. |
| 943 | /// |
| 944 | /// FIXME: When the loop optimizer is more mature, separate this out to a new |
| 945 | /// pass. |
| 946 | /// |
| 947 | void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist) { |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 948 | while (!Worklist.empty()) { |
| 949 | Instruction *I = Worklist.back(); |
| 950 | Worklist.pop_back(); |
| 951 | |
| 952 | // Simple constant folding. |
| 953 | if (Constant *C = ConstantFoldInstruction(I)) { |
| 954 | ReplaceUsesOfWith(I, C, Worklist); |
| 955 | continue; |
Chris Lattner | 10cd9bb | 2006-02-16 19:36:22 +0000 | [diff] [blame] | 956 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 957 | |
| 958 | // Simple DCE. |
| 959 | if (isInstructionTriviallyDead(I)) { |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 960 | DOUT << "Remove dead instruction '" << *I; |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 961 | |
| 962 | // Add uses to the worklist, which may be dead now. |
| 963 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) |
| 964 | if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) |
| 965 | Worklist.push_back(Use); |
| 966 | I->eraseFromParent(); |
| 967 | RemoveFromWorklist(I, Worklist); |
| 968 | ++NumSimplify; |
| 969 | continue; |
| 970 | } |
| 971 | |
| 972 | // Special case hacks that appear commonly in unswitched code. |
| 973 | switch (I->getOpcode()) { |
| 974 | case Instruction::Select: |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 975 | if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(0))) { |
Reid Spencer | 579dca1 | 2007-01-12 04:24:46 +0000 | [diff] [blame] | 976 | ReplaceUsesOfWith(I, I->getOperand(!CB->getZExtValue()+1), Worklist); |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 977 | continue; |
| 978 | } |
| 979 | break; |
| 980 | case Instruction::And: |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 981 | if (isa<ConstantInt>(I->getOperand(0)) && |
Reid Spencer | 4fe16d6 | 2007-01-11 18:21:29 +0000 | [diff] [blame] | 982 | I->getOperand(0)->getType() == Type::Int1Ty) // constant -> RHS |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 983 | cast<BinaryOperator>(I)->swapOperands(); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 984 | if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1))) |
Reid Spencer | 4fe16d6 | 2007-01-11 18:21:29 +0000 | [diff] [blame] | 985 | if (CB->getType() == Type::Int1Ty) { |
Reid Spencer | a5dae0c | 2007-03-02 23:35:28 +0000 | [diff] [blame] | 986 | if (CB->isOne()) // X & 1 -> X |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 987 | ReplaceUsesOfWith(I, I->getOperand(0), Worklist); |
| 988 | else // X & 0 -> 0 |
| 989 | ReplaceUsesOfWith(I, I->getOperand(1), Worklist); |
| 990 | continue; |
| 991 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 992 | break; |
| 993 | case Instruction::Or: |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 994 | if (isa<ConstantInt>(I->getOperand(0)) && |
Reid Spencer | 4fe16d6 | 2007-01-11 18:21:29 +0000 | [diff] [blame] | 995 | I->getOperand(0)->getType() == Type::Int1Ty) // constant -> RHS |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 996 | cast<BinaryOperator>(I)->swapOperands(); |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 997 | if (ConstantInt *CB = dyn_cast<ConstantInt>(I->getOperand(1))) |
Reid Spencer | 4fe16d6 | 2007-01-11 18:21:29 +0000 | [diff] [blame] | 998 | if (CB->getType() == Type::Int1Ty) { |
Reid Spencer | a5dae0c | 2007-03-02 23:35:28 +0000 | [diff] [blame] | 999 | if (CB->isOne()) // X | 1 -> 1 |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 1000 | ReplaceUsesOfWith(I, I->getOperand(1), Worklist); |
| 1001 | else // X | 0 -> X |
| 1002 | ReplaceUsesOfWith(I, I->getOperand(0), Worklist); |
| 1003 | continue; |
| 1004 | } |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 1005 | break; |
| 1006 | case Instruction::Br: { |
| 1007 | BranchInst *BI = cast<BranchInst>(I); |
| 1008 | if (BI->isUnconditional()) { |
| 1009 | // If BI's parent is the only pred of the successor, fold the two blocks |
| 1010 | // together. |
| 1011 | BasicBlock *Pred = BI->getParent(); |
| 1012 | BasicBlock *Succ = BI->getSuccessor(0); |
| 1013 | BasicBlock *SinglePred = Succ->getSinglePredecessor(); |
| 1014 | if (!SinglePred) continue; // Nothing to do. |
| 1015 | assert(SinglePred == Pred && "CFG broken"); |
| 1016 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 1017 | DOUT << "Merging blocks: " << Pred->getName() << " <- " |
| 1018 | << Succ->getName() << "\n"; |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 1019 | |
| 1020 | // Resolve any single entry PHI nodes in Succ. |
| 1021 | while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) |
| 1022 | ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist); |
| 1023 | |
| 1024 | // Move all of the successor contents from Succ to Pred. |
| 1025 | Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(), |
| 1026 | Succ->end()); |
| 1027 | BI->eraseFromParent(); |
| 1028 | RemoveFromWorklist(BI, Worklist); |
| 1029 | |
| 1030 | // If Succ has any successors with PHI nodes, update them to have |
| 1031 | // entries coming from Pred instead of Succ. |
| 1032 | Succ->replaceAllUsesWith(Pred); |
| 1033 | |
| 1034 | // Remove Succ from the loop tree. |
| 1035 | LI->removeBlock(Succ); |
| 1036 | Succ->eraseFromParent(); |
Chris Lattner | f4412d8 | 2006-02-18 01:27:45 +0000 | [diff] [blame] | 1037 | ++NumSimplify; |
Zhou Sheng | 6b6b6ef | 2007-01-11 12:24:14 +0000 | [diff] [blame] | 1038 | } else if (ConstantInt *CB = dyn_cast<ConstantInt>(BI->getCondition())){ |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 1039 | // Conditional branch. Turn it into an unconditional branch, then |
| 1040 | // remove dead blocks. |
Chris Lattner | bd28e3f | 2006-02-22 06:37:14 +0000 | [diff] [blame] | 1041 | break; // FIXME: Enable. |
| 1042 | |
Bill Wendling | b742703 | 2006-11-26 09:46:52 +0000 | [diff] [blame] | 1043 | DOUT << "Folded branch: " << *BI; |
Reid Spencer | 579dca1 | 2007-01-12 04:24:46 +0000 | [diff] [blame] | 1044 | BasicBlock *DeadSucc = BI->getSuccessor(CB->getZExtValue()); |
| 1045 | BasicBlock *LiveSucc = BI->getSuccessor(!CB->getZExtValue()); |
Chris Lattner | db41024 | 2006-02-18 02:42:34 +0000 | [diff] [blame] | 1046 | DeadSucc->removePredecessor(BI->getParent(), true); |
| 1047 | Worklist.push_back(new BranchInst(LiveSucc, BI)); |
| 1048 | BI->eraseFromParent(); |
| 1049 | RemoveFromWorklist(BI, Worklist); |
| 1050 | ++NumSimplify; |
| 1051 | |
| 1052 | RemoveBlockIfDead(DeadSucc, Worklist); |
Chris Lattner | 52221f7 | 2006-02-17 00:31:07 +0000 | [diff] [blame] | 1053 | } |
| 1054 | break; |
| 1055 | } |
| 1056 | } |
| 1057 | } |
Chris Lattner | 18f1609 | 2004-04-19 18:07:02 +0000 | [diff] [blame] | 1058 | } |