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/Analysis/ValueTracking.h" 16 #include "llvm/Constants.h" 17 #include "llvm/Instructions.h" 18 #include "llvm/Analysis/Dominators.h" 19 #include "llvm/Analysis/InstructionSimplify.h" 20 #include "llvm/Support/Debug.h" 21 #include "llvm/Support/ErrorHandling.h" 22 #include "llvm/Support/raw_ostream.h" 23 using namespace llvm; 24 25 static bool CanPHITrans(Instruction *Inst) { 26 if (isa<PHINode>(Inst) || 27 isa<GetElementPtrInst>(Inst)) 28 return true; 29 30 if (isa<CastInst>(Inst) && 31 isSafeToSpeculativelyExecute(Inst)) 32 return true; 33 34 if (Inst->getOpcode() == Instruction::Add && 35 isa<ConstantInt>(Inst->getOperand(1))) 36 return true; 37 38 // cerr << "MEMDEP: Could not PHI translate: " << *Pointer; 39 // if (isa<BitCastInst>(PtrInst) || isa<GetElementPtrInst>(PtrInst)) 40 // cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0); 41 return false; 42 } 43 44 void PHITransAddr::dump() const { 45 if (Addr == 0) { 46 dbgs() << "PHITransAddr: null\n"; 47 return; 48 } 49 dbgs() << "PHITransAddr: " << *Addr << "\n"; 50 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 51 dbgs() << " Input #" << i << " is " << *InstInputs[i] << "\n"; 52 } 53 54 55 static bool VerifySubExpr(Value *Expr, 56 SmallVectorImpl<Instruction*> &InstInputs) { 57 // If this is a non-instruction value, there is nothing to do. 58 Instruction *I = dyn_cast<Instruction>(Expr); 59 if (I == 0) return true; 60 61 // If it's an instruction, it is either in Tmp or its operands recursively 62 // are. 63 SmallVectorImpl<Instruction*>::iterator Entry = 64 std::find(InstInputs.begin(), InstInputs.end(), I); 65 if (Entry != InstInputs.end()) { 66 InstInputs.erase(Entry); 67 return true; 68 } 69 70 // If it isn't in the InstInputs list it is a subexpr incorporated into the 71 // address. Sanity check that it is phi translatable. 72 if (!CanPHITrans(I)) { 73 errs() << "Non phi translatable instruction found in PHITransAddr:\n"; 74 errs() << *I << '\n'; 75 llvm_unreachable("Either something is missing from InstInputs or " 76 "CanPHITrans is wrong."); 77 } 78 79 // Validate the operands of the instruction. 80 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) 81 if (!VerifySubExpr(I->getOperand(i), InstInputs)) 82 return false; 83 84 return true; 85 } 86 87 /// Verify - Check internal consistency of this data structure. If the 88 /// structure is valid, it returns true. If invalid, it prints errors and 89 /// returns false. 90 bool PHITransAddr::Verify() const { 91 if (Addr == 0) return true; 92 93 SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end()); 94 95 if (!VerifySubExpr(Addr, Tmp)) 96 return false; 97 98 if (!Tmp.empty()) { 99 errs() << "PHITransAddr contains extra instructions:\n"; 100 for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) 101 errs() << " InstInput #" << i << " is " << *InstInputs[i] << "\n"; 102 llvm_unreachable("This is unexpected."); 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. 113 bool 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 121 static 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 143 Value *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 (!isSafeToSpeculativelyExecute(Cast)) 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, TD, TLI, 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, TLI, 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. 320 bool 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 /// 343 Value *PHITransAddr:: 344 PHITranslateWithInsertion(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 /// 367 Value *PHITransAddr:: 368 InsertPHITranslatedSubExpr(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 (!isSafeToSpeculativelyExecute(Cast)) 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], makeArrayRef(GEPOps).slice(1), 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