1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- AddrModeMatcher.cpp - Addressing mode matching facility --*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements target addressing mode matcher class. 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Transforms/Utils/AddrModeMatcher.h" 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/DerivedTypes.h" 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/GlobalValue.h" 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Instruction.h" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Assembly/Writer.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetData.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/GetElementPtrTypeIterator.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/PatternMatch.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CallSite.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm::PatternMatch; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ExtAddrMode::print(raw_ostream &OS) const { 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool NeedPlus = false; 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << "["; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BaseGV) { 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << (NeedPlus ? " + " : "") 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "GV:"; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WriteAsOperand(OS, BaseGV, /*PrintType=*/false); 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedPlus = true; 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BaseOffs) 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BaseReg) { 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << (NeedPlus ? " + " : "") 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << "Base:"; 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WriteAsOperand(OS, BaseReg, /*PrintType=*/false); 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedPlus = true; 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Scale) { 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << (NeedPlus ? " + " : "") 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman << Scale << "*"; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman WriteAsOperand(OS, ScaledReg, /*PrintType=*/false); 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NeedPlus = true; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << ']'; 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid ExtAddrMode::dump() const { 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman print(dbgs()); 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << '\n'; 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode. 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Return true and update AddrMode if this addr mode is legal for the target, 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// false if not. 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale, 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Depth) { 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If Scale is 1, then this is the same as adding ScaleReg to the addressing 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // mode. Just process that directly. 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Scale == 1) 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MatchAddr(ScaleReg, Depth); 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the scale is 0, it takes nothing to add this. 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Scale == 0) 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we already have a scale of this value, we can add to it, otherwise, we 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // need an available scale field. 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode TestAddrMode = AddrMode; 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Add scale to turn X*4+X*3 -> X*7. This could also do things like 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // [A+B + A*7] -> [B+A*8]. 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TestAddrMode.Scale += Scale; 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TestAddrMode.ScaledReg = ScaleReg; 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the new address isn't legal, bail out. 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It was legal, so commit it. 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = TestAddrMode; 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // to see if ScaleReg is actually X+C. If so, we can turn this into adding 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // X*Scale + C*Scale to addr mode. 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantInt *CI = 0; Value *AddLHS = 0; 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isa<Instruction>(ScaleReg) && // not a constant expr. 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TestAddrMode.ScaledReg = AddLHS; 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this addressing mode is legal, commit it and remember that we folded 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this instruction. 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) { 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.push_back(cast<Instruction>(ScaleReg)); 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = TestAddrMode; 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, not (x+c)*scale, just return what we have. 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MightBeFoldableInst - This is a little filter, which returns true if an 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// addressing computation involving I might be folded into a load/store 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// accessing it. This doesn't need to be perfect, but needs to accept at least 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the set of instructions that MatchOperationAddr can. 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool MightBeFoldableInst(Instruction *I) { 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (I->getOpcode()) { 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::BitCast: 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't touch identity bitcasts. 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->getType() == I->getOperand(0)->getType()) 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I->getType()->isPointerTy() || I->getType()->isIntegerTy(); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::PtrToInt: 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // PtrToInt is always a noop, as we know that the int type is pointer sized. 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::IntToPtr: 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We know the input is intptr_t, so this is foldable. 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Add: 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Mul: 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Shl: 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Can only handle X*C and X << C. 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return isa<ConstantInt>(I->getOperand(1)); 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::GetElementPtr: 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman default: 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MatchOperationAddr - Given an instruction or constant expr, see if we can 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// fold the operation into the addressing mode. If so, update the addressing 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// mode and return true, otherwise return false without modifying AddrMode. 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Depth) { 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Avoid exponential behavior on extremely deep expression trees. 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Depth >= 5) return false; 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Opcode) { 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::PtrToInt: 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // PtrToInt is always a noop, as we know that the int type is pointer sized. 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MatchAddr(AddrInst->getOperand(0), Depth); 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::IntToPtr: 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This inttoptr is a no-op if the integer type is pointer sized. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.getPointerTy()) 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MatchAddr(AddrInst->getOperand(0), Depth); 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::BitCast: 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // BitCast is always a noop, and we can handle it as long as it is 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // int->int or pointer->pointer (we don't want int<->fp or something). 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((AddrInst->getOperand(0)->getType()->isPointerTy() || 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrInst->getOperand(0)->getType()->isIntegerTy()) && 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Don't touch identity bitcasts. These were probably put here by LSR, 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and we don't want to mess around with them. Assume it knows what it 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // is doing. 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrInst->getOperand(0)->getType() != AddrInst->getType()) 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MatchAddr(AddrInst->getOperand(0), Depth); 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Add: { 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if we can merge in the RHS then the LHS. If so, we win. 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode BackupAddrMode = AddrMode; 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldSize = AddrModeInsts.size(); 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MatchAddr(AddrInst->getOperand(1), Depth+1) && 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MatchAddr(AddrInst->getOperand(0), Depth+1)) 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Restore the old addr mode info. 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MatchAddr(AddrInst->getOperand(0), Depth+1) && 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MatchAddr(AddrInst->getOperand(1), Depth+1)) 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise we definitely can't merge the ADD in. 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //case Instruction::Or: 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //break; 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Mul: 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::Shl: { 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Can only handle X*C and X << C. 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!RHS) return false; 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t Scale = RHS->getSExtValue(); 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Opcode == Instruction::Shl) 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Scale = 1LL << Scale; 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth); 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Instruction::GetElementPtr: { 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Scan the GEP. We check it if it contains constant offsets and at most 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // one variable offset. 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int VariableOperand = -1; 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned VariableScale = 0; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int64_t ConstantOffset = 0; 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetData *TD = TLI.getTargetData(); 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman gep_type_iterator GTI = gep_type_begin(AddrInst); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (StructType *STy = dyn_cast<StructType>(*GTI)) { 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const StructLayout *SL = TD->getStructLayout(STy); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Idx = 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantOffset += SL->getElementOffset(Idx); 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType()); 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ConstantOffset += CI->getSExtValue()*TypeSize; 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (TypeSize) { // Scales of zero don't do anything. 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We only allow one variable index at the moment. 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (VariableOperand != -1) 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember the variable index. 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VariableOperand = i; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VariableScale = TypeSize; 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // A common case is for the GEP to only do a constant offset. In this case, 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // just add it to the disp field and check validity. 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (VariableOperand == -1) { 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs += ConstantOffset; 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if we can fold the base pointer in too. 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MatchAddr(AddrInst->getOperand(0), Depth+1)) 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs -= ConstantOffset; 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Save the valid addressing mode in case we can't match. 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode BackupAddrMode = AddrMode; 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldSize = AddrModeInsts.size(); 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // See if the scale and offset amount is valid for this target. 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs += ConstantOffset; 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Match the base operand of the GEP. 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MatchAddr(AddrInst->getOperand(0), Depth+1)) { 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it couldn't be matched, just stuff the value in a register. 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.HasBaseReg) { 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.HasBaseReg = true; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseReg = AddrInst->getOperand(0); 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Match the remaining variable portion of the GEP. 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Depth)) { 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If it couldn't be matched, try stuffing the base into a register 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instead of matching it, and retrying the match of the scale. 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.HasBaseReg) 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.HasBaseReg = true; 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseReg = AddrInst->getOperand(0); 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs += ConstantOffset; 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VariableScale, Depth)) { 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If even that didn't work, bail. 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MatchAddr - If we can, try to add the value of 'Addr' into the current 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// addressing mode. If Addr can't be added to AddrMode this returns false and 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// leaves AddrMode unmodified. This assumes that Addr is either a pointer type 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// or intptr_t for the target. 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool AddressingModeMatcher::MatchAddr(Value *Addr, unsigned Depth) { 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ConstantInt *CI = dyn_cast<ConstantInt>(Addr)) { 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Fold in immediates if legal for the target. 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs += CI->getSExtValue(); 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseOffs -= CI->getSExtValue(); 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (GlobalValue *GV = dyn_cast<GlobalValue>(Addr)) { 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a global variable, try to fold it into the addressing mode. 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.BaseGV == 0) { 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseGV = GV; 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseGV = 0; 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (Instruction *I = dyn_cast<Instruction>(Addr)) { 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode BackupAddrMode = AddrMode; 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OldSize = AddrModeInsts.size(); 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if it is possible to fold this operation. 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MatchOperationAddr(I, I->getOpcode(), Depth)) { 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, it's possible to fold this. Check to see if it is actually 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // *profitable* to do so. We use a simple cost model to avoid increasing 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // register pressure too much. 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->hasOneUse() || 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman IsProfitableToFoldIntoAddressingMode(I, BackupAddrMode, AddrMode)) { 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.push_back(I); 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // It isn't profitable to do this, roll back. 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //cerr << "NOT FOLDING: " << *I; 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode = BackupAddrMode; 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrModeInsts.resize(OldSize); 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MatchOperationAddr(CE, CE->getOpcode(), Depth)) 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (isa<ConstantPointerNull>(Addr)) { 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Null pointer gets folded without affecting the addressing mode. 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Worse case, the target should support [reg] addressing modes. :) 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!AddrMode.HasBaseReg) { 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.HasBaseReg = true; 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseReg = Addr; 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Still check for legality in case the target supports [imm] but not [i+r]. 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.HasBaseReg = false; 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.BaseReg = 0; 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the base register is already taken, see if we can do [r+r]. 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AddrMode.Scale == 0) { 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.Scale = 1; 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.ScaledReg = Addr; 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.Scale = 0; 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddrMode.ScaledReg = 0; 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Couldn't match. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// IsOperandAMemoryOperand - Check to see if all uses of OpVal by the specified 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// inline asm call are due to memory operands. If so, return true, otherwise 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// return false. 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetLowering &TLI) { 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::AsmOperandInfoVector TargetConstraints = TLI.ParseConstraints(ImmutableCallSite(CI)); 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = TargetConstraints.size(); i != e; ++i) { 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetLowering::AsmOperandInfo &OpInfo = TargetConstraints[i]; 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Compute the constraint code and ConstraintType to use. 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI.ComputeConstraintToUse(OpInfo, SDValue()); 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this asm operand is our Value*, and if it isn't an indirect memory 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // operand, we can't fold it! 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OpInfo.CallOperandVal == OpVal && 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (OpInfo.ConstraintType != TargetLowering::C_Memory || 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !OpInfo.isIndirect)) 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// FindAllMemoryUses - Recursively walk all the uses of I until we find a 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// memory use. If we find an obviously non-foldable instruction, return true. 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Add the ultimately found memory instructions to MemoryUses. 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanstatic bool FindAllMemoryUses(Instruction *I, 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVectorImpl<std::pair<Instruction*,unsigned> > &MemoryUses, 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<Instruction*, 16> &ConsideredInsts, 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetLowering &TLI) { 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we already considered this instruction, we're done. 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!ConsideredInsts.insert(I)) 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is an obviously unfoldable instruction, bail out. 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MightBeFoldableInst(I)) 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Loop over all the uses, recursively processing them. 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) { 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman User *U = *UI; 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo())); 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (StoreInst *SI = dyn_cast<StoreInst>(U)) { 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned opNo = UI.getOperandNo(); 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (opNo == 0) return true; // Storing addr, not into addr. 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MemoryUses.push_back(std::make_pair(SI, opNo)); 431894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CallInst *CI = dyn_cast<CallInst>(U)) { 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue()); 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!IA) return true; 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this is a memory operand, we're cool, otherwise bail out. 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!IsOperandAMemoryOperand(CI, IA, I, TLI)) 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FindAllMemoryUses(cast<Instruction>(U), MemoryUses, ConsideredInsts, 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TLI)) 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ValueAlreadyLiveAtInst - Retrn true if Val is already known to be live at 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the use site that we're folding it into. If so, there is no cost to 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// include it in the addressing mode. KnownLive1 and KnownLive2 are two values 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// that we know are live at the instruction already. 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool AddressingModeMatcher::ValueAlreadyLiveAtInst(Value *Val,Value *KnownLive1, 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *KnownLive2) { 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If Val is either of the known-live values, we know it is live! 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Val == 0 || Val == KnownLive1 || Val == KnownLive2) 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // All values other than instructions and arguments (e.g. constants) are live. 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true; 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If Val is a constant sized alloca in the entry block, it is live, this is 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // true because it is just a reference to the stack/frame pointer, which is 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // live for the whole function. 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AllocaInst *AI = dyn_cast<AllocaInst>(Val)) 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (AI->isStaticAlloca()) 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to see if this value is already used in the memory instruction's 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // block. If so, it's already live into the block at the very least, so we 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // can reasonably fold it. 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BasicBlock *MemBB = MemoryInst->getParent(); 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (Value::use_iterator UI = Val->use_begin(), E = Val->use_end(); 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UI != E; ++UI) 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We know that uses of arguments and instructions have to be instructions. 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (cast<Instruction>(*UI)->getParent() == MemBB) 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// IsProfitableToFoldIntoAddressingMode - It is possible for the addressing 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// mode of the machine to fold the specified instruction into a load or store 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// that ultimately uses it. However, the specified instruction has multiple 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// uses. Given this, it may actually increase register pressure to fold it 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// into the load. For example, consider this code: 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// X = ... 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Y = X+1 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// use(Y) -> nonload/store 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Z = Y+1 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// load Z 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// In this case, Y has multiple uses, and can be folded into the load of Z 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// (yielding load [X+2]). However, doing this will cause both "X" and "X+1" to 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// be live at the use(Y) line. If we don't fold Y into load Z, we use one 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// fewer register. Since Y can't be folded into "use(Y)" we don't increase the 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// number of computations either. 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Note that this (like most of CodeGenPrepare) is just a rough heuristic. If 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// X was live across 'load Z' for other reasons, we actually *would* want to 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// fold the addressing mode in the Z case. This would make Y die earlier. 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool AddressingModeMatcher:: 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanIsProfitableToFoldIntoAddressingMode(Instruction *I, ExtAddrMode &AMBefore, 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode &AMAfter) { 512894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (IgnoreProfitability) return true; 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // AMBefore is the addressing mode before this instruction was folded into it, 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and AMAfter is the addressing mode after the instruction was folded. Get 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the set of registers referenced by AMAfter and subtract out those 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // referenced by AMBefore: this is the set of values which folding in this 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // address extends the lifetime of. 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Note that there are only two potential values being referenced here, 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // BaseReg and ScaleReg (global addresses are always available, as are any 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // folded immediates). 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *BaseReg = AMAfter.BaseReg, *ScaledReg = AMAfter.ScaledReg; 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the BaseReg or ScaledReg was referenced by the previous addrmode, their 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // lifetime wasn't extended by adding this instruction. 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ValueAlreadyLiveAtInst(BaseReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BaseReg = 0; 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScaledReg = 0; 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If folding this instruction (and it's subexprs) didn't extend any live 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ranges, we're ok with it. 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (BaseReg == 0 && ScaledReg == 0) 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If all uses of this instruction are ultimately load/store/inlineasm's, 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // check to see if their addressing modes will include this instruction. If 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // so, we can fold it into all uses, so it doesn't matter if it has multiple 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // uses. 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<std::pair<Instruction*,unsigned>, 16> MemoryUses; 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<Instruction*, 16> ConsideredInsts; 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (FindAllMemoryUses(I, MemoryUses, ConsideredInsts, TLI)) 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; // Has a non-memory, non-foldable use! 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that we know that all uses of this instruction are part of a chain of 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // computation involving only operations that could theoretically be folded 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // into a memory use, loop over each of these uses and see if they could 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // *actually* fold the instruction. 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<Instruction*, 32> MatchedAddrModeInsts; 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MemoryUses.size(); i != e; ++i) { 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instruction *User = MemoryUses[i].first; 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned OpNo = MemoryUses[i].second; 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Get the access type of this use. If the use isn't a pointer, we don't 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // know what it accesses. 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Value *Address = User->getOperand(OpNo); 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Address->getType()->isPointerTy()) 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Type *AddressAccessTy = 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman cast<PointerType>(Address->getType())->getElementType(); 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Do a match against the root of this address, ignoring profitability. This 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // will tell us if the addressing mode for the memory operation will 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // *actually* cover the shared instruction. 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ExtAddrMode Result; 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy, 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MemoryInst, Result); 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Matcher.IgnoreProfitability = true; 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool Success = Matcher.MatchAddr(Address, 0); 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)Success; assert(Success && "Couldn't select *anything*?"); 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the match didn't cover I, then it won't be shared by it. 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (std::find(MatchedAddrModeInsts.begin(), MatchedAddrModeInsts.end(), 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I) == MatchedAddrModeInsts.end()) 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MatchedAddrModeInsts.clear(); 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 583