LLVM  9.0.0svn
InstCombinePHI.cpp
Go to the documentation of this file.
1 //===- InstCombinePHI.cpp -------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the visitPHINode function.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/IR/PatternMatch.h"
21 using namespace llvm;
22 using namespace llvm::PatternMatch;
23 
24 #define DEBUG_TYPE "instcombine"
25 
26 static cl::opt<unsigned>
27 MaxNumPhis("instcombine-max-num-phis", cl::init(512),
28  cl::desc("Maximum number phis to handle in intptr/ptrint folding"));
29 
30 /// The PHI arguments will be folded into a single operation with a PHI node
31 /// as input. The debug location of the single operation will be the merged
32 /// locations of the original PHI node arguments.
33 void InstCombiner::PHIArgMergedDebugLoc(Instruction *Inst, PHINode &PN) {
34  auto *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
35  Inst->setDebugLoc(FirstInst->getDebugLoc());
36  // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc
37  // will be inefficient.
38  assert(!isa<CallInst>(Inst));
39 
40  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
41  auto *I = cast<Instruction>(PN.getIncomingValue(i));
42  Inst->applyMergedLocation(Inst->getDebugLoc(), I->getDebugLoc());
43  }
44 }
45 
46 // Replace Integer typed PHI PN if the PHI's value is used as a pointer value.
47 // If there is an existing pointer typed PHI that produces the same value as PN,
48 // replace PN and the IntToPtr operation with it. Otherwise, synthesize a new
49 // PHI node:
50 //
51 // Case-1:
52 // bb1:
53 // int_init = PtrToInt(ptr_init)
54 // br label %bb2
55 // bb2:
56 // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
57 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
58 // ptr_val2 = IntToPtr(int_val)
59 // ...
60 // use(ptr_val2)
61 // ptr_val_inc = ...
62 // inc_val_inc = PtrToInt(ptr_val_inc)
63 //
64 // ==>
65 // bb1:
66 // br label %bb2
67 // bb2:
68 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
69 // ...
70 // use(ptr_val)
71 // ptr_val_inc = ...
72 //
73 // Case-2:
74 // bb1:
75 // int_ptr = BitCast(ptr_ptr)
76 // int_init = Load(int_ptr)
77 // br label %bb2
78 // bb2:
79 // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
80 // ptr_val2 = IntToPtr(int_val)
81 // ...
82 // use(ptr_val2)
83 // ptr_val_inc = ...
84 // inc_val_inc = PtrToInt(ptr_val_inc)
85 // ==>
86 // bb1:
87 // ptr_init = Load(ptr_ptr)
88 // br label %bb2
89 // bb2:
90 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
91 // ...
92 // use(ptr_val)
93 // ptr_val_inc = ...
94 // ...
95 //
96 Instruction *InstCombiner::FoldIntegerTypedPHI(PHINode &PN) {
97  if (!PN.getType()->isIntegerTy())
98  return nullptr;
99  if (!PN.hasOneUse())
100  return nullptr;
101 
102  auto *IntToPtr = dyn_cast<IntToPtrInst>(PN.user_back());
103  if (!IntToPtr)
104  return nullptr;
105 
106  // Check if the pointer is actually used as pointer:
107  auto HasPointerUse = [](Instruction *IIP) {
108  for (User *U : IIP->users()) {
109  Value *Ptr = nullptr;
110  if (LoadInst *LoadI = dyn_cast<LoadInst>(U)) {
111  Ptr = LoadI->getPointerOperand();
112  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
113  Ptr = SI->getPointerOperand();
114  } else if (GetElementPtrInst *GI = dyn_cast<GetElementPtrInst>(U)) {
115  Ptr = GI->getPointerOperand();
116  }
117 
118  if (Ptr && Ptr == IIP)
119  return true;
120  }
121  return false;
122  };
123 
124  if (!HasPointerUse(IntToPtr))
125  return nullptr;
126 
127  if (DL.getPointerSizeInBits(IntToPtr->getAddressSpace()) !=
128  DL.getTypeSizeInBits(IntToPtr->getOperand(0)->getType()))
129  return nullptr;
130 
131  SmallVector<Value *, 4> AvailablePtrVals;
132  for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) {
133  Value *Arg = PN.getIncomingValue(i);
134 
135  // First look backward:
136  if (auto *PI = dyn_cast<PtrToIntInst>(Arg)) {
137  AvailablePtrVals.emplace_back(PI->getOperand(0));
138  continue;
139  }
140 
141  // Next look forward:
142  Value *ArgIntToPtr = nullptr;
143  for (User *U : Arg->users()) {
144  if (isa<IntToPtrInst>(U) && U->getType() == IntToPtr->getType() &&
145  (DT.dominates(cast<Instruction>(U), PN.getIncomingBlock(i)) ||
146  cast<Instruction>(U)->getParent() == PN.getIncomingBlock(i))) {
147  ArgIntToPtr = U;
148  break;
149  }
150  }
151 
152  if (ArgIntToPtr) {
153  AvailablePtrVals.emplace_back(ArgIntToPtr);
154  continue;
155  }
156 
157  // If Arg is defined by a PHI, allow it. This will also create
158  // more opportunities iteratively.
159  if (isa<PHINode>(Arg)) {
160  AvailablePtrVals.emplace_back(Arg);
161  continue;
162  }
163 
164  // For a single use integer load:
165  auto *LoadI = dyn_cast<LoadInst>(Arg);
166  if (!LoadI)
167  return nullptr;
168 
169  if (!LoadI->hasOneUse())
170  return nullptr;
171 
172  // Push the integer typed Load instruction into the available
173  // value set, and fix it up later when the pointer typed PHI
174  // is synthesized.
175  AvailablePtrVals.emplace_back(LoadI);
176  }
177 
178  // Now search for a matching PHI
179  auto *BB = PN.getParent();
180  assert(AvailablePtrVals.size() == PN.getNumIncomingValues() &&
181  "Not enough available ptr typed incoming values");
182  PHINode *MatchingPtrPHI = nullptr;
183  unsigned NumPhis = 0;
184  for (auto II = BB->begin(), EI = BasicBlock::iterator(BB->getFirstNonPHI());
185  II != EI; II++, NumPhis++) {
186  // FIXME: consider handling this in AggressiveInstCombine
187  if (NumPhis > MaxNumPhis)
188  return nullptr;
189  PHINode *PtrPHI = dyn_cast<PHINode>(II);
190  if (!PtrPHI || PtrPHI == &PN || PtrPHI->getType() != IntToPtr->getType())
191  continue;
192  MatchingPtrPHI = PtrPHI;
193  for (unsigned i = 0; i != PtrPHI->getNumIncomingValues(); ++i) {
194  if (AvailablePtrVals[i] !=
196  MatchingPtrPHI = nullptr;
197  break;
198  }
199  }
200 
201  if (MatchingPtrPHI)
202  break;
203  }
204 
205  if (MatchingPtrPHI) {
206  assert(MatchingPtrPHI->getType() == IntToPtr->getType() &&
207  "Phi's Type does not match with IntToPtr");
208  // The PtrToCast + IntToPtr will be simplified later
209  return CastInst::CreateBitOrPointerCast(MatchingPtrPHI,
210  IntToPtr->getOperand(0)->getType());
211  }
212 
213  // If it requires a conversion for every PHI operand, do not do it.
214  if (all_of(AvailablePtrVals, [&](Value *V) {
215  return (V->getType() != IntToPtr->getType()) || isa<IntToPtrInst>(V);
216  }))
217  return nullptr;
218 
219  // If any of the operand that requires casting is a terminator
220  // instruction, do not do it.
221  if (any_of(AvailablePtrVals, [&](Value *V) {
222  if (V->getType() == IntToPtr->getType())
223  return false;
224 
225  auto *Inst = dyn_cast<Instruction>(V);
226  return Inst && Inst->isTerminator();
227  }))
228  return nullptr;
229 
230  PHINode *NewPtrPHI = PHINode::Create(
231  IntToPtr->getType(), PN.getNumIncomingValues(), PN.getName() + ".ptr");
232 
233  InsertNewInstBefore(NewPtrPHI, PN);
235  for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) {
236  auto *IncomingBB = PN.getIncomingBlock(i);
237  auto *IncomingVal = AvailablePtrVals[i];
238 
239  if (IncomingVal->getType() == IntToPtr->getType()) {
240  NewPtrPHI->addIncoming(IncomingVal, IncomingBB);
241  continue;
242  }
243 
244 #ifndef NDEBUG
245  LoadInst *LoadI = dyn_cast<LoadInst>(IncomingVal);
246  assert((isa<PHINode>(IncomingVal) ||
247  IncomingVal->getType()->isPointerTy() ||
248  (LoadI && LoadI->hasOneUse())) &&
249  "Can not replace LoadInst with multiple uses");
250 #endif
251  // Need to insert a BitCast.
252  // For an integer Load instruction with a single use, the load + IntToPtr
253  // cast will be simplified into a pointer load:
254  // %v = load i64, i64* %a.ip, align 8
255  // %v.cast = inttoptr i64 %v to float **
256  // ==>
257  // %v.ptrp = bitcast i64 * %a.ip to float **
258  // %v.cast = load float *, float ** %v.ptrp, align 8
259  Instruction *&CI = Casts[IncomingVal];
260  if (!CI) {
261  CI = CastInst::CreateBitOrPointerCast(IncomingVal, IntToPtr->getType(),
262  IncomingVal->getName() + ".ptr");
263  if (auto *IncomingI = dyn_cast<Instruction>(IncomingVal)) {
264  BasicBlock::iterator InsertPos(IncomingI);
265  InsertPos++;
266  if (isa<PHINode>(IncomingI))
267  InsertPos = IncomingI->getParent()->getFirstInsertionPt();
268  InsertNewInstBefore(CI, *InsertPos);
269  } else {
270  auto *InsertBB = &IncomingBB->getParent()->getEntryBlock();
271  InsertNewInstBefore(CI, *InsertBB->getFirstInsertionPt());
272  }
273  }
274  NewPtrPHI->addIncoming(CI, IncomingBB);
275  }
276 
277  // The PtrToCast + IntToPtr will be simplified later
278  return CastInst::CreateBitOrPointerCast(NewPtrPHI,
279  IntToPtr->getOperand(0)->getType());
280 }
281 
282 /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
283 /// adds all have a single use, turn this into a phi and a single binop.
284 Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
285  Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
286  assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
287  unsigned Opc = FirstInst->getOpcode();
288  Value *LHSVal = FirstInst->getOperand(0);
289  Value *RHSVal = FirstInst->getOperand(1);
290 
291  Type *LHSType = LHSVal->getType();
292  Type *RHSType = RHSVal->getType();
293 
294  // Scan to see if all operands are the same opcode, and all have one use.
295  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
297  if (!I || I->getOpcode() != Opc || !I->hasOneUse() ||
298  // Verify type of the LHS matches so we don't fold cmp's of different
299  // types.
300  I->getOperand(0)->getType() != LHSType ||
301  I->getOperand(1)->getType() != RHSType)
302  return nullptr;
303 
304  // If they are CmpInst instructions, check their predicates
305  if (CmpInst *CI = dyn_cast<CmpInst>(I))
306  if (CI->getPredicate() != cast<CmpInst>(FirstInst)->getPredicate())
307  return nullptr;
308 
309  // Keep track of which operand needs a phi node.
310  if (I->getOperand(0) != LHSVal) LHSVal = nullptr;
311  if (I->getOperand(1) != RHSVal) RHSVal = nullptr;
312  }
313 
314  // If both LHS and RHS would need a PHI, don't do this transformation,
315  // because it would increase the number of PHIs entering the block,
316  // which leads to higher register pressure. This is especially
317  // bad when the PHIs are in the header of a loop.
318  if (!LHSVal && !RHSVal)
319  return nullptr;
320 
321  // Otherwise, this is safe to transform!
322 
323  Value *InLHS = FirstInst->getOperand(0);
324  Value *InRHS = FirstInst->getOperand(1);
325  PHINode *NewLHS = nullptr, *NewRHS = nullptr;
326  if (!LHSVal) {
327  NewLHS = PHINode::Create(LHSType, PN.getNumIncomingValues(),
328  FirstInst->getOperand(0)->getName() + ".pn");
329  NewLHS->addIncoming(InLHS, PN.getIncomingBlock(0));
330  InsertNewInstBefore(NewLHS, PN);
331  LHSVal = NewLHS;
332  }
333 
334  if (!RHSVal) {
335  NewRHS = PHINode::Create(RHSType, PN.getNumIncomingValues(),
336  FirstInst->getOperand(1)->getName() + ".pn");
337  NewRHS->addIncoming(InRHS, PN.getIncomingBlock(0));
338  InsertNewInstBefore(NewRHS, PN);
339  RHSVal = NewRHS;
340  }
341 
342  // Add all operands to the new PHIs.
343  if (NewLHS || NewRHS) {
344  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
345  Instruction *InInst = cast<Instruction>(PN.getIncomingValue(i));
346  if (NewLHS) {
347  Value *NewInLHS = InInst->getOperand(0);
348  NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i));
349  }
350  if (NewRHS) {
351  Value *NewInRHS = InInst->getOperand(1);
352  NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i));
353  }
354  }
355  }
356 
357  if (CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst)) {
358  CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
359  LHSVal, RHSVal);
360  PHIArgMergedDebugLoc(NewCI, PN);
361  return NewCI;
362  }
363 
364  BinaryOperator *BinOp = cast<BinaryOperator>(FirstInst);
365  BinaryOperator *NewBinOp =
366  BinaryOperator::Create(BinOp->getOpcode(), LHSVal, RHSVal);
367 
368  NewBinOp->copyIRFlags(PN.getIncomingValue(0));
369 
370  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
371  NewBinOp->andIRFlags(PN.getIncomingValue(i));
372 
373  PHIArgMergedDebugLoc(NewBinOp, PN);
374  return NewBinOp;
375 }
376 
377 Instruction *InstCombiner::FoldPHIArgGEPIntoPHI(PHINode &PN) {
378  GetElementPtrInst *FirstInst =cast<GetElementPtrInst>(PN.getIncomingValue(0));
379 
380  SmallVector<Value*, 16> FixedOperands(FirstInst->op_begin(),
381  FirstInst->op_end());
382  // This is true if all GEP bases are allocas and if all indices into them are
383  // constants.
384  bool AllBasePointersAreAllocas = true;
385 
386  // We don't want to replace this phi if the replacement would require
387  // more than one phi, which leads to higher register pressure. This is
388  // especially bad when the PHIs are in the header of a loop.
389  bool NeededPhi = false;
390 
391  bool AllInBounds = true;
392 
393  // Scan to see if all operands are the same opcode, and all have one use.
394  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
396  if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() ||
397  GEP->getNumOperands() != FirstInst->getNumOperands())
398  return nullptr;
399 
400  AllInBounds &= GEP->isInBounds();
401 
402  // Keep track of whether or not all GEPs are of alloca pointers.
403  if (AllBasePointersAreAllocas &&
404  (!isa<AllocaInst>(GEP->getOperand(0)) ||
405  !GEP->hasAllConstantIndices()))
406  AllBasePointersAreAllocas = false;
407 
408  // Compare the operand lists.
409  for (unsigned op = 0, e = FirstInst->getNumOperands(); op != e; ++op) {
410  if (FirstInst->getOperand(op) == GEP->getOperand(op))
411  continue;
412 
413  // Don't merge two GEPs when two operands differ (introducing phi nodes)
414  // if one of the PHIs has a constant for the index. The index may be
415  // substantially cheaper to compute for the constants, so making it a
416  // variable index could pessimize the path. This also handles the case
417  // for struct indices, which must always be constant.
418  if (isa<ConstantInt>(FirstInst->getOperand(op)) ||
419  isa<ConstantInt>(GEP->getOperand(op)))
420  return nullptr;
421 
422  if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType())
423  return nullptr;
424 
425  // If we already needed a PHI for an earlier operand, and another operand
426  // also requires a PHI, we'd be introducing more PHIs than we're
427  // eliminating, which increases register pressure on entry to the PHI's
428  // block.
429  if (NeededPhi)
430  return nullptr;
431 
432  FixedOperands[op] = nullptr; // Needs a PHI.
433  NeededPhi = true;
434  }
435  }
436 
437  // If all of the base pointers of the PHI'd GEPs are from allocas, don't
438  // bother doing this transformation. At best, this will just save a bit of
439  // offset calculation, but all the predecessors will have to materialize the
440  // stack address into a register anyway. We'd actually rather *clone* the
441  // load up into the predecessors so that we have a load of a gep of an alloca,
442  // which can usually all be folded into the load.
443  if (AllBasePointersAreAllocas)
444  return nullptr;
445 
446  // Otherwise, this is safe to transform. Insert PHI nodes for each operand
447  // that is variable.
448  SmallVector<PHINode*, 16> OperandPhis(FixedOperands.size());
449 
450  bool HasAnyPHIs = false;
451  for (unsigned i = 0, e = FixedOperands.size(); i != e; ++i) {
452  if (FixedOperands[i]) continue; // operand doesn't need a phi.
453  Value *FirstOp = FirstInst->getOperand(i);
454  PHINode *NewPN = PHINode::Create(FirstOp->getType(), e,
455  FirstOp->getName()+".pn");
456  InsertNewInstBefore(NewPN, PN);
457 
458  NewPN->addIncoming(FirstOp, PN.getIncomingBlock(0));
459  OperandPhis[i] = NewPN;
460  FixedOperands[i] = NewPN;
461  HasAnyPHIs = true;
462  }
463 
464 
465  // Add all operands to the new PHIs.
466  if (HasAnyPHIs) {
467  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
468  GetElementPtrInst *InGEP =cast<GetElementPtrInst>(PN.getIncomingValue(i));
469  BasicBlock *InBB = PN.getIncomingBlock(i);
470 
471  for (unsigned op = 0, e = OperandPhis.size(); op != e; ++op)
472  if (PHINode *OpPhi = OperandPhis[op])
473  OpPhi->addIncoming(InGEP->getOperand(op), InBB);
474  }
475  }
476 
477  Value *Base = FixedOperands[0];
478  GetElementPtrInst *NewGEP =
480  makeArrayRef(FixedOperands).slice(1));
481  if (AllInBounds) NewGEP->setIsInBounds();
482  PHIArgMergedDebugLoc(NewGEP, PN);
483  return NewGEP;
484 }
485 
486 
487 /// Return true if we know that it is safe to sink the load out of the block
488 /// that defines it. This means that it must be obvious the value of the load is
489 /// not changed from the point of the load to the end of the block it is in.
490 ///
491 /// Finally, it is safe, but not profitable, to sink a load targeting a
492 /// non-address-taken alloca. Doing so will cause us to not promote the alloca
493 /// to a register.
495  BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end();
496 
497  for (++BBI; BBI != E; ++BBI)
498  if (BBI->mayWriteToMemory())
499  return false;
500 
501  // Check for non-address taken alloca. If not address-taken already, it isn't
502  // profitable to do this xform.
503  if (AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
504  bool isAddressTaken = false;
505  for (User *U : AI->users()) {
506  if (isa<LoadInst>(U)) continue;
507  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
508  // If storing TO the alloca, then the address isn't taken.
509  if (SI->getOperand(1) == AI) continue;
510  }
511  isAddressTaken = true;
512  break;
513  }
514 
515  if (!isAddressTaken && AI->isStaticAlloca())
516  return false;
517  }
518 
519  // If this load is a load from a GEP with a constant offset from an alloca,
520  // then we don't want to sink it. In its present form, it will be
521  // load [constant stack offset]. Sinking it will cause us to have to
522  // materialize the stack addresses in each predecessor in a register only to
523  // do a shared load from register in the successor.
524  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(L->getOperand(0)))
525  if (AllocaInst *AI = dyn_cast<AllocaInst>(GEP->getOperand(0)))
526  if (AI->isStaticAlloca() && GEP->hasAllConstantIndices())
527  return false;
528 
529  return true;
530 }
531 
532 Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
533  LoadInst *FirstLI = cast<LoadInst>(PN.getIncomingValue(0));
534 
535  // FIXME: This is overconservative; this transform is allowed in some cases
536  // for atomic operations.
537  if (FirstLI->isAtomic())
538  return nullptr;
539 
540  // When processing loads, we need to propagate two bits of information to the
541  // sunk load: whether it is volatile, and what its alignment is. We currently
542  // don't sink loads when some have their alignment specified and some don't.
543  // visitLoadInst will propagate an alignment onto the load when TD is around,
544  // and if TD isn't around, we can't handle the mixed case.
545  bool isVolatile = FirstLI->isVolatile();
546  unsigned LoadAlignment = FirstLI->getAlignment();
547  unsigned LoadAddrSpace = FirstLI->getPointerAddressSpace();
548 
549  // We can't sink the load if the loaded value could be modified between the
550  // load and the PHI.
551  if (FirstLI->getParent() != PN.getIncomingBlock(0) ||
553  return nullptr;
554 
555  // If the PHI is of volatile loads and the load block has multiple
556  // successors, sinking it would remove a load of the volatile value from
557  // the path through the other successor.
558  if (isVolatile &&
559  FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1)
560  return nullptr;
561 
562  // Check to see if all arguments are the same operation.
563  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
565  if (!LI || !LI->hasOneUse())
566  return nullptr;
567 
568  // We can't sink the load if the loaded value could be modified between
569  // the load and the PHI.
570  if (LI->isVolatile() != isVolatile ||
571  LI->getParent() != PN.getIncomingBlock(i) ||
572  LI->getPointerAddressSpace() != LoadAddrSpace ||
574  return nullptr;
575 
576  // If some of the loads have an alignment specified but not all of them,
577  // we can't do the transformation.
578  if ((LoadAlignment != 0) != (LI->getAlignment() != 0))
579  return nullptr;
580 
581  LoadAlignment = std::min(LoadAlignment, LI->getAlignment());
582 
583  // If the PHI is of volatile loads and the load block has multiple
584  // successors, sinking it would remove a load of the volatile value from
585  // the path through the other successor.
586  if (isVolatile &&
587  LI->getParent()->getTerminator()->getNumSuccessors() != 1)
588  return nullptr;
589  }
590 
591  // Okay, they are all the same operation. Create a new PHI node of the
592  // correct type, and PHI together all of the LHS's of the instructions.
593  PHINode *NewPN = PHINode::Create(FirstLI->getOperand(0)->getType(),
595  PN.getName()+".in");
596 
597  Value *InVal = FirstLI->getOperand(0);
598  NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
599  LoadInst *NewLI = new LoadInst(NewPN, "", isVolatile, LoadAlignment);
600 
601  unsigned KnownIDs[] = {
612  };
613 
614  for (unsigned ID : KnownIDs)
615  NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
616 
617  // Add all operands to the new PHI and combine TBAA metadata.
618  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
619  LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
620  combineMetadata(NewLI, LI, KnownIDs, true);
621  Value *NewInVal = LI->getOperand(0);
622  if (NewInVal != InVal)
623  InVal = nullptr;
624  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
625  }
626 
627  if (InVal) {
628  // The new PHI unions all of the same values together. This is really
629  // common, so we handle it intelligently here for compile-time speed.
630  NewLI->setOperand(0, InVal);
631  delete NewPN;
632  } else {
633  InsertNewInstBefore(NewPN, PN);
634  }
635 
636  // If this was a volatile load that we are merging, make sure to loop through
637  // and mark all the input loads as non-volatile. If we don't do this, we will
638  // insert a new volatile load and the old ones will not be deletable.
639  if (isVolatile)
640  for (Value *IncValue : PN.incoming_values())
641  cast<LoadInst>(IncValue)->setVolatile(false);
642 
643  PHIArgMergedDebugLoc(NewLI, PN);
644  return NewLI;
645 }
646 
647 /// TODO: This function could handle other cast types, but then it might
648 /// require special-casing a cast from the 'i1' type. See the comment in
649 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
650 Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
651  // We cannot create a new instruction after the PHI if the terminator is an
652  // EHPad because there is no valid insertion point.
653  if (Instruction *TI = Phi.getParent()->getTerminator())
654  if (TI->isEHPad())
655  return nullptr;
656 
657  // Early exit for the common case of a phi with two operands. These are
658  // handled elsewhere. See the comment below where we check the count of zexts
659  // and constants for more details.
660  unsigned NumIncomingValues = Phi.getNumIncomingValues();
661  if (NumIncomingValues < 3)
662  return nullptr;
663 
664  // Find the narrower type specified by the first zext.
665  Type *NarrowType = nullptr;
666  for (Value *V : Phi.incoming_values()) {
667  if (auto *Zext = dyn_cast<ZExtInst>(V)) {
668  NarrowType = Zext->getSrcTy();
669  break;
670  }
671  }
672  if (!NarrowType)
673  return nullptr;
674 
675  // Walk the phi operands checking that we only have zexts or constants that
676  // we can shrink for free. Store the new operands for the new phi.
677  SmallVector<Value *, 4> NewIncoming;
678  unsigned NumZexts = 0;
679  unsigned NumConsts = 0;
680  for (Value *V : Phi.incoming_values()) {
681  if (auto *Zext = dyn_cast<ZExtInst>(V)) {
682  // All zexts must be identical and have one use.
683  if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUse())
684  return nullptr;
685  NewIncoming.push_back(Zext->getOperand(0));
686  NumZexts++;
687  } else if (auto *C = dyn_cast<Constant>(V)) {
688  // Make sure that constants can fit in the new type.
689  Constant *Trunc = ConstantExpr::getTrunc(C, NarrowType);
690  if (ConstantExpr::getZExt(Trunc, C->getType()) != C)
691  return nullptr;
692  NewIncoming.push_back(Trunc);
693  NumConsts++;
694  } else {
695  // If it's not a cast or a constant, bail out.
696  return nullptr;
697  }
698  }
699 
700  // The more common cases of a phi with no constant operands or just one
701  // variable operand are handled by FoldPHIArgOpIntoPHI() and foldOpIntoPhi()
702  // respectively. foldOpIntoPhi() wants to do the opposite transform that is
703  // performed here. It tries to replicate a cast in the phi operand's basic
704  // block to expose other folding opportunities. Thus, InstCombine will
705  // infinite loop without this check.
706  if (NumConsts == 0 || NumZexts < 2)
707  return nullptr;
708 
709  // All incoming values are zexts or constants that are safe to truncate.
710  // Create a new phi node of the narrow type, phi together all of the new
711  // operands, and zext the result back to the original type.
712  PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues,
713  Phi.getName() + ".shrunk");
714  for (unsigned i = 0; i != NumIncomingValues; ++i)
715  NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i));
716 
717  InsertNewInstBefore(NewPhi, Phi);
718  return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
719 }
720 
721 /// If all operands to a PHI node are the same "unary" operator and they all are
722 /// only used by the PHI, PHI together their inputs, and do the operation once,
723 /// to the result of the PHI.
724 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
725  // We cannot create a new instruction after the PHI if the terminator is an
726  // EHPad because there is no valid insertion point.
727  if (Instruction *TI = PN.getParent()->getTerminator())
728  if (TI->isEHPad())
729  return nullptr;
730 
731  Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
732 
733  if (isa<GetElementPtrInst>(FirstInst))
734  return FoldPHIArgGEPIntoPHI(PN);
735  if (isa<LoadInst>(FirstInst))
736  return FoldPHIArgLoadIntoPHI(PN);
737 
738  // Scan the instruction, looking for input operations that can be folded away.
739  // If all input operands to the phi are the same instruction (e.g. a cast from
740  // the same type or "+42") we can pull the operation through the PHI, reducing
741  // code size and simplifying code.
742  Constant *ConstantOp = nullptr;
743  Type *CastSrcTy = nullptr;
744 
745  if (isa<CastInst>(FirstInst)) {
746  CastSrcTy = FirstInst->getOperand(0)->getType();
747 
748  // Be careful about transforming integer PHIs. We don't want to pessimize
749  // the code by turning an i32 into an i1293.
750  if (PN.getType()->isIntegerTy() && CastSrcTy->isIntegerTy()) {
751  if (!shouldChangeType(PN.getType(), CastSrcTy))
752  return nullptr;
753  }
754  } else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
755  // Can fold binop, compare or shift here if the RHS is a constant,
756  // otherwise call FoldPHIArgBinOpIntoPHI.
757  ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
758  if (!ConstantOp)
759  return FoldPHIArgBinOpIntoPHI(PN);
760  } else {
761  return nullptr; // Cannot fold this operation.
762  }
763 
764  // Check to see if all arguments are the same operation.
765  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
767  if (!I || !I->hasOneUse() || !I->isSameOperationAs(FirstInst))
768  return nullptr;
769  if (CastSrcTy) {
770  if (I->getOperand(0)->getType() != CastSrcTy)
771  return nullptr; // Cast operation must match.
772  } else if (I->getOperand(1) != ConstantOp) {
773  return nullptr;
774  }
775  }
776 
777  // Okay, they are all the same operation. Create a new PHI node of the
778  // correct type, and PHI together all of the LHS's of the instructions.
779  PHINode *NewPN = PHINode::Create(FirstInst->getOperand(0)->getType(),
781  PN.getName()+".in");
782 
783  Value *InVal = FirstInst->getOperand(0);
784  NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
785 
786  // Add all operands to the new PHI.
787  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
788  Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
789  if (NewInVal != InVal)
790  InVal = nullptr;
791  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
792  }
793 
794  Value *PhiVal;
795  if (InVal) {
796  // The new PHI unions all of the same values together. This is really
797  // common, so we handle it intelligently here for compile-time speed.
798  PhiVal = InVal;
799  delete NewPN;
800  } else {
801  InsertNewInstBefore(NewPN, PN);
802  PhiVal = NewPN;
803  }
804 
805  // Insert and return the new operation.
806  if (CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
807  CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), PhiVal,
808  PN.getType());
809  PHIArgMergedDebugLoc(NewCI, PN);
810  return NewCI;
811  }
812 
813  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
814  BinOp = BinaryOperator::Create(BinOp->getOpcode(), PhiVal, ConstantOp);
815  BinOp->copyIRFlags(PN.getIncomingValue(0));
816 
817  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
818  BinOp->andIRFlags(PN.getIncomingValue(i));
819 
820  PHIArgMergedDebugLoc(BinOp, PN);
821  return BinOp;
822  }
823 
824  CmpInst *CIOp = cast<CmpInst>(FirstInst);
825  CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
826  PhiVal, ConstantOp);
827  PHIArgMergedDebugLoc(NewCI, PN);
828  return NewCI;
829 }
830 
831 /// Return true if this PHI node is only used by a PHI node cycle that is dead.
832 static bool DeadPHICycle(PHINode *PN,
833  SmallPtrSetImpl<PHINode*> &PotentiallyDeadPHIs) {
834  if (PN->use_empty()) return true;
835  if (!PN->hasOneUse()) return false;
836 
837  // Remember this node, and if we find the cycle, return.
838  if (!PotentiallyDeadPHIs.insert(PN).second)
839  return true;
840 
841  // Don't scan crazily complex things.
842  if (PotentiallyDeadPHIs.size() == 16)
843  return false;
844 
845  if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
846  return DeadPHICycle(PU, PotentiallyDeadPHIs);
847 
848  return false;
849 }
850 
851 /// Return true if this phi node is always equal to NonPhiInVal.
852 /// This happens with mutually cyclic phi nodes like:
853 /// z = some value; x = phi (y, z); y = phi (x, z)
854 static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
855  SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
856  // See if we already saw this PHI node.
857  if (!ValueEqualPHIs.insert(PN).second)
858  return true;
859 
860  // Don't scan crazily complex things.
861  if (ValueEqualPHIs.size() == 16)
862  return false;
863 
864  // Scan the operands to see if they are either phi nodes or are equal to
865  // the value.
866  for (Value *Op : PN->incoming_values()) {
867  if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
868  if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
869  return false;
870  } else if (Op != NonPhiInVal)
871  return false;
872  }
873 
874  return true;
875 }
876 
877 /// Return an existing non-zero constant if this phi node has one, otherwise
878 /// return constant 1.
880  assert(isa<IntegerType>(PN.getType()) && "Expect only integer type phi");
881  for (Value *V : PN.operands())
882  if (auto *ConstVA = dyn_cast<ConstantInt>(V))
883  if (!ConstVA->isZero())
884  return ConstVA;
885  return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
886 }
887 
888 namespace {
889 struct PHIUsageRecord {
890  unsigned PHIId; // The ID # of the PHI (something determinstic to sort on)
891  unsigned Shift; // The amount shifted.
892  Instruction *Inst; // The trunc instruction.
893 
894  PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
895  : PHIId(pn), Shift(Sh), Inst(User) {}
896 
897  bool operator<(const PHIUsageRecord &RHS) const {
898  if (PHIId < RHS.PHIId) return true;
899  if (PHIId > RHS.PHIId) return false;
900  if (Shift < RHS.Shift) return true;
901  if (Shift > RHS.Shift) return false;
902  return Inst->getType()->getPrimitiveSizeInBits() <
903  RHS.Inst->getType()->getPrimitiveSizeInBits();
904  }
905 };
906 
907 struct LoweredPHIRecord {
908  PHINode *PN; // The PHI that was lowered.
909  unsigned Shift; // The amount shifted.
910  unsigned Width; // The width extracted.
911 
912  LoweredPHIRecord(PHINode *pn, unsigned Sh, Type *Ty)
913  : PN(pn), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
914 
915  // Ctor form used by DenseMap.
916  LoweredPHIRecord(PHINode *pn, unsigned Sh)
917  : PN(pn), Shift(Sh), Width(0) {}
918 };
919 }
920 
921 namespace llvm {
922  template<>
923  struct DenseMapInfo<LoweredPHIRecord> {
924  static inline LoweredPHIRecord getEmptyKey() {
925  return LoweredPHIRecord(nullptr, 0);
926  }
927  static inline LoweredPHIRecord getTombstoneKey() {
928  return LoweredPHIRecord(nullptr, 1);
929  }
930  static unsigned getHashValue(const LoweredPHIRecord &Val) {
931  return DenseMapInfo<PHINode*>::getHashValue(Val.PN) ^ (Val.Shift>>3) ^
932  (Val.Width>>3);
933  }
934  static bool isEqual(const LoweredPHIRecord &LHS,
935  const LoweredPHIRecord &RHS) {
936  return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift &&
937  LHS.Width == RHS.Width;
938  }
939  };
940 }
941 
942 
943 /// This is an integer PHI and we know that it has an illegal type: see if it is
944 /// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
945 /// the various pieces being extracted. This sort of thing is introduced when
946 /// SROA promotes an aggregate to large integer values.
947 ///
948 /// TODO: The user of the trunc may be an bitcast to float/double/vector or an
949 /// inttoptr. We should produce new PHIs in the right type.
950 ///
952  // PHIUsers - Keep track of all of the truncated values extracted from a set
953  // of PHIs, along with their offset. These are the things we want to rewrite.
955 
956  // PHIs are often mutually cyclic, so we keep track of a whole set of PHI
957  // nodes which are extracted from. PHIsToSlice is a set we use to avoid
958  // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to
959  // check the uses of (to ensure they are all extracts).
960  SmallVector<PHINode*, 8> PHIsToSlice;
961  SmallPtrSet<PHINode*, 8> PHIsInspected;
962 
963  PHIsToSlice.push_back(&FirstPhi);
964  PHIsInspected.insert(&FirstPhi);
965 
966  for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {
967  PHINode *PN = PHIsToSlice[PHIId];
968 
969  // Scan the input list of the PHI. If any input is an invoke, and if the
970  // input is defined in the predecessor, then we won't be split the critical
971  // edge which is required to insert a truncate. Because of this, we have to
972  // bail out.
973  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
975  if (!II) continue;
976  if (II->getParent() != PN->getIncomingBlock(i))
977  continue;
978 
979  // If we have a phi, and if it's directly in the predecessor, then we have
980  // a critical edge where we need to put the truncate. Since we can't
981  // split the edge in instcombine, we have to bail out.
982  return nullptr;
983  }
984 
985  for (User *U : PN->users()) {
986  Instruction *UserI = cast<Instruction>(U);
987 
988  // If the user is a PHI, inspect its uses recursively.
989  if (PHINode *UserPN = dyn_cast<PHINode>(UserI)) {
990  if (PHIsInspected.insert(UserPN).second)
991  PHIsToSlice.push_back(UserPN);
992  continue;
993  }
994 
995  // Truncates are always ok.
996  if (isa<TruncInst>(UserI)) {
997  PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));
998  continue;
999  }
1000 
1001  // Otherwise it must be a lshr which can only be used by one trunc.
1002  if (UserI->getOpcode() != Instruction::LShr ||
1003  !UserI->hasOneUse() || !isa<TruncInst>(UserI->user_back()) ||
1004  !isa<ConstantInt>(UserI->getOperand(1)))
1005  return nullptr;
1006 
1007  unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue();
1008  PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));
1009  }
1010  }
1011 
1012  // If we have no users, they must be all self uses, just nuke the PHI.
1013  if (PHIUsers.empty())
1014  return replaceInstUsesWith(FirstPhi, UndefValue::get(FirstPhi.getType()));
1015 
1016  // If this phi node is transformable, create new PHIs for all the pieces
1017  // extracted out of it. First, sort the users by their offset and size.
1018  array_pod_sort(PHIUsers.begin(), PHIUsers.end());
1019 
1020  LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';
1021  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i) dbgs()
1022  << "AND USER PHI #" << i << ": " << *PHIsToSlice[i] << '\n';);
1023 
1024  // PredValues - This is a temporary used when rewriting PHI nodes. It is
1025  // hoisted out here to avoid construction/destruction thrashing.
1026  DenseMap<BasicBlock*, Value*> PredValues;
1027 
1028  // ExtractedVals - Each new PHI we introduce is saved here so we don't
1029  // introduce redundant PHIs.
1031 
1032  for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {
1033  unsigned PHIId = PHIUsers[UserI].PHIId;
1034  PHINode *PN = PHIsToSlice[PHIId];
1035  unsigned Offset = PHIUsers[UserI].Shift;
1036  Type *Ty = PHIUsers[UserI].Inst->getType();
1037 
1038  PHINode *EltPHI;
1039 
1040  // If we've already lowered a user like this, reuse the previously lowered
1041  // value.
1042  if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {
1043 
1044  // Otherwise, Create the new PHI node for this user.
1045  EltPHI = PHINode::Create(Ty, PN->getNumIncomingValues(),
1046  PN->getName()+".off"+Twine(Offset), PN);
1047  assert(EltPHI->getType() != PN->getType() &&
1048  "Truncate didn't shrink phi?");
1049 
1050  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1051  BasicBlock *Pred = PN->getIncomingBlock(i);
1052  Value *&PredVal = PredValues[Pred];
1053 
1054  // If we already have a value for this predecessor, reuse it.
1055  if (PredVal) {
1056  EltPHI->addIncoming(PredVal, Pred);
1057  continue;
1058  }
1059 
1060  // Handle the PHI self-reuse case.
1061  Value *InVal = PN->getIncomingValue(i);
1062  if (InVal == PN) {
1063  PredVal = EltPHI;
1064  EltPHI->addIncoming(PredVal, Pred);
1065  continue;
1066  }
1067 
1068  if (PHINode *InPHI = dyn_cast<PHINode>(PN)) {
1069  // If the incoming value was a PHI, and if it was one of the PHIs we
1070  // already rewrote it, just use the lowered value.
1071  if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {
1072  PredVal = Res;
1073  EltPHI->addIncoming(PredVal, Pred);
1074  continue;
1075  }
1076  }
1077 
1078  // Otherwise, do an extract in the predecessor.
1079  Builder.SetInsertPoint(Pred->getTerminator());
1080  Value *Res = InVal;
1081  if (Offset)
1082  Res = Builder.CreateLShr(Res, ConstantInt::get(InVal->getType(),
1083  Offset), "extract");
1084  Res = Builder.CreateTrunc(Res, Ty, "extract.t");
1085  PredVal = Res;
1086  EltPHI->addIncoming(Res, Pred);
1087 
1088  // If the incoming value was a PHI, and if it was one of the PHIs we are
1089  // rewriting, we will ultimately delete the code we inserted. This
1090  // means we need to revisit that PHI to make sure we extract out the
1091  // needed piece.
1092  if (PHINode *OldInVal = dyn_cast<PHINode>(PN->getIncomingValue(i)))
1093  if (PHIsInspected.count(OldInVal)) {
1094  unsigned RefPHIId =
1095  find(PHIsToSlice, OldInVal) - PHIsToSlice.begin();
1096  PHIUsers.push_back(PHIUsageRecord(RefPHIId, Offset,
1097  cast<Instruction>(Res)));
1098  ++UserE;
1099  }
1100  }
1101  PredValues.clear();
1102 
1103  LLVM_DEBUG(dbgs() << " Made element PHI for offset " << Offset << ": "
1104  << *EltPHI << '\n');
1105  ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;
1106  }
1107 
1108  // Replace the use of this piece with the PHI node.
1109  replaceInstUsesWith(*PHIUsers[UserI].Inst, EltPHI);
1110  }
1111 
1112  // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
1113  // with undefs.
1114  Value *Undef = UndefValue::get(FirstPhi.getType());
1115  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
1116  replaceInstUsesWith(*PHIsToSlice[i], Undef);
1117  return replaceInstUsesWith(FirstPhi, Undef);
1118 }
1119 
1120 // PHINode simplification
1121 //
1123  if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
1124  return replaceInstUsesWith(PN, V);
1125 
1126  if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
1127  return Result;
1128 
1129  // If all PHI operands are the same operation, pull them through the PHI,
1130  // reducing code size.
1131  if (isa<Instruction>(PN.getIncomingValue(0)) &&
1132  isa<Instruction>(PN.getIncomingValue(1)) &&
1133  cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
1134  cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
1135  // FIXME: The hasOneUse check will fail for PHIs that use the value more
1136  // than themselves more than once.
1137  PN.getIncomingValue(0)->hasOneUse())
1138  if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
1139  return Result;
1140 
1141  // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
1142  // this PHI only has a single use (a PHI), and if that PHI only has one use (a
1143  // PHI)... break the cycle.
1144  if (PN.hasOneUse()) {
1145  if (Instruction *Result = FoldIntegerTypedPHI(PN))
1146  return Result;
1147 
1148  Instruction *PHIUser = cast<Instruction>(PN.user_back());
1149  if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
1150  SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
1151  PotentiallyDeadPHIs.insert(&PN);
1152  if (DeadPHICycle(PU, PotentiallyDeadPHIs))
1153  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1154  }
1155 
1156  // If this phi has a single use, and if that use just computes a value for
1157  // the next iteration of a loop, delete the phi. This occurs with unused
1158  // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
1159  // common case here is good because the only other things that catch this
1160  // are induction variable analysis (sometimes) and ADCE, which is only run
1161  // late.
1162  if (PHIUser->hasOneUse() &&
1163  (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
1164  PHIUser->user_back() == &PN) {
1165  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1166  }
1167  // When a PHI is used only to be compared with zero, it is safe to replace
1168  // an incoming value proved as known nonzero with any non-zero constant.
1169  // For example, in the code below, the incoming value %v can be replaced
1170  // with any non-zero constant based on the fact that the PHI is only used to
1171  // be compared with zero and %v is a known non-zero value:
1172  // %v = select %cond, 1, 2
1173  // %p = phi [%v, BB] ...
1174  // icmp eq, %p, 0
1175  auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
1176  // FIXME: To be simple, handle only integer type for now.
1177  if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
1178  match(CmpInst->getOperand(1), m_Zero())) {
1179  ConstantInt *NonZeroConst = nullptr;
1180  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1181  Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
1182  Value *VA = PN.getIncomingValue(i);
1183  if (isKnownNonZero(VA, DL, 0, &AC, CtxI, &DT)) {
1184  if (!NonZeroConst)
1185  NonZeroConst = GetAnyNonZeroConstInt(PN);
1186  PN.setIncomingValue(i, NonZeroConst);
1187  }
1188  }
1189  }
1190  }
1191 
1192  // We sometimes end up with phi cycles that non-obviously end up being the
1193  // same value, for example:
1194  // z = some value; x = phi (y, z); y = phi (x, z)
1195  // where the phi nodes don't necessarily need to be in the same block. Do a
1196  // quick check to see if the PHI node only contains a single non-phi value, if
1197  // so, scan to see if the phi cycle is actually equal to that value.
1198  {
1199  unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();
1200  // Scan for the first non-phi operand.
1201  while (InValNo != NumIncomingVals &&
1202  isa<PHINode>(PN.getIncomingValue(InValNo)))
1203  ++InValNo;
1204 
1205  if (InValNo != NumIncomingVals) {
1206  Value *NonPhiInVal = PN.getIncomingValue(InValNo);
1207 
1208  // Scan the rest of the operands to see if there are any conflicts, if so
1209  // there is no need to recursively scan other phis.
1210  for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
1211  Value *OpVal = PN.getIncomingValue(InValNo);
1212  if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
1213  break;
1214  }
1215 
1216  // If we scanned over all operands, then we have one unique value plus
1217  // phi values. Scan PHI nodes to see if they all merge in each other or
1218  // the value.
1219  if (InValNo == NumIncomingVals) {
1220  SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
1221  if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
1222  return replaceInstUsesWith(PN, NonPhiInVal);
1223  }
1224  }
1225  }
1226 
1227  // If there are multiple PHIs, sort their operands so that they all list
1228  // the blocks in the same order. This will help identical PHIs be eliminated
1229  // by other passes. Other passes shouldn't depend on this for correctness
1230  // however.
1231  PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());
1232  if (&PN != FirstPN)
1233  for (unsigned i = 0, e = FirstPN->getNumIncomingValues(); i != e; ++i) {
1234  BasicBlock *BBA = PN.getIncomingBlock(i);
1235  BasicBlock *BBB = FirstPN->getIncomingBlock(i);
1236  if (BBA != BBB) {
1237  Value *VA = PN.getIncomingValue(i);
1238  unsigned j = PN.getBasicBlockIndex(BBB);
1239  Value *VB = PN.getIncomingValue(j);
1240  PN.setIncomingBlock(i, BBB);
1241  PN.setIncomingValue(i, VB);
1242  PN.setIncomingBlock(j, BBA);
1243  PN.setIncomingValue(j, VA);
1244  // NOTE: Instcombine normally would want us to "return &PN" if we
1245  // modified any of the operands of an instruction. However, since we
1246  // aren't adding or removing uses (just rearranging them) we don't do
1247  // this in this case.
1248  }
1249  }
1250 
1251  // If this is an integer PHI and we know that it has an illegal type, see if
1252  // it is only used by trunc or trunc(lshr) operations. If so, we split the
1253  // PHI into the various pieces being extracted. This sort of thing is
1254  // introduced when SROA promotes an aggregate to a single large integer type.
1255  if (PN.getType()->isIntegerTy() &&
1256  !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
1257  if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
1258  return Res;
1259 
1260  return nullptr;
1261 }
uint64_t CallInst * C
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:636
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:376
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one...
This class represents lattice values for constants.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:316
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
static LoweredPHIRecord getEmptyKey()
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:880
bool isTerminator() const
Definition: Instruction.h:129
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1186
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
#define op(i)
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
op_iterator op_begin()
Definition: User.h:230
static ConstantInt * GetAnyNonZeroConstInt(PHINode &PN)
Return an existing non-zero constant if this phi node has one, otherwise return constant 1...
static bool isSafeAndProfitableToSinkLoad(LoadInst *L)
Return true if we know that it is safe to sink the load out of the block that defines it...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:48
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:232
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:353
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:197
Instruction * SliceUpIllegalIntegerPHI(PHINode &PN)
This is an integer PHI and we know that it has an illegal type: see if it is only used by trunc or tr...
static bool isEqual(const LoweredPHIRecord &LHS, const LoweredPHIRecord &RHS)
Type * getSourceElementType() const
Definition: Instructions.h:951
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1665
OtherOps getOpcode() const
Get the opcode casted to the right type.
Definition: InstrTypes.h:716
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:221
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name="", Instruction *InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2274
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
An instruction for storing to memory.
Definition: Instructions.h:321
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:170
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:854
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1083
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:129
Value * getIncomingValueForBlock(const BasicBlock *BB) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
op_iterator op_end()
Definition: User.h:232
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1193
This instruction compares its operands according to the predicate given to the constructor.
op_range operands()
Definition: User.h:238
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
This class represents a cast from an integer to a pointer.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
size_t size() const
Definition: SmallVector.h:53
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Instruction * visitPHINode(PHINode &PN)
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1207
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1226
size_type size() const
Definition: SmallPtrSet.h:93
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:88
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
void setIncomingBlock(unsigned i, BasicBlock *BB)
iterator end()
Definition: BasicBlock.h:271
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:64
static cl::opt< unsigned > MaxNumPhis("instcombine-max-num-phis", cl::init(512), cl::desc("Maximum number phis to handle in intptr/ptrint folding"))
static LoweredPHIRecord getTombstoneKey()
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1637
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:622
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
Definition: DebugInfo.cpp:689
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:400
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
amdgpu Simplify well known AMD library false Value Value * Arg
static bool DeadPHICycle(PHINode *PN, SmallPtrSetImpl< PHINode *> &PotentiallyDeadPHIs)
Return true if this PHI node is only used by a PHI node cycle that is dead.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator end()
Definition: SmallVector.h:133
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:311
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:241
void emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:652
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:291
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
LLVM Value Representation.
Definition: Value.h:73
bool isEquality() const
This is just a convenience that dispatches to the subclasses.
This file provides internal interfaces used to implement the InstCombine.
static unsigned getHashValue(const LoweredPHIRecord &Val)
Invoke instruction.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
static bool isVolatile(Instruction *Inst)
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:123
op_range incoming_values()
static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal, SmallPtrSetImpl< PHINode *> &ValueEqualPHIs)
Return true if this phi node is always equal to NonPhiInVal.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
bool use_empty() const
Definition: Value.h:323
bool hasAllConstantIndices() const
Return true if all of the indices of this GEP are constant integers.
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60