LLVM API Documentation
00001 //===- AddrModeMatcher.cpp - Addressing mode matching facility --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements target addressing mode matcher class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Transforms/Utils/AddrModeMatcher.h" 00015 #include "llvm/DerivedTypes.h" 00016 #include "llvm/GlobalValue.h" 00017 #include "llvm/Instruction.h" 00018 #include "llvm/Assembly/Writer.h" 00019 #include "llvm/Target/TargetData.h" 00020 #include "llvm/Support/GetElementPtrTypeIterator.h" 00021 #include "llvm/Support/PatternMatch.h" 00022 #include "llvm/Support/raw_ostream.h" 00023 00024 using namespace llvm; 00025 using namespace llvm::PatternMatch; 00026 00027 void ExtAddrMode::print(raw_ostream &OS) const { 00028 bool NeedPlus = false; 00029 OS << "["; 00030 if (BaseGV) { 00031 OS << (NeedPlus ? " + " : "") 00032 << "GV:"; 00033 WriteAsOperand(OS, BaseGV, /*PrintType=*/false); 00034 NeedPlus = true; 00035 } 00036 00037 if (BaseOffs) 00038 OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true; 00039 00040 if (BaseReg) { 00041 OS << (NeedPlus ? " + " : "") 00042 << "Base:"; 00043 WriteAsOperand(OS, BaseReg, /*PrintType=*/false); 00044 NeedPlus = true; 00045 } 00046 if (Scale) { 00047 OS << (NeedPlus ? " + " : "") 00048 << Scale << "*"; 00049 WriteAsOperand(OS, ScaledReg, /*PrintType=*/false); 00050 NeedPlus = true; 00051 } 00052 00053 OS << ']'; 00054 } 00055 00056 void ExtAddrMode::dump() const { 00057 print(errs()); 00058 cerr << '\n'; 00059 } 00060 00061 00062 /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode. 00063 /// Return true and update AddrMode if this addr mode is legal for the target, 00064 /// false if not. 00065 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale, 00066 unsigned Depth) { 00067 // If Scale is 1, then this is the same as adding ScaleReg to the addressing 00068 // mode. Just process that directly. 00069 if (Scale == 1) 00070 return MatchAddr(ScaleReg, Depth); 00071 00072 // If the scale is 0, it takes nothing to add this. 00073 if (Scale == 0) 00074 return true; 00075 00076 // If we already have a scale of this value, we can add to it, otherwise, we 00077 // need an available scale field. 00078 if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 00079 return false; 00080 00081 ExtAddrMode TestAddrMode = AddrMode; 00082 00083 // Add scale to turn X*4+X*3 -> X*7. This could also do things like 00084 // [A+B + A*7] -> [B+A*8]. 00085 TestAddrMode.Scale += Scale; 00086 TestAddrMode.ScaledReg = ScaleReg; 00087 00088 // If the new address isn't legal, bail out. 00089 if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) 00090 return false; 00091 00092 // It was legal, so commit it. 00093 AddrMode = TestAddrMode; 00094 00095 // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 00096 // to see if ScaleReg is actually X+C. If so, we can turn this into adding 00097 // X*Scale + C*Scale to addr mode. 00098 ConstantInt *CI = 0; Value *AddLHS = 0; 00099 if (isa<Instruction>(ScaleReg) && // not a constant expr. 00100 match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { 00101 TestAddrMode.ScaledReg = AddLHS; 00102 TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; 00103 00104 // If this addressing mode is legal, commit it and remember that we folded 00105 // this instruction. 00106 if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) { 00107 AddrModeInsts.push_back(cast<Instruction>(ScaleReg)); 00108 AddrMode = TestAddrMode; 00109 return true; 00110 } 00111 } 00112 00113 // Otherwise, not (x+c)*scale, just return what we have. 00114 return true; 00115 } 00116 00117 /// MightBeFoldableInst - This is a little filter, which returns true if an 00118 /// addressing computation involving I might be folded into a load/store 00119 /// accessing it. This doesn't need to be perfect, but needs to accept at least 00120 /// the set of instructions that MatchOperationAddr can. 00121 static bool MightBeFoldableInst(Instruction *I) { 00122 switch (I->getOpcode()) { 00123 case Instruction::BitCast: 00124 // Don't touch identity bitcasts. 00125 if (I->getType() == I->getOperand(0)->getType()) 00126 return false; 00127 return isa<PointerType>(I->getType()) || isa<IntegerType>(I->getType()); 00128 case Instruction::PtrToInt: 00129 // PtrToInt is always a noop, as we know that the int type is pointer sized. 00130 return true; 00131 case Instruction::IntToPtr: 00132 // We know the input is intptr_t, so this is foldable. 00133 return true; 00134 case Instruction::Add: 00135 return true; 00136 case Instruction::Mul: 00137 case Instruction::Shl: 00138 // Can only handle X*C and X << C. 00139 return isa<ConstantInt>(I->getOperand(1)); 00140 case Instruction::GetElementPtr: 00141 return true; 00142 default: 00143 return false; 00144 } 00145 } 00146 00147 00148 /// MatchOperationAddr - Given an instruction or constant expr, see if we can 00149 /// fold the operation into the addressing mode. If so, update the addressing 00150 /// mode and return true, otherwise return false without modifying AddrMode. 00151 bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, 00152 unsigned Depth) { 00153 // Avoid exponential behavior on extremely deep expression trees. 00154 if (Depth >= 5) return false; 00155 00156 switch (Opcode) { 00157 case Instruction::PtrToInt: 00158 // PtrToInt is always a noop, as we know that the int type is pointer sized. 00159 return MatchAddr(AddrInst->getOperand(0), Depth); 00160 case Instruction::IntToPtr: 00161 // This inttoptr is a no-op if the integer type is pointer sized. 00162 if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == 00163 TLI.getPointerTy()) 00164 return MatchAddr(AddrInst->getOperand(0), Depth); 00165 return false; 00166 case Instruction::BitCast: 00167 // BitCast is always a noop, and we can handle it as long as it is 00168 // int->int or pointer->pointer (we don't want int<->fp or something). 00169 if ((isa<PointerType>(AddrInst->getOperand(0)->getType()) || 00170 isa<IntegerType>(AddrInst->getOperand(0)->getType())) && 00171 // Don't touch identity bitcasts. These were probably put here by LSR, 00172 // and we don't want to mess around with them. Assume it knows what it 00173 // is doing. 00174 AddrInst->getOperand(0)->getType() != AddrInst->getType()) 00175 return MatchAddr(AddrInst->getOperand(0), Depth); 00176 return false; 00177 case Instruction::Add: { 00178 // Check to see if we can merge in the RHS then the LHS. If so, we win. 00179 ExtAddrMode BackupAddrMode = AddrMode; 00180 unsigned OldSize = AddrModeInsts.size(); 00181 if (MatchAddr(AddrInst->getOperand(1), Depth+1) && 00182 MatchAddr(AddrInst->getOperand(0), Depth+1)) 00183 return true; 00184 00185 // Restore the old addr mode info. 00186 AddrMode = BackupAddrMode; 00187 AddrModeInsts.resize(OldSize); 00188 00189 // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 00190 if (MatchAddr(AddrInst->getOperand(0), Depth+1) && 00191 MatchAddr(AddrInst->getOperand(1), Depth+1)) 00192 return true; 00193 00194 // Otherwise we definitely can't merge the ADD in. 00195 AddrMode = BackupAddrMode; 00196 AddrModeInsts.resize(OldSize); 00197 break; 00198 } 00199 //case Instruction::Or: 00200 // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 00201 //break; 00202 case Instruction::Mul: 00203 case Instruction::Shl: { 00204 // Can only handle X*C and X << C. 00205 ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 00206 if (!RHS) return false; 00207 int64_t Scale = RHS->getSExtValue(); 00208 if (Opcode == Instruction::Shl) 00209 Scale = 1LL << Scale; 00210 00211 return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth); 00212 } 00213 case Instruction::GetElementPtr: { 00214 // Scan the GEP. We check it if it contains constant offsets and at most 00215 // one variable offset. 00216 int VariableOperand = -1; 00217 unsigned VariableScale = 0; 00218 00219 int64_t ConstantOffset = 0; 00220 const TargetData *TD = TLI.getTargetData(); 00221 gep_type_iterator GTI = gep_type_begin(AddrInst); 00222 for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 00223 if (const StructType *STy = dyn_cast<StructType>(*GTI)) { 00224 const StructLayout *SL = TD->getStructLayout(STy); 00225 unsigned Idx = 00226 cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 00227 ConstantOffset += SL->getElementOffset(Idx); 00228 } else { 00229 uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType()); 00230 if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 00231 ConstantOffset += CI->getSExtValue()*TypeSize; 00232 } else if (TypeSize) { // Scales of zero don't do anything. 00233 // We only allow one variable index at the moment. 00234 if (VariableOperand != -1) 00235 return false; 00236 00237 // Remember the variable index. 00238 VariableOperand = i; 00239 VariableScale = TypeSize; 00240 } 00241 } 00242 } 00243 00244 // A common case is for the GEP to only do a constant offset. In this case, 00245 // just add it to the disp field and check validity. 00246 if (VariableOperand == -1) { 00247 AddrMode.BaseOffs += ConstantOffset; 00248 if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ 00249 // Check to see if we can fold the base pointer in too. 00250 if (MatchAddr(AddrInst->getOperand(0), Depth+1)) 00251 return true; 00252 } 00253 AddrMode.BaseOffs -= ConstantOffset; 00254 return false; 00255 } 00256 00257 // Save the valid addressing mode in case we can't match. 00258 ExtAddrMode BackupAddrMode = AddrMode; 00259 unsigned OldSize = AddrModeInsts.size(); 00260 00261 // See if the scale and offset amount is valid for this target. 00262 AddrMode.BaseOffs += ConstantOffset; 00263 00264 // Match the base operand of the GEP. 00265 if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) { 00266 // If it couldn't be matched, just stuff the value in a register. 00267 if (AddrMode.HasBaseReg) { 00268 AddrMode = BackupAddrMode; 00269 AddrModeInsts.resize(OldSize); 00270 return false; 00271 } 00272 AddrMode.HasBaseReg = true; 00273 AddrMode.BaseReg = AddrInst->getOperand(0); 00274 } 00275 00276 // Match the remaining variable portion of the GEP. 00277 if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, 00278 Depth)) { 00279 // If it couldn't be matched, try stuffing the base into a register 00280 // instead of matching it, and retrying the match of the scale. 00281 AddrMode = BackupAddrMode; 00282 AddrModeInsts.resize(OldSize); 00283 if (AddrMode.HasBaseReg) 00284 return false; 00285 AddrMode.HasBaseReg = true; 00286 AddrMode.BaseReg = AddrInst->getOperand(0); 00287 AddrMode.BaseOffs += ConstantOffset; 00288 if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), 00289 VariableScale, Depth)) { 00290 // If even that didn't work, bail. 00291 AddrMode = BackupAddrMode; 00292 AddrModeInsts.resize(OldSize); 00293 return false; 00294 } 00295 } 00296 00297 return true; 00298 } 00299 } 00300 return false; 00301 } 00302 00303 /// MatchAddr - If we can, try to add the value of 'Addr' into the current 00304 /// addressing mode. If Addr can't be added to AddrMode this returns false and 00305 /// leaves AddrMode unmodified. This assumes that Addr is either a pointer type 00306 /// or intptr_t for the target. 00307 /// 00308 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) { 00309 if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 00310 // Fold in immediates if legal for the target. 00311 AddrMode.BaseOffs += CI->getSExtValue(); 00312 if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 00313 return true; 00314 AddrMode.BaseOffs -= CI->getSExtValue(); 00315 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 00316 // If this is a global variable, try to fold it into the addressing mode. 00317 if (AddrMode.BaseGV == 0) { 00318 AddrMode.BaseGV = GV; 00319 if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 00320 return true; 00321 AddrMode.BaseGV = 0; 00322 } 00323 } else if (Instruction *I = dyn_cast<Instruction>(Addr)) { 00324 ExtAddrMode BackupAddrMode = AddrMode; 00325 unsigned OldSize = AddrModeInsts.size(); 00326 00327 // Check to see if it is possible to fold this operation. 00328 if (MatchOperationAddr(I, I->getOpcode(), Depth)) { 00329 // Okay, it's possible to fold this. Check to see if it is actually 00330 // *profitable* to do so. We use a simple cost model to avoid increasing 00331 // register pressure too much. 00332 if (I->hasOneUse() || 00333 IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) { 00334 AddrModeInsts.push_back(I); 00335 return true; 00336 } 00337 00338 // It isn't profitable to do this, roll back. 00339 //cerr << "NOT FOLDING: " << *I; 00340 AddrMode = BackupAddrMode; 00341 AddrModeInsts.resize(OldSize); 00342 } 00343 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 00344 if (MatchOperationAddr(CE, CE->getOpcode(), Depth)) 00345 return true; 00346 } else if (isa<ConstantPointerNull>(Addr)) { 00347 // Null pointer gets folded without affecting the addressing mode. 00348 return true; 00349 } 00350 00351 // Worse case, the target should support [reg] addressing modes. :) 00352 if (!AddrMode.HasBaseReg) { 00353 AddrMode.HasBaseReg = true; 00354 AddrMode.BaseReg = Addr; 00355 // Still check for legality in case the target supports [imm] but not [i+r]. 00356 if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 00357 return true; 00358 AddrMode.HasBaseReg = false; 00359 AddrMode.BaseReg = 0; 00360 } 00361 00362 // If the base register is already taken, see if we can do [r+r]. 00363 if (AddrMode.Scale == 0) { 00364 AddrMode.Scale = 1; 00365 AddrMode.ScaledReg = Addr; 00366 if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 00367 return true; 00368 AddrMode.Scale = 0; 00369 AddrMode.ScaledReg = 0; 00370 } 00371 // Couldn't match. 00372 return false; 00373 } 00374 00375 00376 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified 00377 /// inline asm call are due to memory operands. If so, return true, otherwise 00378 /// return false. 00379 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, 00380 const TargetLowering &TLI) { 00381 std::vector<InlineAsm::ConstraintInfo> 00382 Constraints = IA->ParseConstraints(); 00383 00384 unsigned ArgNo = 1; // ArgNo - The operand of the CallInst. 00385 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 00386 TargetLowering::AsmOperandInfo OpInfo(Constraints[i]); 00387 00388 // Compute the value type for each operand. 00389 switch (OpInfo.Type) { 00390 case InlineAsm::isOutput: 00391 if (OpInfo.isIndirect) 00392 OpInfo.CallOperandVal = CI->getOperand(ArgNo++); 00393 break; 00394 case InlineAsm::isInput: 00395 OpInfo.CallOperandVal = CI->getOperand(ArgNo++); 00396 break; 00397 case InlineAsm::isClobber: 00398 // Nothing to do. 00399 break; 00400 } 00401 00402 // Compute the constraint code and ConstraintType to use. 00403 TLI.ComputeConstraintToUse(OpInfo, SDValue(), 00404 OpInfo.ConstraintType == TargetLowering::C_Memory); 00405 00406 // If this asm operand is our Value*, and if it isn't an indirect memory 00407 // operand, we can't fold it! 00408 if (OpInfo.CallOperandVal == OpVal && 00409 (OpInfo.ConstraintType != TargetLowering::C_Memory || 00410 !OpInfo.isIndirect)) 00411 return false; 00412 } 00413 00414 return true; 00415 } 00416 00417 00418 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a 00419 /// memory use. If we find an obviously non-foldable instruction, return true. 00420 /// Add the ultimately found memory instructions to MemoryUses. 00421 static bool FindAllMemoryUses(Instruction *I, 00422 SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses, 00423 SmallPtrSet<Instruction*, 16> &ConsideredInsts, 00424 const TargetLowering &TLI) { 00425 // If we already considered this instruction, we're done. 00426 if (!ConsideredInsts.insert(I)) 00427 return false; 00428 00429 // If this is an obviously unfoldable instruction, bail out. 00430 if (!MightBeFoldableInst(I)) 00431 return true; 00432 00433 // Loop over all the uses, recursively processing them. 00434 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 00435 UI != E; ++UI) { 00436 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00437 MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo())); 00438 continue; 00439 } 00440 00441 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00442 if (UI.getOperandNo() == 0) return true; // Storing addr, not into addr. 00443 MemoryUses.push_back(std::make_pair(SI, UI.getOperandNo())); 00444 continue; 00445 } 00446 00447 if (CallInst *CI = dyn_cast<CallInst>(*UI)) { 00448 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue()); 00449 if (IA == 0) return true; 00450 00451 // If this is a memory operand, we're cool, otherwise bail out. 00452 if (!IsOperandAMemoryOperand(CI, IA, I, TLI)) 00453 return true; 00454 continue; 00455 } 00456 00457 if (FindAllMemoryUses(cast<Instruction>(*UI), MemoryUses, ConsideredInsts, 00458 TLI)) 00459 return true; 00460 } 00461 00462 return false; 00463 } 00464 00465 00466 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at 00467 /// the use site that we're folding it into. If so, there is no cost to 00468 /// include it in the addressing mode. KnownLive1 and KnownLive2 are two values 00469 /// that we know are live at the instruction already. 00470 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1, 00471 Value *KnownLive2) { 00472 // If Val is either of the known-live values, we know it is live! 00473 if (Val == 0 || Val == KnownLive1 || Val == KnownLive2) 00474 return true; 00475 00476 // All values other than instructions and arguments (e.g. constants) are live. 00477 if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true; 00478 00479 // If Val is a constant sized alloca in the entry block, it is live, this is 00480 // true because it is just a reference to the stack/frame pointer, which is 00481 // live for the whole function. 00482 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val)) 00483 if (AI->isStaticAlloca()) 00484 return true; 00485 00486 // Check to see if this value is already used in the memory instruction's 00487 // block. If so, it's already live into the block at the very least, so we 00488 // can reasonably fold it. 00489 BasicBlock *MemBB = MemoryInst->getParent(); 00490 for (Value::use_iterator UI = Val->use_begin(), E = Val->use_end(); 00491 UI != E; ++UI) 00492 // We know that uses of arguments and instructions have to be instructions. 00493 if (cast<Instruction>(*UI)->getParent() == MemBB) 00494 return true; 00495 00496 return false; 00497 } 00498 00499 00500 00501 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing 00502 /// mode of the machine to fold the specified instruction into a load or store 00503 /// that ultimately uses it. However, the specified instruction has multiple 00504 /// uses. Given this, it may actually increase register pressure to fold it 00505 /// into the load. For example, consider this code: 00506 /// 00507 /// X = ... 00508 /// Y = X+1 00509 /// use(Y) -> nonload/store 00510 /// Z = Y+1 00511 /// load Z 00512 /// 00513 /// In this case, Y has multiple uses, and can be folded into the load of Z 00514 /// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to 00515 /// be live at the use(Y) line. If we don't fold Y into load Z, we use one 00516 /// fewer register. Since Y can't be folded into "use(Y)" we don't increase the 00517 /// number of computations either. 00518 /// 00519 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If 00520 /// X was live across 'load Z' for other reasons, we actually *would* want to 00521 /// fold the addressing mode in the Z case. This would make Y die earlier. 00522 bool AddressingModeMatcher:: 00523 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, 00524 ExtAddrMode &AMAfter) { 00525 if (IgnoreProfitability) return true; 00526 00527 // AMBefore is the addressing mode before this instruction was folded into it, 00528 // and AMAfter is the addressing mode after the instruction was folded. Get 00529 // the set of registers referenced by AMAfter and subtract out those 00530 // referenced by AMBefore: this is the set of values which folding in this 00531 // address extends the lifetime of. 00532 // 00533 // Note that there are only two potential values being referenced here, 00534 // BaseReg and ScaleReg (global addresses are always available, as are any 00535 // folded immediates). 00536 Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg; 00537 00538 // If the BaseReg or ScaledReg was referenced by the previous addrmode, their 00539 // lifetime wasn't extended by adding this instruction. 00540 if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 00541 BaseReg = 0; 00542 if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 00543 ScaledReg = 0; 00544 00545 // If folding this instruction (and it's subexprs) didn't extend any live 00546 // ranges, we're ok with it. 00547 if (BaseReg == 0 && ScaledReg == 0) 00548 return true; 00549 00550 // If all uses of this instruction are ultimately load/store/inlineasm's, 00551 // check to see if their addressing modes will include this instruction. If 00552 // so, we can fold it into all uses, so it doesn't matter if it has multiple 00553 // uses. 00554 SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses; 00555 SmallPtrSet<Instruction*, 16> ConsideredInsts; 00556 if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI)) 00557 return false; // Has a non-memory, non-foldable use! 00558 00559 // Now that we know that all uses of this instruction are part of a chain of 00560 // computation involving only operations that could theoretically be folded 00561 // into a memory use, loop over each of these uses and see if they could 00562 // *actually* fold the instruction. 00563 SmallVector<Instruction*, 32> MatchedAddrModeInsts; 00564 for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) { 00565 Instruction *User = MemoryUses[i].first; 00566 unsigned OpNo = MemoryUses[i].second; 00567 00568 // Get the access type of this use. If the use isn't a pointer, we don't 00569 // know what it accesses. 00570 Value *Address = User->getOperand(OpNo); 00571 if (!isa<PointerType>(Address->getType())) 00572 return false; 00573 const Type *AddressAccessTy = 00574 cast<PointerType>(Address->getType())->getElementType(); 00575 00576 // Do a match against the root of this address, ignoring profitability. This 00577 // will tell us if the addressing mode for the memory operation will 00578 // *actually* cover the shared instruction. 00579 ExtAddrMode Result; 00580 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy, 00581 MemoryInst, Result); 00582 Matcher.IgnoreProfitability = true; 00583 bool Success = Matcher.MatchAddr(Address, 0); 00584 Success = Success; assert(Success && "Couldn't select *anything*?"); 00585 00586 // If the match didn't cover I, then it won't be shared by it. 00587 if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(), 00588 I) == MatchedAddrModeInsts.end()) 00589 return false; 00590 00591 MatchedAddrModeInsts.clear(); 00592 } 00593 00594 return true; 00595 }