Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 1 | //===- LoopIndexSplit.cpp - Loop Index Splitting Pass ---------------------===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by Devang Patel and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements Loop Index Splitting Pass. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #define DEBUG_TYPE "loop-index-split" |
| 15 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 16 | #include "llvm/Transforms/Scalar.h" |
| 17 | #include "llvm/Analysis/LoopPass.h" |
| 18 | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
Devang Patel | 787a713 | 2007-08-08 21:39:47 +0000 | [diff] [blame] | 19 | #include "llvm/Analysis/Dominators.h" |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 20 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| 21 | #include "llvm/Transforms/Utils/Cloning.h" |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 22 | #include "llvm/Support/Compiler.h" |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 23 | #include "llvm/ADT/DepthFirstIterator.h" |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 24 | #include "llvm/ADT/Statistic.h" |
| 25 | |
| 26 | using namespace llvm; |
| 27 | |
| 28 | STATISTIC(NumIndexSplit, "Number of loops index split"); |
| 29 | |
| 30 | namespace { |
| 31 | |
| 32 | class VISIBILITY_HIDDEN LoopIndexSplit : public LoopPass { |
| 33 | |
| 34 | public: |
| 35 | static char ID; // Pass ID, replacement for typeid |
| 36 | LoopIndexSplit() : LoopPass((intptr_t)&ID) {} |
| 37 | |
| 38 | // Index split Loop L. Return true if loop is split. |
| 39 | bool runOnLoop(Loop *L, LPPassManager &LPM); |
| 40 | |
| 41 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 42 | AU.addRequired<ScalarEvolution>(); |
| 43 | AU.addPreserved<ScalarEvolution>(); |
| 44 | AU.addRequiredID(LCSSAID); |
| 45 | AU.addPreservedID(LCSSAID); |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 46 | AU.addRequired<LoopInfo>(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 47 | AU.addPreserved<LoopInfo>(); |
| 48 | AU.addRequiredID(LoopSimplifyID); |
| 49 | AU.addPreservedID(LoopSimplifyID); |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 50 | AU.addRequired<DominatorTree>(); |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 51 | AU.addRequired<DominanceFrontier>(); |
Devang Patel | 787a713 | 2007-08-08 21:39:47 +0000 | [diff] [blame] | 52 | AU.addPreserved<DominatorTree>(); |
| 53 | AU.addPreserved<DominanceFrontier>(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 54 | } |
| 55 | |
| 56 | private: |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 57 | |
| 58 | class SplitInfo { |
| 59 | public: |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 60 | SplitInfo() : SplitValue(NULL), SplitCondition(NULL), |
| 61 | UseTrueBranchFirst(true) {} |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 62 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 63 | // Induction variable's range is split at this value. |
| 64 | Value *SplitValue; |
| 65 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 66 | // This compare instruction compares IndVar against SplitValue. |
| 67 | ICmpInst *SplitCondition; |
| 68 | |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 69 | // True if after loop index split, first loop will execute split condition's |
| 70 | // true branch. |
| 71 | bool UseTrueBranchFirst; |
Devang Patel | 9021c70 | 2007-08-08 21:18:27 +0000 | [diff] [blame] | 72 | // Clear split info. |
| 73 | void clear() { |
Devang Patel | 9021c70 | 2007-08-08 21:18:27 +0000 | [diff] [blame] | 74 | SplitValue = NULL; |
Devang Patel | 9021c70 | 2007-08-08 21:18:27 +0000 | [diff] [blame] | 75 | SplitCondition = NULL; |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 76 | UseTrueBranchFirst = true; |
Devang Patel | 9021c70 | 2007-08-08 21:18:27 +0000 | [diff] [blame] | 77 | } |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 78 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 79 | }; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 80 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 81 | private: |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 82 | /// Find condition inside a loop that is suitable candidate for index split. |
| 83 | void findSplitCondition(); |
| 84 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 85 | /// Find loop's exit condition. |
| 86 | void findLoopConditionals(); |
| 87 | |
| 88 | /// Return induction variable associated with value V. |
| 89 | void findIndVar(Value *V, Loop *L); |
| 90 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 91 | /// processOneIterationLoop - Current loop L contains compare instruction |
| 92 | /// that compares induction variable, IndVar, agains loop invariant. If |
| 93 | /// entire (i.e. meaningful) loop body is dominated by this compare |
| 94 | /// instruction then loop body is executed only for one iteration. In |
| 95 | /// such case eliminate loop structure surrounding this loop body. For |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 96 | bool processOneIterationLoop(SplitInfo &SD); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 97 | |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 98 | /// If loop header includes loop variant instruction operands then |
| 99 | /// this loop may not be eliminated. |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 100 | bool safeHeader(SplitInfo &SD, BasicBlock *BB); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 101 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 102 | /// If Exiting block includes loop variant instructions then this |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 103 | /// loop may not be eliminated. |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 104 | bool safeExitingBlock(SplitInfo &SD, BasicBlock *BB); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 105 | |
Devang Patel | a6a8663 | 2007-08-14 18:35:57 +0000 | [diff] [blame] | 106 | /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB. |
| 107 | /// This routine is used to remove split condition's dead branch, dominated by |
| 108 | /// DeadBB. LiveBB dominates split conidition's other branch. |
| 109 | void removeBlocks(BasicBlock *DeadBB, Loop *LP, BasicBlock *LiveBB); |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 110 | |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 111 | /// safeSplitCondition - Return true if it is possible to |
| 112 | /// split loop using given split condition. |
| 113 | bool safeSplitCondition(SplitInfo &SD); |
| 114 | |
| 115 | /// splitLoop - Split current loop L in two loops using split information |
| 116 | /// SD. Update dominator information. Maintain LCSSA form. |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 117 | bool splitLoop(SplitInfo &SD); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 118 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 119 | void initialize() { |
| 120 | IndVar = NULL; |
| 121 | IndVarIncrement = NULL; |
| 122 | ExitCondition = NULL; |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 123 | StartValue = NULL; |
| 124 | ExitValueNum = 0; |
| 125 | SplitData.clear(); |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 126 | } |
| 127 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 128 | private: |
| 129 | |
| 130 | // Current Loop. |
| 131 | Loop *L; |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 132 | LPPassManager *LPM; |
| 133 | LoopInfo *LI; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 134 | ScalarEvolution *SE; |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 135 | DominatorTree *DT; |
Devang Patel | fc4c5f8 | 2007-08-13 22:13:24 +0000 | [diff] [blame] | 136 | DominanceFrontier *DF; |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 137 | SmallVector<SplitInfo, 4> SplitData; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 138 | |
| 139 | // Induction variable whose range is being split by this transformation. |
| 140 | PHINode *IndVar; |
| 141 | Instruction *IndVarIncrement; |
| 142 | |
| 143 | // Loop exit condition. |
| 144 | ICmpInst *ExitCondition; |
| 145 | |
| 146 | // Induction variable's initial value. |
| 147 | Value *StartValue; |
| 148 | |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 149 | // Induction variable's final loop exit value operand number in exit condition.. |
| 150 | unsigned ExitValueNum; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 151 | }; |
| 152 | |
| 153 | char LoopIndexSplit::ID = 0; |
| 154 | RegisterPass<LoopIndexSplit> X ("loop-index-split", "Index Split Loops"); |
| 155 | } |
| 156 | |
| 157 | LoopPass *llvm::createLoopIndexSplitPass() { |
| 158 | return new LoopIndexSplit(); |
| 159 | } |
| 160 | |
| 161 | // Index split Loop L. Return true if loop is split. |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 162 | bool LoopIndexSplit::runOnLoop(Loop *IncomingLoop, LPPassManager &LPM_Ref) { |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 163 | bool Changed = false; |
| 164 | L = IncomingLoop; |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 165 | LPM = &LPM_Ref; |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 166 | |
Devang Patel | 3fe4f21 | 2007-08-15 02:14:55 +0000 | [diff] [blame] | 167 | // FIXME - Nested loops make dominator info updates tricky. |
Devang Patel | 4e8061c | 2007-08-14 23:53:57 +0000 | [diff] [blame] | 168 | if (!L->getSubLoops().empty()) |
| 169 | return false; |
| 170 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 171 | SE = &getAnalysis<ScalarEvolution>(); |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 172 | DT = &getAnalysis<DominatorTree>(); |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 173 | LI = &getAnalysis<LoopInfo>(); |
Devang Patel | 7375bb9 | 2007-08-15 03:34:53 +0000 | [diff] [blame] | 174 | DF = &getAnalysis<DominanceFrontier>(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 175 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 176 | initialize(); |
| 177 | |
| 178 | findLoopConditionals(); |
| 179 | |
| 180 | if (!ExitCondition) |
| 181 | return false; |
| 182 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 183 | findSplitCondition(); |
| 184 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 185 | if (SplitData.empty()) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 186 | return false; |
| 187 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 188 | // First see if it is possible to eliminate loop itself or not. |
| 189 | for (SmallVector<SplitInfo, 4>::iterator SI = SplitData.begin(), |
Devang Patel | d651f65 | 2007-08-20 20:24:15 +0000 | [diff] [blame] | 190 | E = SplitData.end(); SI != E;) { |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 191 | SplitInfo &SD = *SI; |
| 192 | if (SD.SplitCondition->getPredicate() == ICmpInst::ICMP_EQ) { |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 193 | Changed = processOneIterationLoop(SD); |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 194 | if (Changed) { |
| 195 | ++NumIndexSplit; |
| 196 | // If is loop is eliminated then nothing else to do here. |
| 197 | return Changed; |
Devang Patel | d651f65 | 2007-08-20 20:24:15 +0000 | [diff] [blame] | 198 | } else { |
| 199 | SmallVector<SplitInfo, 4>::iterator Delete_SI = SI; |
| 200 | ++SI; |
| 201 | SplitData.erase(Delete_SI); |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 202 | } |
Devang Patel | d651f65 | 2007-08-20 20:24:15 +0000 | [diff] [blame] | 203 | } else |
| 204 | ++SI; |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 205 | } |
| 206 | |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 207 | if (SplitData.empty()) |
| 208 | return false; |
| 209 | |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 210 | // Split most profitiable condition. |
Devang Patel | 7237d11 | 2007-08-24 05:21:13 +0000 | [diff] [blame] | 211 | // FIXME : Implement cost analysis. |
| 212 | unsigned MostProfitableSDIndex = 0; |
| 213 | Changed = splitLoop(SplitData[MostProfitableSDIndex]); |
Devang Patel | 9704fcf | 2007-08-08 22:25:28 +0000 | [diff] [blame] | 214 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 215 | if (Changed) |
| 216 | ++NumIndexSplit; |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 217 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 218 | return Changed; |
| 219 | } |
| 220 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 221 | /// Return true if V is a induction variable or induction variable's |
| 222 | /// increment for loop L. |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 223 | void LoopIndexSplit::findIndVar(Value *V, Loop *L) { |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 224 | |
| 225 | Instruction *I = dyn_cast<Instruction>(V); |
| 226 | if (!I) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 227 | return; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 228 | |
| 229 | // Check if I is a phi node from loop header or not. |
| 230 | if (PHINode *PN = dyn_cast<PHINode>(V)) { |
| 231 | if (PN->getParent() == L->getHeader()) { |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 232 | IndVar = PN; |
| 233 | return; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 234 | } |
| 235 | } |
| 236 | |
| 237 | // Check if I is a add instruction whose one operand is |
| 238 | // phi node from loop header and second operand is constant. |
| 239 | if (I->getOpcode() != Instruction::Add) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 240 | return; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 241 | |
| 242 | Value *Op0 = I->getOperand(0); |
| 243 | Value *Op1 = I->getOperand(1); |
| 244 | |
| 245 | if (PHINode *PN = dyn_cast<PHINode>(Op0)) { |
| 246 | if (PN->getParent() == L->getHeader() |
| 247 | && isa<ConstantInt>(Op1)) { |
| 248 | IndVar = PN; |
| 249 | IndVarIncrement = I; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 250 | return; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 251 | } |
| 252 | } |
| 253 | |
| 254 | if (PHINode *PN = dyn_cast<PHINode>(Op1)) { |
| 255 | if (PN->getParent() == L->getHeader() |
| 256 | && isa<ConstantInt>(Op0)) { |
| 257 | IndVar = PN; |
| 258 | IndVarIncrement = I; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 259 | return; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 260 | } |
| 261 | } |
| 262 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 263 | return; |
| 264 | } |
| 265 | |
| 266 | // Find loop's exit condition and associated induction variable. |
| 267 | void LoopIndexSplit::findLoopConditionals() { |
| 268 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 269 | BasicBlock *ExitingBlock = NULL; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 270 | |
| 271 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 272 | I != E; ++I) { |
| 273 | BasicBlock *BB = *I; |
| 274 | if (!L->isLoopExit(BB)) |
| 275 | continue; |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 276 | if (ExitingBlock) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 277 | return; |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 278 | ExitingBlock = BB; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 279 | } |
| 280 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 281 | if (!ExitingBlock) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 282 | return; |
Devang Patel | b88e420 | 2007-08-24 05:36:56 +0000 | [diff] [blame] | 283 | |
| 284 | // If exiting block is neither loop header nor loop latch then this loop is |
| 285 | // not suitable. |
| 286 | if (ExitingBlock != L->getHeader() && ExitingBlock != L->getLoopLatch()) |
| 287 | return; |
| 288 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 289 | // If exit block's terminator is conditional branch inst then we have found |
| 290 | // exit condition. |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 291 | BranchInst *BR = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 292 | if (!BR || BR->isUnconditional()) |
| 293 | return; |
| 294 | |
| 295 | ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition()); |
| 296 | if (!CI) |
| 297 | return; |
| 298 | |
| 299 | ExitCondition = CI; |
| 300 | |
| 301 | // Exit condition's one operand is loop invariant exit value and second |
| 302 | // operand is SCEVAddRecExpr based on induction variable. |
| 303 | Value *V0 = CI->getOperand(0); |
| 304 | Value *V1 = CI->getOperand(1); |
| 305 | |
| 306 | SCEVHandle SH0 = SE->getSCEV(V0); |
| 307 | SCEVHandle SH1 = SE->getSCEV(V1); |
| 308 | |
| 309 | if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) { |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 310 | ExitValueNum = 0; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 311 | findIndVar(V1, L); |
| 312 | } |
| 313 | else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) { |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 314 | ExitValueNum = 1; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 315 | findIndVar(V0, L); |
| 316 | } |
| 317 | |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 318 | if (!IndVar) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 319 | ExitCondition = NULL; |
| 320 | else if (IndVar) { |
| 321 | BasicBlock *Preheader = L->getLoopPreheader(); |
| 322 | StartValue = IndVar->getIncomingValueForBlock(Preheader); |
| 323 | } |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 324 | } |
| 325 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 326 | /// Find condition inside a loop that is suitable candidate for index split. |
| 327 | void LoopIndexSplit::findSplitCondition() { |
| 328 | |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 329 | SplitInfo SD; |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 330 | // Check all basic block's terminators. |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 331 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 332 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); |
| 333 | I != E; ++I) { |
| 334 | BasicBlock *BB = *I; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 335 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 336 | // If this basic block does not terminate in a conditional branch |
| 337 | // then terminator is not a suitable split condition. |
| 338 | BranchInst *BR = dyn_cast<BranchInst>(BB->getTerminator()); |
| 339 | if (!BR) |
| 340 | continue; |
| 341 | |
| 342 | if (BR->isUnconditional()) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 343 | continue; |
| 344 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 345 | ICmpInst *CI = dyn_cast<ICmpInst>(BR->getCondition()); |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 346 | if (!CI || CI == ExitCondition) |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 347 | return; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 348 | |
Devang Patel | c830aee | 2007-08-24 06:02:25 +0000 | [diff] [blame] | 349 | if (CI->getPredicate() == ICmpInst::ICMP_NE) |
| 350 | return; |
| 351 | |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 352 | // If split condition predicate is GT or GE then first execute |
| 353 | // false branch of split condition. |
| 354 | if (CI->getPredicate() != ICmpInst::ICMP_ULT |
| 355 | && CI->getPredicate() != ICmpInst::ICMP_SLT |
| 356 | && CI->getPredicate() != ICmpInst::ICMP_ULE |
| 357 | && CI->getPredicate() != ICmpInst::ICMP_SLE) |
| 358 | SD.UseTrueBranchFirst = false; |
| 359 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 360 | // If one operand is loop invariant and second operand is SCEVAddRecExpr |
| 361 | // based on induction variable then CI is a candidate split condition. |
| 362 | Value *V0 = CI->getOperand(0); |
| 363 | Value *V1 = CI->getOperand(1); |
| 364 | |
| 365 | SCEVHandle SH0 = SE->getSCEV(V0); |
| 366 | SCEVHandle SH1 = SE->getSCEV(V1); |
| 367 | |
| 368 | if (SH0->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH1)) { |
| 369 | SD.SplitValue = V0; |
| 370 | SD.SplitCondition = CI; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 371 | if (PHINode *PN = dyn_cast<PHINode>(V1)) { |
| 372 | if (PN == IndVar) |
| 373 | SplitData.push_back(SD); |
| 374 | } |
| 375 | else if (Instruction *Insn = dyn_cast<Instruction>(V1)) { |
| 376 | if (IndVarIncrement && IndVarIncrement == Insn) |
| 377 | SplitData.push_back(SD); |
| 378 | } |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 379 | } |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 380 | else if (SH1->isLoopInvariant(L) && isa<SCEVAddRecExpr>(SH0)) { |
| 381 | SD.SplitValue = V1; |
| 382 | SD.SplitCondition = CI; |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 383 | if (PHINode *PN = dyn_cast<PHINode>(V0)) { |
| 384 | if (PN == IndVar) |
| 385 | SplitData.push_back(SD); |
| 386 | } |
| 387 | else if (Instruction *Insn = dyn_cast<Instruction>(V0)) { |
| 388 | if (IndVarIncrement && IndVarIncrement == Insn) |
| 389 | SplitData.push_back(SD); |
| 390 | } |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 391 | } |
| 392 | } |
| 393 | } |
| 394 | |
| 395 | /// processOneIterationLoop - Current loop L contains compare instruction |
| 396 | /// that compares induction variable, IndVar, against loop invariant. If |
| 397 | /// entire (i.e. meaningful) loop body is dominated by this compare |
| 398 | /// instruction then loop body is executed only once. In such case eliminate |
| 399 | /// loop structure surrounding this loop body. For example, |
| 400 | /// for (int i = start; i < end; ++i) { |
| 401 | /// if ( i == somevalue) { |
| 402 | /// loop_body |
| 403 | /// } |
| 404 | /// } |
| 405 | /// can be transformed into |
| 406 | /// if (somevalue >= start && somevalue < end) { |
| 407 | /// i = somevalue; |
| 408 | /// loop_body |
| 409 | /// } |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 410 | bool LoopIndexSplit::processOneIterationLoop(SplitInfo &SD) { |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 411 | |
| 412 | BasicBlock *Header = L->getHeader(); |
| 413 | |
| 414 | // First of all, check if SplitCondition dominates entire loop body |
| 415 | // or not. |
| 416 | |
| 417 | // If SplitCondition is not in loop header then this loop is not suitable |
| 418 | // for this transformation. |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 419 | if (SD.SplitCondition->getParent() != Header) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 420 | return false; |
| 421 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 422 | // If loop header includes loop variant instruction operands then |
| 423 | // this loop may not be eliminated. |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 424 | if (!safeHeader(SD, Header)) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 425 | return false; |
| 426 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 427 | // If Exiting block includes loop variant instructions then this |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 428 | // loop may not be eliminated. |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 429 | if (!safeExitingBlock(SD, ExitCondition->getParent())) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 430 | return false; |
| 431 | |
Devang Patel | 6a2bfda | 2007-08-08 01:51:27 +0000 | [diff] [blame] | 432 | // Update CFG. |
| 433 | |
Devang Patel | ebc5fea | 2007-08-20 20:49:01 +0000 | [diff] [blame] | 434 | // Replace index variable with split value in loop body. Loop body is executed |
| 435 | // only when index variable is equal to split value. |
| 436 | IndVar->replaceAllUsesWith(SD.SplitValue); |
| 437 | |
| 438 | // Remove Latch to Header edge. |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 439 | BasicBlock *Latch = L->getLoopLatch(); |
Devang Patel | 6a2bfda | 2007-08-08 01:51:27 +0000 | [diff] [blame] | 440 | BasicBlock *LatchSucc = NULL; |
| 441 | BranchInst *BR = dyn_cast<BranchInst>(Latch->getTerminator()); |
| 442 | if (!BR) |
| 443 | return false; |
| 444 | Header->removePredecessor(Latch); |
| 445 | for (succ_iterator SI = succ_begin(Latch), E = succ_end(Latch); |
| 446 | SI != E; ++SI) { |
| 447 | if (Header != *SI) |
| 448 | LatchSucc = *SI; |
| 449 | } |
| 450 | BR->setUnconditionalDest(LatchSucc); |
| 451 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 452 | Instruction *Terminator = Header->getTerminator(); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 453 | Value *ExitValue = ExitCondition->getOperand(ExitValueNum); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 454 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 455 | // Replace split condition in header. |
| 456 | // Transform |
| 457 | // SplitCondition : icmp eq i32 IndVar, SplitValue |
| 458 | // into |
| 459 | // c1 = icmp uge i32 SplitValue, StartValue |
| 460 | // c2 = icmp ult i32 vSplitValue, ExitValue |
| 461 | // and i32 c1, c2 |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 462 | bool SignedPredicate = ExitCondition->isSignedPredicate(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 463 | Instruction *C1 = new ICmpInst(SignedPredicate ? |
| 464 | ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE, |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 465 | SD.SplitValue, StartValue, "lisplit", |
| 466 | Terminator); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 467 | Instruction *C2 = new ICmpInst(SignedPredicate ? |
| 468 | ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 469 | SD.SplitValue, ExitValue, "lisplit", |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 470 | Terminator); |
| 471 | Instruction *NSplitCond = BinaryOperator::createAnd(C1, C2, "lisplit", |
| 472 | Terminator); |
| 473 | SD.SplitCondition->replaceAllUsesWith(NSplitCond); |
| 474 | SD.SplitCondition->eraseFromParent(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 475 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 476 | // Now, clear latch block. Remove instructions that are responsible |
| 477 | // to increment induction variable. |
| 478 | Instruction *LTerminator = Latch->getTerminator(); |
| 479 | for (BasicBlock::iterator LB = Latch->begin(), LE = Latch->end(); |
| 480 | LB != LE; ) { |
| 481 | Instruction *I = LB; |
| 482 | ++LB; |
| 483 | if (isa<PHINode>(I) || I == LTerminator) |
| 484 | continue; |
| 485 | |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 486 | if (I == IndVarIncrement) |
| 487 | I->replaceAllUsesWith(ExitValue); |
| 488 | else |
| 489 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
Devang Patel | 8431a1c | 2007-08-07 17:45:35 +0000 | [diff] [blame] | 490 | I->eraseFromParent(); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 491 | } |
| 492 | |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 493 | LPM->deleteLoopFromQueue(L); |
Devang Patel | 787a713 | 2007-08-08 21:39:47 +0000 | [diff] [blame] | 494 | |
| 495 | // Update Dominator Info. |
| 496 | // Only CFG change done is to remove Latch to Header edge. This |
| 497 | // does not change dominator tree because Latch did not dominate |
| 498 | // Header. |
Devang Patel | fc4c5f8 | 2007-08-13 22:13:24 +0000 | [diff] [blame] | 499 | if (DF) { |
Devang Patel | 787a713 | 2007-08-08 21:39:47 +0000 | [diff] [blame] | 500 | DominanceFrontier::iterator HeaderDF = DF->find(Header); |
| 501 | if (HeaderDF != DF->end()) |
| 502 | DF->removeFromFrontier(HeaderDF, Header); |
| 503 | |
| 504 | DominanceFrontier::iterator LatchDF = DF->find(Latch); |
| 505 | if (LatchDF != DF->end()) |
| 506 | DF->removeFromFrontier(LatchDF, Header); |
| 507 | } |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 508 | return true; |
| 509 | } |
| 510 | |
| 511 | // If loop header includes loop variant instruction operands then |
| 512 | // this loop can not be eliminated. This is used by processOneIterationLoop(). |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 513 | bool LoopIndexSplit::safeHeader(SplitInfo &SD, BasicBlock *Header) { |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 514 | |
| 515 | Instruction *Terminator = Header->getTerminator(); |
| 516 | for(BasicBlock::iterator BI = Header->begin(), BE = Header->end(); |
| 517 | BI != BE; ++BI) { |
| 518 | Instruction *I = BI; |
| 519 | |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 520 | // PHI Nodes are OK. |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 521 | if (isa<PHINode>(I)) |
| 522 | continue; |
| 523 | |
| 524 | // SplitCondition itself is OK. |
Devang Patel | 71554b8 | 2007-08-08 21:02:17 +0000 | [diff] [blame] | 525 | if (I == SD.SplitCondition) |
Devang Patel | 6a2bfda | 2007-08-08 01:51:27 +0000 | [diff] [blame] | 526 | continue; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 527 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 528 | // Induction variable is OK. |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 529 | if (I == IndVar) |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 530 | continue; |
| 531 | |
| 532 | // Induction variable increment is OK. |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 533 | if (I == IndVarIncrement) |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 534 | continue; |
| 535 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 536 | // Terminator is also harmless. |
| 537 | if (I == Terminator) |
| 538 | continue; |
| 539 | |
| 540 | // Otherwise we have a instruction that may not be safe. |
| 541 | return false; |
| 542 | } |
| 543 | |
| 544 | return true; |
| 545 | } |
| 546 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 547 | // If Exiting block includes loop variant instructions then this |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 548 | // loop may not be eliminated. This is used by processOneIterationLoop(). |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 549 | bool LoopIndexSplit::safeExitingBlock(SplitInfo &SD, |
| 550 | BasicBlock *ExitingBlock) { |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 551 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 552 | for (BasicBlock::iterator BI = ExitingBlock->begin(), |
| 553 | BE = ExitingBlock->end(); BI != BE; ++BI) { |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 554 | Instruction *I = BI; |
| 555 | |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 556 | // PHI Nodes are OK. |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 557 | if (isa<PHINode>(I)) |
| 558 | continue; |
| 559 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 560 | // Induction variable increment is OK. |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 561 | if (IndVarIncrement && IndVarIncrement == I) |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 562 | continue; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 563 | |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 564 | // Check if I is induction variable increment instruction. |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 565 | if (!IndVarIncrement && I->getOpcode() == Instruction::Add) { |
Devang Patel | c9d123d | 2007-08-09 01:39:01 +0000 | [diff] [blame] | 566 | |
| 567 | Value *Op0 = I->getOperand(0); |
| 568 | Value *Op1 = I->getOperand(1); |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 569 | PHINode *PN = NULL; |
| 570 | ConstantInt *CI = NULL; |
| 571 | |
| 572 | if ((PN = dyn_cast<PHINode>(Op0))) { |
| 573 | if ((CI = dyn_cast<ConstantInt>(Op1))) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 574 | IndVarIncrement = I; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 575 | } else |
| 576 | if ((PN = dyn_cast<PHINode>(Op1))) { |
| 577 | if ((CI = dyn_cast<ConstantInt>(Op0))) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 578 | IndVarIncrement = I; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 579 | } |
| 580 | |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 581 | if (IndVarIncrement && PN == IndVar && CI->isOne()) |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 582 | continue; |
| 583 | } |
Devang Patel | 6a2bfda | 2007-08-08 01:51:27 +0000 | [diff] [blame] | 584 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 585 | // I is an Exit condition if next instruction is block terminator. |
| 586 | // Exit condition is OK if it compares loop invariant exit value, |
| 587 | // which is checked below. |
Devang Patel | 002fe25 | 2007-08-07 23:17:52 +0000 | [diff] [blame] | 588 | else if (ICmpInst *EC = dyn_cast<ICmpInst>(I)) { |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 589 | if (EC == ExitCondition) |
Devang Patel | 6a2bfda | 2007-08-08 01:51:27 +0000 | [diff] [blame] | 590 | continue; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 591 | } |
| 592 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 593 | if (I == ExitingBlock->getTerminator()) |
Devang Patel | bacf519 | 2007-08-10 00:33:50 +0000 | [diff] [blame] | 594 | continue; |
| 595 | |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 596 | // Otherwise we have instruction that may not be safe. |
| 597 | return false; |
| 598 | } |
| 599 | |
Devang Patel | 1cc2ec8 | 2007-08-20 23:51:18 +0000 | [diff] [blame] | 600 | // We could not find any reason to consider ExitingBlock unsafe. |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 601 | return true; |
| 602 | } |
| 603 | |
Devang Patel | a6a8663 | 2007-08-14 18:35:57 +0000 | [diff] [blame] | 604 | /// removeBlocks - Remove basic block DeadBB and all blocks dominated by DeadBB. |
| 605 | /// This routine is used to remove split condition's dead branch, dominated by |
| 606 | /// DeadBB. LiveBB dominates split conidition's other branch. |
| 607 | void LoopIndexSplit::removeBlocks(BasicBlock *DeadBB, Loop *LP, |
| 608 | BasicBlock *LiveBB) { |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 609 | |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 610 | // First update DeadBB's dominance frontier. |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 611 | SmallVector<BasicBlock *, 8> FrontierBBs; |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 612 | DominanceFrontier::iterator DeadBBDF = DF->find(DeadBB); |
| 613 | if (DeadBBDF != DF->end()) { |
| 614 | SmallVector<BasicBlock *, 8> PredBlocks; |
| 615 | |
| 616 | DominanceFrontier::DomSetType DeadBBSet = DeadBBDF->second; |
| 617 | for (DominanceFrontier::DomSetType::iterator DeadBBSetI = DeadBBSet.begin(), |
| 618 | DeadBBSetE = DeadBBSet.end(); DeadBBSetI != DeadBBSetE; ++DeadBBSetI) { |
| 619 | BasicBlock *FrontierBB = *DeadBBSetI; |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 620 | FrontierBBs.push_back(FrontierBB); |
| 621 | |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 622 | // Rremove any PHI incoming edge from blocks dominated by DeadBB. |
| 623 | PredBlocks.clear(); |
| 624 | for(pred_iterator PI = pred_begin(FrontierBB), PE = pred_end(FrontierBB); |
| 625 | PI != PE; ++PI) { |
| 626 | BasicBlock *P = *PI; |
| 627 | if (P == DeadBB || DT->dominates(DeadBB, P)) |
| 628 | PredBlocks.push_back(P); |
Devang Patel | fc4c5f8 | 2007-08-13 22:13:24 +0000 | [diff] [blame] | 629 | } |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 630 | |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 631 | for(BasicBlock::iterator FBI = FrontierBB->begin(), FBE = FrontierBB->end(); |
| 632 | FBI != FBE; ++FBI) { |
| 633 | if (PHINode *PN = dyn_cast<PHINode>(FBI)) { |
| 634 | for(SmallVector<BasicBlock *, 8>::iterator PI = PredBlocks.begin(), |
| 635 | PE = PredBlocks.end(); PI != PE; ++PI) { |
| 636 | BasicBlock *P = *PI; |
| 637 | PN->removeIncomingValue(P); |
| 638 | } |
| 639 | } |
| 640 | else |
| 641 | break; |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 642 | } |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 643 | } |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 644 | } |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 645 | |
| 646 | // Now remove DeadBB and all nodes dominated by DeadBB in df order. |
| 647 | SmallVector<BasicBlock *, 32> WorkList; |
| 648 | DomTreeNode *DN = DT->getNode(DeadBB); |
| 649 | for (df_iterator<DomTreeNode*> DI = df_begin(DN), |
| 650 | E = df_end(DN); DI != E; ++DI) { |
| 651 | BasicBlock *BB = DI->getBlock(); |
| 652 | WorkList.push_back(BB); |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 653 | BB->replaceAllUsesWith(UndefValue::get(Type::LabelTy)); |
Devang Patel | 5b8ec61 | 2007-08-15 03:31:47 +0000 | [diff] [blame] | 654 | } |
| 655 | |
| 656 | while (!WorkList.empty()) { |
| 657 | BasicBlock *BB = WorkList.back(); WorkList.pop_back(); |
| 658 | for(BasicBlock::iterator BBI = BB->begin(), BBE = BB->end(); |
| 659 | BBI != BBE; ++BBI) { |
| 660 | Instruction *I = BBI; |
| 661 | I->replaceAllUsesWith(UndefValue::get(I->getType())); |
| 662 | I->eraseFromParent(); |
| 663 | } |
| 664 | LPM->deleteSimpleAnalysisValue(BB, LP); |
| 665 | DT->eraseNode(BB); |
| 666 | DF->removeBlock(BB); |
| 667 | LI->removeBlock(BB); |
| 668 | BB->eraseFromParent(); |
| 669 | } |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 670 | |
| 671 | // Update Frontier BBs' dominator info. |
| 672 | while (!FrontierBBs.empty()) { |
| 673 | BasicBlock *FBB = FrontierBBs.back(); FrontierBBs.pop_back(); |
| 674 | BasicBlock *NewDominator = FBB->getSinglePredecessor(); |
| 675 | if (!NewDominator) { |
| 676 | pred_iterator PI = pred_begin(FBB), PE = pred_end(FBB); |
| 677 | NewDominator = *PI; |
| 678 | ++PI; |
| 679 | if (NewDominator != LiveBB) { |
| 680 | for(; PI != PE; ++PI) { |
| 681 | BasicBlock *P = *PI; |
| 682 | if (P == LiveBB) { |
| 683 | NewDominator = LiveBB; |
| 684 | break; |
| 685 | } |
| 686 | NewDominator = DT->findNearestCommonDominator(NewDominator, P); |
| 687 | } |
| 688 | } |
| 689 | } |
| 690 | assert (NewDominator && "Unable to fix dominator info."); |
| 691 | DT->changeImmediateDominator(FBB, NewDominator); |
| 692 | DF->changeImmediateDominator(FBB, NewDominator, DT); |
| 693 | } |
| 694 | |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 695 | } |
| 696 | |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 697 | /// safeSplitCondition - Return true if it is possible to |
| 698 | /// split loop using given split condition. |
| 699 | bool LoopIndexSplit::safeSplitCondition(SplitInfo &SD) { |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 700 | |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 701 | BasicBlock *SplitCondBlock = SD.SplitCondition->getParent(); |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 702 | |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 703 | // Unable to handle triange loops at the moment. |
Devang Patel | 3fe4f21 | 2007-08-15 02:14:55 +0000 | [diff] [blame] | 704 | // In triangle loop, split condition is in header and one of the |
| 705 | // the split destination is loop latch. If split condition is EQ |
| 706 | // then such loops are already handle in processOneIterationLoop(). |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 707 | BasicBlock *Latch = L->getLoopLatch(); |
| 708 | BranchInst *SplitTerminator = |
| 709 | cast<BranchInst>(SplitCondBlock->getTerminator()); |
| 710 | BasicBlock *Succ0 = SplitTerminator->getSuccessor(0); |
| 711 | BasicBlock *Succ1 = SplitTerminator->getSuccessor(1); |
| 712 | if (L->getHeader() == SplitCondBlock |
| 713 | && (Latch == Succ0 || Latch == Succ1)) |
Devang Patel | 3fe4f21 | 2007-08-15 02:14:55 +0000 | [diff] [blame] | 714 | return false; |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 715 | |
Devang Patel | 20d260a | 2007-08-18 00:00:32 +0000 | [diff] [blame] | 716 | // If one of the split condition branch is post dominating other then loop |
| 717 | // index split is not appropriate. |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 718 | if (DT->dominates(Succ0, Latch) || DT->dominates(Succ1, Latch)) |
Devang Patel | 96bf524 | 2007-08-17 21:59:16 +0000 | [diff] [blame] | 719 | return false; |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 720 | |
Devang Patel | 20d260a | 2007-08-18 00:00:32 +0000 | [diff] [blame] | 721 | // If one of the split condition branch is a predecessor of the other |
| 722 | // split condition branch head then do not split loop on this condition. |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 723 | for(pred_iterator PI = pred_begin(Succ0), PE = pred_end(Succ0); |
| 724 | PI != PE; ++PI) |
Devang Patel | 20d260a | 2007-08-18 00:00:32 +0000 | [diff] [blame] | 725 | if (Succ1 == *PI) |
| 726 | return false; |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 727 | for(pred_iterator PI = pred_begin(Succ1), PE = pred_end(Succ1); |
| 728 | PI != PE; ++PI) |
Devang Patel | 20d260a | 2007-08-18 00:00:32 +0000 | [diff] [blame] | 729 | if (Succ0 == *PI) |
| 730 | return false; |
| 731 | |
Devang Patel | b88e420 | 2007-08-24 05:36:56 +0000 | [diff] [blame] | 732 | // Finally this split condition is safe only if merge point for |
| 733 | // split condition branch is loop latch. This check along with previous |
| 734 | // check, to ensure that exit condition is in either loop latch or header, |
| 735 | // filters all loops with non-empty loop body between merge point |
| 736 | // and exit condition. |
| 737 | DominanceFrontier::iterator Succ0DF = DF->find(Succ0); |
| 738 | assert (Succ0DF != DF->end() && "Unable to find Succ0 dominance frontier"); |
| 739 | if (Succ0DF->second.count(Latch)) |
| 740 | return true; |
| 741 | |
| 742 | DominanceFrontier::iterator Succ1DF = DF->find(Succ1); |
| 743 | assert (Succ1DF != DF->end() && "Unable to find Succ1 dominance frontier"); |
| 744 | if (Succ1DF->second.count(Latch)) |
| 745 | return true; |
| 746 | |
| 747 | return false; |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 748 | } |
| 749 | |
| 750 | /// splitLoop - Split current loop L in two loops using split information |
| 751 | /// SD. Update dominator information. Maintain LCSSA form. |
| 752 | bool LoopIndexSplit::splitLoop(SplitInfo &SD) { |
| 753 | |
| 754 | if (!safeSplitCondition(SD)) |
| 755 | return false; |
| 756 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 757 | // After loop is cloned there are two loops. |
| 758 | // |
| 759 | // First loop, referred as ALoop, executes first part of loop's iteration |
| 760 | // space split. Second loop, referred as BLoop, executes remaining |
| 761 | // part of loop's iteration space. |
| 762 | // |
| 763 | // ALoop's exit edge enters BLoop's header through a forwarding block which |
| 764 | // acts as a BLoop's preheader. |
Devang Patel | dc52395 | 2007-08-22 18:27:01 +0000 | [diff] [blame] | 765 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 766 | //[*] Calculate ALoop induction variable's new exiting value and |
| 767 | // BLoop induction variable's new starting value. Calculuate these |
| 768 | // values in original loop's preheader. |
| 769 | // A_ExitValue = min(SplitValue, OrignalLoopExitValue) |
| 770 | // B_StartValue = max(SplitValue, OriginalLoopStartValue) |
| 771 | Value *A_ExitValue = NULL; |
| 772 | Value *B_StartValue = NULL; |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 773 | if (isa<ConstantInt>(SD.SplitValue)) { |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 774 | A_ExitValue = SD.SplitValue; |
| 775 | B_StartValue = SD.SplitValue; |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 776 | } |
| 777 | else { |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 778 | BasicBlock *Preheader = L->getLoopPreheader(); |
| 779 | Instruction *PHTerminator = Preheader->getTerminator(); |
| 780 | bool SignedPredicate = ExitCondition->isSignedPredicate(); |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 781 | Value *C1 = new ICmpInst(SignedPredicate ? |
| 782 | ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 783 | SD.SplitValue, |
| 784 | ExitCondition->getOperand(ExitValueNum), |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 785 | "lsplit.ev", PHTerminator); |
| 786 | A_ExitValue = new SelectInst(C1, SD.SplitValue, |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 787 | ExitCondition->getOperand(ExitValueNum), |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 788 | "lsplit.ev", PHTerminator); |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 789 | |
| 790 | Value *C2 = new ICmpInst(SignedPredicate ? |
| 791 | ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT, |
| 792 | SD.SplitValue, StartValue, "lsplit.sv", |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 793 | PHTerminator); |
| 794 | B_StartValue = new SelectInst(C2, StartValue, SD.SplitValue, |
| 795 | "lsplit.sv", PHTerminator); |
Devang Patel | 23a19f8 | 2007-08-10 00:53:35 +0000 | [diff] [blame] | 796 | } |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 797 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 798 | //[*] Clone loop. |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 799 | DenseMap<const Value *, Value *> ValueMap; |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 800 | Loop *BLoop = CloneLoop(L, LPM, LI, ValueMap, this); |
| 801 | BasicBlock *B_Header = BLoop->getHeader(); |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 802 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 803 | //[*] ALoop's exiting edge BLoop's header. |
| 804 | // ALoop's original exit block becomes BLoop's exit block. |
| 805 | PHINode *B_IndVar = cast<PHINode>(ValueMap[IndVar]); |
| 806 | BasicBlock *A_ExitingBlock = ExitCondition->getParent(); |
| 807 | BranchInst *A_ExitInsn = |
| 808 | dyn_cast<BranchInst>(A_ExitingBlock->getTerminator()); |
| 809 | assert (A_ExitInsn && "Unable to find suitable loop exit branch"); |
| 810 | BasicBlock *B_ExitBlock = A_ExitInsn->getSuccessor(1); |
| 811 | if (L->contains(B_ExitBlock)) { |
| 812 | B_ExitBlock = A_ExitInsn->getSuccessor(0); |
| 813 | A_ExitInsn->setSuccessor(0, B_Header); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 814 | } else |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 815 | A_ExitInsn->setSuccessor(1, B_Header); |
| 816 | |
| 817 | //[*] Update ALoop's exit value using new exit value. |
| 818 | ExitCondition->setOperand(ExitValueNum, A_ExitValue); |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 819 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 820 | // [*] Update BLoop's header phi nodes. Remove incoming PHINode's from |
| 821 | // original loop's preheader. Add incoming PHINode values from |
| 822 | // ALoop's exiting block. Update BLoop header's domiantor info. |
| 823 | |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 824 | // Collect inverse map of Header PHINodes. |
| 825 | DenseMap<Value *, Value *> InverseMap; |
| 826 | for (BasicBlock::iterator BI = L->getHeader()->begin(), |
| 827 | BE = L->getHeader()->end(); BI != BE; ++BI) { |
| 828 | if (PHINode *PN = dyn_cast<PHINode>(BI)) { |
| 829 | PHINode *PNClone = cast<PHINode>(ValueMap[PN]); |
| 830 | InverseMap[PNClone] = PN; |
| 831 | } else |
| 832 | break; |
| 833 | } |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 834 | BasicBlock *Preheader = L->getLoopPreheader(); |
| 835 | for (BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 836 | BI != BE; ++BI) { |
| 837 | if (PHINode *PN = dyn_cast<PHINode>(BI)) { |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 838 | // Remove incoming value from original preheader. |
| 839 | PN->removeIncomingValue(Preheader); |
| 840 | |
| 841 | // Add incoming value from A_ExitingBlock. |
| 842 | if (PN == B_IndVar) |
| 843 | PN->addIncoming(B_StartValue, A_ExitingBlock); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 844 | else { |
| 845 | PHINode *OrigPN = cast<PHINode>(InverseMap[PN]); |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 846 | Value *V2 = OrigPN->getIncomingValueForBlock(A_ExitingBlock); |
| 847 | PN->addIncoming(V2, A_ExitingBlock); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 848 | } |
| 849 | } else |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 850 | break; |
| 851 | } |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 852 | DT->changeImmediateDominator(B_Header, A_ExitingBlock); |
| 853 | DF->changeImmediateDominator(B_Header, A_ExitingBlock, DT); |
Devang Patel | 0b8e02b | 2007-08-21 21:12:02 +0000 | [diff] [blame] | 854 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 855 | // [*] Update BLoop's exit block. Its new predecessor is BLoop's exit |
| 856 | // block. Remove incoming PHINode values from ALoop's exiting block. |
| 857 | // Add new incoming values from BLoop's incoming exiting value. |
| 858 | // Update BLoop exit block's dominator info.. |
| 859 | BasicBlock *B_ExitingBlock = cast<BasicBlock>(ValueMap[A_ExitingBlock]); |
| 860 | for (BasicBlock::iterator BI = B_ExitBlock->begin(), BE = B_ExitBlock->end(); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 861 | BI != BE; ++BI) { |
| 862 | if (PHINode *PN = dyn_cast<PHINode>(BI)) { |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 863 | PN->addIncoming(ValueMap[PN->getIncomingValueForBlock(A_ExitingBlock)], |
| 864 | B_ExitingBlock); |
| 865 | PN->removeIncomingValue(A_ExitingBlock); |
Devang Patel | ada054a | 2007-08-14 01:30:57 +0000 | [diff] [blame] | 866 | } else |
| 867 | break; |
| 868 | } |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 869 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 870 | DT->changeImmediateDominator(B_ExitBlock, B_ExitingBlock); |
| 871 | DF->changeImmediateDominator(B_ExitBlock, B_ExitingBlock, DT); |
Devang Patel | fc4c5f8 | 2007-08-13 22:13:24 +0000 | [diff] [blame] | 872 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 873 | //[*] Split ALoop's exit edge. This creates a new block which |
| 874 | // serves two purposes. First one is to hold PHINode defnitions |
| 875 | // to ensure that ALoop's LCSSA form. Second use it to act |
| 876 | // as a preheader for BLoop. |
| 877 | BasicBlock *A_ExitBlock = SplitEdge(A_ExitingBlock, B_Header, this); |
Devang Patel | 423c8b2 | 2007-08-10 18:07:13 +0000 | [diff] [blame] | 878 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 879 | //[*] Preserve ALoop's LCSSA form. Create new forwarding PHINodes |
| 880 | // in A_ExitBlock to redefine outgoing PHI definitions from ALoop. |
| 881 | for(BasicBlock::iterator BI = B_Header->begin(), BE = B_Header->end(); |
Devang Patel | 60cbab4 | 2007-08-21 19:47:46 +0000 | [diff] [blame] | 882 | BI != BE; ++BI) { |
| 883 | if (PHINode *PN = dyn_cast<PHINode>(BI)) { |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 884 | Value *V1 = PN->getIncomingValueForBlock(A_ExitBlock); |
Devang Patel | 60cbab4 | 2007-08-21 19:47:46 +0000 | [diff] [blame] | 885 | PHINode *newPHI = new PHINode(PN->getType(), PN->getName()); |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 886 | newPHI->addIncoming(V1, A_ExitingBlock); |
| 887 | A_ExitBlock->getInstList().push_front(newPHI); |
| 888 | PN->removeIncomingValue(A_ExitBlock); |
| 889 | PN->addIncoming(newPHI, A_ExitBlock); |
Devang Patel | 60cbab4 | 2007-08-21 19:47:46 +0000 | [diff] [blame] | 890 | } else |
| 891 | break; |
| 892 | } |
| 893 | |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 894 | //[*] Eliminate split condition's inactive branch from ALoop. |
| 895 | BasicBlock *A_SplitCondBlock = SD.SplitCondition->getParent(); |
| 896 | BranchInst *A_BR = cast<BranchInst>(A_SplitCondBlock->getTerminator()); |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 897 | BasicBlock *A_InactiveBranch = NULL; |
| 898 | BasicBlock *A_ActiveBranch = NULL; |
| 899 | if (SD.UseTrueBranchFirst) { |
| 900 | A_ActiveBranch = A_BR->getSuccessor(0); |
| 901 | A_InactiveBranch = A_BR->getSuccessor(1); |
| 902 | } else { |
| 903 | A_ActiveBranch = A_BR->getSuccessor(1); |
| 904 | A_InactiveBranch = A_BR->getSuccessor(0); |
| 905 | } |
Devang Patel | 7097e9a | 2007-08-24 19:32:26 +0000 | [diff] [blame^] | 906 | A_BR->setUnconditionalDest(A_ActiveBranch); |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 907 | removeBlocks(A_InactiveBranch, L, A_ActiveBranch); |
| 908 | |
| 909 | //[*] Eliminate split condition's inactive branch in from BLoop. |
| 910 | BasicBlock *B_SplitCondBlock = cast<BasicBlock>(ValueMap[A_SplitCondBlock]); |
| 911 | BranchInst *B_BR = cast<BranchInst>(B_SplitCondBlock->getTerminator()); |
Devang Patel | 4259fe3 | 2007-08-24 06:17:19 +0000 | [diff] [blame] | 912 | BasicBlock *B_InactiveBranch = NULL; |
| 913 | BasicBlock *B_ActiveBranch = NULL; |
| 914 | if (SD.UseTrueBranchFirst) { |
| 915 | B_ActiveBranch = B_BR->getSuccessor(1); |
| 916 | B_InactiveBranch = B_BR->getSuccessor(0); |
| 917 | } else { |
| 918 | B_ActiveBranch = B_BR->getSuccessor(0); |
| 919 | B_InactiveBranch = B_BR->getSuccessor(1); |
| 920 | } |
Devang Patel | 7097e9a | 2007-08-24 19:32:26 +0000 | [diff] [blame^] | 921 | B_BR->setUnconditionalDest(B_ActiveBranch); |
Devang Patel | a8644e3 | 2007-08-22 19:33:29 +0000 | [diff] [blame] | 922 | removeBlocks(B_InactiveBranch, BLoop, B_ActiveBranch); |
| 923 | |
Devang Patel | 98147a3 | 2007-08-12 07:02:51 +0000 | [diff] [blame] | 924 | return true; |
Devang Patel | fee76bd | 2007-08-07 00:25:56 +0000 | [diff] [blame] | 925 | } |