Home | History | Annotate | Download | only in Utils
      1 //===- AddrModeMatcher.cpp - Addressing mode matching facility --*- C++ -*-===//
      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 target addressing mode matcher class.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "llvm/Transforms/Utils/AddrModeMatcher.h"
     15 #include "llvm/DerivedTypes.h"
     16 #include "llvm/GlobalValue.h"
     17 #include "llvm/Instruction.h"
     18 #include "llvm/Assembly/Writer.h"
     19 #include "llvm/Target/TargetData.h"
     20 #include "llvm/Support/Debug.h"
     21 #include "llvm/Support/GetElementPtrTypeIterator.h"
     22 #include "llvm/Support/PatternMatch.h"
     23 #include "llvm/Support/raw_ostream.h"
     24 #include "llvm/Support/CallSite.h"
     25 
     26 using namespace llvm;
     27 using namespace llvm::PatternMatch;
     28 
     29 void ExtAddrMode::print(raw_ostream &OS) const {
     30   bool NeedPlus = false;
     31   OS << "[";
     32   if (BaseGV) {
     33     OS << (NeedPlus ? " + " : "")
     34        << "GV:";
     35     WriteAsOperand(OS, BaseGV, /*PrintType=*/false);
     36     NeedPlus = true;
     37   }
     38 
     39   if (BaseOffs)
     40     OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true;
     41 
     42   if (BaseReg) {
     43     OS << (NeedPlus ? " + " : "")
     44        << "Base:";
     45     WriteAsOperand(OS, BaseReg, /*PrintType=*/false);
     46     NeedPlus = true;
     47   }
     48   if (Scale) {
     49     OS << (NeedPlus ? " + " : "")
     50        << Scale << "*";
     51     WriteAsOperand(OS, ScaledReg, /*PrintType=*/false);
     52     NeedPlus = true;
     53   }
     54 
     55   OS << ']';
     56 }
     57 
     58 void ExtAddrMode::dump() const {
     59   print(dbgs());
     60   dbgs() << '\n';
     61 }
     62 
     63 
     64 /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode.
     65 /// Return true and update AddrMode if this addr mode is legal for the target,
     66 /// false if not.
     67 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
     68                                              unsigned Depth) {
     69   // If Scale is 1, then this is the same as adding ScaleReg to the addressing
     70   // mode.  Just process that directly.
     71   if (Scale == 1)
     72     return MatchAddr(ScaleReg, Depth);
     73 
     74   // If the scale is 0, it takes nothing to add this.
     75   if (Scale == 0)
     76     return true;
     77 
     78   // If we already have a scale of this value, we can add to it, otherwise, we
     79   // need an available scale field.
     80   if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg)
     81     return false;
     82 
     83   ExtAddrMode TestAddrMode = AddrMode;
     84 
     85   // Add scale to turn X*4+X*3 -> X*7.  This could also do things like
     86   // [A+B + A*7] -> [B+A*8].
     87   TestAddrMode.Scale += Scale;
     88   TestAddrMode.ScaledReg = ScaleReg;
     89 
     90   // If the new address isn't legal, bail out.
     91   if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
     92     return false;
     93 
     94   // It was legal, so commit it.
     95   AddrMode = TestAddrMode;
     96 
     97   // Okay, we decided that we can add ScaleReg+Scale to AddrMode.  Check now
     98   // to see if ScaleReg is actually X+C.  If so, we can turn this into adding
     99   // X*Scale + C*Scale to addr mode.
    100   ConstantInt *CI = 0; Value *AddLHS = 0;
    101   if (isa<Instruction>(ScaleReg) &&  // not a constant expr.
    102       match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) {
    103     TestAddrMode.ScaledReg = AddLHS;
    104     TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale;
    105 
    106     // If this addressing mode is legal, commit it and remember that we folded
    107     // this instruction.
    108     if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
    109       AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
    110       AddrMode = TestAddrMode;
    111       return true;
    112     }
    113   }
    114 
    115   // Otherwise, not (x+c)*scale, just return what we have.
    116   return true;
    117 }
    118 
    119 /// MightBeFoldableInst - This is a little filter, which returns true if an
    120 /// addressing computation involving I might be folded into a load/store
    121 /// accessing it.  This doesn't need to be perfect, but needs to accept at least
    122 /// the set of instructions that MatchOperationAddr can.
    123 static bool MightBeFoldableInst(Instruction *I) {
    124   switch (I->getOpcode()) {
    125   case Instruction::BitCast:
    126     // Don't touch identity bitcasts.
    127     if (I->getType() == I->getOperand(0)->getType())
    128       return false;
    129     return I->getType()->isPointerTy() || I->getType()->isIntegerTy();
    130   case Instruction::PtrToInt:
    131     // PtrToInt is always a noop, as we know that the int type is pointer sized.
    132     return true;
    133   case Instruction::IntToPtr:
    134     // We know the input is intptr_t, so this is foldable.
    135     return true;
    136   case Instruction::Add:
    137     return true;
    138   case Instruction::Mul:
    139   case Instruction::Shl:
    140     // Can only handle X*C and X << C.
    141     return isa<ConstantInt>(I->getOperand(1));
    142   case Instruction::GetElementPtr:
    143     return true;
    144   default:
    145     return false;
    146   }
    147 }
    148 
    149 
    150 /// MatchOperationAddr - Given an instruction or constant expr, see if we can
    151 /// fold the operation into the addressing mode.  If so, update the addressing
    152 /// mode and return true, otherwise return false without modifying AddrMode.
    153 bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode,
    154                                                unsigned Depth) {
    155   // Avoid exponential behavior on extremely deep expression trees.
    156   if (Depth >= 5) return false;
    157 
    158   switch (Opcode) {
    159   case Instruction::PtrToInt:
    160     // PtrToInt is always a noop, as we know that the int type is pointer sized.
    161     return MatchAddr(AddrInst->getOperand(0), Depth);
    162   case Instruction::IntToPtr:
    163     // This inttoptr is a no-op if the integer type is pointer sized.
    164     if (TLI.getValueType(AddrInst->getOperand(0)->getType()) ==
    165         TLI.getPointerTy())
    166       return MatchAddr(AddrInst->getOperand(0), Depth);
    167     return false;
    168   case Instruction::BitCast:
    169     // BitCast is always a noop, and we can handle it as long as it is
    170     // int->int or pointer->pointer (we don't want int<->fp or something).
    171     if ((AddrInst->getOperand(0)->getType()->isPointerTy() ||
    172          AddrInst->getOperand(0)->getType()->isIntegerTy()) &&
    173         // Don't touch identity bitcasts.  These were probably put here by LSR,
    174         // and we don't want to mess around with them.  Assume it knows what it
    175         // is doing.
    176         AddrInst->getOperand(0)->getType() != AddrInst->getType())
    177       return MatchAddr(AddrInst->getOperand(0), Depth);
    178     return false;
    179   case Instruction::Add: {
    180     // Check to see if we can merge in the RHS then the LHS.  If so, we win.
    181     ExtAddrMode BackupAddrMode = AddrMode;
    182     unsigned OldSize = AddrModeInsts.size();
    183     if (MatchAddr(AddrInst->getOperand(1), Depth+1) &&
    184         MatchAddr(AddrInst->getOperand(0), Depth+1))
    185       return true;
    186 
    187     // Restore the old addr mode info.
    188     AddrMode = BackupAddrMode;
    189     AddrModeInsts.resize(OldSize);
    190 
    191     // Otherwise this was over-aggressive.  Try merging in the LHS then the RHS.
    192     if (MatchAddr(AddrInst->getOperand(0), Depth+1) &&
    193         MatchAddr(AddrInst->getOperand(1), Depth+1))
    194       return true;
    195 
    196     // Otherwise we definitely can't merge the ADD in.
    197     AddrMode = BackupAddrMode;
    198     AddrModeInsts.resize(OldSize);
    199     break;
    200   }
    201   //case Instruction::Or:
    202   // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
    203   //break;
    204   case Instruction::Mul:
    205   case Instruction::Shl: {
    206     // Can only handle X*C and X << C.
    207     ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1));
    208     if (!RHS) return false;
    209     int64_t Scale = RHS->getSExtValue();
    210     if (Opcode == Instruction::Shl)
    211       Scale = 1LL << Scale;
    212 
    213     return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
    214   }
    215   case Instruction::GetElementPtr: {
    216     // Scan the GEP.  We check it if it contains constant offsets and at most
    217     // one variable offset.
    218     int VariableOperand = -1;
    219     unsigned VariableScale = 0;
    220 
    221     int64_t ConstantOffset = 0;
    222     const TargetData *TD = TLI.getTargetData();
    223     gep_type_iterator GTI = gep_type_begin(AddrInst);
    224     for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) {
    225       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
    226         const StructLayout *SL = TD->getStructLayout(STy);
    227         unsigned Idx =
    228           cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
    229         ConstantOffset += SL->getElementOffset(Idx);
    230       } else {
    231         uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType());
    232         if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) {
    233           ConstantOffset += CI->getSExtValue()*TypeSize;
    234         } else if (TypeSize) {  // Scales of zero don't do anything.
    235           // We only allow one variable index at the moment.
    236           if (VariableOperand != -1)
    237             return false;
    238 
    239           // Remember the variable index.
    240           VariableOperand = i;
    241           VariableScale = TypeSize;
    242         }
    243       }
    244     }
    245 
    246     // A common case is for the GEP to only do a constant offset.  In this case,
    247     // just add it to the disp field and check validity.
    248     if (VariableOperand == -1) {
    249       AddrMode.BaseOffs += ConstantOffset;
    250       if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){
    251         // Check to see if we can fold the base pointer in too.
    252         if (MatchAddr(AddrInst->getOperand(0), Depth+1))
    253           return true;
    254       }
    255       AddrMode.BaseOffs -= ConstantOffset;
    256       return false;
    257     }
    258 
    259     // Save the valid addressing mode in case we can't match.
    260     ExtAddrMode BackupAddrMode = AddrMode;
    261     unsigned OldSize = AddrModeInsts.size();
    262 
    263     // See if the scale and offset amount is valid for this target.
    264     AddrMode.BaseOffs += ConstantOffset;
    265 
    266     // Match the base operand of the GEP.
    267     if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
    268       // If it couldn't be matched, just stuff the value in a register.
    269       if (AddrMode.HasBaseReg) {
    270         AddrMode = BackupAddrMode;
    271         AddrModeInsts.resize(OldSize);
    272         return false;
    273       }
    274       AddrMode.HasBaseReg = true;
    275       AddrMode.BaseReg = AddrInst->getOperand(0);
    276     }
    277 
    278     // Match the remaining variable portion of the GEP.
    279     if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
    280                           Depth)) {
    281       // If it couldn't be matched, try stuffing the base into a register
    282       // instead of matching it, and retrying the match of the scale.
    283       AddrMode = BackupAddrMode;
    284       AddrModeInsts.resize(OldSize);
    285       if (AddrMode.HasBaseReg)
    286         return false;
    287       AddrMode.HasBaseReg = true;
    288       AddrMode.BaseReg = AddrInst->getOperand(0);
    289       AddrMode.BaseOffs += ConstantOffset;
    290       if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
    291                             VariableScale, Depth)) {
    292         // If even that didn't work, bail.
    293         AddrMode = BackupAddrMode;
    294         AddrModeInsts.resize(OldSize);
    295         return false;
    296       }
    297     }
    298 
    299     return true;
    300   }
    301   }
    302   return false;
    303 }
    304 
    305 /// MatchAddr - If we can, try to add the value of 'Addr' into the current
    306 /// addressing mode.  If Addr can't be added to AddrMode this returns false and
    307 /// leaves AddrMode unmodified.  This assumes that Addr is either a pointer type
    308 /// or intptr_t for the target.
    309 ///
    310 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
    311   if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
    312     // Fold in immediates if legal for the target.
    313     AddrMode.BaseOffs += CI->getSExtValue();
    314     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
    315       return true;
    316     AddrMode.BaseOffs -= CI->getSExtValue();
    317   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
    318     // If this is a global variable, try to fold it into the addressing mode.
    319     if (AddrMode.BaseGV == 0) {
    320       AddrMode.BaseGV = GV;
    321       if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
    322         return true;
    323       AddrMode.BaseGV = 0;
    324     }
    325   } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
    326     ExtAddrMode BackupAddrMode = AddrMode;
    327     unsigned OldSize = AddrModeInsts.size();
    328 
    329     // Check to see if it is possible to fold this operation.
    330     if (MatchOperationAddr(I, I->getOpcode(), Depth)) {
    331       // Okay, it's possible to fold this.  Check to see if it is actually
    332       // *profitable* to do so.  We use a simple cost model to avoid increasing
    333       // register pressure too much.
    334       if (I->hasOneUse() ||
    335           IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
    336         AddrModeInsts.push_back(I);
    337         return true;
    338       }
    339 
    340       // It isn't profitable to do this, roll back.
    341       //cerr << "NOT FOLDING: " << *I;
    342       AddrMode = BackupAddrMode;
    343       AddrModeInsts.resize(OldSize);
    344     }
    345   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
    346     if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
    347       return true;
    348   } else if (isa<ConstantPointerNull>(Addr)) {
    349     // Null pointer gets folded without affecting the addressing mode.
    350     return true;
    351   }
    352 
    353   // Worse case, the target should support [reg] addressing modes. :)
    354   if (!AddrMode.HasBaseReg) {
    355     AddrMode.HasBaseReg = true;
    356     AddrMode.BaseReg = Addr;
    357     // Still check for legality in case the target supports [imm] but not [i+r].
    358     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
    359       return true;
    360     AddrMode.HasBaseReg = false;
    361     AddrMode.BaseReg = 0;
    362   }
    363 
    364   // If the base register is already taken, see if we can do [r+r].
    365   if (AddrMode.Scale == 0) {
    366     AddrMode.Scale = 1;
    367     AddrMode.ScaledReg = Addr;
    368     if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
    369       return true;
    370     AddrMode.Scale = 0;
    371     AddrMode.ScaledReg = 0;
    372   }
    373   // Couldn't match.
    374   return false;
    375 }
    376 
    377 
    378 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified
    379 /// inline asm call are due to memory operands.  If so, return true, otherwise
    380 /// return false.
    381 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
    382                                     const TargetLowering &TLI) {
    383   TargetLowering::AsmOperandInfoVector TargetConstraints = TLI.ParseConstraints(ImmutableCallSite(CI));
    384   for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) {
    385     TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i];
    386 
    387     // Compute the constraint code and ConstraintType to use.
    388     TLI.ComputeConstraintToUse(OpInfo, SDValue());
    389 
    390     // If this asm operand is our Value*, and if it isn't an indirect memory
    391     // operand, we can't fold it!
    392     if (OpInfo.CallOperandVal == OpVal &&
    393         (OpInfo.ConstraintType != TargetLowering::C_Memory ||
    394          !OpInfo.isIndirect))
    395       return false;
    396   }
    397 
    398   return true;
    399 }
    400 
    401 
    402 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a
    403 /// memory use.  If we find an obviously non-foldable instruction, return true.
    404 /// Add the ultimately found memory instructions to MemoryUses.
    405 static bool FindAllMemoryUses(Instruction *I,
    406                 SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
    407                               SmallPtrSet<Instruction*, 16> &ConsideredInsts,
    408                               const TargetLowering &TLI) {
    409   // If we already considered this instruction, we're done.
    410   if (!ConsideredInsts.insert(I))
    411     return false;
    412 
    413   // If this is an obviously unfoldable instruction, bail out.
    414   if (!MightBeFoldableInst(I))
    415     return true;
    416 
    417   // Loop over all the uses, recursively processing them.
    418   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
    419        UI != E; ++UI) {
    420     User *U = *UI;
    421 
    422     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
    423       MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo()));
    424       continue;
    425     }
    426 
    427     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
    428       unsigned opNo = UI.getOperandNo();
    429       if (opNo == 0) return true; // Storing addr, not into addr.
    430       MemoryUses.push_back(std::make_pair(SI, opNo));
    431       continue;
    432     }
    433 
    434     if (CallInst *CI = dyn_cast<CallInst>(U)) {
    435       InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
    436       if (!IA) return true;
    437 
    438       // If this is a memory operand, we're cool, otherwise bail out.
    439       if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
    440         return true;
    441       continue;
    442     }
    443 
    444     if (FindAllMemoryUses(cast<Instruction>(U), MemoryUses, ConsideredInsts,
    445                           TLI))
    446       return true;
    447   }
    448 
    449   return false;
    450 }
    451 
    452 
    453 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at
    454 /// the use site that we're folding it into.  If so, there is no cost to
    455 /// include it in the addressing mode.  KnownLive1 and KnownLive2 are two values
    456 /// that we know are live at the instruction already.
    457 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
    458                                                    Value *KnownLive2) {
    459   // If Val is either of the known-live values, we know it is live!
    460   if (Val == 0 || Val == KnownLive1 || Val == KnownLive2)
    461     return true;
    462 
    463   // All values other than instructions and arguments (e.g. constants) are live.
    464   if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
    465 
    466   // If Val is a constant sized alloca in the entry block, it is live, this is
    467   // true because it is just a reference to the stack/frame pointer, which is
    468   // live for the whole function.
    469   if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
    470     if (AI->isStaticAlloca())
    471       return true;
    472 
    473   // Check to see if this value is already used in the memory instruction's
    474   // block.  If so, it's already live into the block at the very least, so we
    475   // can reasonably fold it.
    476   return Val->isUsedInBasicBlock(MemoryInst->getParent());
    477 }
    478 
    479 
    480 
    481 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing
    482 /// mode of the machine to fold the specified instruction into a load or store
    483 /// that ultimately uses it.  However, the specified instruction has multiple
    484 /// uses.  Given this, it may actually increase register pressure to fold it
    485 /// into the load.  For example, consider this code:
    486 ///
    487 ///     X = ...
    488 ///     Y = X+1
    489 ///     use(Y)   -> nonload/store
    490 ///     Z = Y+1
    491 ///     load Z
    492 ///
    493 /// In this case, Y has multiple uses, and can be folded into the load of Z
    494 /// (yielding load [X+2]).  However, doing this will cause both "X" and "X+1" to
    495 /// be live at the use(Y) line.  If we don't fold Y into load Z, we use one
    496 /// fewer register.  Since Y can't be folded into "use(Y)" we don't increase the
    497 /// number of computations either.
    498 ///
    499 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic.  If
    500 /// X was live across 'load Z' for other reasons, we actually *would* want to
    501 /// fold the addressing mode in the Z case.  This would make Y die earlier.
    502 bool AddressingModeMatcher::
    503 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
    504                                      ExtAddrMode &AMAfter) {
    505   if (IgnoreProfitability) return true;
    506 
    507   // AMBefore is the addressing mode before this instruction was folded into it,
    508   // and AMAfter is the addressing mode after the instruction was folded.  Get
    509   // the set of registers referenced by AMAfter and subtract out those
    510   // referenced by AMBefore: this is the set of values which folding in this
    511   // address extends the lifetime of.
    512   //
    513   // Note that there are only two potential values being referenced here,
    514   // BaseReg and ScaleReg (global addresses are always available, as are any
    515   // folded immediates).
    516   Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
    517 
    518   // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
    519   // lifetime wasn't extended by adding this instruction.
    520   if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
    521     BaseReg = 0;
    522   if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
    523     ScaledReg = 0;
    524 
    525   // If folding this instruction (and it's subexprs) didn't extend any live
    526   // ranges, we're ok with it.
    527   if (BaseReg == 0 && ScaledReg == 0)
    528     return true;
    529 
    530   // If all uses of this instruction are ultimately load/store/inlineasm's,
    531   // check to see if their addressing modes will include this instruction.  If
    532   // so, we can fold it into all uses, so it doesn't matter if it has multiple
    533   // uses.
    534   SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
    535   SmallPtrSet<Instruction*, 16> ConsideredInsts;
    536   if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI))
    537     return false;  // Has a non-memory, non-foldable use!
    538 
    539   // Now that we know that all uses of this instruction are part of a chain of
    540   // computation involving only operations that could theoretically be folded
    541   // into a memory use, loop over each of these uses and see if they could
    542   // *actually* fold the instruction.
    543   SmallVector<Instruction*, 32> MatchedAddrModeInsts;
    544   for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
    545     Instruction *User = MemoryUses[i].first;
    546     unsigned OpNo = MemoryUses[i].second;
    547 
    548     // Get the access type of this use.  If the use isn't a pointer, we don't
    549     // know what it accesses.
    550     Value *Address = User->getOperand(OpNo);
    551     if (!Address->getType()->isPointerTy())
    552       return false;
    553     Type *AddressAccessTy =
    554       cast<PointerType>(Address->getType())->getElementType();
    555 
    556     // Do a match against the root of this address, ignoring profitability. This
    557     // will tell us if the addressing mode for the memory operation will
    558     // *actually* cover the shared instruction.
    559     ExtAddrMode Result;
    560     AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy,
    561                                   MemoryInst, Result);
    562     Matcher.IgnoreProfitability = true;
    563     bool Success = Matcher.MatchAddr(Address, 0);
    564     (void)Success; assert(Success && "Couldn't select *anything*?");
    565 
    566     // If the match didn't cover I, then it won't be shared by it.
    567     if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
    568                   I) == MatchedAddrModeInsts.end())
    569       return false;
    570 
    571     MatchedAddrModeInsts.clear();
    572   }
    573 
    574   return true;
    575 }
    576