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