1 //===- AddrModeMatcher.cpp - Addressing mode matching facility --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements target addressing mode matcher class.
12 //===----------------------------------------------------------------------===//
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"
24 using namespace llvm::PatternMatch;
26 void ExtAddrMode::print(OStream &OS) const {
27 bool NeedPlus = false;
30 OS << (NeedPlus ? " + " : "")
32 WriteAsOperand(*OS.stream(), BaseGV, /*PrintType=*/false);
37 OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true;
40 OS << (NeedPlus ? " + " : "")
42 WriteAsOperand(*OS.stream(), BaseReg, /*PrintType=*/false);
46 OS << (NeedPlus ? " + " : "")
48 WriteAsOperand(*OS.stream(), ScaledReg, /*PrintType=*/false);
55 void ExtAddrMode::dump() const {
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,
64 bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale,
66 // If Scale is 1, then this is the same as adding ScaleReg to the addressing
67 // mode. Just process that directly.
69 return MatchAddr(ScaleReg, Depth);
71 // If the scale is 0, it takes nothing to add this.
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)
80 ExtAddrMode TestAddrMode = AddrMode;
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;
87 // If the new address isn't legal, bail out.
88 if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy))
91 // It was legal, so commit it.
92 AddrMode = TestAddrMode;
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 = 0; Value *AddLHS = 0;
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;
103 // If this addressing mode is legal, commit it and remember that we folded
105 if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) {
106 AddrModeInsts.push_back(cast<Instruction>(ScaleReg));
107 AddrMode = TestAddrMode;
112 // Otherwise, not (x+c)*scale, just return what we have.
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())
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.
130 case Instruction::IntToPtr:
131 // We know the input is intptr_t, so this is foldable.
133 case Instruction::Add:
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:
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,
152 // Avoid exponential behavior on extremely deep expression trees.
153 if (Depth >= 5) return false;
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()) ==
163 return MatchAddr(AddrInst->getOperand(0), Depth);
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
173 AddrInst->getOperand(0)->getType() != AddrInst->getType())
174 return MatchAddr(AddrInst->getOperand(0), Depth);
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))
184 // Restore the old addr mode info.
185 AddrMode = BackupAddrMode;
186 AddrModeInsts.resize(OldSize);
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))
193 // Otherwise we definitely can't merge the ADD in.
194 AddrMode = BackupAddrMode;
195 AddrModeInsts.resize(OldSize);
198 //case Instruction::Or:
199 // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD.
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)
210 return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth);
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;
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);
225 cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue();
226 ConstantOffset += SL->getElementOffset(Idx);
228 uint64_t TypeSize = TD->getTypeAllocSize(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)
236 // Remember the variable index.
238 VariableScale = TypeSize;
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))
252 AddrMode.BaseOffs -= ConstantOffset;
256 // Save the valid addressing mode in case we can't match.
257 ExtAddrMode BackupAddrMode = AddrMode;
258 unsigned OldSize = AddrModeInsts.size();
260 // See if the scale and offset amount is valid for this target.
261 AddrMode.BaseOffs += ConstantOffset;
263 // Match the base operand of the GEP.
264 if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) {
265 // If it couldn't be matched, just stuff the value in a register.
266 if (AddrMode.HasBaseReg) {
267 AddrMode = BackupAddrMode;
268 AddrModeInsts.resize(OldSize);
271 AddrMode.HasBaseReg = true;
272 AddrMode.BaseReg = AddrInst->getOperand(0);
275 // Match the remaining variable portion of the GEP.
276 if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale,
278 // If it couldn't be matched, try stuffing the base into a register
279 // instead of matching it, and retrying the match of the scale.
280 AddrMode = BackupAddrMode;
281 AddrModeInsts.resize(OldSize);
282 if (AddrMode.HasBaseReg)
284 AddrMode.HasBaseReg = true;
285 AddrMode.BaseReg = AddrInst->getOperand(0);
286 AddrMode.BaseOffs += ConstantOffset;
287 if (!MatchScaledValue(AddrInst->getOperand(VariableOperand),
288 VariableScale, Depth)) {
289 // If even that didn't work, bail.
290 AddrMode = BackupAddrMode;
291 AddrModeInsts.resize(OldSize);
302 /// MatchAddr - If we can, try to add the value of 'Addr' into the current
303 /// addressing mode. If Addr can't be added to AddrMode this returns false and
304 /// leaves AddrMode unmodified. This assumes that Addr is either a pointer type
305 /// or intptr_t for the target.
307 bool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) {
308 if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) {
309 // Fold in immediates if legal for the target.
310 AddrMode.BaseOffs += CI->getSExtValue();
311 if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
313 AddrMode.BaseOffs -= CI->getSExtValue();
314 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) {
315 // If this is a global variable, try to fold it into the addressing mode.
316 if (AddrMode.BaseGV == 0) {
317 AddrMode.BaseGV = GV;
318 if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
322 } else if (Instruction *I = dyn_cast<Instruction>(Addr)) {
323 ExtAddrMode BackupAddrMode = AddrMode;
324 unsigned OldSize = AddrModeInsts.size();
326 // Check to see if it is possible to fold this operation.
327 if (MatchOperationAddr(I, I->getOpcode(), Depth)) {
328 // Okay, it's possible to fold this. Check to see if it is actually
329 // *profitable* to do so. We use a simple cost model to avoid increasing
330 // register pressure too much.
331 if (I->hasOneUse() ||
332 IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) {
333 AddrModeInsts.push_back(I);
337 // It isn't profitable to do this, roll back.
338 //cerr << "NOT FOLDING: " << *I;
339 AddrMode = BackupAddrMode;
340 AddrModeInsts.resize(OldSize);
342 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) {
343 if (MatchOperationAddr(CE, CE->getOpcode(), Depth))
345 } else if (isa<ConstantPointerNull>(Addr)) {
346 // Null pointer gets folded without affecting the addressing mode.
350 // Worse case, the target should support [reg] addressing modes. :)
351 if (!AddrMode.HasBaseReg) {
352 AddrMode.HasBaseReg = true;
353 AddrMode.BaseReg = Addr;
354 // Still check for legality in case the target supports [imm] but not [i+r].
355 if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
357 AddrMode.HasBaseReg = false;
358 AddrMode.BaseReg = 0;
361 // If the base register is already taken, see if we can do [r+r].
362 if (AddrMode.Scale == 0) {
364 AddrMode.ScaledReg = Addr;
365 if (TLI.isLegalAddressingMode(AddrMode, AccessTy))
368 AddrMode.ScaledReg = 0;
375 /// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified
376 /// inline asm call are due to memory operands. If so, return true, otherwise
378 static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal,
379 const TargetLowering &TLI) {
380 std::vector<InlineAsm::ConstraintInfo>
381 Constraints = IA->ParseConstraints();
383 unsigned ArgNo = 1; // ArgNo - The operand of the CallInst.
384 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
385 TargetLowering::AsmOperandInfo OpInfo(Constraints[i]);
387 // Compute the value type for each operand.
388 switch (OpInfo.Type) {
389 case InlineAsm::isOutput:
390 if (OpInfo.isIndirect)
391 OpInfo.CallOperandVal = CI->getOperand(ArgNo++);
393 case InlineAsm::isInput:
394 OpInfo.CallOperandVal = CI->getOperand(ArgNo++);
396 case InlineAsm::isClobber:
401 // Compute the constraint code and ConstraintType to use.
402 TLI.ComputeConstraintToUse(OpInfo, SDValue(),
403 OpInfo.ConstraintType == TargetLowering::C_Memory);
405 // If this asm operand is our Value*, and if it isn't an indirect memory
406 // operand, we can't fold it!
407 if (OpInfo.CallOperandVal == OpVal &&
408 (OpInfo.ConstraintType != TargetLowering::C_Memory ||
417 /// FindAllMemoryUses - Recursively walk all the uses of I until we find a
418 /// memory use. If we find an obviously non-foldable instruction, return true.
419 /// Add the ultimately found memory instructions to MemoryUses.
420 static bool FindAllMemoryUses(Instruction *I,
421 SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses,
422 SmallPtrSet<Instruction*, 16> &ConsideredInsts,
423 const TargetLowering &TLI) {
424 // If we already considered this instruction, we're done.
425 if (!ConsideredInsts.insert(I))
428 // If this is an obviously unfoldable instruction, bail out.
429 if (!MightBeFoldableInst(I))
432 // Loop over all the uses, recursively processing them.
433 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
435 if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
436 MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo()));
440 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
441 if (UI.getOperandNo() == 0) return true; // Storing addr, not into addr.
442 MemoryUses.push_back(std::make_pair(SI, UI.getOperandNo()));
446 if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
447 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue());
448 if (IA == 0) return true;
450 // If this is a memory operand, we're cool, otherwise bail out.
451 if (!IsOperandAMemoryOperand(CI, IA, I, TLI))
456 if (FindAllMemoryUses(cast<Instruction>(*UI), MemoryUses, ConsideredInsts,
465 /// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at
466 /// the use site that we're folding it into. If so, there is no cost to
467 /// include it in the addressing mode. KnownLive1 and KnownLive2 are two values
468 /// that we know are live at the instruction already.
469 bool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1,
471 // If Val is either of the known-live values, we know it is live!
472 if (Val == 0 || Val == KnownLive1 || Val == KnownLive2)
475 // All values other than instructions and arguments (e.g. constants) are live.
476 if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true;
478 // If Val is a constant sized alloca in the entry block, it is live, this is
479 // true because it is just a reference to the stack/frame pointer, which is
480 // live for the whole function.
481 if (AllocaInst *AI = dyn_cast<AllocaInst>(Val))
482 if (AI->isStaticAlloca())
485 // Check to see if this value is already used in the memory instruction's
486 // block. If so, it's already live into the block at the very least, so we
487 // can reasonably fold it.
488 BasicBlock *MemBB = MemoryInst->getParent();
489 for (Value::use_iterator UI = Val->use_begin(), E = Val->use_end();
491 // We know that uses of arguments and instructions have to be instructions.
492 if (cast<Instruction>(*UI)->getParent() == MemBB)
500 /// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing
501 /// mode of the machine to fold the specified instruction into a load or store
502 /// that ultimately uses it. However, the specified instruction has multiple
503 /// uses. Given this, it may actually increase register pressure to fold it
504 /// into the load. For example, consider this code:
508 /// use(Y) -> nonload/store
512 /// In this case, Y has multiple uses, and can be folded into the load of Z
513 /// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to
514 /// be live at the use(Y) line. If we don't fold Y into load Z, we use one
515 /// fewer register. Since Y can't be folded into "use(Y)" we don't increase the
516 /// number of computations either.
518 /// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If
519 /// X was live across 'load Z' for other reasons, we actually *would* want to
520 /// fold the addressing mode in the Z case. This would make Y die earlier.
521 bool AddressingModeMatcher::
522 IsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore,
523 ExtAddrMode &AMAfter) {
524 if (IgnoreProfitability) return true;
526 // AMBefore is the addressing mode before this instruction was folded into it,
527 // and AMAfter is the addressing mode after the instruction was folded. Get
528 // the set of registers referenced by AMAfter and subtract out those
529 // referenced by AMBefore: this is the set of values which folding in this
530 // address extends the lifetime of.
532 // Note that there are only two potential values being referenced here,
533 // BaseReg and ScaleReg (global addresses are always available, as are any
534 // folded immediates).
535 Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg;
537 // If the BaseReg or ScaledReg was referenced by the previous addrmode, their
538 // lifetime wasn't extended by adding this instruction.
539 if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg))
541 if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg))
544 // If folding this instruction (and it's subexprs) didn't extend any live
545 // ranges, we're ok with it.
546 if (BaseReg == 0 && ScaledReg == 0)
549 // If all uses of this instruction are ultimately load/store/inlineasm's,
550 // check to see if their addressing modes will include this instruction. If
551 // so, we can fold it into all uses, so it doesn't matter if it has multiple
553 SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses;
554 SmallPtrSet<Instruction*, 16> ConsideredInsts;
555 if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI))
556 return false; // Has a non-memory, non-foldable use!
558 // Now that we know that all uses of this instruction are part of a chain of
559 // computation involving only operations that could theoretically be folded
560 // into a memory use, loop over each of these uses and see if they could
561 // *actually* fold the instruction.
562 SmallVector<Instruction*, 32> MatchedAddrModeInsts;
563 for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) {
564 Instruction *User = MemoryUses[i].first;
565 unsigned OpNo = MemoryUses[i].second;
567 // Get the access type of this use. If the use isn't a pointer, we don't
568 // know what it accesses.
569 Value *Address = User->getOperand(OpNo);
570 if (!isa<PointerType>(Address->getType()))
572 const Type *AddressAccessTy =
573 cast<PointerType>(Address->getType())->getElementType();
575 // Do a match against the root of this address, ignoring profitability. This
576 // will tell us if the addressing mode for the memory operation will
577 // *actually* cover the shared instruction.
579 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy,
581 Matcher.IgnoreProfitability = true;
582 bool Success = Matcher.MatchAddr(Address, 0);
583 Success = Success; assert(Success && "Couldn't select *anything*?");
585 // If the match didn't cover I, then it won't be shared by it.
586 if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(),
587 I) == MatchedAddrModeInsts.end())
590 MatchedAddrModeInsts.clear();