contrib/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

   1 //===- InstCombinePHI.cpp -------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the visitPHINode function.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "InstCombineInternal.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/Analysis/InstructionSimplify.h"
  18 #include "llvm/Analysis/ValueTracking.h"
  19 #include "llvm/IR/PatternMatch.h"
  20 #include "llvm/Transforms/Utils/Local.h"
  21 using namespace llvm;
  22 using namespace llvm::PatternMatch;
  23
  24 #define DEBUG_TYPE "instcombine"
  25
  26 /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
  27 /// adds all have a single use, turn this into a phi and a single binop.
  28 Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
  29   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
  30   assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
  31   unsigned Opc = FirstInst->getOpcode();
  32   Value *LHSVal = FirstInst->getOperand(0);
  33   Value *RHSVal = FirstInst->getOperand(1);
  34
  35   Type *LHSType = LHSVal->getType();
  36   Type *RHSType = RHSVal->getType();
  37
  38   // Scan to see if all operands are the same opcode, and all have one use.
  39   for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
  40     Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
  41     if (!I || I->getOpcode() != Opc || !I->hasOneUse() ||
  42         // Verify type of the LHS matches so we don't fold cmp's of different
  43         // types.
  44         I->getOperand(0)->getType() != LHSType ||
  45         I->getOperand(1)->getType() != RHSType)
  46       return nullptr;
  47
  48     // If they are CmpInst instructions, check their predicates
  49     if (CmpInst *CI = dyn_cast<CmpInst>(I))
  50       if (CI->getPredicate() != cast<CmpInst>(FirstInst)->getPredicate())
  51         return nullptr;
  52
  53     // Keep track of which operand needs a phi node.
  54     if (I->getOperand(0) != LHSVal) LHSVal = nullptr;
  55     if (I->getOperand(1) != RHSVal) RHSVal = nullptr;
  56   }
  57
  58   // If both LHS and RHS would need a PHI, don't do this transformation,
  59   // because it would increase the number of PHIs entering the block,
  60   // which leads to higher register pressure. This is especially
  61   // bad when the PHIs are in the header of a loop.
  62   if (!LHSVal && !RHSVal)
  63     return nullptr;
  64
  65   // Otherwise, this is safe to transform!
  66
  67   Value *InLHS = FirstInst->getOperand(0);
  68   Value *InRHS = FirstInst->getOperand(1);
  69   PHINode *NewLHS = nullptr, *NewRHS = nullptr;
  70   if (!LHSVal) {
  71     NewLHS = PHINode::Create(LHSType, PN.getNumIncomingValues(),
  72                              FirstInst->getOperand(0)->getName() + ".pn");
  73     NewLHS->addIncoming(InLHS, PN.getIncomingBlock(0));
  74     InsertNewInstBefore(NewLHS, PN);
  75     LHSVal = NewLHS;
  76   }
  77
  78   if (!RHSVal) {
  79     NewRHS = PHINode::Create(RHSType, PN.getNumIncomingValues(),
  80                              FirstInst->getOperand(1)->getName() + ".pn");
  81     NewRHS->addIncoming(InRHS, PN.getIncomingBlock(0));
  82     InsertNewInstBefore(NewRHS, PN);
  83     RHSVal = NewRHS;
  84   }
  85
  86   // Add all operands to the new PHIs.
  87   if (NewLHS || NewRHS) {
  88     for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
  89       Instruction *InInst = cast<Instruction>(PN.getIncomingValue(i));
  90       if (NewLHS) {
  91         Value *NewInLHS = InInst->getOperand(0);
  92         NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i));
  93       }
  94       if (NewRHS) {
  95         Value *NewInRHS = InInst->getOperand(1);
  96         NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i));
  97       }
  98     }
  99   }
 100
 101   if (CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst)) {
 102     CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
 103                                      LHSVal, RHSVal);
 104     NewCI->setDebugLoc(FirstInst->getDebugLoc());
 105     return NewCI;
 106   }
 107
 108   BinaryOperator *BinOp = cast<BinaryOperator>(FirstInst);
 109   BinaryOperator *NewBinOp =
 110     BinaryOperator::Create(BinOp->getOpcode(), LHSVal, RHSVal);
 111
 112   NewBinOp->copyIRFlags(PN.getIncomingValue(0));
 113
 114   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
 115     NewBinOp->andIRFlags(PN.getIncomingValue(i));
 116
 117   NewBinOp->setDebugLoc(FirstInst->getDebugLoc());
 118   return NewBinOp;
 119 }
 120
 121 Instruction *InstCombiner::FoldPHIArgGEPIntoPHI(PHINode &PN) {
 122   GetElementPtrInst *FirstInst =cast<GetElementPtrInst>(PN.getIncomingValue(0));
 123
 124   SmallVector<Value*, 16> FixedOperands(FirstInst->op_begin(),
 125                                         FirstInst->op_end());
 126   // This is true if all GEP bases are allocas and if all indices into them are
 127   // constants.
 128   bool AllBasePointersAreAllocas = true;
 129
 130   // We don't want to replace this phi if the replacement would require
 131   // more than one phi, which leads to higher register pressure. This is
 132   // especially bad when the PHIs are in the header of a loop.
 133   bool NeededPhi = false;
 134
 135   bool AllInBounds = true;
 136
 137   // Scan to see if all operands are the same opcode, and all have one use.
 138   for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
 139     GetElementPtrInst *GEP= dyn_cast<GetElementPtrInst>(PN.getIncomingValue(i));
 140     if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() ||
 141       GEP->getNumOperands() != FirstInst->getNumOperands())
 142       return nullptr;
 143
 144     AllInBounds &= GEP->isInBounds();
 145
 146     // Keep track of whether or not all GEPs are of alloca pointers.
 147     if (AllBasePointersAreAllocas &&
 148         (!isa<AllocaInst>(GEP->getOperand(0)) ||
 149          !GEP->hasAllConstantIndices()))
 150       AllBasePointersAreAllocas = false;
 151
 152     // Compare the operand lists.
 153     for (unsigned op = 0, e = FirstInst->getNumOperands(); op != e; ++op) {
 154       if (FirstInst->getOperand(op) == GEP->getOperand(op))
 155         continue;
 156
 157       // Don't merge two GEPs when two operands differ (introducing phi nodes)
 158       // if one of the PHIs has a constant for the index.  The index may be
 159       // substantially cheaper to compute for the constants, so making it a
 160       // variable index could pessimize the path.  This also handles the case
 161       // for struct indices, which must always be constant.
 162       if (isa<ConstantInt>(FirstInst->getOperand(op)) ||
 163           isa<ConstantInt>(GEP->getOperand(op)))
 164         return nullptr;
 165
 166       if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType())
 167         return nullptr;
 168
 169       // If we already needed a PHI for an earlier operand, and another operand
 170       // also requires a PHI, we'd be introducing more PHIs than we're
 171       // eliminating, which increases register pressure on entry to the PHI's
 172       // block.
 173       if (NeededPhi)
 174         return nullptr;
 175
 176       FixedOperands[op] = nullptr;  // Needs a PHI.
 177       NeededPhi = true;
 178     }
 179   }
 180
 181   // If all of the base pointers of the PHI'd GEPs are from allocas, don't
 182   // bother doing this transformation.  At best, this will just save a bit of
 183   // offset calculation, but all the predecessors will have to materialize the
 184   // stack address into a register anyway.  We'd actually rather *clone* the
 185   // load up into the predecessors so that we have a load of a gep of an alloca,
 186   // which can usually all be folded into the load.
 187   if (AllBasePointersAreAllocas)
 188     return nullptr;
 189
 190   // Otherwise, this is safe to transform.  Insert PHI nodes for each operand
 191   // that is variable.
 192   SmallVector<PHINode*, 16> OperandPhis(FixedOperands.size());
 193
 194   bool HasAnyPHIs = false;
 195   for (unsigned i = 0, e = FixedOperands.size(); i != e; ++i) {
 196     if (FixedOperands[i]) continue;  // operand doesn't need a phi.
 197     Value *FirstOp = FirstInst->getOperand(i);
 198     PHINode *NewPN = PHINode::Create(FirstOp->getType(), e,
 199                                      FirstOp->getName()+".pn");
 200     InsertNewInstBefore(NewPN, PN);
 201
 202     NewPN->addIncoming(FirstOp, PN.getIncomingBlock(0));
 203     OperandPhis[i] = NewPN;
 204     FixedOperands[i] = NewPN;
 205     HasAnyPHIs = true;
 206   }
 207
 208
 209   // Add all operands to the new PHIs.
 210   if (HasAnyPHIs) {
 211     for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
 212       GetElementPtrInst *InGEP =cast<GetElementPtrInst>(PN.getIncomingValue(i));
 213       BasicBlock *InBB = PN.getIncomingBlock(i);
 214
 215       for (unsigned op = 0, e = OperandPhis.size(); op != e; ++op)
 216         if (PHINode *OpPhi = OperandPhis[op])
 217           OpPhi->addIncoming(InGEP->getOperand(op), InBB);
 218     }
 219   }
 220
 221   Value *Base = FixedOperands[0];
 222   GetElementPtrInst *NewGEP =
 223       GetElementPtrInst::Create(FirstInst->getSourceElementType(), Base,
 224                                 makeArrayRef(FixedOperands).slice(1));
 225   if (AllInBounds) NewGEP->setIsInBounds();
 226   NewGEP->setDebugLoc(FirstInst->getDebugLoc());
 227   return NewGEP;
 228 }
 229
 230
 231 /// Return true if we know that it is safe to sink the load out of the block
 232 /// that defines it. This means that it must be obvious the value of the load is
 233 /// not changed from the point of the load to the end of the block it is in.
 234 ///
 235 /// Finally, it is safe, but not profitable, to sink a load targeting a
 236 /// non-address-taken alloca.  Doing so will cause us to not promote the alloca
 237 /// to a register.
 238 static bool isSafeAndProfitableToSinkLoad(LoadInst *L) {
 239   BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end();
 240
 241   for (++BBI; BBI != E; ++BBI)
 242     if (BBI->mayWriteToMemory())
 243       return false;
 244
 245   // Check for non-address taken alloca.  If not address-taken already, it isn't
 246   // profitable to do this xform.
 247   if (AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
 248     bool isAddressTaken = false;
 249     for (User *U : AI->users()) {
 250       if (isa<LoadInst>(U)) continue;
 251       if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 252         // If storing TO the alloca, then the address isn't taken.
 253         if (SI->getOperand(1) == AI) continue;
 254       }
 255       isAddressTaken = true;
 256       break;
 257     }
 258
 259     if (!isAddressTaken && AI->isStaticAlloca())
 260       return false;
 261   }
 262
 263   // If this load is a load from a GEP with a constant offset from an alloca,
 264   // then we don't want to sink it.  In its present form, it will be
 265   // load [constant stack offset].  Sinking it will cause us to have to
 266   // materialize the stack addresses in each predecessor in a register only to
 267   // do a shared load from register in the successor.
 268   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(L->getOperand(0)))
 269     if (AllocaInst *AI = dyn_cast<AllocaInst>(GEP->getOperand(0)))
 270       if (AI->isStaticAlloca() && GEP->hasAllConstantIndices())
 271         return false;
 272
 273   return true;
 274 }
 275
 276 Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
 277   LoadInst *FirstLI = cast<LoadInst>(PN.getIncomingValue(0));
 278
 279   // FIXME: This is overconservative; this transform is allowed in some cases
 280   // for atomic operations.
 281   if (FirstLI->isAtomic())
 282     return nullptr;
 283
 284   // When processing loads, we need to propagate two bits of information to the
 285   // sunk load: whether it is volatile, and what its alignment is.  We currently
 286   // don't sink loads when some have their alignment specified and some don't.
 287   // visitLoadInst will propagate an alignment onto the load when TD is around,
 288   // and if TD isn't around, we can't handle the mixed case.
 289   bool isVolatile = FirstLI->isVolatile();
 290   unsigned LoadAlignment = FirstLI->getAlignment();
 291   unsigned LoadAddrSpace = FirstLI->getPointerAddressSpace();
 292
 293   // We can't sink the load if the loaded value could be modified between the
 294   // load and the PHI.
 295   if (FirstLI->getParent() != PN.getIncomingBlock(0) ||
 296       !isSafeAndProfitableToSinkLoad(FirstLI))
 297     return nullptr;
 298
 299   // If the PHI is of volatile loads and the load block has multiple
 300   // successors, sinking it would remove a load of the volatile value from
 301   // the path through the other successor.
 302   if (isVolatile &&
 303       FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1)
 304     return nullptr;
 305
 306   // Check to see if all arguments are the same operation.
 307   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
 308     LoadInst *LI = dyn_cast<LoadInst>(PN.getIncomingValue(i));
 309     if (!LI || !LI->hasOneUse())
 310       return nullptr;
 311
 312     // We can't sink the load if the loaded value could be modified between
 313     // the load and the PHI.
 314     if (LI->isVolatile() != isVolatile ||
 315         LI->getParent() != PN.getIncomingBlock(i) ||
 316         LI->getPointerAddressSpace() != LoadAddrSpace ||
 317         !isSafeAndProfitableToSinkLoad(LI))
 318       return nullptr;
 319
 320     // If some of the loads have an alignment specified but not all of them,
 321     // we can't do the transformation.
 322     if ((LoadAlignment != 0) != (LI->getAlignment() != 0))
 323       return nullptr;
 324
 325     LoadAlignment = std::min(LoadAlignment, LI->getAlignment());
 326
 327     // If the PHI is of volatile loads and the load block has multiple
 328     // successors, sinking it would remove a load of the volatile value from
 329     // the path through the other successor.
 330     if (isVolatile &&
 331         LI->getParent()->getTerminator()->getNumSuccessors() != 1)
 332       return nullptr;
 333   }
 334
 335   // Okay, they are all the same operation.  Create a new PHI node of the
 336   // correct type, and PHI together all of the LHS's of the instructions.
 337   PHINode *NewPN = PHINode::Create(FirstLI->getOperand(0)->getType(),
 338                                    PN.getNumIncomingValues(),
 339                                    PN.getName()+".in");
 340
 341   Value *InVal = FirstLI->getOperand(0);
 342   NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
 343   LoadInst *NewLI = new LoadInst(NewPN, "", isVolatile, LoadAlignment);
 344
 345   unsigned KnownIDs[] = {
 346     LLVMContext::MD_tbaa,
 347     LLVMContext::MD_range,
 348     LLVMContext::MD_invariant_load,
 349     LLVMContext::MD_alias_scope,
 350     LLVMContext::MD_noalias,
 351     LLVMContext::MD_nonnull,
 352     LLVMContext::MD_align,
 353     LLVMContext::MD_dereferenceable,
 354     LLVMContext::MD_dereferenceable_or_null,
 355   };
 356
 357   for (unsigned ID : KnownIDs)
 358     NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
 359
 360   // Add all operands to the new PHI and combine TBAA metadata.
 361   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
 362     LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
 363     combineMetadata(NewLI, LI, KnownIDs);
 364     Value *NewInVal = LI->getOperand(0);
 365     if (NewInVal != InVal)
 366       InVal = nullptr;
 367     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
 368   }
 369
 370   if (InVal) {
 371     // The new PHI unions all of the same values together.  This is really
 372     // common, so we handle it intelligently here for compile-time speed.
 373     NewLI->setOperand(0, InVal);
 374     delete NewPN;
 375   } else {
 376     InsertNewInstBefore(NewPN, PN);
 377   }
 378
 379   // If this was a volatile load that we are merging, make sure to loop through
 380   // and mark all the input loads as non-volatile.  If we don't do this, we will
 381   // insert a new volatile load and the old ones will not be deletable.
 382   if (isVolatile)
 383     for (Value *IncValue : PN.incoming_values())
 384       cast<LoadInst>(IncValue)->setVolatile(false);
 385
 386   NewLI->setDebugLoc(FirstLI->getDebugLoc());
 387   return NewLI;
 388 }
 389
 390 /// TODO: This function could handle other cast types, but then it might
 391 /// require special-casing a cast from the 'i1' type. See the comment in
 392 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
 393 Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
 394   // We cannot create a new instruction after the PHI if the terminator is an
 395   // EHPad because there is no valid insertion point.
 396   if (TerminatorInst *TI = Phi.getParent()->getTerminator())
 397     if (TI->isEHPad())
 398       return nullptr;
 399
 400   // Early exit for the common case of a phi with two operands. These are
 401   // handled elsewhere. See the comment below where we check the count of zexts
 402   // and constants for more details.
 403   unsigned NumIncomingValues = Phi.getNumIncomingValues();
 404   if (NumIncomingValues < 3)
 405     return nullptr;
 406
 407   // Find the narrower type specified by the first zext.
 408   Type *NarrowType = nullptr;
 409   for (Value *V : Phi.incoming_values()) {
 410     if (auto *Zext = dyn_cast<ZExtInst>(V)) {
 411       NarrowType = Zext->getSrcTy();
 412       break;
 413     }
 414   }
 415   if (!NarrowType)
 416     return nullptr;
 417
 418   // Walk the phi operands checking that we only have zexts or constants that
 419   // we can shrink for free. Store the new operands for the new phi.
 420   SmallVector<Value *, 4> NewIncoming;
 421   unsigned NumZexts = 0;
 422   unsigned NumConsts = 0;
 423   for (Value *V : Phi.incoming_values()) {
 424     if (auto *Zext = dyn_cast<ZExtInst>(V)) {
 425       // All zexts must be identical and have one use.
 426       if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUse())
 427         return nullptr;
 428       NewIncoming.push_back(Zext->getOperand(0));
 429       NumZexts++;
 430     } else if (auto *C = dyn_cast<Constant>(V)) {
 431       // Make sure that constants can fit in the new type.
 432       Constant *Trunc = ConstantExpr::getTrunc(C, NarrowType);
 433       if (ConstantExpr::getZExt(Trunc, C->getType()) != C)
 434         return nullptr;
 435       NewIncoming.push_back(Trunc);
 436       NumConsts++;
 437     } else {
 438       // If it's not a cast or a constant, bail out.
 439       return nullptr;
 440     }
 441   }
 442
 443   // The more common cases of a phi with no constant operands or just one
 444   // variable operand are handled by FoldPHIArgOpIntoPHI() and FoldOpIntoPhi()
 445   // respectively. FoldOpIntoPhi() wants to do the opposite transform that is
 446   // performed here. It tries to replicate a cast in the phi operand's basic
 447   // block to expose other folding opportunities. Thus, InstCombine will
 448   // infinite loop without this check.
 449   if (NumConsts == 0 || NumZexts < 2)
 450     return nullptr;
 451
 452   // All incoming values are zexts or constants that are safe to truncate.
 453   // Create a new phi node of the narrow type, phi together all of the new
 454   // operands, and zext the result back to the original type.
 455   PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues,
 456                                     Phi.getName() + ".shrunk");
 457   for (unsigned i = 0; i != NumIncomingValues; ++i)
 458     NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i));
 459
 460   InsertNewInstBefore(NewPhi, Phi);
 461   return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
 462 }
 463
 464 /// If all operands to a PHI node are the same "unary" operator and they all are
 465 /// only used by the PHI, PHI together their inputs, and do the operation once,
 466 /// to the result of the PHI.
 467 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
 468   // We cannot create a new instruction after the PHI if the terminator is an
 469   // EHPad because there is no valid insertion point.
 470   if (TerminatorInst *TI = PN.getParent()->getTerminator())
 471     if (TI->isEHPad())
 472       return nullptr;
 473
 474   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
 475
 476   if (isa<GetElementPtrInst>(FirstInst))
 477     return FoldPHIArgGEPIntoPHI(PN);
 478   if (isa<LoadInst>(FirstInst))
 479     return FoldPHIArgLoadIntoPHI(PN);
 480
 481   // Scan the instruction, looking for input operations that can be folded away.
 482   // If all input operands to the phi are the same instruction (e.g. a cast from
 483   // the same type or "+42") we can pull the operation through the PHI, reducing
 484   // code size and simplifying code.
 485   Constant *ConstantOp = nullptr;
 486   Type *CastSrcTy = nullptr;
 487
 488   if (isa<CastInst>(FirstInst)) {
 489     CastSrcTy = FirstInst->getOperand(0)->getType();
 490
 491     // Be careful about transforming integer PHIs.  We don't want to pessimize
 492     // the code by turning an i32 into an i1293.
 493     if (PN.getType()->isIntegerTy() && CastSrcTy->isIntegerTy()) {
 494       if (!ShouldChangeType(PN.getType(), CastSrcTy))
 495         return nullptr;
 496     }
 497   } else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
 498     // Can fold binop, compare or shift here if the RHS is a constant,
 499     // otherwise call FoldPHIArgBinOpIntoPHI.
 500     ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
 501     if (!ConstantOp)
 502       return FoldPHIArgBinOpIntoPHI(PN);
 503   } else {
 504     return nullptr;  // Cannot fold this operation.
 505   }
 506
 507   // Check to see if all arguments are the same operation.
 508   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
 509     Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
 510     if (!I || !I->hasOneUse() || !I->isSameOperationAs(FirstInst))
 511       return nullptr;
 512     if (CastSrcTy) {
 513       if (I->getOperand(0)->getType() != CastSrcTy)
 514         return nullptr;  // Cast operation must match.
 515     } else if (I->getOperand(1) != ConstantOp) {
 516       return nullptr;
 517     }
 518   }
 519
 520   // Okay, they are all the same operation.  Create a new PHI node of the
 521   // correct type, and PHI together all of the LHS's of the instructions.
 522   PHINode *NewPN = PHINode::Create(FirstInst->getOperand(0)->getType(),
 523                                    PN.getNumIncomingValues(),
 524                                    PN.getName()+".in");
 525
 526   Value *InVal = FirstInst->getOperand(0);
 527   NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
 528
 529   // Add all operands to the new PHI.
 530   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
 531     Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
 532     if (NewInVal != InVal)
 533       InVal = nullptr;
 534     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
 535   }
 536
 537   Value *PhiVal;
 538   if (InVal) {
 539     // The new PHI unions all of the same values together.  This is really
 540     // common, so we handle it intelligently here for compile-time speed.
 541     PhiVal = InVal;
 542     delete NewPN;
 543   } else {
 544     InsertNewInstBefore(NewPN, PN);
 545     PhiVal = NewPN;
 546   }
 547
 548   // Insert and return the new operation.
 549   if (CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
 550     CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), PhiVal,
 551                                        PN.getType());
 552     NewCI->setDebugLoc(FirstInst->getDebugLoc());
 553     return NewCI;
 554   }
 555
 556   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
 557     BinOp = BinaryOperator::Create(BinOp->getOpcode(), PhiVal, ConstantOp);
 558     BinOp->copyIRFlags(PN.getIncomingValue(0));
 559
 560     for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
 561       BinOp->andIRFlags(PN.getIncomingValue(i));
 562
 563     BinOp->setDebugLoc(FirstInst->getDebugLoc());
 564     return BinOp;
 565   }
 566
 567   CmpInst *CIOp = cast<CmpInst>(FirstInst);
 568   CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
 569                                    PhiVal, ConstantOp);
 570   NewCI->setDebugLoc(FirstInst->getDebugLoc());
 571   return NewCI;
 572 }
 573
 574 /// Return true if this PHI node is only used by a PHI node cycle that is dead.
 575 static bool DeadPHICycle(PHINode *PN,
 576                          SmallPtrSetImpl<PHINode*> &PotentiallyDeadPHIs) {
 577   if (PN->use_empty()) return true;
 578   if (!PN->hasOneUse()) return false;
 579
 580   // Remember this node, and if we find the cycle, return.
 581   if (!PotentiallyDeadPHIs.insert(PN).second)
 582     return true;
 583
 584   // Don't scan crazily complex things.
 585   if (PotentiallyDeadPHIs.size() == 16)
 586     return false;
 587
 588   if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
 589     return DeadPHICycle(PU, PotentiallyDeadPHIs);
 590
 591   return false;
 592 }
 593
 594 /// Return true if this phi node is always equal to NonPhiInVal.
 595 /// This happens with mutually cyclic phi nodes like:
 596 ///   z = some value; x = phi (y, z); y = phi (x, z)
 597 static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
 598                            SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
 599   // See if we already saw this PHI node.
 600   if (!ValueEqualPHIs.insert(PN).second)
 601     return true;
 602
 603   // Don't scan crazily complex things.
 604   if (ValueEqualPHIs.size() == 16)
 605     return false;
 606
 607   // Scan the operands to see if they are either phi nodes or are equal to
 608   // the value.
 609   for (Value *Op : PN->incoming_values()) {
 610     if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
 611       if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
 612         return false;
 613     } else if (Op != NonPhiInVal)
 614       return false;
 615   }
 616
 617   return true;
 618 }
 619
 620 /// Return an existing non-zero constant if this phi node has one, otherwise
 621 /// return constant 1.
 622 static ConstantInt *GetAnyNonZeroConstInt(PHINode &PN) {
 623   assert(isa<IntegerType>(PN.getType()) && "Expect only intger type phi");
 624   for (Value *V : PN.operands())
 625     if (auto *ConstVA = dyn_cast<ConstantInt>(V))
 626       if (!ConstVA->isZeroValue())
 627         return ConstVA;
 628   return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
 629 }
 630
 631 namespace {
 632 struct PHIUsageRecord {
 633   unsigned PHIId;     // The ID # of the PHI (something determinstic to sort on)
 634   unsigned Shift;     // The amount shifted.
 635   Instruction *Inst;  // The trunc instruction.
 636
 637   PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
 638     : PHIId(pn), Shift(Sh), Inst(User) {}
 639
 640   bool operator<(const PHIUsageRecord &RHS) const {
 641     if (PHIId < RHS.PHIId) return true;
 642     if (PHIId > RHS.PHIId) return false;
 643     if (Shift < RHS.Shift) return true;
 644     if (Shift > RHS.Shift) return false;
 645     return Inst->getType()->getPrimitiveSizeInBits() <
 646            RHS.Inst->getType()->getPrimitiveSizeInBits();
 647   }
 648 };
 649
 650 struct LoweredPHIRecord {
 651   PHINode *PN;        // The PHI that was lowered.
 652   unsigned Shift;     // The amount shifted.
 653   unsigned Width;     // The width extracted.
 654
 655   LoweredPHIRecord(PHINode *pn, unsigned Sh, Type *Ty)
 656     : PN(pn), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
 657
 658   // Ctor form used by DenseMap.
 659   LoweredPHIRecord(PHINode *pn, unsigned Sh)
 660     : PN(pn), Shift(Sh), Width(0) {}
 661 };
 662 }
 663
 664 namespace llvm {
 665   template<>
 666   struct DenseMapInfo<LoweredPHIRecord> {
 667     static inline LoweredPHIRecord getEmptyKey() {
 668       return LoweredPHIRecord(nullptr, 0);
 669     }
 670     static inline LoweredPHIRecord getTombstoneKey() {
 671       return LoweredPHIRecord(nullptr, 1);
 672     }
 673     static unsigned getHashValue(const LoweredPHIRecord &Val) {
 674       return DenseMapInfo<PHINode*>::getHashValue(Val.PN) ^ (Val.Shift>>3) ^
 675              (Val.Width>>3);
 676     }
 677     static bool isEqual(const LoweredPHIRecord &LHS,
 678                         const LoweredPHIRecord &RHS) {
 679       return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift &&
 680              LHS.Width == RHS.Width;
 681     }
 682   };
 683 }
 684
 685
 686 /// This is an integer PHI and we know that it has an illegal type: see if it is
 687 /// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
 688 /// the various pieces being extracted. This sort of thing is introduced when
 689 /// SROA promotes an aggregate to large integer values.
 690 ///
 691 /// TODO: The user of the trunc may be an bitcast to float/double/vector or an
 692 /// inttoptr.  We should produce new PHIs in the right type.
 693 ///
 694 Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
 695   // PHIUsers - Keep track of all of the truncated values extracted from a set
 696   // of PHIs, along with their offset.  These are the things we want to rewrite.
 697   SmallVector<PHIUsageRecord, 16> PHIUsers;
 698
 699   // PHIs are often mutually cyclic, so we keep track of a whole set of PHI
 700   // nodes which are extracted from. PHIsToSlice is a set we use to avoid
 701   // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to
 702   // check the uses of (to ensure they are all extracts).
 703   SmallVector<PHINode*, 8> PHIsToSlice;
 704   SmallPtrSet<PHINode*, 8> PHIsInspected;
 705
 706   PHIsToSlice.push_back(&FirstPhi);
 707   PHIsInspected.insert(&FirstPhi);
 708
 709   for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {
 710     PHINode *PN = PHIsToSlice[PHIId];
 711
 712     // Scan the input list of the PHI.  If any input is an invoke, and if the
 713     // input is defined in the predecessor, then we won't be split the critical
 714     // edge which is required to insert a truncate.  Because of this, we have to
 715     // bail out.
 716     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 717       InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i));
 718       if (!II) continue;
 719       if (II->getParent() != PN->getIncomingBlock(i))
 720         continue;
 721
 722       // If we have a phi, and if it's directly in the predecessor, then we have
 723       // a critical edge where we need to put the truncate.  Since we can't
 724       // split the edge in instcombine, we have to bail out.
 725       return nullptr;
 726     }
 727
 728     for (User *U : PN->users()) {
 729       Instruction *UserI = cast<Instruction>(U);
 730
 731       // If the user is a PHI, inspect its uses recursively.
 732       if (PHINode *UserPN = dyn_cast<PHINode>(UserI)) {
 733         if (PHIsInspected.insert(UserPN).second)
 734           PHIsToSlice.push_back(UserPN);
 735         continue;
 736       }
 737
 738       // Truncates are always ok.
 739       if (isa<TruncInst>(UserI)) {
 740         PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));
 741         continue;
 742       }
 743
 744       // Otherwise it must be a lshr which can only be used by one trunc.
 745       if (UserI->getOpcode() != Instruction::LShr ||
 746           !UserI->hasOneUse() || !isa<TruncInst>(UserI->user_back()) ||
 747           !isa<ConstantInt>(UserI->getOperand(1)))
 748         return nullptr;
 749
 750       unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue();
 751       PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));
 752     }
 753   }
 754
 755   // If we have no users, they must be all self uses, just nuke the PHI.
 756   if (PHIUsers.empty())
 757     return replaceInstUsesWith(FirstPhi, UndefValue::get(FirstPhi.getType()));
 758
 759   // If this phi node is transformable, create new PHIs for all the pieces
 760   // extracted out of it.  First, sort the users by their offset and size.
 761   array_pod_sort(PHIUsers.begin(), PHIUsers.end());
 762
 763   DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';
 764         for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
 765           dbgs() << "AND USER PHI #" << i << ": " << *PHIsToSlice[i] << '\n';
 766     );
 767
 768   // PredValues - This is a temporary used when rewriting PHI nodes.  It is
 769   // hoisted out here to avoid construction/destruction thrashing.
 770   DenseMap<BasicBlock*, Value*> PredValues;
 771
 772   // ExtractedVals - Each new PHI we introduce is saved here so we don't
 773   // introduce redundant PHIs.
 774   DenseMap<LoweredPHIRecord, PHINode*> ExtractedVals;
 775
 776   for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {
 777     unsigned PHIId = PHIUsers[UserI].PHIId;
 778     PHINode *PN = PHIsToSlice[PHIId];
 779     unsigned Offset = PHIUsers[UserI].Shift;
 780     Type *Ty = PHIUsers[UserI].Inst->getType();
 781
 782     PHINode *EltPHI;
 783
 784     // If we've already lowered a user like this, reuse the previously lowered
 785     // value.
 786     if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {
 787
 788       // Otherwise, Create the new PHI node for this user.
 789       EltPHI = PHINode::Create(Ty, PN->getNumIncomingValues(),
 790                                PN->getName()+".off"+Twine(Offset), PN);
 791       assert(EltPHI->getType() != PN->getType() &&
 792              "Truncate didn't shrink phi?");
 793
 794       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 795         BasicBlock *Pred = PN->getIncomingBlock(i);
 796         Value *&PredVal = PredValues[Pred];
 797
 798         // If we already have a value for this predecessor, reuse it.
 799         if (PredVal) {
 800           EltPHI->addIncoming(PredVal, Pred);
 801           continue;
 802         }
 803
 804         // Handle the PHI self-reuse case.
 805         Value *InVal = PN->getIncomingValue(i);
 806         if (InVal == PN) {
 807           PredVal = EltPHI;
 808           EltPHI->addIncoming(PredVal, Pred);
 809           continue;
 810         }
 811
 812         if (PHINode *InPHI = dyn_cast<PHINode>(PN)) {
 813           // If the incoming value was a PHI, and if it was one of the PHIs we
 814           // already rewrote it, just use the lowered value.
 815           if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {
 816             PredVal = Res;
 817             EltPHI->addIncoming(PredVal, Pred);
 818             continue;
 819           }
 820         }
 821
 822         // Otherwise, do an extract in the predecessor.
 823         Builder->SetInsertPoint(Pred->getTerminator());
 824         Value *Res = InVal;
 825         if (Offset)
 826           Res = Builder->CreateLShr(Res, ConstantInt::get(InVal->getType(),
 827                                                           Offset), "extract");
 828         Res = Builder->CreateTrunc(Res, Ty, "extract.t");
 829         PredVal = Res;
 830         EltPHI->addIncoming(Res, Pred);
 831
 832         // If the incoming value was a PHI, and if it was one of the PHIs we are
 833         // rewriting, we will ultimately delete the code we inserted.  This
 834         // means we need to revisit that PHI to make sure we extract out the
 835         // needed piece.
 836         if (PHINode *OldInVal = dyn_cast<PHINode>(PN->getIncomingValue(i)))
 837           if (PHIsInspected.count(OldInVal)) {
 838             unsigned RefPHIId = std::find(PHIsToSlice.begin(),PHIsToSlice.end(),
 839                                           OldInVal)-PHIsToSlice.begin();
 840             PHIUsers.push_back(PHIUsageRecord(RefPHIId, Offset,
 841                                               cast<Instruction>(Res)));
 842             ++UserE;
 843           }
 844       }
 845       PredValues.clear();
 846
 847       DEBUG(dbgs() << "  Made element PHI for offset " << Offset << ": "
 848                    << *EltPHI << '\n');
 849       ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;
 850     }
 851
 852     // Replace the use of this piece with the PHI node.
 853     replaceInstUsesWith(*PHIUsers[UserI].Inst, EltPHI);
 854   }
 855
 856   // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
 857   // with undefs.
 858   Value *Undef = UndefValue::get(FirstPhi.getType());
 859   for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
 860     replaceInstUsesWith(*PHIsToSlice[i], Undef);
 861   return replaceInstUsesWith(FirstPhi, Undef);
 862 }
 863
 864 // PHINode simplification
 865 //
 866 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
 867   if (Value *V = SimplifyInstruction(&PN, DL, TLI, DT, AC))
 868     return replaceInstUsesWith(PN, V);
 869
 870   if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
 871     return Result;
 872
 873   // If all PHI operands are the same operation, pull them through the PHI,
 874   // reducing code size.
 875   if (isa<Instruction>(PN.getIncomingValue(0)) &&
 876       isa<Instruction>(PN.getIncomingValue(1)) &&
 877       cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
 878       cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
 879       // FIXME: The hasOneUse check will fail for PHIs that use the value more
 880       // than themselves more than once.
 881       PN.getIncomingValue(0)->hasOneUse())
 882     if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
 883       return Result;
 884
 885   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
 886   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
 887   // PHI)... break the cycle.
 888   if (PN.hasOneUse()) {
 889     Instruction *PHIUser = cast<Instruction>(PN.user_back());
 890     if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
 891       SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
 892       PotentiallyDeadPHIs.insert(&PN);
 893       if (DeadPHICycle(PU, PotentiallyDeadPHIs))
 894         return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
 895     }
 896
 897     // If this phi has a single use, and if that use just computes a value for
 898     // the next iteration of a loop, delete the phi.  This occurs with unused
 899     // induction variables, e.g. "for (int j = 0; ; ++j);".  Detecting this
 900     // common case here is good because the only other things that catch this
 901     // are induction variable analysis (sometimes) and ADCE, which is only run
 902     // late.
 903     if (PHIUser->hasOneUse() &&
 904         (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
 905         PHIUser->user_back() == &PN) {
 906       return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
 907     }
 908     // When a PHI is used only to be compared with zero, it is safe to replace
 909     // an incoming value proved as known nonzero with any non-zero constant.
 910     // For example, in the code below, the incoming value %v can be replaced
 911     // with any non-zero constant based on the fact that the PHI is only used to
 912     // be compared with zero and %v is a known non-zero value:
 913     // %v = select %cond, 1, 2
 914     // %p = phi [%v, BB] ...
 915     //      icmp eq, %p, 0
 916     auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
 917     // FIXME: To be simple, handle only integer type for now.
 918     if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
 919         match(CmpInst->getOperand(1), m_Zero())) {
 920       ConstantInt *NonZeroConst = nullptr;
 921       for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
 922         Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
 923         Value *VA = PN.getIncomingValue(i);
 924         if (isKnownNonZero(VA, DL, 0, AC, CtxI, DT)) {
 925           if (!NonZeroConst)
 926             NonZeroConst = GetAnyNonZeroConstInt(PN);
 927           PN.setIncomingValue(i, NonZeroConst);
 928         }
 929       }
 930     }
 931   }
 932
 933   // We sometimes end up with phi cycles that non-obviously end up being the
 934   // same value, for example:
 935   //   z = some value; x = phi (y, z); y = phi (x, z)
 936   // where the phi nodes don't necessarily need to be in the same block.  Do a
 937   // quick check to see if the PHI node only contains a single non-phi value, if
 938   // so, scan to see if the phi cycle is actually equal to that value.
 939   {
 940     unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();
 941     // Scan for the first non-phi operand.
 942     while (InValNo != NumIncomingVals &&
 943            isa<PHINode>(PN.getIncomingValue(InValNo)))
 944       ++InValNo;
 945
 946     if (InValNo != NumIncomingVals) {
 947       Value *NonPhiInVal = PN.getIncomingValue(InValNo);
 948
 949       // Scan the rest of the operands to see if there are any conflicts, if so
 950       // there is no need to recursively scan other phis.
 951       for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
 952         Value *OpVal = PN.getIncomingValue(InValNo);
 953         if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
 954           break;
 955       }
 956
 957       // If we scanned over all operands, then we have one unique value plus
 958       // phi values.  Scan PHI nodes to see if they all merge in each other or
 959       // the value.
 960       if (InValNo == NumIncomingVals) {
 961         SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
 962         if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
 963           return replaceInstUsesWith(PN, NonPhiInVal);
 964       }
 965     }
 966   }
 967
 968   // If there are multiple PHIs, sort their operands so that they all list
 969   // the blocks in the same order. This will help identical PHIs be eliminated
 970   // by other passes. Other passes shouldn't depend on this for correctness
 971   // however.
 972   PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());
 973   if (&PN != FirstPN)
 974     for (unsigned i = 0, e = FirstPN->getNumIncomingValues(); i != e; ++i) {
 975       BasicBlock *BBA = PN.getIncomingBlock(i);
 976       BasicBlock *BBB = FirstPN->getIncomingBlock(i);
 977       if (BBA != BBB) {
 978         Value *VA = PN.getIncomingValue(i);
 979         unsigned j = PN.getBasicBlockIndex(BBB);
 980         Value *VB = PN.getIncomingValue(j);
 981         PN.setIncomingBlock(i, BBB);
 982         PN.setIncomingValue(i, VB);
 983         PN.setIncomingBlock(j, BBA);
 984         PN.setIncomingValue(j, VA);
 985         // NOTE: Instcombine normally would want us to "return &PN" if we
 986         // modified any of the operands of an instruction.  However, since we
 987         // aren't adding or removing uses (just rearranging them) we don't do
 988         // this in this case.
 989       }
 990     }
 991
 992   // If this is an integer PHI and we know that it has an illegal type, see if
 993   // it is only used by trunc or trunc(lshr) operations.  If so, we split the
 994   // PHI into the various pieces being extracted.  This sort of thing is
 995   // introduced when SROA promotes an aggregate to a single large integer type.
 996   if (PN.getType()->isIntegerTy() &&
 997       !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
 998     if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
 999       return Res;
1000
1001   return nullptr;
1002 }