LLVM  8.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 (std::all_of(AvailablePtrVals.begin(), AvailablePtrVals.end(),
215  [&](Value *V) {
216  return (V->getType() != IntToPtr->getType()) ||
217  isa<IntToPtrInst>(V);
218  }))
219  return nullptr;
220 
221  // If any of the operand that requires casting is a terminator
222  // instruction, do not do it.
223  if (std::any_of(AvailablePtrVals.begin(), AvailablePtrVals.end(),
224  [&](Value *V) {
225  return (V->getType() != IntToPtr->getType()) &&
226  isa<TerminatorInst>(V);
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[] = {
611  };
612 
613  for (unsigned ID : KnownIDs)
614  NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
615 
616  // Add all operands to the new PHI and combine TBAA metadata.
617  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
618  LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
619  combineMetadata(NewLI, LI, KnownIDs);
620  Value *NewInVal = LI->getOperand(0);
621  if (NewInVal != InVal)
622  InVal = nullptr;
623  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
624  }
625 
626  if (InVal) {
627  // The new PHI unions all of the same values together. This is really
628  // common, so we handle it intelligently here for compile-time speed.
629  NewLI->setOperand(0, InVal);
630  delete NewPN;
631  } else {
632  InsertNewInstBefore(NewPN, PN);
633  }
634 
635  // If this was a volatile load that we are merging, make sure to loop through
636  // and mark all the input loads as non-volatile. If we don't do this, we will
637  // insert a new volatile load and the old ones will not be deletable.
638  if (isVolatile)
639  for (Value *IncValue : PN.incoming_values())
640  cast<LoadInst>(IncValue)->setVolatile(false);
641 
642  PHIArgMergedDebugLoc(NewLI, PN);
643  return NewLI;
644 }
645 
646 /// TODO: This function could handle other cast types, but then it might
647 /// require special-casing a cast from the 'i1' type. See the comment in
648 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
649 Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
650  // We cannot create a new instruction after the PHI if the terminator is an
651  // EHPad because there is no valid insertion point.
652  if (TerminatorInst *TI = Phi.getParent()->getTerminator())
653  if (TI->isEHPad())
654  return nullptr;
655 
656  // Early exit for the common case of a phi with two operands. These are
657  // handled elsewhere. See the comment below where we check the count of zexts
658  // and constants for more details.
659  unsigned NumIncomingValues = Phi.getNumIncomingValues();
660  if (NumIncomingValues < 3)
661  return nullptr;
662 
663  // Find the narrower type specified by the first zext.
664  Type *NarrowType = nullptr;
665  for (Value *V : Phi.incoming_values()) {
666  if (auto *Zext = dyn_cast<ZExtInst>(V)) {
667  NarrowType = Zext->getSrcTy();
668  break;
669  }
670  }
671  if (!NarrowType)
672  return nullptr;
673 
674  // Walk the phi operands checking that we only have zexts or constants that
675  // we can shrink for free. Store the new operands for the new phi.
676  SmallVector<Value *, 4> NewIncoming;
677  unsigned NumZexts = 0;
678  unsigned NumConsts = 0;
679  for (Value *V : Phi.incoming_values()) {
680  if (auto *Zext = dyn_cast<ZExtInst>(V)) {
681  // All zexts must be identical and have one use.
682  if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUse())
683  return nullptr;
684  NewIncoming.push_back(Zext->getOperand(0));
685  NumZexts++;
686  } else if (auto *C = dyn_cast<Constant>(V)) {
687  // Make sure that constants can fit in the new type.
688  Constant *Trunc = ConstantExpr::getTrunc(C, NarrowType);
689  if (ConstantExpr::getZExt(Trunc, C->getType()) != C)
690  return nullptr;
691  NewIncoming.push_back(Trunc);
692  NumConsts++;
693  } else {
694  // If it's not a cast or a constant, bail out.
695  return nullptr;
696  }
697  }
698 
699  // The more common cases of a phi with no constant operands or just one
700  // variable operand are handled by FoldPHIArgOpIntoPHI() and foldOpIntoPhi()
701  // respectively. foldOpIntoPhi() wants to do the opposite transform that is
702  // performed here. It tries to replicate a cast in the phi operand's basic
703  // block to expose other folding opportunities. Thus, InstCombine will
704  // infinite loop without this check.
705  if (NumConsts == 0 || NumZexts < 2)
706  return nullptr;
707 
708  // All incoming values are zexts or constants that are safe to truncate.
709  // Create a new phi node of the narrow type, phi together all of the new
710  // operands, and zext the result back to the original type.
711  PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues,
712  Phi.getName() + ".shrunk");
713  for (unsigned i = 0; i != NumIncomingValues; ++i)
714  NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i));
715 
716  InsertNewInstBefore(NewPhi, Phi);
717  return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
718 }
719 
720 /// If all operands to a PHI node are the same "unary" operator and they all are
721 /// only used by the PHI, PHI together their inputs, and do the operation once,
722 /// to the result of the PHI.
723 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
724  // We cannot create a new instruction after the PHI if the terminator is an
725  // EHPad because there is no valid insertion point.
726  if (TerminatorInst *TI = PN.getParent()->getTerminator())
727  if (TI->isEHPad())
728  return nullptr;
729 
730  Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
731 
732  if (isa<GetElementPtrInst>(FirstInst))
733  return FoldPHIArgGEPIntoPHI(PN);
734  if (isa<LoadInst>(FirstInst))
735  return FoldPHIArgLoadIntoPHI(PN);
736 
737  // Scan the instruction, looking for input operations that can be folded away.
738  // If all input operands to the phi are the same instruction (e.g. a cast from
739  // the same type or "+42") we can pull the operation through the PHI, reducing
740  // code size and simplifying code.
741  Constant *ConstantOp = nullptr;
742  Type *CastSrcTy = nullptr;
743 
744  if (isa<CastInst>(FirstInst)) {
745  CastSrcTy = FirstInst->getOperand(0)->getType();
746 
747  // Be careful about transforming integer PHIs. We don't want to pessimize
748  // the code by turning an i32 into an i1293.
749  if (PN.getType()->isIntegerTy() && CastSrcTy->isIntegerTy()) {
750  if (!shouldChangeType(PN.getType(), CastSrcTy))
751  return nullptr;
752  }
753  } else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
754  // Can fold binop, compare or shift here if the RHS is a constant,
755  // otherwise call FoldPHIArgBinOpIntoPHI.
756  ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
757  if (!ConstantOp)
758  return FoldPHIArgBinOpIntoPHI(PN);
759  } else {
760  return nullptr; // Cannot fold this operation.
761  }
762 
763  // Check to see if all arguments are the same operation.
764  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
766  if (!I || !I->hasOneUse() || !I->isSameOperationAs(FirstInst))
767  return nullptr;
768  if (CastSrcTy) {
769  if (I->getOperand(0)->getType() != CastSrcTy)
770  return nullptr; // Cast operation must match.
771  } else if (I->getOperand(1) != ConstantOp) {
772  return nullptr;
773  }
774  }
775 
776  // Okay, they are all the same operation. Create a new PHI node of the
777  // correct type, and PHI together all of the LHS's of the instructions.
778  PHINode *NewPN = PHINode::Create(FirstInst->getOperand(0)->getType(),
780  PN.getName()+".in");
781 
782  Value *InVal = FirstInst->getOperand(0);
783  NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
784 
785  // Add all operands to the new PHI.
786  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
787  Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
788  if (NewInVal != InVal)
789  InVal = nullptr;
790  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
791  }
792 
793  Value *PhiVal;
794  if (InVal) {
795  // The new PHI unions all of the same values together. This is really
796  // common, so we handle it intelligently here for compile-time speed.
797  PhiVal = InVal;
798  delete NewPN;
799  } else {
800  InsertNewInstBefore(NewPN, PN);
801  PhiVal = NewPN;
802  }
803 
804  // Insert and return the new operation.
805  if (CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
806  CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), PhiVal,
807  PN.getType());
808  PHIArgMergedDebugLoc(NewCI, PN);
809  return NewCI;
810  }
811 
812  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
813  BinOp = BinaryOperator::Create(BinOp->getOpcode(), PhiVal, ConstantOp);
814  BinOp->copyIRFlags(PN.getIncomingValue(0));
815 
816  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
817  BinOp->andIRFlags(PN.getIncomingValue(i));
818 
819  PHIArgMergedDebugLoc(BinOp, PN);
820  return BinOp;
821  }
822 
823  CmpInst *CIOp = cast<CmpInst>(FirstInst);
824  CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
825  PhiVal, ConstantOp);
826  PHIArgMergedDebugLoc(NewCI, PN);
827  return NewCI;
828 }
829 
830 /// Return true if this PHI node is only used by a PHI node cycle that is dead.
831 static bool DeadPHICycle(PHINode *PN,
832  SmallPtrSetImpl<PHINode*> &PotentiallyDeadPHIs) {
833  if (PN->use_empty()) return true;
834  if (!PN->hasOneUse()) return false;
835 
836  // Remember this node, and if we find the cycle, return.
837  if (!PotentiallyDeadPHIs.insert(PN).second)
838  return true;
839 
840  // Don't scan crazily complex things.
841  if (PotentiallyDeadPHIs.size() == 16)
842  return false;
843 
844  if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
845  return DeadPHICycle(PU, PotentiallyDeadPHIs);
846 
847  return false;
848 }
849 
850 /// Return true if this phi node is always equal to NonPhiInVal.
851 /// This happens with mutually cyclic phi nodes like:
852 /// z = some value; x = phi (y, z); y = phi (x, z)
853 static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
854  SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
855  // See if we already saw this PHI node.
856  if (!ValueEqualPHIs.insert(PN).second)
857  return true;
858 
859  // Don't scan crazily complex things.
860  if (ValueEqualPHIs.size() == 16)
861  return false;
862 
863  // Scan the operands to see if they are either phi nodes or are equal to
864  // the value.
865  for (Value *Op : PN->incoming_values()) {
866  if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
867  if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
868  return false;
869  } else if (Op != NonPhiInVal)
870  return false;
871  }
872 
873  return true;
874 }
875 
876 /// Return an existing non-zero constant if this phi node has one, otherwise
877 /// return constant 1.
879  assert(isa<IntegerType>(PN.getType()) && "Expect only integer type phi");
880  for (Value *V : PN.operands())
881  if (auto *ConstVA = dyn_cast<ConstantInt>(V))
882  if (!ConstVA->isZero())
883  return ConstVA;
884  return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
885 }
886 
887 namespace {
888 struct PHIUsageRecord {
889  unsigned PHIId; // The ID # of the PHI (something determinstic to sort on)
890  unsigned Shift; // The amount shifted.
891  Instruction *Inst; // The trunc instruction.
892 
893  PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
894  : PHIId(pn), Shift(Sh), Inst(User) {}
895 
896  bool operator<(const PHIUsageRecord &RHS) const {
897  if (PHIId < RHS.PHIId) return true;
898  if (PHIId > RHS.PHIId) return false;
899  if (Shift < RHS.Shift) return true;
900  if (Shift > RHS.Shift) return false;
901  return Inst->getType()->getPrimitiveSizeInBits() <
902  RHS.Inst->getType()->getPrimitiveSizeInBits();
903  }
904 };
905 
906 struct LoweredPHIRecord {
907  PHINode *PN; // The PHI that was lowered.
908  unsigned Shift; // The amount shifted.
909  unsigned Width; // The width extracted.
910 
911  LoweredPHIRecord(PHINode *pn, unsigned Sh, Type *Ty)
912  : PN(pn), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
913 
914  // Ctor form used by DenseMap.
915  LoweredPHIRecord(PHINode *pn, unsigned Sh)
916  : PN(pn), Shift(Sh), Width(0) {}
917 };
918 }
919 
920 namespace llvm {
921  template<>
922  struct DenseMapInfo<LoweredPHIRecord> {
923  static inline LoweredPHIRecord getEmptyKey() {
924  return LoweredPHIRecord(nullptr, 0);
925  }
926  static inline LoweredPHIRecord getTombstoneKey() {
927  return LoweredPHIRecord(nullptr, 1);
928  }
929  static unsigned getHashValue(const LoweredPHIRecord &Val) {
930  return DenseMapInfo<PHINode*>::getHashValue(Val.PN) ^ (Val.Shift>>3) ^
931  (Val.Width>>3);
932  }
933  static bool isEqual(const LoweredPHIRecord &LHS,
934  const LoweredPHIRecord &RHS) {
935  return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift &&
936  LHS.Width == RHS.Width;
937  }
938  };
939 }
940 
941 
942 /// This is an integer PHI and we know that it has an illegal type: see if it is
943 /// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
944 /// the various pieces being extracted. This sort of thing is introduced when
945 /// SROA promotes an aggregate to large integer values.
946 ///
947 /// TODO: The user of the trunc may be an bitcast to float/double/vector or an
948 /// inttoptr. We should produce new PHIs in the right type.
949 ///
951  // PHIUsers - Keep track of all of the truncated values extracted from a set
952  // of PHIs, along with their offset. These are the things we want to rewrite.
954 
955  // PHIs are often mutually cyclic, so we keep track of a whole set of PHI
956  // nodes which are extracted from. PHIsToSlice is a set we use to avoid
957  // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to
958  // check the uses of (to ensure they are all extracts).
959  SmallVector<PHINode*, 8> PHIsToSlice;
960  SmallPtrSet<PHINode*, 8> PHIsInspected;
961 
962  PHIsToSlice.push_back(&FirstPhi);
963  PHIsInspected.insert(&FirstPhi);
964 
965  for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {
966  PHINode *PN = PHIsToSlice[PHIId];
967 
968  // Scan the input list of the PHI. If any input is an invoke, and if the
969  // input is defined in the predecessor, then we won't be split the critical
970  // edge which is required to insert a truncate. Because of this, we have to
971  // bail out.
972  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
974  if (!II) continue;
975  if (II->getParent() != PN->getIncomingBlock(i))
976  continue;
977 
978  // If we have a phi, and if it's directly in the predecessor, then we have
979  // a critical edge where we need to put the truncate. Since we can't
980  // split the edge in instcombine, we have to bail out.
981  return nullptr;
982  }
983 
984  for (User *U : PN->users()) {
985  Instruction *UserI = cast<Instruction>(U);
986 
987  // If the user is a PHI, inspect its uses recursively.
988  if (PHINode *UserPN = dyn_cast<PHINode>(UserI)) {
989  if (PHIsInspected.insert(UserPN).second)
990  PHIsToSlice.push_back(UserPN);
991  continue;
992  }
993 
994  // Truncates are always ok.
995  if (isa<TruncInst>(UserI)) {
996  PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));
997  continue;
998  }
999 
1000  // Otherwise it must be a lshr which can only be used by one trunc.
1001  if (UserI->getOpcode() != Instruction::LShr ||
1002  !UserI->hasOneUse() || !isa<TruncInst>(UserI->user_back()) ||
1003  !isa<ConstantInt>(UserI->getOperand(1)))
1004  return nullptr;
1005 
1006  unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue();
1007  PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));
1008  }
1009  }
1010 
1011  // If we have no users, they must be all self uses, just nuke the PHI.
1012  if (PHIUsers.empty())
1013  return replaceInstUsesWith(FirstPhi, UndefValue::get(FirstPhi.getType()));
1014 
1015  // If this phi node is transformable, create new PHIs for all the pieces
1016  // extracted out of it. First, sort the users by their offset and size.
1017  array_pod_sort(PHIUsers.begin(), PHIUsers.end());
1018 
1019  LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';
1020  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i) dbgs()
1021  << "AND USER PHI #" << i << ": " << *PHIsToSlice[i] << '\n';);
1022 
1023  // PredValues - This is a temporary used when rewriting PHI nodes. It is
1024  // hoisted out here to avoid construction/destruction thrashing.
1025  DenseMap<BasicBlock*, Value*> PredValues;
1026 
1027  // ExtractedVals - Each new PHI we introduce is saved here so we don't
1028  // introduce redundant PHIs.
1030 
1031  for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {
1032  unsigned PHIId = PHIUsers[UserI].PHIId;
1033  PHINode *PN = PHIsToSlice[PHIId];
1034  unsigned Offset = PHIUsers[UserI].Shift;
1035  Type *Ty = PHIUsers[UserI].Inst->getType();
1036 
1037  PHINode *EltPHI;
1038 
1039  // If we've already lowered a user like this, reuse the previously lowered
1040  // value.
1041  if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {
1042 
1043  // Otherwise, Create the new PHI node for this user.
1044  EltPHI = PHINode::Create(Ty, PN->getNumIncomingValues(),
1045  PN->getName()+".off"+Twine(Offset), PN);
1046  assert(EltPHI->getType() != PN->getType() &&
1047  "Truncate didn't shrink phi?");
1048 
1049  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1050  BasicBlock *Pred = PN->getIncomingBlock(i);
1051  Value *&PredVal = PredValues[Pred];
1052 
1053  // If we already have a value for this predecessor, reuse it.
1054  if (PredVal) {
1055  EltPHI->addIncoming(PredVal, Pred);
1056  continue;
1057  }
1058 
1059  // Handle the PHI self-reuse case.
1060  Value *InVal = PN->getIncomingValue(i);
1061  if (InVal == PN) {
1062  PredVal = EltPHI;
1063  EltPHI->addIncoming(PredVal, Pred);
1064  continue;
1065  }
1066 
1067  if (PHINode *InPHI = dyn_cast<PHINode>(PN)) {
1068  // If the incoming value was a PHI, and if it was one of the PHIs we
1069  // already rewrote it, just use the lowered value.
1070  if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {
1071  PredVal = Res;
1072  EltPHI->addIncoming(PredVal, Pred);
1073  continue;
1074  }
1075  }
1076 
1077  // Otherwise, do an extract in the predecessor.
1078  Builder.SetInsertPoint(Pred->getTerminator());
1079  Value *Res = InVal;
1080  if (Offset)
1081  Res = Builder.CreateLShr(Res, ConstantInt::get(InVal->getType(),
1082  Offset), "extract");
1083  Res = Builder.CreateTrunc(Res, Ty, "extract.t");
1084  PredVal = Res;
1085  EltPHI->addIncoming(Res, Pred);
1086 
1087  // If the incoming value was a PHI, and if it was one of the PHIs we are
1088  // rewriting, we will ultimately delete the code we inserted. This
1089  // means we need to revisit that PHI to make sure we extract out the
1090  // needed piece.
1091  if (PHINode *OldInVal = dyn_cast<PHINode>(PN->getIncomingValue(i)))
1092  if (PHIsInspected.count(OldInVal)) {
1093  unsigned RefPHIId =
1094  find(PHIsToSlice, OldInVal) - PHIsToSlice.begin();
1095  PHIUsers.push_back(PHIUsageRecord(RefPHIId, Offset,
1096  cast<Instruction>(Res)));
1097  ++UserE;
1098  }
1099  }
1100  PredValues.clear();
1101 
1102  LLVM_DEBUG(dbgs() << " Made element PHI for offset " << Offset << ": "
1103  << *EltPHI << '\n');
1104  ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;
1105  }
1106 
1107  // Replace the use of this piece with the PHI node.
1108  replaceInstUsesWith(*PHIUsers[UserI].Inst, EltPHI);
1109  }
1110 
1111  // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
1112  // with undefs.
1113  Value *Undef = UndefValue::get(FirstPhi.getType());
1114  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
1115  replaceInstUsesWith(*PHIsToSlice[i], Undef);
1116  return replaceInstUsesWith(FirstPhi, Undef);
1117 }
1118 
1119 // PHINode simplification
1120 //
1122  if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
1123  return replaceInstUsesWith(PN, V);
1124 
1125  if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
1126  return Result;
1127 
1128  // If all PHI operands are the same operation, pull them through the PHI,
1129  // reducing code size.
1130  if (isa<Instruction>(PN.getIncomingValue(0)) &&
1131  isa<Instruction>(PN.getIncomingValue(1)) &&
1132  cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
1133  cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
1134  // FIXME: The hasOneUse check will fail for PHIs that use the value more
1135  // than themselves more than once.
1136  PN.getIncomingValue(0)->hasOneUse())
1137  if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
1138  return Result;
1139 
1140  // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
1141  // this PHI only has a single use (a PHI), and if that PHI only has one use (a
1142  // PHI)... break the cycle.
1143  if (PN.hasOneUse()) {
1144  if (Instruction *Result = FoldIntegerTypedPHI(PN))
1145  return Result;
1146 
1147  Instruction *PHIUser = cast<Instruction>(PN.user_back());
1148  if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
1149  SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
1150  PotentiallyDeadPHIs.insert(&PN);
1151  if (DeadPHICycle(PU, PotentiallyDeadPHIs))
1152  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1153  }
1154 
1155  // If this phi has a single use, and if that use just computes a value for
1156  // the next iteration of a loop, delete the phi. This occurs with unused
1157  // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
1158  // common case here is good because the only other things that catch this
1159  // are induction variable analysis (sometimes) and ADCE, which is only run
1160  // late.
1161  if (PHIUser->hasOneUse() &&
1162  (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
1163  PHIUser->user_back() == &PN) {
1164  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1165  }
1166  // When a PHI is used only to be compared with zero, it is safe to replace
1167  // an incoming value proved as known nonzero with any non-zero constant.
1168  // For example, in the code below, the incoming value %v can be replaced
1169  // with any non-zero constant based on the fact that the PHI is only used to
1170  // be compared with zero and %v is a known non-zero value:
1171  // %v = select %cond, 1, 2
1172  // %p = phi [%v, BB] ...
1173  // icmp eq, %p, 0
1174  auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
1175  // FIXME: To be simple, handle only integer type for now.
1176  if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
1177  match(CmpInst->getOperand(1), m_Zero())) {
1178  ConstantInt *NonZeroConst = nullptr;
1179  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1180  Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
1181  Value *VA = PN.getIncomingValue(i);
1182  if (isKnownNonZero(VA, DL, 0, &AC, CtxI, &DT)) {
1183  if (!NonZeroConst)
1184  NonZeroConst = GetAnyNonZeroConstInt(PN);
1185  PN.setIncomingValue(i, NonZeroConst);
1186  }
1187  }
1188  }
1189  }
1190 
1191  // We sometimes end up with phi cycles that non-obviously end up being the
1192  // same value, for example:
1193  // z = some value; x = phi (y, z); y = phi (x, z)
1194  // where the phi nodes don't necessarily need to be in the same block. Do a
1195  // quick check to see if the PHI node only contains a single non-phi value, if
1196  // so, scan to see if the phi cycle is actually equal to that value.
1197  {
1198  unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();
1199  // Scan for the first non-phi operand.
1200  while (InValNo != NumIncomingVals &&
1201  isa<PHINode>(PN.getIncomingValue(InValNo)))
1202  ++InValNo;
1203 
1204  if (InValNo != NumIncomingVals) {
1205  Value *NonPhiInVal = PN.getIncomingValue(InValNo);
1206 
1207  // Scan the rest of the operands to see if there are any conflicts, if so
1208  // there is no need to recursively scan other phis.
1209  for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
1210  Value *OpVal = PN.getIncomingValue(InValNo);
1211  if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
1212  break;
1213  }
1214 
1215  // If we scanned over all operands, then we have one unique value plus
1216  // phi values. Scan PHI nodes to see if they all merge in each other or
1217  // the value.
1218  if (InValNo == NumIncomingVals) {
1219  SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
1220  if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
1221  return replaceInstUsesWith(PN, NonPhiInVal);
1222  }
1223  }
1224  }
1225 
1226  // If there are multiple PHIs, sort their operands so that they all list
1227  // the blocks in the same order. This will help identical PHIs be eliminated
1228  // by other passes. Other passes shouldn't depend on this for correctness
1229  // however.
1230  PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());
1231  if (&PN != FirstPN)
1232  for (unsigned i = 0, e = FirstPN->getNumIncomingValues(); i != e; ++i) {
1233  BasicBlock *BBA = PN.getIncomingBlock(i);
1234  BasicBlock *BBB = FirstPN->getIncomingBlock(i);
1235  if (BBA != BBB) {
1236  Value *VA = PN.getIncomingValue(i);
1237  unsigned j = PN.getBasicBlockIndex(BBB);
1238  Value *VB = PN.getIncomingValue(j);
1239  PN.setIncomingBlock(i, BBB);
1240  PN.setIncomingValue(i, VB);
1241  PN.setIncomingBlock(j, BBA);
1242  PN.setIncomingValue(j, VA);
1243  // NOTE: Instcombine normally would want us to "return &PN" if we
1244  // modified any of the operands of an instruction. However, since we
1245  // aren't adding or removing uses (just rearranging them) we don't do
1246  // this in this case.
1247  }
1248  }
1249 
1250  // If this is an integer PHI and we know that it has an illegal type, see if
1251  // it is only used by trunc or trunc(lshr) operations. If so, we split the
1252  // PHI into the various pieces being extracted. This sort of thing is
1253  // introduced when SROA promotes an aggregate to a single large integer type.
1254  if (PN.getType()->isIntegerTy() &&
1255  !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
1256  if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
1257  return Res;
1258 
1259  return nullptr;
1260 }
uint64_t CallInst * C
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:875
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:373
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
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:867
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:1018
An instruction for reading from memory.
Definition: Instructions.h:168
Hexagon Common GEP
#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...
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove=true)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2282
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:264
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:221
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:592
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:451
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:938
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1642
OtherOps getOpcode() const
Get the opcode casted to the right type.
Definition: InstrTypes.h:954
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:200
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.
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:310
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:841
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
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:936
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:55
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:287
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:1025
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:1392
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:1039
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:266
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:1614
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:621
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:691
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
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:91
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:959
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:290
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:230
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:224
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:280
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned getNumSuccessors() const
Return the number of successors that this terminator has.
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 isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Return true if the given value is known to be non-zero when defined.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
static bool isVolatile(Instruction *Inst)
const TerminatorInst * 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
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:119
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