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

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