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