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