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