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