lib/Transforms/Utils/AddrModeMatcher.cpp

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