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