1 | //===- InstCombinePHI.cpp -------------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file implements the visitPHINode function. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "InstCombineInternal.h" |
14 | #include "llvm/ADT/STLExtras.h" |
15 | #include "llvm/ADT/SmallPtrSet.h" |
16 | #include "llvm/ADT/Statistic.h" |
17 | #include "llvm/Analysis/InstructionSimplify.h" |
18 | #include "llvm/Analysis/ValueTracking.h" |
19 | #include "llvm/IR/PatternMatch.h" |
20 | #include "llvm/Support/CommandLine.h" |
21 | #include "llvm/Transforms/InstCombine/InstCombiner.h" |
22 | #include "llvm/Transforms/Utils/Local.h" |
23 | #include <optional> |
24 | |
25 | using namespace llvm; |
26 | using namespace llvm::PatternMatch; |
27 | |
28 | #define DEBUG_TYPE "instcombine" |
29 | |
30 | static cl::opt<unsigned> |
31 | MaxNumPhis("instcombine-max-num-phis" , cl::init(Val: 512), |
32 | cl::desc("Maximum number phis to handle in intptr/ptrint folding" )); |
33 | |
34 | STATISTIC(NumPHIsOfInsertValues, |
35 | "Number of phi-of-insertvalue turned into insertvalue-of-phis" ); |
36 | STATISTIC(, |
37 | "Number of phi-of-extractvalue turned into extractvalue-of-phi" ); |
38 | STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd" ); |
39 | |
40 | /// The PHI arguments will be folded into a single operation with a PHI node |
41 | /// as input. The debug location of the single operation will be the merged |
42 | /// locations of the original PHI node arguments. |
43 | void InstCombinerImpl::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) { |
44 | auto *FirstInst = cast<Instruction>(Val: PN.getIncomingValue(i: 0)); |
45 | Inst->setDebugLoc(FirstInst->getDebugLoc()); |
46 | // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc |
47 | // will be inefficient. |
48 | assert(!isa<CallInst>(Inst)); |
49 | |
50 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
51 | auto *I = cast<Instruction>(Val: V); |
52 | Inst->applyMergedLocation(LocA: Inst->getDebugLoc(), LocB: I->getDebugLoc()); |
53 | } |
54 | } |
55 | |
56 | // Replace Integer typed PHI PN if the PHI's value is used as a pointer value. |
57 | // If there is an existing pointer typed PHI that produces the same value as PN, |
58 | // replace PN and the IntToPtr operation with it. Otherwise, synthesize a new |
59 | // PHI node: |
60 | // |
61 | // Case-1: |
62 | // bb1: |
63 | // int_init = PtrToInt(ptr_init) |
64 | // br label %bb2 |
65 | // bb2: |
66 | // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2] |
67 | // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2] |
68 | // ptr_val2 = IntToPtr(int_val) |
69 | // ... |
70 | // use(ptr_val2) |
71 | // ptr_val_inc = ... |
72 | // inc_val_inc = PtrToInt(ptr_val_inc) |
73 | // |
74 | // ==> |
75 | // bb1: |
76 | // br label %bb2 |
77 | // bb2: |
78 | // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2] |
79 | // ... |
80 | // use(ptr_val) |
81 | // ptr_val_inc = ... |
82 | // |
83 | // Case-2: |
84 | // bb1: |
85 | // int_ptr = BitCast(ptr_ptr) |
86 | // int_init = Load(int_ptr) |
87 | // br label %bb2 |
88 | // bb2: |
89 | // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2] |
90 | // ptr_val2 = IntToPtr(int_val) |
91 | // ... |
92 | // use(ptr_val2) |
93 | // ptr_val_inc = ... |
94 | // inc_val_inc = PtrToInt(ptr_val_inc) |
95 | // ==> |
96 | // bb1: |
97 | // ptr_init = Load(ptr_ptr) |
98 | // br label %bb2 |
99 | // bb2: |
100 | // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2] |
101 | // ... |
102 | // use(ptr_val) |
103 | // ptr_val_inc = ... |
104 | // ... |
105 | // |
106 | bool InstCombinerImpl::foldIntegerTypedPHI(PHINode &PN) { |
107 | if (!PN.getType()->isIntegerTy()) |
108 | return false; |
109 | if (!PN.hasOneUse()) |
110 | return false; |
111 | |
112 | auto *IntToPtr = dyn_cast<IntToPtrInst>(Val: PN.user_back()); |
113 | if (!IntToPtr) |
114 | return false; |
115 | |
116 | // Check if the pointer is actually used as pointer: |
117 | auto HasPointerUse = [](Instruction *IIP) { |
118 | for (User *U : IIP->users()) { |
119 | Value *Ptr = nullptr; |
120 | if (LoadInst *LoadI = dyn_cast<LoadInst>(Val: U)) { |
121 | Ptr = LoadI->getPointerOperand(); |
122 | } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
123 | Ptr = SI->getPointerOperand(); |
124 | } else if (GetElementPtrInst *GI = dyn_cast<GetElementPtrInst>(Val: U)) { |
125 | Ptr = GI->getPointerOperand(); |
126 | } |
127 | |
128 | if (Ptr && Ptr == IIP) |
129 | return true; |
130 | } |
131 | return false; |
132 | }; |
133 | |
134 | if (!HasPointerUse(IntToPtr)) |
135 | return false; |
136 | |
137 | if (DL.getPointerSizeInBits(AS: IntToPtr->getAddressSpace()) != |
138 | DL.getTypeSizeInBits(Ty: IntToPtr->getOperand(i_nocapture: 0)->getType())) |
139 | return false; |
140 | |
141 | SmallVector<Value *, 4> AvailablePtrVals; |
142 | for (auto Incoming : zip(t: PN.blocks(), u: PN.incoming_values())) { |
143 | BasicBlock *BB = std::get<0>(t&: Incoming); |
144 | Value *Arg = std::get<1>(t&: Incoming); |
145 | |
146 | // First look backward: |
147 | if (auto *PI = dyn_cast<PtrToIntInst>(Val: Arg)) { |
148 | AvailablePtrVals.emplace_back(Args: PI->getOperand(i_nocapture: 0)); |
149 | continue; |
150 | } |
151 | |
152 | // Next look forward: |
153 | Value *ArgIntToPtr = nullptr; |
154 | for (User *U : Arg->users()) { |
155 | if (isa<IntToPtrInst>(Val: U) && U->getType() == IntToPtr->getType() && |
156 | (DT.dominates(Def: cast<Instruction>(Val: U), BB) || |
157 | cast<Instruction>(Val: U)->getParent() == BB)) { |
158 | ArgIntToPtr = U; |
159 | break; |
160 | } |
161 | } |
162 | |
163 | if (ArgIntToPtr) { |
164 | AvailablePtrVals.emplace_back(Args&: ArgIntToPtr); |
165 | continue; |
166 | } |
167 | |
168 | // If Arg is defined by a PHI, allow it. This will also create |
169 | // more opportunities iteratively. |
170 | if (isa<PHINode>(Val: Arg)) { |
171 | AvailablePtrVals.emplace_back(Args&: Arg); |
172 | continue; |
173 | } |
174 | |
175 | // For a single use integer load: |
176 | auto *LoadI = dyn_cast<LoadInst>(Val: Arg); |
177 | if (!LoadI) |
178 | return false; |
179 | |
180 | if (!LoadI->hasOneUse()) |
181 | return false; |
182 | |
183 | // Push the integer typed Load instruction into the available |
184 | // value set, and fix it up later when the pointer typed PHI |
185 | // is synthesized. |
186 | AvailablePtrVals.emplace_back(Args&: LoadI); |
187 | } |
188 | |
189 | // Now search for a matching PHI |
190 | auto *BB = PN.getParent(); |
191 | assert(AvailablePtrVals.size() == PN.getNumIncomingValues() && |
192 | "Not enough available ptr typed incoming values" ); |
193 | PHINode *MatchingPtrPHI = nullptr; |
194 | unsigned NumPhis = 0; |
195 | for (PHINode &PtrPHI : BB->phis()) { |
196 | // FIXME: consider handling this in AggressiveInstCombine |
197 | if (NumPhis++ > MaxNumPhis) |
198 | return false; |
199 | if (&PtrPHI == &PN || PtrPHI.getType() != IntToPtr->getType()) |
200 | continue; |
201 | if (any_of(Range: zip(t: PN.blocks(), u&: AvailablePtrVals), |
202 | P: [&](const auto &BlockAndValue) { |
203 | BasicBlock *BB = std::get<0>(BlockAndValue); |
204 | Value *V = std::get<1>(BlockAndValue); |
205 | return PtrPHI.getIncomingValueForBlock(BB) != V; |
206 | })) |
207 | continue; |
208 | MatchingPtrPHI = &PtrPHI; |
209 | break; |
210 | } |
211 | |
212 | if (MatchingPtrPHI) { |
213 | assert(MatchingPtrPHI->getType() == IntToPtr->getType() && |
214 | "Phi's Type does not match with IntToPtr" ); |
215 | // Explicitly replace the inttoptr (rather than inserting a ptrtoint) here, |
216 | // to make sure another transform can't undo it in the meantime. |
217 | replaceInstUsesWith(I&: *IntToPtr, V: MatchingPtrPHI); |
218 | eraseInstFromFunction(I&: *IntToPtr); |
219 | eraseInstFromFunction(I&: PN); |
220 | return true; |
221 | } |
222 | |
223 | // If it requires a conversion for every PHI operand, do not do it. |
224 | if (all_of(Range&: AvailablePtrVals, P: [&](Value *V) { |
225 | return (V->getType() != IntToPtr->getType()) || isa<IntToPtrInst>(Val: V); |
226 | })) |
227 | return false; |
228 | |
229 | // If any of the operand that requires casting is a terminator |
230 | // instruction, do not do it. Similarly, do not do the transform if the value |
231 | // is PHI in a block with no insertion point, for example, a catchswitch |
232 | // block, since we will not be able to insert a cast after the PHI. |
233 | if (any_of(Range&: AvailablePtrVals, P: [&](Value *V) { |
234 | if (V->getType() == IntToPtr->getType()) |
235 | return false; |
236 | auto *Inst = dyn_cast<Instruction>(Val: V); |
237 | if (!Inst) |
238 | return false; |
239 | if (Inst->isTerminator()) |
240 | return true; |
241 | auto *BB = Inst->getParent(); |
242 | if (isa<PHINode>(Val: Inst) && BB->getFirstInsertionPt() == BB->end()) |
243 | return true; |
244 | return false; |
245 | })) |
246 | return false; |
247 | |
248 | PHINode *NewPtrPHI = PHINode::Create( |
249 | Ty: IntToPtr->getType(), NumReservedValues: PN.getNumIncomingValues(), NameStr: PN.getName() + ".ptr" ); |
250 | |
251 | InsertNewInstBefore(New: NewPtrPHI, Old: PN.getIterator()); |
252 | SmallDenseMap<Value *, Instruction *> Casts; |
253 | for (auto Incoming : zip(t: PN.blocks(), u&: AvailablePtrVals)) { |
254 | auto *IncomingBB = std::get<0>(t&: Incoming); |
255 | auto *IncomingVal = std::get<1>(t&: Incoming); |
256 | |
257 | if (IncomingVal->getType() == IntToPtr->getType()) { |
258 | NewPtrPHI->addIncoming(V: IncomingVal, BB: IncomingBB); |
259 | continue; |
260 | } |
261 | |
262 | #ifndef NDEBUG |
263 | LoadInst *LoadI = dyn_cast<LoadInst>(Val: IncomingVal); |
264 | assert((isa<PHINode>(IncomingVal) || |
265 | IncomingVal->getType()->isPointerTy() || |
266 | (LoadI && LoadI->hasOneUse())) && |
267 | "Can not replace LoadInst with multiple uses" ); |
268 | #endif |
269 | // Need to insert a BitCast. |
270 | // For an integer Load instruction with a single use, the load + IntToPtr |
271 | // cast will be simplified into a pointer load: |
272 | // %v = load i64, i64* %a.ip, align 8 |
273 | // %v.cast = inttoptr i64 %v to float ** |
274 | // ==> |
275 | // %v.ptrp = bitcast i64 * %a.ip to float ** |
276 | // %v.cast = load float *, float ** %v.ptrp, align 8 |
277 | Instruction *&CI = Casts[IncomingVal]; |
278 | if (!CI) { |
279 | CI = CastInst::CreateBitOrPointerCast(S: IncomingVal, Ty: IntToPtr->getType(), |
280 | Name: IncomingVal->getName() + ".ptr" ); |
281 | if (auto *IncomingI = dyn_cast<Instruction>(Val: IncomingVal)) { |
282 | BasicBlock::iterator InsertPos(IncomingI); |
283 | InsertPos++; |
284 | BasicBlock *BB = IncomingI->getParent(); |
285 | if (isa<PHINode>(Val: IncomingI)) |
286 | InsertPos = BB->getFirstInsertionPt(); |
287 | assert(InsertPos != BB->end() && "should have checked above" ); |
288 | InsertNewInstBefore(New: CI, Old: InsertPos); |
289 | } else { |
290 | auto *InsertBB = &IncomingBB->getParent()->getEntryBlock(); |
291 | InsertNewInstBefore(New: CI, Old: InsertBB->getFirstInsertionPt()); |
292 | } |
293 | } |
294 | NewPtrPHI->addIncoming(V: CI, BB: IncomingBB); |
295 | } |
296 | |
297 | // Explicitly replace the inttoptr (rather than inserting a ptrtoint) here, |
298 | // to make sure another transform can't undo it in the meantime. |
299 | replaceInstUsesWith(I&: *IntToPtr, V: NewPtrPHI); |
300 | eraseInstFromFunction(I&: *IntToPtr); |
301 | eraseInstFromFunction(I&: PN); |
302 | return true; |
303 | } |
304 | |
305 | // Remove RoundTrip IntToPtr/PtrToInt Cast on PHI-Operand and |
306 | // fold Phi-operand to bitcast. |
307 | Instruction *InstCombinerImpl::foldPHIArgIntToPtrToPHI(PHINode &PN) { |
308 | // convert ptr2int ( phi[ int2ptr(ptr2int(x))] ) --> ptr2int ( phi [ x ] ) |
309 | // Make sure all uses of phi are ptr2int. |
310 | if (!all_of(Range: PN.users(), P: [](User *U) { return isa<PtrToIntInst>(Val: U); })) |
311 | return nullptr; |
312 | |
313 | // Iterating over all operands to check presence of target pointers for |
314 | // optimization. |
315 | bool OperandWithRoundTripCast = false; |
316 | for (unsigned OpNum = 0; OpNum != PN.getNumIncomingValues(); ++OpNum) { |
317 | if (auto *NewOp = |
318 | simplifyIntToPtrRoundTripCast(Val: PN.getIncomingValue(i: OpNum))) { |
319 | replaceOperand(I&: PN, OpNum, V: NewOp); |
320 | OperandWithRoundTripCast = true; |
321 | } |
322 | } |
323 | if (!OperandWithRoundTripCast) |
324 | return nullptr; |
325 | return &PN; |
326 | } |
327 | |
328 | /// If we have something like phi [insertvalue(a,b,0), insertvalue(c,d,0)], |
329 | /// turn this into a phi[a,c] and phi[b,d] and a single insertvalue. |
330 | Instruction * |
331 | InstCombinerImpl::foldPHIArgInsertValueInstructionIntoPHI(PHINode &PN) { |
332 | auto *FirstIVI = cast<InsertValueInst>(Val: PN.getIncomingValue(i: 0)); |
333 | |
334 | // Scan to see if all operands are `insertvalue`'s with the same indicies, |
335 | // and all have a single use. |
336 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
337 | auto *I = dyn_cast<InsertValueInst>(Val: V); |
338 | if (!I || !I->hasOneUser() || I->getIndices() != FirstIVI->getIndices()) |
339 | return nullptr; |
340 | } |
341 | |
342 | // For each operand of an `insertvalue` |
343 | std::array<PHINode *, 2> NewOperands; |
344 | for (int OpIdx : {0, 1}) { |
345 | auto *&NewOperand = NewOperands[OpIdx]; |
346 | // Create a new PHI node to receive the values the operand has in each |
347 | // incoming basic block. |
348 | NewOperand = PHINode::Create( |
349 | Ty: FirstIVI->getOperand(i_nocapture: OpIdx)->getType(), NumReservedValues: PN.getNumIncomingValues(), |
350 | NameStr: FirstIVI->getOperand(i_nocapture: OpIdx)->getName() + ".pn" ); |
351 | // And populate each operand's PHI with said values. |
352 | for (auto Incoming : zip(t: PN.blocks(), u: PN.incoming_values())) |
353 | NewOperand->addIncoming( |
354 | V: cast<InsertValueInst>(Val&: std::get<1>(t&: Incoming))->getOperand(i_nocapture: OpIdx), |
355 | BB: std::get<0>(t&: Incoming)); |
356 | InsertNewInstBefore(New: NewOperand, Old: PN.getIterator()); |
357 | } |
358 | |
359 | // And finally, create `insertvalue` over the newly-formed PHI nodes. |
360 | auto *NewIVI = InsertValueInst::Create(Agg: NewOperands[0], Val: NewOperands[1], |
361 | Idxs: FirstIVI->getIndices(), NameStr: PN.getName()); |
362 | |
363 | PHIArgMergedDebugLoc(Inst: NewIVI, PN); |
364 | ++NumPHIsOfInsertValues; |
365 | return NewIVI; |
366 | } |
367 | |
368 | /// If we have something like phi [extractvalue(a,0), extractvalue(b,0)], |
369 | /// turn this into a phi[a,b] and a single extractvalue. |
370 | Instruction * |
371 | InstCombinerImpl::(PHINode &PN) { |
372 | auto *FirstEVI = cast<ExtractValueInst>(Val: PN.getIncomingValue(i: 0)); |
373 | |
374 | // Scan to see if all operands are `extractvalue`'s with the same indicies, |
375 | // and all have a single use. |
376 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
377 | auto *I = dyn_cast<ExtractValueInst>(Val: V); |
378 | if (!I || !I->hasOneUser() || I->getIndices() != FirstEVI->getIndices() || |
379 | I->getAggregateOperand()->getType() != |
380 | FirstEVI->getAggregateOperand()->getType()) |
381 | return nullptr; |
382 | } |
383 | |
384 | // Create a new PHI node to receive the values the aggregate operand has |
385 | // in each incoming basic block. |
386 | auto *NewAggregateOperand = PHINode::Create( |
387 | Ty: FirstEVI->getAggregateOperand()->getType(), NumReservedValues: PN.getNumIncomingValues(), |
388 | NameStr: FirstEVI->getAggregateOperand()->getName() + ".pn" ); |
389 | // And populate the PHI with said values. |
390 | for (auto Incoming : zip(t: PN.blocks(), u: PN.incoming_values())) |
391 | NewAggregateOperand->addIncoming( |
392 | V: cast<ExtractValueInst>(Val&: std::get<1>(t&: Incoming))->getAggregateOperand(), |
393 | BB: std::get<0>(t&: Incoming)); |
394 | InsertNewInstBefore(New: NewAggregateOperand, Old: PN.getIterator()); |
395 | |
396 | // And finally, create `extractvalue` over the newly-formed PHI nodes. |
397 | auto *NewEVI = ExtractValueInst::Create(Agg: NewAggregateOperand, |
398 | Idxs: FirstEVI->getIndices(), NameStr: PN.getName()); |
399 | |
400 | PHIArgMergedDebugLoc(Inst: NewEVI, PN); |
401 | ++NumPHIsOfExtractValues; |
402 | return NewEVI; |
403 | } |
404 | |
405 | /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the |
406 | /// adds all have a single user, turn this into a phi and a single binop. |
407 | Instruction *InstCombinerImpl::foldPHIArgBinOpIntoPHI(PHINode &PN) { |
408 | Instruction *FirstInst = cast<Instruction>(Val: PN.getIncomingValue(i: 0)); |
409 | assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)); |
410 | unsigned Opc = FirstInst->getOpcode(); |
411 | Value *LHSVal = FirstInst->getOperand(i: 0); |
412 | Value *RHSVal = FirstInst->getOperand(i: 1); |
413 | |
414 | Type *LHSType = LHSVal->getType(); |
415 | Type *RHSType = RHSVal->getType(); |
416 | |
417 | // Scan to see if all operands are the same opcode, and all have one user. |
418 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
419 | Instruction *I = dyn_cast<Instruction>(Val: V); |
420 | if (!I || I->getOpcode() != Opc || !I->hasOneUser() || |
421 | // Verify type of the LHS matches so we don't fold cmp's of different |
422 | // types. |
423 | I->getOperand(i: 0)->getType() != LHSType || |
424 | I->getOperand(i: 1)->getType() != RHSType) |
425 | return nullptr; |
426 | |
427 | // If they are CmpInst instructions, check their predicates |
428 | if (CmpInst *CI = dyn_cast<CmpInst>(Val: I)) |
429 | if (CI->getPredicate() != cast<CmpInst>(Val: FirstInst)->getPredicate()) |
430 | return nullptr; |
431 | |
432 | // Keep track of which operand needs a phi node. |
433 | if (I->getOperand(i: 0) != LHSVal) LHSVal = nullptr; |
434 | if (I->getOperand(i: 1) != RHSVal) RHSVal = nullptr; |
435 | } |
436 | |
437 | // If both LHS and RHS would need a PHI, don't do this transformation, |
438 | // because it would increase the number of PHIs entering the block, |
439 | // which leads to higher register pressure. This is especially |
440 | // bad when the PHIs are in the header of a loop. |
441 | if (!LHSVal && !RHSVal) |
442 | return nullptr; |
443 | |
444 | // Otherwise, this is safe to transform! |
445 | |
446 | Value *InLHS = FirstInst->getOperand(i: 0); |
447 | Value *InRHS = FirstInst->getOperand(i: 1); |
448 | PHINode *NewLHS = nullptr, *NewRHS = nullptr; |
449 | if (!LHSVal) { |
450 | NewLHS = PHINode::Create(Ty: LHSType, NumReservedValues: PN.getNumIncomingValues(), |
451 | NameStr: FirstInst->getOperand(i: 0)->getName() + ".pn" ); |
452 | NewLHS->addIncoming(V: InLHS, BB: PN.getIncomingBlock(i: 0)); |
453 | InsertNewInstBefore(New: NewLHS, Old: PN.getIterator()); |
454 | LHSVal = NewLHS; |
455 | } |
456 | |
457 | if (!RHSVal) { |
458 | NewRHS = PHINode::Create(Ty: RHSType, NumReservedValues: PN.getNumIncomingValues(), |
459 | NameStr: FirstInst->getOperand(i: 1)->getName() + ".pn" ); |
460 | NewRHS->addIncoming(V: InRHS, BB: PN.getIncomingBlock(i: 0)); |
461 | InsertNewInstBefore(New: NewRHS, Old: PN.getIterator()); |
462 | RHSVal = NewRHS; |
463 | } |
464 | |
465 | // Add all operands to the new PHIs. |
466 | if (NewLHS || NewRHS) { |
467 | for (auto Incoming : drop_begin(RangeOrContainer: zip(t: PN.blocks(), u: PN.incoming_values()))) { |
468 | BasicBlock *InBB = std::get<0>(t&: Incoming); |
469 | Value *InVal = std::get<1>(t&: Incoming); |
470 | Instruction *InInst = cast<Instruction>(Val: InVal); |
471 | if (NewLHS) { |
472 | Value *NewInLHS = InInst->getOperand(i: 0); |
473 | NewLHS->addIncoming(V: NewInLHS, BB: InBB); |
474 | } |
475 | if (NewRHS) { |
476 | Value *NewInRHS = InInst->getOperand(i: 1); |
477 | NewRHS->addIncoming(V: NewInRHS, BB: InBB); |
478 | } |
479 | } |
480 | } |
481 | |
482 | if (CmpInst *CIOp = dyn_cast<CmpInst>(Val: FirstInst)) { |
483 | CmpInst *NewCI = CmpInst::Create(Op: CIOp->getOpcode(), Pred: CIOp->getPredicate(), |
484 | S1: LHSVal, S2: RHSVal); |
485 | PHIArgMergedDebugLoc(Inst: NewCI, PN); |
486 | return NewCI; |
487 | } |
488 | |
489 | BinaryOperator *BinOp = cast<BinaryOperator>(Val: FirstInst); |
490 | BinaryOperator *NewBinOp = |
491 | BinaryOperator::Create(Op: BinOp->getOpcode(), S1: LHSVal, S2: RHSVal); |
492 | |
493 | NewBinOp->copyIRFlags(V: PN.getIncomingValue(i: 0)); |
494 | |
495 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) |
496 | NewBinOp->andIRFlags(V); |
497 | |
498 | PHIArgMergedDebugLoc(Inst: NewBinOp, PN); |
499 | return NewBinOp; |
500 | } |
501 | |
502 | Instruction *InstCombinerImpl::foldPHIArgGEPIntoPHI(PHINode &PN) { |
503 | GetElementPtrInst *FirstInst =cast<GetElementPtrInst>(Val: PN.getIncomingValue(i: 0)); |
504 | |
505 | SmallVector<Value*, 16> FixedOperands(FirstInst->op_begin(), |
506 | FirstInst->op_end()); |
507 | // This is true if all GEP bases are allocas and if all indices into them are |
508 | // constants. |
509 | bool AllBasePointersAreAllocas = true; |
510 | |
511 | // We don't want to replace this phi if the replacement would require |
512 | // more than one phi, which leads to higher register pressure. This is |
513 | // especially bad when the PHIs are in the header of a loop. |
514 | bool NeededPhi = false; |
515 | |
516 | bool AllInBounds = true; |
517 | |
518 | // Scan to see if all operands are the same opcode, and all have one user. |
519 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
520 | GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: V); |
521 | if (!GEP || !GEP->hasOneUser() || |
522 | GEP->getSourceElementType() != FirstInst->getSourceElementType() || |
523 | GEP->getNumOperands() != FirstInst->getNumOperands()) |
524 | return nullptr; |
525 | |
526 | AllInBounds &= GEP->isInBounds(); |
527 | |
528 | // Keep track of whether or not all GEPs are of alloca pointers. |
529 | if (AllBasePointersAreAllocas && |
530 | (!isa<AllocaInst>(Val: GEP->getOperand(i_nocapture: 0)) || |
531 | !GEP->hasAllConstantIndices())) |
532 | AllBasePointersAreAllocas = false; |
533 | |
534 | // Compare the operand lists. |
535 | for (unsigned Op = 0, E = FirstInst->getNumOperands(); Op != E; ++Op) { |
536 | if (FirstInst->getOperand(i_nocapture: Op) == GEP->getOperand(i_nocapture: Op)) |
537 | continue; |
538 | |
539 | // Don't merge two GEPs when two operands differ (introducing phi nodes) |
540 | // if one of the PHIs has a constant for the index. The index may be |
541 | // substantially cheaper to compute for the constants, so making it a |
542 | // variable index could pessimize the path. This also handles the case |
543 | // for struct indices, which must always be constant. |
544 | if (isa<ConstantInt>(Val: FirstInst->getOperand(i_nocapture: Op)) || |
545 | isa<ConstantInt>(Val: GEP->getOperand(i_nocapture: Op))) |
546 | return nullptr; |
547 | |
548 | if (FirstInst->getOperand(i_nocapture: Op)->getType() != |
549 | GEP->getOperand(i_nocapture: Op)->getType()) |
550 | return nullptr; |
551 | |
552 | // If we already needed a PHI for an earlier operand, and another operand |
553 | // also requires a PHI, we'd be introducing more PHIs than we're |
554 | // eliminating, which increases register pressure on entry to the PHI's |
555 | // block. |
556 | if (NeededPhi) |
557 | return nullptr; |
558 | |
559 | FixedOperands[Op] = nullptr; // Needs a PHI. |
560 | NeededPhi = true; |
561 | } |
562 | } |
563 | |
564 | // If all of the base pointers of the PHI'd GEPs are from allocas, don't |
565 | // bother doing this transformation. At best, this will just save a bit of |
566 | // offset calculation, but all the predecessors will have to materialize the |
567 | // stack address into a register anyway. We'd actually rather *clone* the |
568 | // load up into the predecessors so that we have a load of a gep of an alloca, |
569 | // which can usually all be folded into the load. |
570 | if (AllBasePointersAreAllocas) |
571 | return nullptr; |
572 | |
573 | // Otherwise, this is safe to transform. Insert PHI nodes for each operand |
574 | // that is variable. |
575 | SmallVector<PHINode*, 16> OperandPhis(FixedOperands.size()); |
576 | |
577 | bool HasAnyPHIs = false; |
578 | for (unsigned I = 0, E = FixedOperands.size(); I != E; ++I) { |
579 | if (FixedOperands[I]) |
580 | continue; // operand doesn't need a phi. |
581 | Value *FirstOp = FirstInst->getOperand(i_nocapture: I); |
582 | PHINode *NewPN = |
583 | PHINode::Create(Ty: FirstOp->getType(), NumReservedValues: E, NameStr: FirstOp->getName() + ".pn" ); |
584 | InsertNewInstBefore(New: NewPN, Old: PN.getIterator()); |
585 | |
586 | NewPN->addIncoming(V: FirstOp, BB: PN.getIncomingBlock(i: 0)); |
587 | OperandPhis[I] = NewPN; |
588 | FixedOperands[I] = NewPN; |
589 | HasAnyPHIs = true; |
590 | } |
591 | |
592 | // Add all operands to the new PHIs. |
593 | if (HasAnyPHIs) { |
594 | for (auto Incoming : drop_begin(RangeOrContainer: zip(t: PN.blocks(), u: PN.incoming_values()))) { |
595 | BasicBlock *InBB = std::get<0>(t&: Incoming); |
596 | Value *InVal = std::get<1>(t&: Incoming); |
597 | GetElementPtrInst *InGEP = cast<GetElementPtrInst>(Val: InVal); |
598 | |
599 | for (unsigned Op = 0, E = OperandPhis.size(); Op != E; ++Op) |
600 | if (PHINode *OpPhi = OperandPhis[Op]) |
601 | OpPhi->addIncoming(V: InGEP->getOperand(i_nocapture: Op), BB: InBB); |
602 | } |
603 | } |
604 | |
605 | Value *Base = FixedOperands[0]; |
606 | GetElementPtrInst *NewGEP = |
607 | GetElementPtrInst::Create(PointeeType: FirstInst->getSourceElementType(), Ptr: Base, |
608 | IdxList: ArrayRef(FixedOperands).slice(N: 1)); |
609 | if (AllInBounds) NewGEP->setIsInBounds(); |
610 | PHIArgMergedDebugLoc(Inst: NewGEP, PN); |
611 | return NewGEP; |
612 | } |
613 | |
614 | /// Return true if we know that it is safe to sink the load out of the block |
615 | /// that defines it. This means that it must be obvious the value of the load is |
616 | /// not changed from the point of the load to the end of the block it is in. |
617 | /// |
618 | /// Finally, it is safe, but not profitable, to sink a load targeting a |
619 | /// non-address-taken alloca. Doing so will cause us to not promote the alloca |
620 | /// to a register. |
621 | static bool isSafeAndProfitableToSinkLoad(LoadInst *L) { |
622 | BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end(); |
623 | |
624 | for (++BBI; BBI != E; ++BBI) |
625 | if (BBI->mayWriteToMemory()) { |
626 | // Calls that only access inaccessible memory do not block sinking the |
627 | // load. |
628 | if (auto *CB = dyn_cast<CallBase>(Val&: BBI)) |
629 | if (CB->onlyAccessesInaccessibleMemory()) |
630 | continue; |
631 | return false; |
632 | } |
633 | |
634 | // Check for non-address taken alloca. If not address-taken already, it isn't |
635 | // profitable to do this xform. |
636 | if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: L->getOperand(i_nocapture: 0))) { |
637 | bool IsAddressTaken = false; |
638 | for (User *U : AI->users()) { |
639 | if (isa<LoadInst>(Val: U)) continue; |
640 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
641 | // If storing TO the alloca, then the address isn't taken. |
642 | if (SI->getOperand(i_nocapture: 1) == AI) continue; |
643 | } |
644 | IsAddressTaken = true; |
645 | break; |
646 | } |
647 | |
648 | if (!IsAddressTaken && AI->isStaticAlloca()) |
649 | return false; |
650 | } |
651 | |
652 | // If this load is a load from a GEP with a constant offset from an alloca, |
653 | // then we don't want to sink it. In its present form, it will be |
654 | // load [constant stack offset]. Sinking it will cause us to have to |
655 | // materialize the stack addresses in each predecessor in a register only to |
656 | // do a shared load from register in the successor. |
657 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: L->getOperand(i_nocapture: 0))) |
658 | if (AllocaInst *AI = dyn_cast<AllocaInst>(Val: GEP->getOperand(i_nocapture: 0))) |
659 | if (AI->isStaticAlloca() && GEP->hasAllConstantIndices()) |
660 | return false; |
661 | |
662 | return true; |
663 | } |
664 | |
665 | Instruction *InstCombinerImpl::foldPHIArgLoadIntoPHI(PHINode &PN) { |
666 | LoadInst *FirstLI = cast<LoadInst>(Val: PN.getIncomingValue(i: 0)); |
667 | |
668 | // Can't forward swifterror through a phi. |
669 | if (FirstLI->getOperand(i_nocapture: 0)->isSwiftError()) |
670 | return nullptr; |
671 | |
672 | // FIXME: This is overconservative; this transform is allowed in some cases |
673 | // for atomic operations. |
674 | if (FirstLI->isAtomic()) |
675 | return nullptr; |
676 | |
677 | // When processing loads, we need to propagate two bits of information to the |
678 | // sunk load: whether it is volatile, and what its alignment is. |
679 | bool IsVolatile = FirstLI->isVolatile(); |
680 | Align LoadAlignment = FirstLI->getAlign(); |
681 | const unsigned LoadAddrSpace = FirstLI->getPointerAddressSpace(); |
682 | |
683 | // We can't sink the load if the loaded value could be modified between the |
684 | // load and the PHI. |
685 | if (FirstLI->getParent() != PN.getIncomingBlock(i: 0) || |
686 | !isSafeAndProfitableToSinkLoad(L: FirstLI)) |
687 | return nullptr; |
688 | |
689 | // If the PHI is of volatile loads and the load block has multiple |
690 | // successors, sinking it would remove a load of the volatile value from |
691 | // the path through the other successor. |
692 | if (IsVolatile && |
693 | FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1) |
694 | return nullptr; |
695 | |
696 | for (auto Incoming : drop_begin(RangeOrContainer: zip(t: PN.blocks(), u: PN.incoming_values()))) { |
697 | BasicBlock *InBB = std::get<0>(t&: Incoming); |
698 | Value *InVal = std::get<1>(t&: Incoming); |
699 | LoadInst *LI = dyn_cast<LoadInst>(Val: InVal); |
700 | if (!LI || !LI->hasOneUser() || LI->isAtomic()) |
701 | return nullptr; |
702 | |
703 | // Make sure all arguments are the same type of operation. |
704 | if (LI->isVolatile() != IsVolatile || |
705 | LI->getPointerAddressSpace() != LoadAddrSpace) |
706 | return nullptr; |
707 | |
708 | // Can't forward swifterror through a phi. |
709 | if (LI->getOperand(i_nocapture: 0)->isSwiftError()) |
710 | return nullptr; |
711 | |
712 | // We can't sink the load if the loaded value could be modified between |
713 | // the load and the PHI. |
714 | if (LI->getParent() != InBB || !isSafeAndProfitableToSinkLoad(L: LI)) |
715 | return nullptr; |
716 | |
717 | LoadAlignment = std::min(a: LoadAlignment, b: LI->getAlign()); |
718 | |
719 | // If the PHI is of volatile loads and the load block has multiple |
720 | // successors, sinking it would remove a load of the volatile value from |
721 | // the path through the other successor. |
722 | if (IsVolatile && LI->getParent()->getTerminator()->getNumSuccessors() != 1) |
723 | return nullptr; |
724 | } |
725 | |
726 | // Okay, they are all the same operation. Create a new PHI node of the |
727 | // correct type, and PHI together all of the LHS's of the instructions. |
728 | PHINode *NewPN = PHINode::Create(Ty: FirstLI->getOperand(i_nocapture: 0)->getType(), |
729 | NumReservedValues: PN.getNumIncomingValues(), |
730 | NameStr: PN.getName()+".in" ); |
731 | |
732 | Value *InVal = FirstLI->getOperand(i_nocapture: 0); |
733 | NewPN->addIncoming(V: InVal, BB: PN.getIncomingBlock(i: 0)); |
734 | LoadInst *NewLI = |
735 | new LoadInst(FirstLI->getType(), NewPN, "" , IsVolatile, LoadAlignment); |
736 | |
737 | unsigned KnownIDs[] = { |
738 | LLVMContext::MD_tbaa, |
739 | LLVMContext::MD_range, |
740 | LLVMContext::MD_invariant_load, |
741 | LLVMContext::MD_alias_scope, |
742 | LLVMContext::MD_noalias, |
743 | LLVMContext::MD_nonnull, |
744 | LLVMContext::MD_align, |
745 | LLVMContext::MD_dereferenceable, |
746 | LLVMContext::MD_dereferenceable_or_null, |
747 | LLVMContext::MD_access_group, |
748 | LLVMContext::MD_noundef, |
749 | }; |
750 | |
751 | for (unsigned ID : KnownIDs) |
752 | NewLI->setMetadata(KindID: ID, Node: FirstLI->getMetadata(KindID: ID)); |
753 | |
754 | // Add all operands to the new PHI and combine TBAA metadata. |
755 | for (auto Incoming : drop_begin(RangeOrContainer: zip(t: PN.blocks(), u: PN.incoming_values()))) { |
756 | BasicBlock *BB = std::get<0>(t&: Incoming); |
757 | Value *V = std::get<1>(t&: Incoming); |
758 | LoadInst *LI = cast<LoadInst>(Val: V); |
759 | combineMetadata(K: NewLI, J: LI, KnownIDs, DoesKMove: true); |
760 | Value *NewInVal = LI->getOperand(i_nocapture: 0); |
761 | if (NewInVal != InVal) |
762 | InVal = nullptr; |
763 | NewPN->addIncoming(V: NewInVal, BB); |
764 | } |
765 | |
766 | if (InVal) { |
767 | // The new PHI unions all of the same values together. This is really |
768 | // common, so we handle it intelligently here for compile-time speed. |
769 | NewLI->setOperand(i_nocapture: 0, Val_nocapture: InVal); |
770 | delete NewPN; |
771 | } else { |
772 | InsertNewInstBefore(New: NewPN, Old: PN.getIterator()); |
773 | } |
774 | |
775 | // If this was a volatile load that we are merging, make sure to loop through |
776 | // and mark all the input loads as non-volatile. If we don't do this, we will |
777 | // insert a new volatile load and the old ones will not be deletable. |
778 | if (IsVolatile) |
779 | for (Value *IncValue : PN.incoming_values()) |
780 | cast<LoadInst>(Val: IncValue)->setVolatile(false); |
781 | |
782 | PHIArgMergedDebugLoc(Inst: NewLI, PN); |
783 | return NewLI; |
784 | } |
785 | |
786 | /// TODO: This function could handle other cast types, but then it might |
787 | /// require special-casing a cast from the 'i1' type. See the comment in |
788 | /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types. |
789 | Instruction *InstCombinerImpl::foldPHIArgZextsIntoPHI(PHINode &Phi) { |
790 | // We cannot create a new instruction after the PHI if the terminator is an |
791 | // EHPad because there is no valid insertion point. |
792 | if (Instruction *TI = Phi.getParent()->getTerminator()) |
793 | if (TI->isEHPad()) |
794 | return nullptr; |
795 | |
796 | // Early exit for the common case of a phi with two operands. These are |
797 | // handled elsewhere. See the comment below where we check the count of zexts |
798 | // and constants for more details. |
799 | unsigned NumIncomingValues = Phi.getNumIncomingValues(); |
800 | if (NumIncomingValues < 3) |
801 | return nullptr; |
802 | |
803 | // Find the narrower type specified by the first zext. |
804 | Type *NarrowType = nullptr; |
805 | for (Value *V : Phi.incoming_values()) { |
806 | if (auto *Zext = dyn_cast<ZExtInst>(Val: V)) { |
807 | NarrowType = Zext->getSrcTy(); |
808 | break; |
809 | } |
810 | } |
811 | if (!NarrowType) |
812 | return nullptr; |
813 | |
814 | // Walk the phi operands checking that we only have zexts or constants that |
815 | // we can shrink for free. Store the new operands for the new phi. |
816 | SmallVector<Value *, 4> NewIncoming; |
817 | unsigned NumZexts = 0; |
818 | unsigned NumConsts = 0; |
819 | for (Value *V : Phi.incoming_values()) { |
820 | if (auto *Zext = dyn_cast<ZExtInst>(Val: V)) { |
821 | // All zexts must be identical and have one user. |
822 | if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUser()) |
823 | return nullptr; |
824 | NewIncoming.push_back(Elt: Zext->getOperand(i_nocapture: 0)); |
825 | NumZexts++; |
826 | } else if (auto *C = dyn_cast<Constant>(Val: V)) { |
827 | // Make sure that constants can fit in the new type. |
828 | Constant *Trunc = getLosslessUnsignedTrunc(C, TruncTy: NarrowType); |
829 | if (!Trunc) |
830 | return nullptr; |
831 | NewIncoming.push_back(Elt: Trunc); |
832 | NumConsts++; |
833 | } else { |
834 | // If it's not a cast or a constant, bail out. |
835 | return nullptr; |
836 | } |
837 | } |
838 | |
839 | // The more common cases of a phi with no constant operands or just one |
840 | // variable operand are handled by FoldPHIArgOpIntoPHI() and foldOpIntoPhi() |
841 | // respectively. foldOpIntoPhi() wants to do the opposite transform that is |
842 | // performed here. It tries to replicate a cast in the phi operand's basic |
843 | // block to expose other folding opportunities. Thus, InstCombine will |
844 | // infinite loop without this check. |
845 | if (NumConsts == 0 || NumZexts < 2) |
846 | return nullptr; |
847 | |
848 | // All incoming values are zexts or constants that are safe to truncate. |
849 | // Create a new phi node of the narrow type, phi together all of the new |
850 | // operands, and zext the result back to the original type. |
851 | PHINode *NewPhi = PHINode::Create(Ty: NarrowType, NumReservedValues: NumIncomingValues, |
852 | NameStr: Phi.getName() + ".shrunk" ); |
853 | for (unsigned I = 0; I != NumIncomingValues; ++I) |
854 | NewPhi->addIncoming(V: NewIncoming[I], BB: Phi.getIncomingBlock(i: I)); |
855 | |
856 | InsertNewInstBefore(New: NewPhi, Old: Phi.getIterator()); |
857 | return CastInst::CreateZExtOrBitCast(S: NewPhi, Ty: Phi.getType()); |
858 | } |
859 | |
860 | /// If all operands to a PHI node are the same "unary" operator and they all are |
861 | /// only used by the PHI, PHI together their inputs, and do the operation once, |
862 | /// to the result of the PHI. |
863 | Instruction *InstCombinerImpl::foldPHIArgOpIntoPHI(PHINode &PN) { |
864 | // We cannot create a new instruction after the PHI if the terminator is an |
865 | // EHPad because there is no valid insertion point. |
866 | if (Instruction *TI = PN.getParent()->getTerminator()) |
867 | if (TI->isEHPad()) |
868 | return nullptr; |
869 | |
870 | Instruction *FirstInst = cast<Instruction>(Val: PN.getIncomingValue(i: 0)); |
871 | |
872 | if (isa<GetElementPtrInst>(Val: FirstInst)) |
873 | return foldPHIArgGEPIntoPHI(PN); |
874 | if (isa<LoadInst>(Val: FirstInst)) |
875 | return foldPHIArgLoadIntoPHI(PN); |
876 | if (isa<InsertValueInst>(Val: FirstInst)) |
877 | return foldPHIArgInsertValueInstructionIntoPHI(PN); |
878 | if (isa<ExtractValueInst>(Val: FirstInst)) |
879 | return foldPHIArgExtractValueInstructionIntoPHI(PN); |
880 | |
881 | // Scan the instruction, looking for input operations that can be folded away. |
882 | // If all input operands to the phi are the same instruction (e.g. a cast from |
883 | // the same type or "+42") we can pull the operation through the PHI, reducing |
884 | // code size and simplifying code. |
885 | Constant *ConstantOp = nullptr; |
886 | Type *CastSrcTy = nullptr; |
887 | |
888 | if (isa<CastInst>(Val: FirstInst)) { |
889 | CastSrcTy = FirstInst->getOperand(i: 0)->getType(); |
890 | |
891 | // Be careful about transforming integer PHIs. We don't want to pessimize |
892 | // the code by turning an i32 into an i1293. |
893 | if (PN.getType()->isIntegerTy() && CastSrcTy->isIntegerTy()) { |
894 | if (!shouldChangeType(From: PN.getType(), To: CastSrcTy)) |
895 | return nullptr; |
896 | } |
897 | } else if (isa<BinaryOperator>(Val: FirstInst) || isa<CmpInst>(Val: FirstInst)) { |
898 | // Can fold binop, compare or shift here if the RHS is a constant, |
899 | // otherwise call FoldPHIArgBinOpIntoPHI. |
900 | ConstantOp = dyn_cast<Constant>(Val: FirstInst->getOperand(i: 1)); |
901 | if (!ConstantOp) |
902 | return foldPHIArgBinOpIntoPHI(PN); |
903 | } else { |
904 | return nullptr; // Cannot fold this operation. |
905 | } |
906 | |
907 | // Check to see if all arguments are the same operation. |
908 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) { |
909 | Instruction *I = dyn_cast<Instruction>(Val: V); |
910 | if (!I || !I->hasOneUser() || !I->isSameOperationAs(I: FirstInst)) |
911 | return nullptr; |
912 | if (CastSrcTy) { |
913 | if (I->getOperand(i: 0)->getType() != CastSrcTy) |
914 | return nullptr; // Cast operation must match. |
915 | } else if (I->getOperand(i: 1) != ConstantOp) { |
916 | return nullptr; |
917 | } |
918 | } |
919 | |
920 | // Okay, they are all the same operation. Create a new PHI node of the |
921 | // correct type, and PHI together all of the LHS's of the instructions. |
922 | PHINode *NewPN = PHINode::Create(Ty: FirstInst->getOperand(i: 0)->getType(), |
923 | NumReservedValues: PN.getNumIncomingValues(), |
924 | NameStr: PN.getName()+".in" ); |
925 | |
926 | Value *InVal = FirstInst->getOperand(i: 0); |
927 | NewPN->addIncoming(V: InVal, BB: PN.getIncomingBlock(i: 0)); |
928 | |
929 | // Add all operands to the new PHI. |
930 | for (auto Incoming : drop_begin(RangeOrContainer: zip(t: PN.blocks(), u: PN.incoming_values()))) { |
931 | BasicBlock *BB = std::get<0>(t&: Incoming); |
932 | Value *V = std::get<1>(t&: Incoming); |
933 | Value *NewInVal = cast<Instruction>(Val: V)->getOperand(i: 0); |
934 | if (NewInVal != InVal) |
935 | InVal = nullptr; |
936 | NewPN->addIncoming(V: NewInVal, BB); |
937 | } |
938 | |
939 | Value *PhiVal; |
940 | if (InVal) { |
941 | // The new PHI unions all of the same values together. This is really |
942 | // common, so we handle it intelligently here for compile-time speed. |
943 | PhiVal = InVal; |
944 | delete NewPN; |
945 | } else { |
946 | InsertNewInstBefore(New: NewPN, Old: PN.getIterator()); |
947 | PhiVal = NewPN; |
948 | } |
949 | |
950 | // Insert and return the new operation. |
951 | if (CastInst *FirstCI = dyn_cast<CastInst>(Val: FirstInst)) { |
952 | CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), S: PhiVal, |
953 | Ty: PN.getType()); |
954 | PHIArgMergedDebugLoc(Inst: NewCI, PN); |
955 | return NewCI; |
956 | } |
957 | |
958 | if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Val: FirstInst)) { |
959 | BinOp = BinaryOperator::Create(Op: BinOp->getOpcode(), S1: PhiVal, S2: ConstantOp); |
960 | BinOp->copyIRFlags(V: PN.getIncomingValue(i: 0)); |
961 | |
962 | for (Value *V : drop_begin(RangeOrContainer: PN.incoming_values())) |
963 | BinOp->andIRFlags(V); |
964 | |
965 | PHIArgMergedDebugLoc(Inst: BinOp, PN); |
966 | return BinOp; |
967 | } |
968 | |
969 | CmpInst *CIOp = cast<CmpInst>(Val: FirstInst); |
970 | CmpInst *NewCI = CmpInst::Create(Op: CIOp->getOpcode(), Pred: CIOp->getPredicate(), |
971 | S1: PhiVal, S2: ConstantOp); |
972 | PHIArgMergedDebugLoc(Inst: NewCI, PN); |
973 | return NewCI; |
974 | } |
975 | |
976 | /// Return true if this PHI node is only used by a PHI node cycle that is dead. |
977 | static bool isDeadPHICycle(PHINode *PN, |
978 | SmallPtrSetImpl<PHINode *> &PotentiallyDeadPHIs) { |
979 | if (PN->use_empty()) return true; |
980 | if (!PN->hasOneUse()) return false; |
981 | |
982 | // Remember this node, and if we find the cycle, return. |
983 | if (!PotentiallyDeadPHIs.insert(Ptr: PN).second) |
984 | return true; |
985 | |
986 | // Don't scan crazily complex things. |
987 | if (PotentiallyDeadPHIs.size() == 16) |
988 | return false; |
989 | |
990 | if (PHINode *PU = dyn_cast<PHINode>(Val: PN->user_back())) |
991 | return isDeadPHICycle(PN: PU, PotentiallyDeadPHIs); |
992 | |
993 | return false; |
994 | } |
995 | |
996 | /// Return true if this phi node is always equal to NonPhiInVal. |
997 | /// This happens with mutually cyclic phi nodes like: |
998 | /// z = some value; x = phi (y, z); y = phi (x, z) |
999 | static bool PHIsEqualValue(PHINode *PN, Value *&NonPhiInVal, |
1000 | SmallPtrSetImpl<PHINode *> &ValueEqualPHIs) { |
1001 | // See if we already saw this PHI node. |
1002 | if (!ValueEqualPHIs.insert(Ptr: PN).second) |
1003 | return true; |
1004 | |
1005 | // Don't scan crazily complex things. |
1006 | if (ValueEqualPHIs.size() == 16) |
1007 | return false; |
1008 | |
1009 | // Scan the operands to see if they are either phi nodes or are equal to |
1010 | // the value. |
1011 | for (Value *Op : PN->incoming_values()) { |
1012 | if (PHINode *OpPN = dyn_cast<PHINode>(Val: Op)) { |
1013 | if (!PHIsEqualValue(PN: OpPN, NonPhiInVal, ValueEqualPHIs)) { |
1014 | if (NonPhiInVal) |
1015 | return false; |
1016 | NonPhiInVal = OpPN; |
1017 | } |
1018 | } else if (Op != NonPhiInVal) |
1019 | return false; |
1020 | } |
1021 | |
1022 | return true; |
1023 | } |
1024 | |
1025 | /// Return an existing non-zero constant if this phi node has one, otherwise |
1026 | /// return constant 1. |
1027 | static ConstantInt *getAnyNonZeroConstInt(PHINode &PN) { |
1028 | assert(isa<IntegerType>(PN.getType()) && "Expect only integer type phi" ); |
1029 | for (Value *V : PN.operands()) |
1030 | if (auto *ConstVA = dyn_cast<ConstantInt>(Val: V)) |
1031 | if (!ConstVA->isZero()) |
1032 | return ConstVA; |
1033 | return ConstantInt::get(Ty: cast<IntegerType>(Val: PN.getType()), V: 1); |
1034 | } |
1035 | |
1036 | namespace { |
1037 | struct PHIUsageRecord { |
1038 | unsigned PHIId; // The ID # of the PHI (something determinstic to sort on) |
1039 | unsigned Shift; // The amount shifted. |
1040 | Instruction *Inst; // The trunc instruction. |
1041 | |
1042 | PHIUsageRecord(unsigned Pn, unsigned Sh, Instruction *User) |
1043 | : PHIId(Pn), Shift(Sh), Inst(User) {} |
1044 | |
1045 | bool operator<(const PHIUsageRecord &RHS) const { |
1046 | if (PHIId < RHS.PHIId) return true; |
1047 | if (PHIId > RHS.PHIId) return false; |
1048 | if (Shift < RHS.Shift) return true; |
1049 | if (Shift > RHS.Shift) return false; |
1050 | return Inst->getType()->getPrimitiveSizeInBits() < |
1051 | RHS.Inst->getType()->getPrimitiveSizeInBits(); |
1052 | } |
1053 | }; |
1054 | |
1055 | struct LoweredPHIRecord { |
1056 | PHINode *PN; // The PHI that was lowered. |
1057 | unsigned Shift; // The amount shifted. |
1058 | unsigned Width; // The width extracted. |
1059 | |
1060 | LoweredPHIRecord(PHINode *Phi, unsigned Sh, Type *Ty) |
1061 | : PN(Phi), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {} |
1062 | |
1063 | // Ctor form used by DenseMap. |
1064 | LoweredPHIRecord(PHINode *Phi, unsigned Sh) : PN(Phi), Shift(Sh), Width(0) {} |
1065 | }; |
1066 | } // namespace |
1067 | |
1068 | namespace llvm { |
1069 | template<> |
1070 | struct DenseMapInfo<LoweredPHIRecord> { |
1071 | static inline LoweredPHIRecord getEmptyKey() { |
1072 | return LoweredPHIRecord(nullptr, 0); |
1073 | } |
1074 | static inline LoweredPHIRecord getTombstoneKey() { |
1075 | return LoweredPHIRecord(nullptr, 1); |
1076 | } |
1077 | static unsigned getHashValue(const LoweredPHIRecord &Val) { |
1078 | return DenseMapInfo<PHINode*>::getHashValue(PtrVal: Val.PN) ^ (Val.Shift>>3) ^ |
1079 | (Val.Width>>3); |
1080 | } |
1081 | static bool isEqual(const LoweredPHIRecord &LHS, |
1082 | const LoweredPHIRecord &RHS) { |
1083 | return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift && |
1084 | LHS.Width == RHS.Width; |
1085 | } |
1086 | }; |
1087 | } // namespace llvm |
1088 | |
1089 | |
1090 | /// This is an integer PHI and we know that it has an illegal type: see if it is |
1091 | /// only used by trunc or trunc(lshr) operations. If so, we split the PHI into |
1092 | /// the various pieces being extracted. This sort of thing is introduced when |
1093 | /// SROA promotes an aggregate to large integer values. |
1094 | /// |
1095 | /// TODO: The user of the trunc may be an bitcast to float/double/vector or an |
1096 | /// inttoptr. We should produce new PHIs in the right type. |
1097 | /// |
1098 | Instruction *InstCombinerImpl::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) { |
1099 | // PHIUsers - Keep track of all of the truncated values extracted from a set |
1100 | // of PHIs, along with their offset. These are the things we want to rewrite. |
1101 | SmallVector<PHIUsageRecord, 16> PHIUsers; |
1102 | |
1103 | // PHIs are often mutually cyclic, so we keep track of a whole set of PHI |
1104 | // nodes which are extracted from. PHIsToSlice is a set we use to avoid |
1105 | // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to |
1106 | // check the uses of (to ensure they are all extracts). |
1107 | SmallVector<PHINode*, 8> PHIsToSlice; |
1108 | SmallPtrSet<PHINode*, 8> PHIsInspected; |
1109 | |
1110 | PHIsToSlice.push_back(Elt: &FirstPhi); |
1111 | PHIsInspected.insert(Ptr: &FirstPhi); |
1112 | |
1113 | for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) { |
1114 | PHINode *PN = PHIsToSlice[PHIId]; |
1115 | |
1116 | // Scan the input list of the PHI. If any input is an invoke, and if the |
1117 | // input is defined in the predecessor, then we won't be split the critical |
1118 | // edge which is required to insert a truncate. Because of this, we have to |
1119 | // bail out. |
1120 | for (auto Incoming : zip(t: PN->blocks(), u: PN->incoming_values())) { |
1121 | BasicBlock *BB = std::get<0>(t&: Incoming); |
1122 | Value *V = std::get<1>(t&: Incoming); |
1123 | InvokeInst *II = dyn_cast<InvokeInst>(Val: V); |
1124 | if (!II) |
1125 | continue; |
1126 | if (II->getParent() != BB) |
1127 | continue; |
1128 | |
1129 | // If we have a phi, and if it's directly in the predecessor, then we have |
1130 | // a critical edge where we need to put the truncate. Since we can't |
1131 | // split the edge in instcombine, we have to bail out. |
1132 | return nullptr; |
1133 | } |
1134 | |
1135 | // If the incoming value is a PHI node before a catchswitch, we cannot |
1136 | // extract the value within that BB because we cannot insert any non-PHI |
1137 | // instructions in the BB. |
1138 | for (auto *Pred : PN->blocks()) |
1139 | if (Pred->getFirstInsertionPt() == Pred->end()) |
1140 | return nullptr; |
1141 | |
1142 | for (User *U : PN->users()) { |
1143 | Instruction *UserI = cast<Instruction>(Val: U); |
1144 | |
1145 | // If the user is a PHI, inspect its uses recursively. |
1146 | if (PHINode *UserPN = dyn_cast<PHINode>(Val: UserI)) { |
1147 | if (PHIsInspected.insert(Ptr: UserPN).second) |
1148 | PHIsToSlice.push_back(Elt: UserPN); |
1149 | continue; |
1150 | } |
1151 | |
1152 | // Truncates are always ok. |
1153 | if (isa<TruncInst>(Val: UserI)) { |
1154 | PHIUsers.push_back(Elt: PHIUsageRecord(PHIId, 0, UserI)); |
1155 | continue; |
1156 | } |
1157 | |
1158 | // Otherwise it must be a lshr which can only be used by one trunc. |
1159 | if (UserI->getOpcode() != Instruction::LShr || |
1160 | !UserI->hasOneUse() || !isa<TruncInst>(Val: UserI->user_back()) || |
1161 | !isa<ConstantInt>(Val: UserI->getOperand(i: 1))) |
1162 | return nullptr; |
1163 | |
1164 | // Bail on out of range shifts. |
1165 | unsigned SizeInBits = UserI->getType()->getScalarSizeInBits(); |
1166 | if (cast<ConstantInt>(Val: UserI->getOperand(i: 1))->getValue().uge(RHS: SizeInBits)) |
1167 | return nullptr; |
1168 | |
1169 | unsigned Shift = cast<ConstantInt>(Val: UserI->getOperand(i: 1))->getZExtValue(); |
1170 | PHIUsers.push_back(Elt: PHIUsageRecord(PHIId, Shift, UserI->user_back())); |
1171 | } |
1172 | } |
1173 | |
1174 | // If we have no users, they must be all self uses, just nuke the PHI. |
1175 | if (PHIUsers.empty()) |
1176 | return replaceInstUsesWith(I&: FirstPhi, V: PoisonValue::get(T: FirstPhi.getType())); |
1177 | |
1178 | // If this phi node is transformable, create new PHIs for all the pieces |
1179 | // extracted out of it. First, sort the users by their offset and size. |
1180 | array_pod_sort(Start: PHIUsers.begin(), End: PHIUsers.end()); |
1181 | |
1182 | LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n'; |
1183 | for (unsigned I = 1; I != PHIsToSlice.size(); ++I) dbgs() |
1184 | << "AND USER PHI #" << I << ": " << *PHIsToSlice[I] << '\n'); |
1185 | |
1186 | // PredValues - This is a temporary used when rewriting PHI nodes. It is |
1187 | // hoisted out here to avoid construction/destruction thrashing. |
1188 | DenseMap<BasicBlock*, Value*> PredValues; |
1189 | |
1190 | // ExtractedVals - Each new PHI we introduce is saved here so we don't |
1191 | // introduce redundant PHIs. |
1192 | DenseMap<LoweredPHIRecord, PHINode*> ; |
1193 | |
1194 | for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) { |
1195 | unsigned PHIId = PHIUsers[UserI].PHIId; |
1196 | PHINode *PN = PHIsToSlice[PHIId]; |
1197 | unsigned Offset = PHIUsers[UserI].Shift; |
1198 | Type *Ty = PHIUsers[UserI].Inst->getType(); |
1199 | |
1200 | PHINode *EltPHI; |
1201 | |
1202 | // If we've already lowered a user like this, reuse the previously lowered |
1203 | // value. |
1204 | if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) { |
1205 | |
1206 | // Otherwise, Create the new PHI node for this user. |
1207 | EltPHI = PHINode::Create(Ty, NumReservedValues: PN->getNumIncomingValues(), |
1208 | NameStr: PN->getName() + ".off" + Twine(Offset), |
1209 | InsertBefore: PN->getIterator()); |
1210 | assert(EltPHI->getType() != PN->getType() && |
1211 | "Truncate didn't shrink phi?" ); |
1212 | |
1213 | for (auto Incoming : zip(t: PN->blocks(), u: PN->incoming_values())) { |
1214 | BasicBlock *Pred = std::get<0>(t&: Incoming); |
1215 | Value *InVal = std::get<1>(t&: Incoming); |
1216 | Value *&PredVal = PredValues[Pred]; |
1217 | |
1218 | // If we already have a value for this predecessor, reuse it. |
1219 | if (PredVal) { |
1220 | EltPHI->addIncoming(V: PredVal, BB: Pred); |
1221 | continue; |
1222 | } |
1223 | |
1224 | // Handle the PHI self-reuse case. |
1225 | if (InVal == PN) { |
1226 | PredVal = EltPHI; |
1227 | EltPHI->addIncoming(V: PredVal, BB: Pred); |
1228 | continue; |
1229 | } |
1230 | |
1231 | if (PHINode *InPHI = dyn_cast<PHINode>(Val: PN)) { |
1232 | // If the incoming value was a PHI, and if it was one of the PHIs we |
1233 | // already rewrote it, just use the lowered value. |
1234 | if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) { |
1235 | PredVal = Res; |
1236 | EltPHI->addIncoming(V: PredVal, BB: Pred); |
1237 | continue; |
1238 | } |
1239 | } |
1240 | |
1241 | // Otherwise, do an extract in the predecessor. |
1242 | Builder.SetInsertPoint(Pred->getTerminator()); |
1243 | Value *Res = InVal; |
1244 | if (Offset) |
1245 | Res = Builder.CreateLShr( |
1246 | LHS: Res, RHS: ConstantInt::get(Ty: InVal->getType(), V: Offset), Name: "extract" ); |
1247 | Res = Builder.CreateTrunc(V: Res, DestTy: Ty, Name: "extract.t" ); |
1248 | PredVal = Res; |
1249 | EltPHI->addIncoming(V: Res, BB: Pred); |
1250 | |
1251 | // If the incoming value was a PHI, and if it was one of the PHIs we are |
1252 | // rewriting, we will ultimately delete the code we inserted. This |
1253 | // means we need to revisit that PHI to make sure we extract out the |
1254 | // needed piece. |
1255 | if (PHINode *OldInVal = dyn_cast<PHINode>(Val: InVal)) |
1256 | if (PHIsInspected.count(Ptr: OldInVal)) { |
1257 | unsigned RefPHIId = |
1258 | find(Range&: PHIsToSlice, Val: OldInVal) - PHIsToSlice.begin(); |
1259 | PHIUsers.push_back( |
1260 | Elt: PHIUsageRecord(RefPHIId, Offset, cast<Instruction>(Val: Res))); |
1261 | ++UserE; |
1262 | } |
1263 | } |
1264 | PredValues.clear(); |
1265 | |
1266 | LLVM_DEBUG(dbgs() << " Made element PHI for offset " << Offset << ": " |
1267 | << *EltPHI << '\n'); |
1268 | ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI; |
1269 | } |
1270 | |
1271 | // Replace the use of this piece with the PHI node. |
1272 | replaceInstUsesWith(I&: *PHIUsers[UserI].Inst, V: EltPHI); |
1273 | } |
1274 | |
1275 | // Replace all the remaining uses of the PHI nodes (self uses and the lshrs) |
1276 | // with poison. |
1277 | Value *Poison = PoisonValue::get(T: FirstPhi.getType()); |
1278 | for (PHINode *PHI : drop_begin(RangeOrContainer&: PHIsToSlice)) |
1279 | replaceInstUsesWith(I&: *PHI, V: Poison); |
1280 | return replaceInstUsesWith(I&: FirstPhi, V: Poison); |
1281 | } |
1282 | |
1283 | static Value *simplifyUsingControlFlow(InstCombiner &Self, PHINode &PN, |
1284 | const DominatorTree &DT) { |
1285 | // Simplify the following patterns: |
1286 | // if (cond) |
1287 | // / \ |
1288 | // ... ... |
1289 | // \ / |
1290 | // phi [true] [false] |
1291 | // and |
1292 | // switch (cond) |
1293 | // case v1: / \ case v2: |
1294 | // ... ... |
1295 | // \ / |
1296 | // phi [v1] [v2] |
1297 | // Make sure all inputs are constants. |
1298 | if (!all_of(Range: PN.operands(), P: [](Value *V) { return isa<ConstantInt>(Val: V); })) |
1299 | return nullptr; |
1300 | |
1301 | BasicBlock *BB = PN.getParent(); |
1302 | // Do not bother with unreachable instructions. |
1303 | if (!DT.isReachableFromEntry(A: BB)) |
1304 | return nullptr; |
1305 | |
1306 | // Determine which value the condition of the idom has for which successor. |
1307 | LLVMContext &Context = PN.getContext(); |
1308 | auto *IDom = DT.getNode(BB)->getIDom()->getBlock(); |
1309 | Value *Cond; |
1310 | SmallDenseMap<ConstantInt *, BasicBlock *, 8> SuccForValue; |
1311 | SmallDenseMap<BasicBlock *, unsigned, 8> SuccCount; |
1312 | auto AddSucc = [&](ConstantInt *C, BasicBlock *Succ) { |
1313 | SuccForValue[C] = Succ; |
1314 | ++SuccCount[Succ]; |
1315 | }; |
1316 | if (auto *BI = dyn_cast<BranchInst>(Val: IDom->getTerminator())) { |
1317 | if (BI->isUnconditional()) |
1318 | return nullptr; |
1319 | |
1320 | Cond = BI->getCondition(); |
1321 | AddSucc(ConstantInt::getTrue(Context), BI->getSuccessor(i: 0)); |
1322 | AddSucc(ConstantInt::getFalse(Context), BI->getSuccessor(i: 1)); |
1323 | } else if (auto *SI = dyn_cast<SwitchInst>(Val: IDom->getTerminator())) { |
1324 | Cond = SI->getCondition(); |
1325 | ++SuccCount[SI->getDefaultDest()]; |
1326 | for (auto Case : SI->cases()) |
1327 | AddSucc(Case.getCaseValue(), Case.getCaseSuccessor()); |
1328 | } else { |
1329 | return nullptr; |
1330 | } |
1331 | |
1332 | if (Cond->getType() != PN.getType()) |
1333 | return nullptr; |
1334 | |
1335 | // Check that edges outgoing from the idom's terminators dominate respective |
1336 | // inputs of the Phi. |
1337 | std::optional<bool> Invert; |
1338 | for (auto Pair : zip(t: PN.incoming_values(), u: PN.blocks())) { |
1339 | auto *Input = cast<ConstantInt>(Val&: std::get<0>(t&: Pair)); |
1340 | BasicBlock *Pred = std::get<1>(t&: Pair); |
1341 | auto IsCorrectInput = [&](ConstantInt *Input) { |
1342 | // The input needs to be dominated by the corresponding edge of the idom. |
1343 | // This edge cannot be a multi-edge, as that would imply that multiple |
1344 | // different condition values follow the same edge. |
1345 | auto It = SuccForValue.find(Val: Input); |
1346 | return It != SuccForValue.end() && SuccCount[It->second] == 1 && |
1347 | DT.dominates(BBE1: BasicBlockEdge(IDom, It->second), |
1348 | BBE2: BasicBlockEdge(Pred, BB)); |
1349 | }; |
1350 | |
1351 | // Depending on the constant, the condition may need to be inverted. |
1352 | bool NeedsInvert; |
1353 | if (IsCorrectInput(Input)) |
1354 | NeedsInvert = false; |
1355 | else if (IsCorrectInput(cast<ConstantInt>(Val: ConstantExpr::getNot(C: Input)))) |
1356 | NeedsInvert = true; |
1357 | else |
1358 | return nullptr; |
1359 | |
1360 | // Make sure the inversion requirement is always the same. |
1361 | if (Invert && *Invert != NeedsInvert) |
1362 | return nullptr; |
1363 | |
1364 | Invert = NeedsInvert; |
1365 | } |
1366 | |
1367 | if (!*Invert) |
1368 | return Cond; |
1369 | |
1370 | // This Phi is actually opposite to branching condition of IDom. We invert |
1371 | // the condition that will potentially open up some opportunities for |
1372 | // sinking. |
1373 | auto InsertPt = BB->getFirstInsertionPt(); |
1374 | if (InsertPt != BB->end()) { |
1375 | Self.Builder.SetInsertPoint(TheBB: &*BB, IP: InsertPt); |
1376 | return Self.Builder.CreateNot(V: Cond); |
1377 | } |
1378 | |
1379 | return nullptr; |
1380 | } |
1381 | |
1382 | // Fold iv = phi(start, iv.next = iv2.next op start) |
1383 | // where iv2 = phi(iv2.start, iv2.next = iv2 + iv2.step) |
1384 | // and iv2.start op start = start |
1385 | // to iv = iv2 op start |
1386 | static Value *foldDependentIVs(PHINode &PN, IRBuilderBase &Builder) { |
1387 | BasicBlock *BB = PN.getParent(); |
1388 | if (PN.getNumIncomingValues() != 2) |
1389 | return nullptr; |
1390 | |
1391 | Value *Start; |
1392 | Instruction *IvNext; |
1393 | BinaryOperator *Iv2Next; |
1394 | auto MatchOuterIV = [&](Value *V1, Value *V2) { |
1395 | if (match(V: V2, P: m_c_BinOp(L: m_Specific(V: V1), R: m_BinOp(I&: Iv2Next))) || |
1396 | match(V: V2, P: m_GEP(Ops: m_Specific(V: V1), Ops: m_BinOp(I&: Iv2Next)))) { |
1397 | Start = V1; |
1398 | IvNext = cast<Instruction>(Val: V2); |
1399 | return true; |
1400 | } |
1401 | return false; |
1402 | }; |
1403 | |
1404 | if (!MatchOuterIV(PN.getIncomingValue(i: 0), PN.getIncomingValue(i: 1)) && |
1405 | !MatchOuterIV(PN.getIncomingValue(i: 1), PN.getIncomingValue(i: 0))) |
1406 | return nullptr; |
1407 | |
1408 | PHINode *Iv2; |
1409 | Value *Iv2Start, *Iv2Step; |
1410 | if (!matchSimpleRecurrence(I: Iv2Next, P&: Iv2, Start&: Iv2Start, Step&: Iv2Step) || |
1411 | Iv2->getParent() != BB) |
1412 | return nullptr; |
1413 | |
1414 | auto *BO = dyn_cast<BinaryOperator>(Val: IvNext); |
1415 | Constant *Identity = |
1416 | BO ? ConstantExpr::getBinOpIdentity(Opcode: BO->getOpcode(), Ty: Iv2Start->getType()) |
1417 | : Constant::getNullValue(Ty: Iv2Start->getType()); |
1418 | if (Iv2Start != Identity) |
1419 | return nullptr; |
1420 | |
1421 | Builder.SetInsertPoint(TheBB: &*BB, IP: BB->getFirstInsertionPt()); |
1422 | if (!BO) { |
1423 | auto *GEP = cast<GEPOperator>(Val: IvNext); |
1424 | return Builder.CreateGEP(Ty: GEP->getSourceElementType(), Ptr: Start, IdxList: Iv2, Name: "" , |
1425 | IsInBounds: cast<GEPOperator>(Val: IvNext)->isInBounds()); |
1426 | } |
1427 | |
1428 | assert(BO->isCommutative() && "Must be commutative" ); |
1429 | Value *Res = Builder.CreateBinOp(Opc: BO->getOpcode(), LHS: Iv2, RHS: Start); |
1430 | cast<Instruction>(Val: Res)->copyIRFlags(V: BO); |
1431 | return Res; |
1432 | } |
1433 | |
1434 | // PHINode simplification |
1435 | // |
1436 | Instruction *InstCombinerImpl::visitPHINode(PHINode &PN) { |
1437 | if (Value *V = simplifyInstruction(I: &PN, Q: SQ.getWithInstruction(I: &PN))) |
1438 | return replaceInstUsesWith(I&: PN, V); |
1439 | |
1440 | if (Instruction *Result = foldPHIArgZextsIntoPHI(Phi&: PN)) |
1441 | return Result; |
1442 | |
1443 | if (Instruction *Result = foldPHIArgIntToPtrToPHI(PN)) |
1444 | return Result; |
1445 | |
1446 | // If all PHI operands are the same operation, pull them through the PHI, |
1447 | // reducing code size. |
1448 | auto *Inst0 = dyn_cast<Instruction>(Val: PN.getIncomingValue(i: 0)); |
1449 | auto *Inst1 = dyn_cast<Instruction>(Val: PN.getIncomingValue(i: 1)); |
1450 | if (Inst0 && Inst1 && Inst0->getOpcode() == Inst1->getOpcode() && |
1451 | Inst0->hasOneUser()) |
1452 | if (Instruction *Result = foldPHIArgOpIntoPHI(PN)) |
1453 | return Result; |
1454 | |
1455 | // If the incoming values are pointer casts of the same original value, |
1456 | // replace the phi with a single cast iff we can insert a non-PHI instruction. |
1457 | if (PN.getType()->isPointerTy() && |
1458 | PN.getParent()->getFirstInsertionPt() != PN.getParent()->end()) { |
1459 | Value *IV0 = PN.getIncomingValue(i: 0); |
1460 | Value *IV0Stripped = IV0->stripPointerCasts(); |
1461 | // Set to keep track of values known to be equal to IV0Stripped after |
1462 | // stripping pointer casts. |
1463 | SmallPtrSet<Value *, 4> CheckedIVs; |
1464 | CheckedIVs.insert(Ptr: IV0); |
1465 | if (IV0 != IV0Stripped && |
1466 | all_of(Range: PN.incoming_values(), P: [&CheckedIVs, IV0Stripped](Value *IV) { |
1467 | return !CheckedIVs.insert(Ptr: IV).second || |
1468 | IV0Stripped == IV->stripPointerCasts(); |
1469 | })) { |
1470 | return CastInst::CreatePointerCast(S: IV0Stripped, Ty: PN.getType()); |
1471 | } |
1472 | } |
1473 | |
1474 | // If this is a trivial cycle in the PHI node graph, remove it. Basically, if |
1475 | // this PHI only has a single use (a PHI), and if that PHI only has one use (a |
1476 | // PHI)... break the cycle. |
1477 | if (PN.hasOneUse()) { |
1478 | if (foldIntegerTypedPHI(PN)) |
1479 | return nullptr; |
1480 | |
1481 | Instruction *PHIUser = cast<Instruction>(Val: PN.user_back()); |
1482 | if (PHINode *PU = dyn_cast<PHINode>(Val: PHIUser)) { |
1483 | SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs; |
1484 | PotentiallyDeadPHIs.insert(Ptr: &PN); |
1485 | if (isDeadPHICycle(PN: PU, PotentiallyDeadPHIs)) |
1486 | return replaceInstUsesWith(I&: PN, V: PoisonValue::get(T: PN.getType())); |
1487 | } |
1488 | |
1489 | // If this phi has a single use, and if that use just computes a value for |
1490 | // the next iteration of a loop, delete the phi. This occurs with unused |
1491 | // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this |
1492 | // common case here is good because the only other things that catch this |
1493 | // are induction variable analysis (sometimes) and ADCE, which is only run |
1494 | // late. |
1495 | if (PHIUser->hasOneUse() && |
1496 | (isa<BinaryOperator>(Val: PHIUser) || isa<UnaryOperator>(Val: PHIUser) || |
1497 | isa<GetElementPtrInst>(Val: PHIUser)) && |
1498 | PHIUser->user_back() == &PN) { |
1499 | return replaceInstUsesWith(I&: PN, V: PoisonValue::get(T: PN.getType())); |
1500 | } |
1501 | } |
1502 | |
1503 | // When a PHI is used only to be compared with zero, it is safe to replace |
1504 | // an incoming value proved as known nonzero with any non-zero constant. |
1505 | // For example, in the code below, the incoming value %v can be replaced |
1506 | // with any non-zero constant based on the fact that the PHI is only used to |
1507 | // be compared with zero and %v is a known non-zero value: |
1508 | // %v = select %cond, 1, 2 |
1509 | // %p = phi [%v, BB] ... |
1510 | // icmp eq, %p, 0 |
1511 | // FIXME: To be simple, handle only integer type for now. |
1512 | // This handles a small number of uses to keep the complexity down, and an |
1513 | // icmp(or(phi)) can equally be replaced with any non-zero constant as the |
1514 | // "or" will only add bits. |
1515 | if (!PN.hasNUsesOrMore(N: 3)) { |
1516 | SmallVector<Instruction *> DropPoisonFlags; |
1517 | bool AllUsesOfPhiEndsInCmp = all_of(Range: PN.users(), P: [&](User *U) { |
1518 | auto *CmpInst = dyn_cast<ICmpInst>(Val: U); |
1519 | if (!CmpInst) { |
1520 | // This is always correct as OR only add bits and we are checking |
1521 | // against 0. |
1522 | if (U->hasOneUse() && match(V: U, P: m_c_Or(L: m_Specific(V: &PN), R: m_Value()))) { |
1523 | DropPoisonFlags.push_back(Elt: cast<Instruction>(Val: U)); |
1524 | CmpInst = dyn_cast<ICmpInst>(Val: U->user_back()); |
1525 | } |
1526 | } |
1527 | if (!CmpInst || !isa<IntegerType>(Val: PN.getType()) || |
1528 | !CmpInst->isEquality() || !match(V: CmpInst->getOperand(i_nocapture: 1), P: m_Zero())) { |
1529 | return false; |
1530 | } |
1531 | return true; |
1532 | }); |
1533 | // All uses of PHI results in a compare with zero. |
1534 | if (AllUsesOfPhiEndsInCmp) { |
1535 | ConstantInt *NonZeroConst = nullptr; |
1536 | bool MadeChange = false; |
1537 | for (unsigned I = 0, E = PN.getNumIncomingValues(); I != E; ++I) { |
1538 | Instruction *CtxI = PN.getIncomingBlock(i: I)->getTerminator(); |
1539 | Value *VA = PN.getIncomingValue(i: I); |
1540 | if (isKnownNonZero(V: VA, Q: getSimplifyQuery().getWithInstruction(I: CtxI))) { |
1541 | if (!NonZeroConst) |
1542 | NonZeroConst = getAnyNonZeroConstInt(PN); |
1543 | if (NonZeroConst != VA) { |
1544 | replaceOperand(I&: PN, OpNum: I, V: NonZeroConst); |
1545 | // The "disjoint" flag may no longer hold after the transform. |
1546 | for (Instruction *I : DropPoisonFlags) |
1547 | I->dropPoisonGeneratingFlags(); |
1548 | MadeChange = true; |
1549 | } |
1550 | } |
1551 | } |
1552 | if (MadeChange) |
1553 | return &PN; |
1554 | } |
1555 | } |
1556 | |
1557 | // We sometimes end up with phi cycles that non-obviously end up being the |
1558 | // same value, for example: |
1559 | // z = some value; x = phi (y, z); y = phi (x, z) |
1560 | // where the phi nodes don't necessarily need to be in the same block. Do a |
1561 | // quick check to see if the PHI node only contains a single non-phi value, if |
1562 | // so, scan to see if the phi cycle is actually equal to that value. If the |
1563 | // phi has no non-phi values then allow the "NonPhiInVal" to be set later if |
1564 | // one of the phis itself does not have a single input. |
1565 | { |
1566 | unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues(); |
1567 | // Scan for the first non-phi operand. |
1568 | while (InValNo != NumIncomingVals && |
1569 | isa<PHINode>(Val: PN.getIncomingValue(i: InValNo))) |
1570 | ++InValNo; |
1571 | |
1572 | Value *NonPhiInVal = |
1573 | InValNo != NumIncomingVals ? PN.getIncomingValue(i: InValNo) : nullptr; |
1574 | |
1575 | // Scan the rest of the operands to see if there are any conflicts, if so |
1576 | // there is no need to recursively scan other phis. |
1577 | if (NonPhiInVal) |
1578 | for (++InValNo; InValNo != NumIncomingVals; ++InValNo) { |
1579 | Value *OpVal = PN.getIncomingValue(i: InValNo); |
1580 | if (OpVal != NonPhiInVal && !isa<PHINode>(Val: OpVal)) |
1581 | break; |
1582 | } |
1583 | |
1584 | // If we scanned over all operands, then we have one unique value plus |
1585 | // phi values. Scan PHI nodes to see if they all merge in each other or |
1586 | // the value. |
1587 | if (InValNo == NumIncomingVals) { |
1588 | SmallPtrSet<PHINode *, 16> ValueEqualPHIs; |
1589 | if (PHIsEqualValue(PN: &PN, NonPhiInVal, ValueEqualPHIs)) |
1590 | return replaceInstUsesWith(I&: PN, V: NonPhiInVal); |
1591 | } |
1592 | } |
1593 | |
1594 | // If there are multiple PHIs, sort their operands so that they all list |
1595 | // the blocks in the same order. This will help identical PHIs be eliminated |
1596 | // by other passes. Other passes shouldn't depend on this for correctness |
1597 | // however. |
1598 | auto Res = PredOrder.try_emplace(Key: PN.getParent()); |
1599 | if (!Res.second) { |
1600 | const auto &Preds = Res.first->second; |
1601 | for (unsigned I = 0, E = PN.getNumIncomingValues(); I != E; ++I) { |
1602 | BasicBlock *BBA = PN.getIncomingBlock(i: I); |
1603 | BasicBlock *BBB = Preds[I]; |
1604 | if (BBA != BBB) { |
1605 | Value *VA = PN.getIncomingValue(i: I); |
1606 | unsigned J = PN.getBasicBlockIndex(BB: BBB); |
1607 | Value *VB = PN.getIncomingValue(i: J); |
1608 | PN.setIncomingBlock(i: I, BB: BBB); |
1609 | PN.setIncomingValue(i: I, V: VB); |
1610 | PN.setIncomingBlock(i: J, BB: BBA); |
1611 | PN.setIncomingValue(i: J, V: VA); |
1612 | // NOTE: Instcombine normally would want us to "return &PN" if we |
1613 | // modified any of the operands of an instruction. However, since we |
1614 | // aren't adding or removing uses (just rearranging them) we don't do |
1615 | // this in this case. |
1616 | } |
1617 | } |
1618 | } else { |
1619 | // Remember the block order of the first encountered phi node. |
1620 | append_range(C&: Res.first->second, R: PN.blocks()); |
1621 | } |
1622 | |
1623 | // Is there an identical PHI node in this basic block? |
1624 | for (PHINode &IdenticalPN : PN.getParent()->phis()) { |
1625 | // Ignore the PHI node itself. |
1626 | if (&IdenticalPN == &PN) |
1627 | continue; |
1628 | // Note that even though we've just canonicalized this PHI, due to the |
1629 | // worklist visitation order, there are no guarantess that *every* PHI |
1630 | // has been canonicalized, so we can't just compare operands ranges. |
1631 | if (!PN.isIdenticalToWhenDefined(I: &IdenticalPN)) |
1632 | continue; |
1633 | // Just use that PHI instead then. |
1634 | ++NumPHICSEs; |
1635 | return replaceInstUsesWith(I&: PN, V: &IdenticalPN); |
1636 | } |
1637 | |
1638 | // If this is an integer PHI and we know that it has an illegal type, see if |
1639 | // it is only used by trunc or trunc(lshr) operations. If so, we split the |
1640 | // PHI into the various pieces being extracted. This sort of thing is |
1641 | // introduced when SROA promotes an aggregate to a single large integer type. |
1642 | if (PN.getType()->isIntegerTy() && |
1643 | !DL.isLegalInteger(Width: PN.getType()->getPrimitiveSizeInBits())) |
1644 | if (Instruction *Res = SliceUpIllegalIntegerPHI(FirstPhi&: PN)) |
1645 | return Res; |
1646 | |
1647 | // Ultimately, try to replace this Phi with a dominating condition. |
1648 | if (auto *V = simplifyUsingControlFlow(Self&: *this, PN, DT)) |
1649 | return replaceInstUsesWith(I&: PN, V); |
1650 | |
1651 | if (Value *Res = foldDependentIVs(PN, Builder)) |
1652 | return replaceInstUsesWith(I&: PN, V: Res); |
1653 | |
1654 | return nullptr; |
1655 | } |
1656 | |