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