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