LLVM API Documentation

AddrModeMatcher.cpp

Go to the documentation of this file.
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 }