PHITransAddr.cpp revision 9fc5cdf77c812aaa80419036de27576d45894d0d
1//===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===// 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 PHITransAddr class. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Analysis/PHITransAddr.h" 15#include "llvm/Instructions.h" 16#include "llvm/Analysis/Dominators.h" 17#include "llvm/Analysis/InstructionSimplify.h" 18#include "llvm/Support/Debug.h" 19#include "llvm/Support/ErrorHandling.h" 20#include "llvm/Support/raw_ostream.h" 21using namespace llvm; 22 23static bool CanPHITrans(Instruction *Inst) { 24 if (isa<PHINode>(Inst) || 25 isa<GetElementPtrInst>(Inst)) 26 return true; 27 28 if (isa<CastInst>(Inst) && 29 Inst->isSafeToSpeculativelyExecute()) 30 return true; 31 32 if (Inst->getOpcode() == Instruction::Add && 33 isa<ConstantInt>(Inst->getOperand(1))) 34 return true; 35 36 // cerr << "MEMDEP: Could not PHI translate: " << *Pointer; 37 // if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst)) 38 // cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0); 39 return false; 40} 41 42void PHITransAddr::dump() const { 43 if (Addr == 0) { 44 dbgs() << "PHITransAddr: null\n"; 45 return; 46 } 47 dbgs() << "PHITransAddr: " << *Addr << "\n"; 48 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 49 dbgs() << " Input #" << i << " is " << *InstInputs[i] << "\n"; 50} 51 52 53static bool VerifySubExpr(Value *Expr, 54 SmallVectorImpl<Instruction*> &InstInputs) { 55 // If this is a non-instruction value, there is nothing to do. 56 Instruction *I = dyn_cast<Instruction>(Expr); 57 if (I == 0) return true; 58 59 // If it's an instruction, it is either in Tmp or its operands recursively 60 // are. 61 SmallVectorImpl<Instruction*>::iterator Entry = 62 std::find(InstInputs.begin(), InstInputs.end(), I); 63 if (Entry != InstInputs.end()) { 64 InstInputs.erase(Entry); 65 return true; 66 } 67 68 // If it isn't in the InstInputs list it is a subexpr incorporated into the 69 // address. Sanity check that it is phi translatable. 70 if (!CanPHITrans(I)) { 71 errs() << "Non phi translatable instruction found in PHITransAddr:\n"; 72 errs() << *I << '\n'; 73 llvm_unreachable("Either something is missing from InstInputs or " 74 "CanPHITrans is wrong."); 75 return false; 76 } 77 78 // Validate the operands of the instruction. 79 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 80 if (!VerifySubExpr(I->getOperand(i), InstInputs)) 81 return false; 82 83 return true; 84} 85 86/// Verify - Check internal consistency of this data structure. If the 87/// structure is valid, it returns true. If invalid, it prints errors and 88/// returns false. 89bool PHITransAddr::Verify() const { 90 if (Addr == 0) return true; 91 92 SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end()); 93 94 if (!VerifySubExpr(Addr, Tmp)) 95 return false; 96 97 if (!Tmp.empty()) { 98 errs() << "PHITransAddr contains extra instructions:\n"; 99 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 100 errs() << " InstInput #" << i << " is " << *InstInputs[i] << "\n"; 101 llvm_unreachable("This is unexpected."); 102 return false; 103 } 104 105 // a-ok. 106 return true; 107} 108 109 110/// IsPotentiallyPHITranslatable - If this needs PHI translation, return true 111/// if we have some hope of doing it. This should be used as a filter to 112/// avoid calling PHITranslateValue in hopeless situations. 113bool PHITransAddr::IsPotentiallyPHITranslatable() const { 114 // If the input value is not an instruction, or if it is not defined in CurBB, 115 // then we don't need to phi translate it. 116 Instruction *Inst = dyn_cast<Instruction>(Addr); 117 return Inst == 0 || CanPHITrans(Inst); 118} 119 120 121static void RemoveInstInputs(Value *V, 122 SmallVectorImpl<Instruction*> &InstInputs) { 123 Instruction *I = dyn_cast<Instruction>(V); 124 if (I == 0) return; 125 126 // If the instruction is in the InstInputs list, remove it. 127 SmallVectorImpl<Instruction*>::iterator Entry = 128 std::find(InstInputs.begin(), InstInputs.end(), I); 129 if (Entry != InstInputs.end()) { 130 InstInputs.erase(Entry); 131 return; 132 } 133 134 assert(!isa<PHINode>(I) && "Error, removing something that isn't an input"); 135 136 // Otherwise, it must have instruction inputs itself. Zap them recursively. 137 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 138 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i))) 139 RemoveInstInputs(Op, InstInputs); 140 } 141} 142 143Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB, 144 BasicBlock *PredBB, 145 const DominatorTree *DT) { 146 // If this is a non-instruction value, it can't require PHI translation. 147 Instruction *Inst = dyn_cast<Instruction>(V); 148 if (Inst == 0) return V; 149 150 // Determine whether 'Inst' is an input to our PHI translatable expression. 151 bool isInput = std::count(InstInputs.begin(), InstInputs.end(), Inst); 152 153 // Handle inputs instructions if needed. 154 if (isInput) { 155 if (Inst->getParent() != CurBB) { 156 // If it is an input defined in a different block, then it remains an 157 // input. 158 return Inst; 159 } 160 161 // If 'Inst' is defined in this block and is an input that needs to be phi 162 // translated, we need to incorporate the value into the expression or fail. 163 164 // In either case, the instruction itself isn't an input any longer. 165 InstInputs.erase(std::find(InstInputs.begin(), InstInputs.end(), Inst)); 166 167 // If this is a PHI, go ahead and translate it. 168 if (PHINode *PN = dyn_cast<PHINode>(Inst)) 169 return AddAsInput(PN->getIncomingValueForBlock(PredBB)); 170 171 // If this is a non-phi value, and it is analyzable, we can incorporate it 172 // into the expression by making all instruction operands be inputs. 173 if (!CanPHITrans(Inst)) 174 return 0; 175 176 // All instruction operands are now inputs (and of course, they may also be 177 // defined in this block, so they may need to be phi translated themselves. 178 for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i) 179 if (Instruction *Op = dyn_cast<Instruction>(Inst->getOperand(i))) 180 InstInputs.push_back(Op); 181 } 182 183 // Ok, it must be an intermediate result (either because it started that way 184 // or because we just incorporated it into the expression). See if its 185 // operands need to be phi translated, and if so, reconstruct it. 186 187 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) { 188 if (!Cast->isSafeToSpeculativelyExecute()) return 0; 189 Value *PHIIn = PHITranslateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT); 190 if (PHIIn == 0) return 0; 191 if (PHIIn == Cast->getOperand(0)) 192 return Cast; 193 194 // Find an available version of this cast. 195 196 // Constants are trivial to find. 197 if (Constant *C = dyn_cast<Constant>(PHIIn)) 198 return AddAsInput(ConstantExpr::getCast(Cast->getOpcode(), 199 C, Cast->getType())); 200 201 // Otherwise we have to see if a casted version of the incoming pointer 202 // is available. If so, we can use it, otherwise we have to fail. 203 for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end(); 204 UI != E; ++UI) { 205 if (CastInst *CastI = dyn_cast<CastInst>(*UI)) 206 if (CastI->getOpcode() == Cast->getOpcode() && 207 CastI->getType() == Cast->getType() && 208 (!DT || DT->dominates(CastI->getParent(), PredBB))) 209 return CastI; 210 } 211 return 0; 212 } 213 214 // Handle getelementptr with at least one PHI translatable operand. 215 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) { 216 SmallVector<Value*, 8> GEPOps; 217 bool AnyChanged = false; 218 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) { 219 Value *GEPOp = PHITranslateSubExpr(GEP->getOperand(i), CurBB, PredBB, DT); 220 if (GEPOp == 0) return 0; 221 222 AnyChanged |= GEPOp != GEP->getOperand(i); 223 GEPOps.push_back(GEPOp); 224 } 225 226 if (!AnyChanged) 227 return GEP; 228 229 // Simplify the GEP to handle 'gep x, 0' -> x etc. 230 if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD, DT)) { 231 for (unsigned i = 0, e = GEPOps.size(); i != e; ++i) 232 RemoveInstInputs(GEPOps[i], InstInputs); 233 234 return AddAsInput(V); 235 } 236 237 // Scan to see if we have this GEP available. 238 Value *APHIOp = GEPOps[0]; 239 for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end(); 240 UI != E; ++UI) { 241 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(*UI)) 242 if (GEPI->getType() == GEP->getType() && 243 GEPI->getNumOperands() == GEPOps.size() && 244 GEPI->getParent()->getParent() == CurBB->getParent() && 245 (!DT || DT->dominates(GEPI->getParent(), PredBB))) { 246 bool Mismatch = false; 247 for (unsigned i = 0, e = GEPOps.size(); i != e; ++i) 248 if (GEPI->getOperand(i) != GEPOps[i]) { 249 Mismatch = true; 250 break; 251 } 252 if (!Mismatch) 253 return GEPI; 254 } 255 } 256 return 0; 257 } 258 259 // Handle add with a constant RHS. 260 if (Inst->getOpcode() == Instruction::Add && 261 isa<ConstantInt>(Inst->getOperand(1))) { 262 // PHI translate the LHS. 263 Constant *RHS = cast<ConstantInt>(Inst->getOperand(1)); 264 bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap(); 265 bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap(); 266 267 Value *LHS = PHITranslateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT); 268 if (LHS == 0) return 0; 269 270 // If the PHI translated LHS is an add of a constant, fold the immediates. 271 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS)) 272 if (BOp->getOpcode() == Instruction::Add) 273 if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) { 274 LHS = BOp->getOperand(0); 275 RHS = ConstantExpr::getAdd(RHS, CI); 276 isNSW = isNUW = false; 277 278 // If the old 'LHS' was an input, add the new 'LHS' as an input. 279 if (std::count(InstInputs.begin(), InstInputs.end(), BOp)) { 280 RemoveInstInputs(BOp, InstInputs); 281 AddAsInput(LHS); 282 } 283 } 284 285 // See if the add simplifies away. 286 if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD, DT)) { 287 // If we simplified the operands, the LHS is no longer an input, but Res 288 // is. 289 RemoveInstInputs(LHS, InstInputs); 290 return AddAsInput(Res); 291 } 292 293 // If we didn't modify the add, just return it. 294 if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1)) 295 return Inst; 296 297 // Otherwise, see if we have this add available somewhere. 298 for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end(); 299 UI != E; ++UI) { 300 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(*UI)) 301 if (BO->getOpcode() == Instruction::Add && 302 BO->getOperand(0) == LHS && BO->getOperand(1) == RHS && 303 BO->getParent()->getParent() == CurBB->getParent() && 304 (!DT || DT->dominates(BO->getParent(), PredBB))) 305 return BO; 306 } 307 308 return 0; 309 } 310 311 // Otherwise, we failed. 312 return 0; 313} 314 315 316/// PHITranslateValue - PHI translate the current address up the CFG from 317/// CurBB to Pred, updating our state to reflect any needed changes. If the 318/// dominator tree DT is non-null, the translated value must dominate 319/// PredBB. This returns true on failure and sets Addr to null. 320bool PHITransAddr::PHITranslateValue(BasicBlock *CurBB, BasicBlock *PredBB, 321 const DominatorTree *DT) { 322 assert(Verify() && "Invalid PHITransAddr!"); 323 Addr = PHITranslateSubExpr(Addr, CurBB, PredBB, DT); 324 assert(Verify() && "Invalid PHITransAddr!"); 325 326 if (DT) { 327 // Make sure the value is live in the predecessor. 328 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr)) 329 if (!DT->dominates(Inst->getParent(), PredBB)) 330 Addr = 0; 331 } 332 333 return Addr == 0; 334} 335 336/// PHITranslateWithInsertion - PHI translate this value into the specified 337/// predecessor block, inserting a computation of the value if it is 338/// unavailable. 339/// 340/// All newly created instructions are added to the NewInsts list. This 341/// returns null on failure. 342/// 343Value *PHITransAddr:: 344PHITranslateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, 345 const DominatorTree &DT, 346 SmallVectorImpl<Instruction*> &NewInsts) { 347 unsigned NISize = NewInsts.size(); 348 349 // Attempt to PHI translate with insertion. 350 Addr = InsertPHITranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts); 351 352 // If successful, return the new value. 353 if (Addr) return Addr; 354 355 // If not, destroy any intermediate instructions inserted. 356 while (NewInsts.size() != NISize) 357 NewInsts.pop_back_val()->eraseFromParent(); 358 return 0; 359} 360 361 362/// InsertPHITranslatedPointer - Insert a computation of the PHI translated 363/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB 364/// block. All newly created instructions are added to the NewInsts list. 365/// This returns null on failure. 366/// 367Value *PHITransAddr:: 368InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB, 369 BasicBlock *PredBB, const DominatorTree &DT, 370 SmallVectorImpl<Instruction*> &NewInsts) { 371 // See if we have a version of this value already available and dominating 372 // PredBB. If so, there is no need to insert a new instance of it. 373 PHITransAddr Tmp(InVal, TD); 374 if (!Tmp.PHITranslateValue(CurBB, PredBB, &DT)) 375 return Tmp.getAddr(); 376 377 // If we don't have an available version of this value, it must be an 378 // instruction. 379 Instruction *Inst = cast<Instruction>(InVal); 380 381 // Handle cast of PHI translatable value. 382 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) { 383 if (!Cast->isSafeToSpeculativelyExecute()) return 0; 384 Value *OpVal = InsertPHITranslatedSubExpr(Cast->getOperand(0), 385 CurBB, PredBB, DT, NewInsts); 386 if (OpVal == 0) return 0; 387 388 // Otherwise insert a cast at the end of PredBB. 389 CastInst *New = CastInst::Create(Cast->getOpcode(), 390 OpVal, InVal->getType(), 391 InVal->getName()+".phi.trans.insert", 392 PredBB->getTerminator()); 393 NewInsts.push_back(New); 394 return New; 395 } 396 397 // Handle getelementptr with at least one PHI operand. 398 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) { 399 SmallVector<Value*, 8> GEPOps; 400 BasicBlock *CurBB = GEP->getParent(); 401 for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) { 402 Value *OpVal = InsertPHITranslatedSubExpr(GEP->getOperand(i), 403 CurBB, PredBB, DT, NewInsts); 404 if (OpVal == 0) return 0; 405 GEPOps.push_back(OpVal); 406 } 407 408 GetElementPtrInst *Result = 409 GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(), 410 InVal->getName()+".phi.trans.insert", 411 PredBB->getTerminator()); 412 Result->setIsInBounds(GEP->isInBounds()); 413 NewInsts.push_back(Result); 414 return Result; 415 } 416 417#if 0 418 // FIXME: This code works, but it is unclear that we actually want to insert 419 // a big chain of computation in order to make a value available in a block. 420 // This needs to be evaluated carefully to consider its cost trade offs. 421 422 // Handle add with a constant RHS. 423 if (Inst->getOpcode() == Instruction::Add && 424 isa<ConstantInt>(Inst->getOperand(1))) { 425 // PHI translate the LHS. 426 Value *OpVal = InsertPHITranslatedSubExpr(Inst->getOperand(0), 427 CurBB, PredBB, DT, NewInsts); 428 if (OpVal == 0) return 0; 429 430 BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1), 431 InVal->getName()+".phi.trans.insert", 432 PredBB->getTerminator()); 433 Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap()); 434 Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap()); 435 NewInsts.push_back(Res); 436 return Res; 437 } 438#endif 439 440 return 0; 441} 442