/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/PowerPC/PPCLoopPreIncPrep.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===------ PPCLoopPreIncPrep.cpp - Loop Pre-Inc. AM Prep. Pass -----------===// |
2 | | // |
3 | | // The LLVM Compiler Infrastructure |
4 | | // |
5 | | // This file is distributed under the University of Illinois Open Source |
6 | | // License. See LICENSE.TXT for details. |
7 | | // |
8 | | //===----------------------------------------------------------------------===// |
9 | | // |
10 | | // This file implements a pass to prepare loops for pre-increment addressing |
11 | | // modes. Additional PHIs are created for loop induction variables used by |
12 | | // load/store instructions so that the pre-increment forms can be used. |
13 | | // Generically, this means transforming loops like this: |
14 | | // for (int i = 0; i < n; ++i) |
15 | | // array[i] = c; |
16 | | // to look like this: |
17 | | // T *p = array[-1]; |
18 | | // for (int i = 0; i < n; ++i) |
19 | | // *++p = c; |
20 | | //===----------------------------------------------------------------------===// |
21 | | |
22 | | #define DEBUG_TYPE "ppc-loop-preinc-prep" |
23 | | |
24 | | #include "PPC.h" |
25 | | #include "PPCSubtarget.h" |
26 | | #include "PPCTargetMachine.h" |
27 | | #include "llvm/ADT/DepthFirstIterator.h" |
28 | | #include "llvm/ADT/SmallPtrSet.h" |
29 | | #include "llvm/ADT/SmallSet.h" |
30 | | #include "llvm/ADT/SmallVector.h" |
31 | | #include "llvm/ADT/Statistic.h" |
32 | | #include "llvm/Analysis/LoopInfo.h" |
33 | | #include "llvm/Analysis/ScalarEvolution.h" |
34 | | #include "llvm/Analysis/ScalarEvolutionExpander.h" |
35 | | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
36 | | #include "llvm/IR/BasicBlock.h" |
37 | | #include "llvm/IR/CFG.h" |
38 | | #include "llvm/IR/Dominators.h" |
39 | | #include "llvm/IR/Instruction.h" |
40 | | #include "llvm/IR/Instructions.h" |
41 | | #include "llvm/IR/IntrinsicInst.h" |
42 | | #include "llvm/IR/Module.h" |
43 | | #include "llvm/IR/Type.h" |
44 | | #include "llvm/IR/Value.h" |
45 | | #include "llvm/Pass.h" |
46 | | #include "llvm/Support/Casting.h" |
47 | | #include "llvm/Support/CommandLine.h" |
48 | | #include "llvm/Support/Debug.h" |
49 | | #include "llvm/Transforms/Scalar.h" |
50 | | #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
51 | | #include "llvm/Transforms/Utils/Local.h" |
52 | | #include "llvm/Transforms/Utils/LoopUtils.h" |
53 | | #include <cassert> |
54 | | #include <iterator> |
55 | | #include <utility> |
56 | | |
57 | | using namespace llvm; |
58 | | |
59 | | // By default, we limit this to creating 16 PHIs (which is a little over half |
60 | | // of the allocatable register set). |
61 | | static cl::opt<unsigned> MaxVars("ppc-preinc-prep-max-vars", |
62 | | cl::Hidden, cl::init(16), |
63 | | cl::desc("Potential PHI threshold for PPC preinc loop prep")); |
64 | | |
65 | | STATISTIC(PHINodeAlreadyExists, "PHI node already in pre-increment form"); |
66 | | |
67 | | namespace llvm { |
68 | | |
69 | | void initializePPCLoopPreIncPrepPass(PassRegistry&); |
70 | | |
71 | | } // end namespace llvm |
72 | | |
73 | | namespace { |
74 | | |
75 | | class PPCLoopPreIncPrep : public FunctionPass { |
76 | | public: |
77 | | static char ID; // Pass ID, replacement for typeid |
78 | | |
79 | 0 | PPCLoopPreIncPrep() : FunctionPass(ID) { |
80 | 0 | initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); |
81 | 0 | } |
82 | | |
83 | 1.23k | PPCLoopPreIncPrep(PPCTargetMachine &TM) : FunctionPass(ID), TM(&TM) { |
84 | 1.23k | initializePPCLoopPreIncPrepPass(*PassRegistry::getPassRegistry()); |
85 | 1.23k | } |
86 | | |
87 | 1.22k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
88 | 1.22k | AU.addPreserved<DominatorTreeWrapperPass>(); |
89 | 1.22k | AU.addRequired<LoopInfoWrapperPass>(); |
90 | 1.22k | AU.addPreserved<LoopInfoWrapperPass>(); |
91 | 1.22k | AU.addRequired<ScalarEvolutionWrapperPass>(); |
92 | 1.22k | } |
93 | | |
94 | | bool alreadyPrepared(Loop *L, Instruction* MemI, |
95 | | const SCEV *BasePtrStartSCEV, |
96 | | const SCEVConstant *BasePtrIncSCEV); |
97 | | bool runOnFunction(Function &F) override; |
98 | | |
99 | | bool runOnLoop(Loop *L); |
100 | | void simplifyLoopLatch(Loop *L); |
101 | | bool rotateLoop(Loop *L); |
102 | | |
103 | | private: |
104 | | PPCTargetMachine *TM = nullptr; |
105 | | DominatorTree *DT; |
106 | | LoopInfo *LI; |
107 | | ScalarEvolution *SE; |
108 | | bool PreserveLCSSA; |
109 | | }; |
110 | | |
111 | | } // end anonymous namespace |
112 | | |
113 | | char PPCLoopPreIncPrep::ID = 0; |
114 | | static const char *name = "Prepare loop for pre-inc. addressing modes"; |
115 | 1.23k | INITIALIZE_PASS_BEGIN1.23k (PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false)
|
116 | 1.23k | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) |
117 | 1.23k | INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) |
118 | 1.23k | INITIALIZE_PASS_END(PPCLoopPreIncPrep, DEBUG_TYPE, name, false, false) |
119 | | |
120 | 1.23k | FunctionPass *llvm::createPPCLoopPreIncPrepPass(PPCTargetMachine &TM) { |
121 | 1.23k | return new PPCLoopPreIncPrep(TM); |
122 | 1.23k | } |
123 | | |
124 | | namespace { |
125 | | |
126 | | struct BucketElement { |
127 | 202 | BucketElement(const SCEVConstant *O, Instruction *I) : Offset(O), Instr(I) {} |
128 | 152 | BucketElement(Instruction *I) : Offset(nullptr), Instr(I) {} |
129 | | |
130 | | const SCEVConstant *Offset; |
131 | | Instruction *Instr; |
132 | | }; |
133 | | |
134 | | struct Bucket { |
135 | | Bucket(const SCEV *B, Instruction *I) : BaseSCEV(B), |
136 | 152 | Elements(1, BucketElement(I)) {} |
137 | | |
138 | | const SCEV *BaseSCEV; |
139 | | SmallVector<BucketElement, 16> Elements; |
140 | | }; |
141 | | |
142 | | } // end anonymous namespace |
143 | | |
144 | 242 | static bool IsPtrInBounds(Value *BasePtr) { |
145 | 242 | Value *StrippedBasePtr = BasePtr; |
146 | 327 | while (BitCastInst *BC = dyn_cast<BitCastInst>(StrippedBasePtr)) |
147 | 85 | StrippedBasePtr = BC->getOperand(0); |
148 | 242 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(StrippedBasePtr)) |
149 | 211 | return GEP->isInBounds(); |
150 | 31 | |
151 | 31 | return false; |
152 | 31 | } |
153 | | |
154 | 341 | static Value *GetPointerOperand(Value *MemI) { |
155 | 341 | if (LoadInst *LMemI341 = dyn_cast<LoadInst>(MemI)) { |
156 | 191 | return LMemI->getPointerOperand(); |
157 | 150 | } else if (StoreInst *150 SMemI150 = dyn_cast<StoreInst>(MemI)) { |
158 | 131 | return SMemI->getPointerOperand(); |
159 | 19 | } else if (IntrinsicInst *19 IMemI19 = dyn_cast<IntrinsicInst>(MemI)) { |
160 | 19 | if (IMemI->getIntrinsicID() == Intrinsic::prefetch) |
161 | 19 | return IMemI->getArgOperand(0); |
162 | 0 | } |
163 | 0 |
|
164 | 0 | return nullptr; |
165 | 0 | } |
166 | | |
167 | 6.88k | bool PPCLoopPreIncPrep::runOnFunction(Function &F) { |
168 | 6.88k | if (skipFunction(F)) |
169 | 1 | return false; |
170 | 6.88k | |
171 | 6.88k | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); |
172 | 6.88k | SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); |
173 | 6.88k | auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); |
174 | 6.88k | DT = DTWP ? &DTWP->getDomTree()6.88k : nullptr0 ; |
175 | 6.88k | PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); |
176 | 6.88k | |
177 | 6.88k | bool MadeChange = false; |
178 | 6.88k | |
179 | 7.15k | for (auto I = LI->begin(), IE = LI->end(); I != IE7.15k ; ++I272 ) |
180 | 580 | for (auto L = df_begin(*I), LE = df_end(*I); 272 L != LE580 ; ++L308 ) |
181 | 308 | MadeChange |= runOnLoop(*L); |
182 | 6.88k | |
183 | 6.88k | return MadeChange; |
184 | 6.88k | } |
185 | | |
186 | | // In order to prepare for the pre-increment a PHI is added. |
187 | | // This function will check to see if that PHI already exists and will return |
188 | | // true if it found an existing PHI with the same start and increment as the |
189 | | // one we wanted to create. |
190 | | bool PPCLoopPreIncPrep::alreadyPrepared(Loop *L, Instruction* MemI, |
191 | | const SCEV *BasePtrStartSCEV, |
192 | 142 | const SCEVConstant *BasePtrIncSCEV) { |
193 | 142 | BasicBlock *BB = MemI->getParent(); |
194 | 142 | if (!BB) |
195 | 0 | return false; |
196 | 142 | |
197 | 142 | BasicBlock *PredBB = L->getLoopPredecessor(); |
198 | 142 | BasicBlock *LatchBB = L->getLoopLatch(); |
199 | 142 | |
200 | 142 | if (!PredBB || 142 !LatchBB142 ) |
201 | 0 | return false; |
202 | 142 | |
203 | 142 | // Run through the PHIs and see if we have some that looks like a preparation |
204 | 142 | iterator_range<BasicBlock::phi_iterator> PHIIter = BB->phis(); |
205 | 224 | for (auto & CurrentPHI : PHIIter) { |
206 | 224 | PHINode *CurrentPHINode = dyn_cast<PHINode>(&CurrentPHI); |
207 | 224 | if (!CurrentPHINode) |
208 | 0 | continue; |
209 | 224 | |
210 | 224 | if (224 !SE->isSCEVable(CurrentPHINode->getType())224 ) |
211 | 4 | continue; |
212 | 220 | |
213 | 220 | const SCEV *PHISCEV = SE->getSCEVAtScope(CurrentPHINode, L); |
214 | 220 | |
215 | 220 | const SCEVAddRecExpr *PHIBasePtrSCEV = dyn_cast<SCEVAddRecExpr>(PHISCEV); |
216 | 220 | if (!PHIBasePtrSCEV) |
217 | 20 | continue; |
218 | 200 | |
219 | 200 | const SCEVConstant *PHIBasePtrIncSCEV = |
220 | 200 | dyn_cast<SCEVConstant>(PHIBasePtrSCEV->getStepRecurrence(*SE)); |
221 | 200 | if (!PHIBasePtrIncSCEV) |
222 | 5 | continue; |
223 | 195 | |
224 | 195 | if (195 CurrentPHINode->getNumIncomingValues() == 2195 ) { |
225 | 195 | if ( (CurrentPHINode->getIncomingBlock(0) == LatchBB && |
226 | 150 | CurrentPHINode->getIncomingBlock(1) == PredBB) || |
227 | 45 | (CurrentPHINode->getIncomingBlock(1) == LatchBB && |
228 | 195 | CurrentPHINode->getIncomingBlock(0) == PredBB45 ) ) { |
229 | 195 | if (PHIBasePtrSCEV->getStart() == BasePtrStartSCEV && |
230 | 195 | PHIBasePtrIncSCEV == BasePtrIncSCEV5 ) { |
231 | 5 | // The existing PHI (CurrentPHINode) has the same start and increment |
232 | 5 | // as the PHI that we wanted to create. |
233 | 5 | ++PHINodeAlreadyExists; |
234 | 5 | return true; |
235 | 5 | } |
236 | 137 | } |
237 | 195 | } |
238 | 224 | } |
239 | 137 | return false; |
240 | 137 | } |
241 | | |
242 | 308 | bool PPCLoopPreIncPrep::runOnLoop(Loop *L) { |
243 | 308 | bool MadeChange = false; |
244 | 308 | |
245 | 308 | // Only prep. the inner-most loop |
246 | 308 | if (!L->empty()) |
247 | 25 | return MadeChange; |
248 | 283 | |
249 | 283 | DEBUG283 (dbgs() << "PIP: Examining: " << *L << "\n"); |
250 | 283 | |
251 | 283 | BasicBlock *Header = L->getHeader(); |
252 | 283 | |
253 | 283 | const PPCSubtarget *ST = |
254 | 283 | TM ? TM->getSubtargetImpl(*Header->getParent())283 : nullptr0 ; |
255 | 283 | |
256 | 283 | unsigned HeaderLoopPredCount = |
257 | 283 | std::distance(pred_begin(Header), pred_end(Header)); |
258 | 283 | |
259 | 283 | // Collect buckets of comparable addresses used by loads and stores. |
260 | 283 | SmallVector<Bucket, 16> Buckets; |
261 | 283 | for (Loop::block_iterator I = L->block_begin(), IE = L->block_end(); |
262 | 666 | I != IE666 ; ++I383 ) { |
263 | 383 | for (BasicBlock::iterator J = (*I)->begin(), JE = (*I)->end(); |
264 | 4.42k | J != JE4.42k ; ++J4.04k ) { |
265 | 4.04k | Value *PtrValue; |
266 | 4.04k | Instruction *MemI; |
267 | 4.04k | |
268 | 4.04k | if (LoadInst *LMemI4.04k = dyn_cast<LoadInst>(J)) { |
269 | 393 | MemI = LMemI; |
270 | 393 | PtrValue = LMemI->getPointerOperand(); |
271 | 4.04k | } else if (StoreInst *3.65k SMemI3.65k = dyn_cast<StoreInst>(J)) { |
272 | 245 | MemI = SMemI; |
273 | 245 | PtrValue = SMemI->getPointerOperand(); |
274 | 3.65k | } else if (IntrinsicInst *3.40k IMemI3.40k = dyn_cast<IntrinsicInst>(J)) { |
275 | 23 | if (IMemI->getIntrinsicID() == Intrinsic::prefetch23 ) { |
276 | 19 | MemI = IMemI; |
277 | 19 | PtrValue = IMemI->getArgOperand(0); |
278 | 23 | } else continue; |
279 | 3.38k | } else continue; |
280 | 657 | |
281 | 657 | unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); |
282 | 657 | if (PtrAddrSpace) |
283 | 0 | continue; |
284 | 657 | |
285 | 657 | // There are no update forms for Altivec vector load/stores. |
286 | 657 | if (657 ST && 657 ST->hasAltivec()657 && |
287 | 381 | PtrValue->getType()->getPointerElementType()->isVectorTy()) |
288 | 115 | continue; |
289 | 542 | |
290 | 542 | if (542 L->isLoopInvariant(PtrValue)542 ) |
291 | 71 | continue; |
292 | 471 | |
293 | 471 | const SCEV *LSCEV = SE->getSCEVAtScope(PtrValue, L); |
294 | 471 | if (const SCEVAddRecExpr *LARSCEV471 = dyn_cast<SCEVAddRecExpr>(LSCEV)) { |
295 | 354 | if (LARSCEV->getLoop() != L) |
296 | 0 | continue; |
297 | 117 | } else { |
298 | 117 | continue; |
299 | 117 | } |
300 | 354 | |
301 | 354 | bool FoundBucket = false; |
302 | 244 | for (auto &B : Buckets) { |
303 | 244 | const SCEV *Diff = SE->getMinusSCEV(LSCEV, B.BaseSCEV); |
304 | 244 | if (const auto *CDiff244 = dyn_cast<SCEVConstant>(Diff)) { |
305 | 202 | B.Elements.push_back(BucketElement(CDiff, MemI)); |
306 | 202 | FoundBucket = true; |
307 | 202 | break; |
308 | 202 | } |
309 | 354 | } |
310 | 354 | |
311 | 354 | if (!FoundBucket354 ) { |
312 | 152 | if (Buckets.size() == MaxVars) |
313 | 0 | return MadeChange; |
314 | 152 | Buckets.push_back(Bucket(LSCEV, MemI)); |
315 | 152 | } |
316 | 4.04k | } |
317 | 383 | } |
318 | 283 | |
319 | 283 | if (283 Buckets.empty()283 ) |
320 | 147 | return MadeChange; |
321 | 136 | |
322 | 136 | BasicBlock *LoopPredecessor = L->getLoopPredecessor(); |
323 | 136 | // If there is no loop predecessor, or the loop predecessor's terminator |
324 | 136 | // returns a value (which might contribute to determining the loop's |
325 | 136 | // iteration space), insert a new preheader for the loop. |
326 | 136 | if (!LoopPredecessor || |
327 | 136 | !LoopPredecessor->getTerminator()->getType()->isVoidTy()136 ) { |
328 | 0 | LoopPredecessor = InsertPreheaderForLoop(L, DT, LI, PreserveLCSSA); |
329 | 0 | if (LoopPredecessor) |
330 | 0 | MadeChange = true; |
331 | 0 | } |
332 | 136 | if (!LoopPredecessor) |
333 | 0 | return MadeChange; |
334 | 136 | |
335 | 136 | DEBUG136 (dbgs() << "PIP: Found " << Buckets.size() << " buckets\n"); |
336 | 136 | |
337 | 136 | SmallSet<BasicBlock *, 16> BBChanged; |
338 | 288 | for (unsigned i = 0, e = Buckets.size(); i != e288 ; ++i152 ) { |
339 | 152 | // The base address of each bucket is transformed into a phi and the others |
340 | 152 | // are rewritten as offsets of that variable. |
341 | 152 | |
342 | 152 | // We have a choice now of which instruction's memory operand we use as the |
343 | 152 | // base for the generated PHI. Always picking the first instruction in each |
344 | 152 | // bucket does not work well, specifically because that instruction might |
345 | 152 | // be a prefetch (and there are no pre-increment dcbt variants). Otherwise, |
346 | 152 | // the choice is somewhat arbitrary, because the backend will happily |
347 | 152 | // generate direct offsets from both the pre-incremented and |
348 | 152 | // post-incremented pointer values. Thus, we'll pick the first non-prefetch |
349 | 152 | // instruction in each bucket, and adjust the recurrence and other offsets |
350 | 152 | // accordingly. |
351 | 165 | for (int j = 0, je = Buckets[i].Elements.size(); j != je165 ; ++j13 ) { |
352 | 165 | if (auto *II = dyn_cast<IntrinsicInst>(Buckets[i].Elements[j].Instr)) |
353 | 13 | if (13 II->getIntrinsicID() == Intrinsic::prefetch13 ) |
354 | 13 | continue; |
355 | 152 | |
356 | 152 | // If we'd otherwise pick the first element anyway, there's nothing to do. |
357 | 152 | if (152 j == 0152 ) |
358 | 139 | break; |
359 | 13 | |
360 | 13 | // If our chosen element has no offset from the base pointer, there's |
361 | 13 | // nothing to do. |
362 | 13 | if (13 !Buckets[i].Elements[j].Offset || |
363 | 13 | Buckets[i].Elements[j].Offset->isZero()) |
364 | 0 | break; |
365 | 13 | |
366 | 13 | const SCEV *Offset = Buckets[i].Elements[j].Offset; |
367 | 13 | Buckets[i].BaseSCEV = SE->getAddExpr(Buckets[i].BaseSCEV, Offset); |
368 | 45 | for (auto &E : Buckets[i].Elements) { |
369 | 45 | if (E.Offset) |
370 | 32 | E.Offset = cast<SCEVConstant>(SE->getMinusSCEV(E.Offset, Offset)); |
371 | 45 | else |
372 | 13 | E.Offset = cast<SCEVConstant>(SE->getNegativeSCEV(Offset)); |
373 | 45 | } |
374 | 165 | |
375 | 165 | std::swap(Buckets[i].Elements[j], Buckets[i].Elements[0]); |
376 | 165 | break; |
377 | 165 | } |
378 | 152 | |
379 | 152 | const SCEVAddRecExpr *BasePtrSCEV = |
380 | 152 | cast<SCEVAddRecExpr>(Buckets[i].BaseSCEV); |
381 | 152 | if (!BasePtrSCEV->isAffine()) |
382 | 0 | continue; |
383 | 152 | |
384 | 152 | DEBUG152 (dbgs() << "PIP: Transforming: " << *BasePtrSCEV << "\n"); |
385 | 152 | assert(BasePtrSCEV->getLoop() == L && |
386 | 152 | "AddRec for the wrong loop?"); |
387 | 152 | |
388 | 152 | // The instruction corresponding to the Bucket's BaseSCEV must be the first |
389 | 152 | // in the vector of elements. |
390 | 152 | Instruction *MemI = Buckets[i].Elements.begin()->Instr; |
391 | 152 | Value *BasePtr = GetPointerOperand(MemI); |
392 | 152 | assert(BasePtr && "No pointer operand"); |
393 | 152 | |
394 | 152 | Type *I8Ty = Type::getInt8Ty(MemI->getParent()->getContext()); |
395 | 152 | Type *I8PtrTy = Type::getInt8PtrTy(MemI->getParent()->getContext(), |
396 | 152 | BasePtr->getType()->getPointerAddressSpace()); |
397 | 152 | |
398 | 152 | const SCEV *BasePtrStartSCEV = BasePtrSCEV->getStart(); |
399 | 152 | if (!SE->isLoopInvariant(BasePtrStartSCEV, L)) |
400 | 0 | continue; |
401 | 152 | |
402 | 152 | const SCEVConstant *BasePtrIncSCEV = |
403 | 152 | dyn_cast<SCEVConstant>(BasePtrSCEV->getStepRecurrence(*SE)); |
404 | 152 | if (!BasePtrIncSCEV) |
405 | 10 | continue; |
406 | 142 | BasePtrStartSCEV = SE->getMinusSCEV(BasePtrStartSCEV, BasePtrIncSCEV); |
407 | 142 | if (!isSafeToExpand(BasePtrStartSCEV, *SE)) |
408 | 0 | continue; |
409 | 142 | |
410 | 142 | DEBUG142 (dbgs() << "PIP: New start is: " << *BasePtrStartSCEV << "\n"); |
411 | 142 | |
412 | 142 | if (alreadyPrepared(L, MemI, BasePtrStartSCEV, BasePtrIncSCEV)) |
413 | 5 | continue; |
414 | 137 | |
415 | 137 | PHINode *NewPHI = PHINode::Create(I8PtrTy, HeaderLoopPredCount, |
416 | 137 | MemI->hasName() ? MemI->getName() + ".phi"4 : ""133 , |
417 | 137 | Header->getFirstNonPHI()); |
418 | 137 | |
419 | 137 | SCEVExpander SCEVE(*SE, Header->getModule()->getDataLayout(), "pistart"); |
420 | 137 | Value *BasePtrStart = SCEVE.expandCodeFor(BasePtrStartSCEV, I8PtrTy, |
421 | 137 | LoopPredecessor->getTerminator()); |
422 | 137 | |
423 | 137 | // Note that LoopPredecessor might occur in the predecessor list multiple |
424 | 137 | // times, and we need to add it the right number of times. |
425 | 137 | for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); |
426 | 411 | PI != PE411 ; ++PI274 ) { |
427 | 274 | if (*PI != LoopPredecessor) |
428 | 137 | continue; |
429 | 137 | |
430 | 137 | NewPHI->addIncoming(BasePtrStart, LoopPredecessor); |
431 | 137 | } |
432 | 137 | |
433 | 137 | Instruction *InsPoint = &*Header->getFirstInsertionPt(); |
434 | 137 | GetElementPtrInst *PtrInc = GetElementPtrInst::Create( |
435 | 137 | I8Ty, NewPHI, BasePtrIncSCEV->getValue(), |
436 | 137 | MemI->hasName() ? MemI->getName() + ".inc"4 : ""133 , InsPoint); |
437 | 137 | PtrInc->setIsInBounds(IsPtrInBounds(BasePtr)); |
438 | 137 | for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); |
439 | 411 | PI != PE411 ; ++PI274 ) { |
440 | 274 | if (*PI == LoopPredecessor) |
441 | 137 | continue; |
442 | 137 | |
443 | 137 | NewPHI->addIncoming(PtrInc, *PI); |
444 | 137 | } |
445 | 137 | |
446 | 137 | Instruction *NewBasePtr; |
447 | 137 | if (PtrInc->getType() != BasePtr->getType()) |
448 | 90 | NewBasePtr = new BitCastInst(PtrInc, BasePtr->getType(), |
449 | 90 | PtrInc->hasName() ? PtrInc->getName() + ".cast"4 : ""86 , InsPoint); |
450 | 137 | else |
451 | 47 | NewBasePtr = PtrInc; |
452 | 137 | |
453 | 137 | if (Instruction *IDel = dyn_cast<Instruction>(BasePtr)) |
454 | 137 | BBChanged.insert(IDel->getParent()); |
455 | 137 | BasePtr->replaceAllUsesWith(NewBasePtr); |
456 | 137 | RecursivelyDeleteTriviallyDeadInstructions(BasePtr); |
457 | 137 | |
458 | 137 | // Keep track of the replacement pointer values we've inserted so that we |
459 | 137 | // don't generate more pointer values than necessary. |
460 | 137 | SmallPtrSet<Value *, 16> NewPtrs; |
461 | 137 | NewPtrs.insert( NewBasePtr); |
462 | 137 | |
463 | 137 | for (auto I = std::next(Buckets[i].Elements.begin()), |
464 | 326 | IE = Buckets[i].Elements.end(); I != IE326 ; ++I189 ) { |
465 | 189 | Value *Ptr = GetPointerOperand(I->Instr); |
466 | 189 | assert(Ptr && "No pointer operand"); |
467 | 189 | if (NewPtrs.count(Ptr)) |
468 | 84 | continue; |
469 | 105 | |
470 | 105 | Instruction *RealNewPtr; |
471 | 105 | if (!I->Offset || 105 I->Offset->getValue()->isZero()105 ) { |
472 | 0 | RealNewPtr = NewBasePtr; |
473 | 105 | } else { |
474 | 105 | Instruction *PtrIP = dyn_cast<Instruction>(Ptr); |
475 | 105 | if (PtrIP && 105 isa<Instruction>(NewBasePtr)105 && |
476 | 105 | cast<Instruction>(NewBasePtr)->getParent() == PtrIP->getParent()) |
477 | 105 | PtrIP = nullptr; |
478 | 0 | else if (0 isa<PHINode>(PtrIP)0 ) |
479 | 0 | PtrIP = &*PtrIP->getParent()->getFirstInsertionPt(); |
480 | 0 | else if (0 !PtrIP0 ) |
481 | 0 | PtrIP = I->Instr; |
482 | 105 | |
483 | 105 | GetElementPtrInst *NewPtr = GetElementPtrInst::Create( |
484 | 105 | I8Ty, PtrInc, I->Offset->getValue(), |
485 | 105 | I->Instr->hasName() ? I->Instr->getName() + ".off"15 : ""90 , PtrIP); |
486 | 105 | if (!PtrIP) |
487 | 105 | NewPtr->insertAfter(cast<Instruction>(PtrInc)); |
488 | 105 | NewPtr->setIsInBounds(IsPtrInBounds(Ptr)); |
489 | 105 | RealNewPtr = NewPtr; |
490 | 105 | } |
491 | 105 | |
492 | 105 | if (Instruction *IDel = dyn_cast<Instruction>(Ptr)) |
493 | 105 | BBChanged.insert(IDel->getParent()); |
494 | 105 | |
495 | 105 | Instruction *ReplNewPtr; |
496 | 105 | if (Ptr->getType() != RealNewPtr->getType()105 ) { |
497 | 86 | ReplNewPtr = new BitCastInst(RealNewPtr, Ptr->getType(), |
498 | 86 | Ptr->hasName() ? Ptr->getName() + ".cast"86 : ""0 ); |
499 | 86 | ReplNewPtr->insertAfter(RealNewPtr); |
500 | 86 | } else |
501 | 19 | ReplNewPtr = RealNewPtr; |
502 | 189 | |
503 | 189 | Ptr->replaceAllUsesWith(ReplNewPtr); |
504 | 189 | RecursivelyDeleteTriviallyDeadInstructions(Ptr); |
505 | 189 | |
506 | 189 | NewPtrs.insert(RealNewPtr); |
507 | 189 | } |
508 | 152 | |
509 | 152 | MadeChange = true; |
510 | 152 | } |
511 | 136 | |
512 | 136 | for (Loop::block_iterator I = L->block_begin(), IE = L->block_end(); |
513 | 281 | I != IE281 ; ++I145 ) { |
514 | 145 | if (BBChanged.count(*I)) |
515 | 126 | DeleteDeadPHIs(*I); |
516 | 145 | } |
517 | 308 | |
518 | 308 | return MadeChange; |
519 | 308 | } |