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