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