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