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