Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 1 | //===- AddrModeMatcher.cpp - Addressing mode matching facility --*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements target addressing mode matcher class. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "llvm/Transforms/Utils/AddrModeMatcher.h" |
| 15 | #include "llvm/DerivedTypes.h" |
| 16 | #include "llvm/GlobalValue.h" |
| 17 | #include "llvm/Instruction.h" |
| 18 | #include "llvm/Assembly/Writer.h" |
| 19 | #include "llvm/Target/TargetData.h" |
| 20 | #include "llvm/Support/GetElementPtrTypeIterator.h" |
| 21 | #include "llvm/Support/PatternMatch.h" |
| 22 | |
| 23 | using namespace llvm; |
| 24 | using namespace llvm::PatternMatch; |
| 25 | |
| 26 | void ExtAddrMode::print(OStream &OS) const { |
| 27 | bool NeedPlus = false; |
| 28 | OS << "["; |
| 29 | if (BaseGV) { |
| 30 | OS << (NeedPlus ? " + " : "") |
| 31 | << "GV:"; |
| 32 | WriteAsOperand(*OS.stream(), BaseGV, /*PrintType=*/false); |
| 33 | NeedPlus = true; |
| 34 | } |
| 35 | |
| 36 | if (BaseOffs) |
| 37 | OS << (NeedPlus ? " + " : "") << BaseOffs, NeedPlus = true; |
| 38 | |
| 39 | if (BaseReg) { |
| 40 | OS << (NeedPlus ? " + " : "") |
| 41 | << "Base:"; |
| 42 | WriteAsOperand(*OS.stream(), BaseReg, /*PrintType=*/false); |
| 43 | NeedPlus = true; |
| 44 | } |
| 45 | if (Scale) { |
| 46 | OS << (NeedPlus ? " + " : "") |
| 47 | << Scale << "*"; |
| 48 | WriteAsOperand(*OS.stream(), ScaledReg, /*PrintType=*/false); |
| 49 | NeedPlus = true; |
| 50 | } |
| 51 | |
| 52 | OS << ']'; |
| 53 | } |
| 54 | |
| 55 | void ExtAddrMode::dump() const { |
| 56 | print(cerr); |
| 57 | cerr << '\n'; |
| 58 | } |
| 59 | |
| 60 | |
| 61 | /// MatchScaledValue - Try adding ScaleReg*Scale to the current addressing mode. |
| 62 | /// Return true and update AddrMode if this addr mode is legal for the target, |
| 63 | /// false if not. |
| 64 | bool AddressingModeMatcher::MatchScaledValue(Value *ScaleReg, int64_t Scale, |
| 65 | unsigned Depth) { |
| 66 | // If Scale is 1, then this is the same as adding ScaleReg to the addressing |
| 67 | // mode. Just process that directly. |
| 68 | if (Scale == 1) |
| 69 | return MatchAddr(ScaleReg, Depth); |
| 70 | |
| 71 | // If the scale is 0, it takes nothing to add this. |
| 72 | if (Scale == 0) |
| 73 | return true; |
| 74 | |
| 75 | // If we already have a scale of this value, we can add to it, otherwise, we |
| 76 | // need an available scale field. |
| 77 | if (AddrMode.Scale != 0 && AddrMode.ScaledReg != ScaleReg) |
| 78 | return false; |
| 79 | |
| 80 | ExtAddrMode TestAddrMode = AddrMode; |
| 81 | |
| 82 | // Add scale to turn X*4+X*3 -> X*7. This could also do things like |
| 83 | // [A+B + A*7] -> [B+A*8]. |
| 84 | TestAddrMode.Scale += Scale; |
| 85 | TestAddrMode.ScaledReg = ScaleReg; |
| 86 | |
| 87 | // If the new address isn't legal, bail out. |
| 88 | if (!TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) |
| 89 | return false; |
| 90 | |
| 91 | // It was legal, so commit it. |
| 92 | AddrMode = TestAddrMode; |
| 93 | |
| 94 | // Okay, we decided that we can add ScaleReg+Scale to AddrMode. Check now |
| 95 | // to see if ScaleReg is actually X+C. If so, we can turn this into adding |
| 96 | // X*Scale + C*Scale to addr mode. |
Nick Lewycky | 7569af7 | 2009-02-27 06:29:31 +0000 | [diff] [blame] | 97 | ConstantInt *CI = 0; Value *AddLHS = 0; |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 98 | if (isa<Instruction>(ScaleReg) && // not a constant expr. |
| 99 | match(ScaleReg, m_Add(m_Value(AddLHS), m_ConstantInt(CI)))) { |
| 100 | TestAddrMode.ScaledReg = AddLHS; |
| 101 | TestAddrMode.BaseOffs += CI->getSExtValue()*TestAddrMode.Scale; |
| 102 | |
| 103 | // If this addressing mode is legal, commit it and remember that we folded |
| 104 | // this instruction. |
| 105 | if (TLI.isLegalAddressingMode(TestAddrMode, AccessTy)) { |
| 106 | AddrModeInsts.push_back(cast<Instruction>(ScaleReg)); |
| 107 | AddrMode = TestAddrMode; |
| 108 | return true; |
| 109 | } |
| 110 | } |
| 111 | |
| 112 | // Otherwise, not (x+c)*scale, just return what we have. |
| 113 | return true; |
| 114 | } |
| 115 | |
| 116 | /// MightBeFoldableInst - This is a little filter, which returns true if an |
| 117 | /// addressing computation involving I might be folded into a load/store |
| 118 | /// accessing it. This doesn't need to be perfect, but needs to accept at least |
| 119 | /// the set of instructions that MatchOperationAddr can. |
| 120 | static bool MightBeFoldableInst(Instruction *I) { |
| 121 | switch (I->getOpcode()) { |
| 122 | case Instruction::BitCast: |
| 123 | // Don't touch identity bitcasts. |
| 124 | if (I->getType() == I->getOperand(0)->getType()) |
| 125 | return false; |
| 126 | return isa<PointerType>(I->getType()) || isa<IntegerType>(I->getType()); |
| 127 | case Instruction::PtrToInt: |
| 128 | // PtrToInt is always a noop, as we know that the int type is pointer sized. |
| 129 | return true; |
| 130 | case Instruction::IntToPtr: |
| 131 | // We know the input is intptr_t, so this is foldable. |
| 132 | return true; |
| 133 | case Instruction::Add: |
| 134 | return true; |
| 135 | case Instruction::Mul: |
| 136 | case Instruction::Shl: |
| 137 | // Can only handle X*C and X << C. |
| 138 | return isa<ConstantInt>(I->getOperand(1)); |
| 139 | case Instruction::GetElementPtr: |
| 140 | return true; |
| 141 | default: |
| 142 | return false; |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | |
| 147 | /// MatchOperationAddr - Given an instruction or constant expr, see if we can |
| 148 | /// fold the operation into the addressing mode. If so, update the addressing |
| 149 | /// mode and return true, otherwise return false without modifying AddrMode. |
| 150 | bool AddressingModeMatcher::MatchOperationAddr(User *AddrInst, unsigned Opcode, |
| 151 | unsigned Depth) { |
| 152 | // Avoid exponential behavior on extremely deep expression trees. |
| 153 | if (Depth >= 5) return false; |
| 154 | |
| 155 | switch (Opcode) { |
| 156 | case Instruction::PtrToInt: |
| 157 | // PtrToInt is always a noop, as we know that the int type is pointer sized. |
| 158 | return MatchAddr(AddrInst->getOperand(0), Depth); |
| 159 | case Instruction::IntToPtr: |
| 160 | // This inttoptr is a no-op if the integer type is pointer sized. |
| 161 | if (TLI.getValueType(AddrInst->getOperand(0)->getType()) == |
| 162 | TLI.getPointerTy()) |
| 163 | return MatchAddr(AddrInst->getOperand(0), Depth); |
| 164 | return false; |
| 165 | case Instruction::BitCast: |
| 166 | // BitCast is always a noop, and we can handle it as long as it is |
| 167 | // int->int or pointer->pointer (we don't want int<->fp or something). |
| 168 | if ((isa<PointerType>(AddrInst->getOperand(0)->getType()) || |
| 169 | isa<IntegerType>(AddrInst->getOperand(0)->getType())) && |
| 170 | // Don't touch identity bitcasts. These were probably put here by LSR, |
| 171 | // and we don't want to mess around with them. Assume it knows what it |
| 172 | // is doing. |
| 173 | AddrInst->getOperand(0)->getType() != AddrInst->getType()) |
| 174 | return MatchAddr(AddrInst->getOperand(0), Depth); |
| 175 | return false; |
| 176 | case Instruction::Add: { |
| 177 | // Check to see if we can merge in the RHS then the LHS. If so, we win. |
| 178 | ExtAddrMode BackupAddrMode = AddrMode; |
| 179 | unsigned OldSize = AddrModeInsts.size(); |
| 180 | if (MatchAddr(AddrInst->getOperand(1), Depth+1) && |
| 181 | MatchAddr(AddrInst->getOperand(0), Depth+1)) |
| 182 | return true; |
| 183 | |
| 184 | // Restore the old addr mode info. |
| 185 | AddrMode = BackupAddrMode; |
| 186 | AddrModeInsts.resize(OldSize); |
| 187 | |
| 188 | // Otherwise this was over-aggressive. Try merging in the LHS then the RHS. |
| 189 | if (MatchAddr(AddrInst->getOperand(0), Depth+1) && |
| 190 | MatchAddr(AddrInst->getOperand(1), Depth+1)) |
| 191 | return true; |
| 192 | |
| 193 | // Otherwise we definitely can't merge the ADD in. |
| 194 | AddrMode = BackupAddrMode; |
| 195 | AddrModeInsts.resize(OldSize); |
| 196 | break; |
| 197 | } |
| 198 | //case Instruction::Or: |
| 199 | // TODO: We can handle "Or Val, Imm" iff this OR is equivalent to an ADD. |
| 200 | //break; |
| 201 | case Instruction::Mul: |
| 202 | case Instruction::Shl: { |
| 203 | // Can only handle X*C and X << C. |
| 204 | ConstantInt *RHS = dyn_cast<ConstantInt>(AddrInst->getOperand(1)); |
| 205 | if (!RHS) return false; |
| 206 | int64_t Scale = RHS->getSExtValue(); |
| 207 | if (Opcode == Instruction::Shl) |
| 208 | Scale = 1 << Scale; |
| 209 | |
| 210 | return MatchScaledValue(AddrInst->getOperand(0), Scale, Depth); |
| 211 | } |
| 212 | case Instruction::GetElementPtr: { |
| 213 | // Scan the GEP. We check it if it contains constant offsets and at most |
| 214 | // one variable offset. |
| 215 | int VariableOperand = -1; |
| 216 | unsigned VariableScale = 0; |
| 217 | |
| 218 | int64_t ConstantOffset = 0; |
| 219 | const TargetData *TD = TLI.getTargetData(); |
| 220 | gep_type_iterator GTI = gep_type_begin(AddrInst); |
| 221 | for (unsigned i = 1, e = AddrInst->getNumOperands(); i != e; ++i, ++GTI) { |
| 222 | if (const StructType *STy = dyn_cast<StructType>(*GTI)) { |
| 223 | const StructLayout *SL = TD->getStructLayout(STy); |
| 224 | unsigned Idx = |
| 225 | cast<ConstantInt>(AddrInst->getOperand(i))->getZExtValue(); |
| 226 | ConstantOffset += SL->getElementOffset(Idx); |
| 227 | } else { |
Duncan Sands | 777d230 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 228 | uint64_t TypeSize = TD->getTypeAllocSize(GTI.getIndexedType()); |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 229 | if (ConstantInt *CI = dyn_cast<ConstantInt>(AddrInst->getOperand(i))) { |
| 230 | ConstantOffset += CI->getSExtValue()*TypeSize; |
| 231 | } else if (TypeSize) { // Scales of zero don't do anything. |
| 232 | // We only allow one variable index at the moment. |
| 233 | if (VariableOperand != -1) |
| 234 | return false; |
| 235 | |
| 236 | // Remember the variable index. |
| 237 | VariableOperand = i; |
| 238 | VariableScale = TypeSize; |
| 239 | } |
| 240 | } |
| 241 | } |
| 242 | |
| 243 | // A common case is for the GEP to only do a constant offset. In this case, |
| 244 | // just add it to the disp field and check validity. |
| 245 | if (VariableOperand == -1) { |
| 246 | AddrMode.BaseOffs += ConstantOffset; |
| 247 | if (ConstantOffset == 0 || TLI.isLegalAddressingMode(AddrMode, AccessTy)){ |
| 248 | // Check to see if we can fold the base pointer in too. |
| 249 | if (MatchAddr(AddrInst->getOperand(0), Depth+1)) |
| 250 | return true; |
| 251 | } |
| 252 | AddrMode.BaseOffs -= ConstantOffset; |
| 253 | return false; |
| 254 | } |
| 255 | |
| 256 | // Save the valid addressing mode in case we can't match. |
| 257 | ExtAddrMode BackupAddrMode = AddrMode; |
Dan Gohman | 5be18e8 | 2009-05-19 02:15:55 +0000 | [diff] [blame^] | 258 | unsigned OldSize = AddrModeInsts.size(); |
| 259 | |
| 260 | // See if the scale and offset amount is valid for this target. |
| 261 | AddrMode.BaseOffs += ConstantOffset; |
| 262 | |
| 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); |
| 269 | return false; |
| 270 | } |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 271 | AddrMode.HasBaseReg = true; |
| 272 | AddrMode.BaseReg = AddrInst->getOperand(0); |
| 273 | } |
Dan Gohman | 5be18e8 | 2009-05-19 02:15:55 +0000 | [diff] [blame^] | 274 | |
| 275 | // Match the remaining variable portion of the GEP. |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 276 | if (!MatchScaledValue(AddrInst->getOperand(VariableOperand), VariableScale, |
| 277 | Depth)) { |
Dan Gohman | 5be18e8 | 2009-05-19 02:15:55 +0000 | [diff] [blame^] | 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. |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 280 | AddrMode = BackupAddrMode; |
Dan Gohman | 5be18e8 | 2009-05-19 02:15:55 +0000 | [diff] [blame^] | 281 | AddrModeInsts.resize(OldSize); |
| 282 | if (AddrMode.HasBaseReg) |
| 283 | return false; |
| 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); |
| 292 | return false; |
| 293 | } |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 294 | } |
Dan Gohman | 5be18e8 | 2009-05-19 02:15:55 +0000 | [diff] [blame^] | 295 | |
Evan Cheng | a1fd5b3 | 2009-02-20 18:24:38 +0000 | [diff] [blame] | 296 | return true; |
| 297 | } |
| 298 | } |
| 299 | return false; |
| 300 | } |
| 301 | |
| 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. |
| 306 | /// |
| 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)) |
| 312 | return true; |
| 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)) |
| 319 | return true; |
| 320 | AddrMode.BaseGV = 0; |
| 321 | } |
| 322 | } else if (Instruction *I = dyn_cast<Instruction>(Addr)) { |
| 323 | ExtAddrMode BackupAddrMode = AddrMode; |
| 324 | unsigned OldSize = AddrModeInsts.size(); |
| 325 | |
| 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); |
| 334 | return true; |
| 335 | } |
| 336 | |
| 337 | // It isn't profitable to do this, roll back. |
| 338 | //cerr << "NOT FOLDING: " << *I; |
| 339 | AddrMode = BackupAddrMode; |
| 340 | AddrModeInsts.resize(OldSize); |
| 341 | } |
| 342 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Addr)) { |
| 343 | if (MatchOperationAddr(CE, CE->getOpcode(), Depth)) |
| 344 | return true; |
| 345 | } else if (isa<ConstantPointerNull>(Addr)) { |
| 346 | // Null pointer gets folded without affecting the addressing mode. |
| 347 | return true; |
| 348 | } |
| 349 | |
| 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)) |
| 356 | return true; |
| 357 | AddrMode.HasBaseReg = false; |
| 358 | AddrMode.BaseReg = 0; |
| 359 | } |
| 360 | |
| 361 | // If the base register is already taken, see if we can do [r+r]. |
| 362 | if (AddrMode.Scale == 0) { |
| 363 | AddrMode.Scale = 1; |
| 364 | AddrMode.ScaledReg = Addr; |
| 365 | if (TLI.isLegalAddressingMode(AddrMode, AccessTy)) |
| 366 | return true; |
| 367 | AddrMode.Scale = 0; |
| 368 | AddrMode.ScaledReg = 0; |
| 369 | } |
| 370 | // Couldn't match. |
| 371 | return false; |
| 372 | } |
| 373 | |
| 374 | |
| 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 |
| 377 | /// return false. |
| 378 | static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, |
| 379 | const TargetLowering &TLI) { |
| 380 | std::vector<InlineAsm::ConstraintInfo> |
| 381 | Constraints = IA->ParseConstraints(); |
| 382 | |
| 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]); |
| 386 | |
| 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++); |
| 392 | break; |
| 393 | case InlineAsm::isInput: |
| 394 | OpInfo.CallOperandVal = CI->getOperand(ArgNo++); |
| 395 | break; |
| 396 | case InlineAsm::isClobber: |
| 397 | // Nothing to do. |
| 398 | break; |
| 399 | } |
| 400 | |
| 401 | // Compute the constraint code and ConstraintType to use. |
| 402 | TLI.ComputeConstraintToUse(OpInfo, SDValue(), |
| 403 | OpInfo.ConstraintType == TargetLowering::C_Memory); |
| 404 | |
| 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 || |
| 409 | !OpInfo.isIndirect)) |
| 410 | return false; |
| 411 | } |
| 412 | |
| 413 | return true; |
| 414 | } |
| 415 | |
| 416 | |
| 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)) |
| 426 | return false; |
| 427 | |
| 428 | // If this is an obviously unfoldable instruction, bail out. |
| 429 | if (!MightBeFoldableInst(I)) |
| 430 | return true; |
| 431 | |
| 432 | // Loop over all the uses, recursively processing them. |
| 433 | for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); |
| 434 | UI != E; ++UI) { |
| 435 | if (LoadInst *LI = dyn_cast<LoadInst>(*UI)) { |
| 436 | MemoryUses.push_back(std::make_pair(LI, UI.getOperandNo())); |
| 437 | continue; |
| 438 | } |
| 439 | |
| 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())); |
| 443 | continue; |
| 444 | } |
| 445 | |
| 446 | if (CallInst *CI = dyn_cast<CallInst>(*UI)) { |
| 447 | InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledValue()); |
| 448 | if (IA == 0) return true; |
| 449 | |
| 450 | // If this is a memory operand, we're cool, otherwise bail out. |
| 451 | if (!IsOperandAMemoryOperand(CI, IA, I, TLI)) |
| 452 | return true; |
| 453 | continue; |
| 454 | } |
| 455 | |
| 456 | if (FindAllMemoryUses(cast<Instruction>(*UI), MemoryUses, ConsideredInsts, |
| 457 | TLI)) |
| 458 | return true; |
| 459 | } |
| 460 | |
| 461 | return false; |
| 462 | } |
| 463 | |
| 464 | |
| 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, |
| 470 | Value *KnownLive2) { |
| 471 | // If Val is either of the known-live values, we know it is live! |
| 472 | if (Val == 0 || Val == KnownLive1 || Val == KnownLive2) |
| 473 | return true; |
| 474 | |
| 475 | // All values other than instructions and arguments (e.g. constants) are live. |
| 476 | if (!isa<Instruction>(Val) && !isa<Argument>(Val)) return true; |
| 477 | |
| 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()) |
| 483 | return true; |
| 484 | |
| 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(); |
| 490 | UI != E; ++UI) |
| 491 | // We know that uses of arguments and instructions have to be instructions. |
| 492 | if (cast<Instruction>(*UI)->getParent() == MemBB) |
| 493 | return true; |
| 494 | |
| 495 | return false; |
| 496 | } |
| 497 | |
| 498 | |
| 499 | |
| 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: |
| 505 | /// |
| 506 | /// X = ... |
| 507 | /// Y = X+1 |
| 508 | /// use(Y) -> nonload/store |
| 509 | /// Z = Y+1 |
| 510 | /// load Z |
| 511 | /// |
| 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. |
| 517 | /// |
| 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; |
| 525 | |
| 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. |
| 531 | // |
| 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; |
| 536 | |
| 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)) |
| 540 | BaseReg = 0; |
| 541 | if (ValueAlreadyLiveAtInst(ScaledReg, AMBefore.BaseReg, AMBefore.ScaledReg)) |
| 542 | ScaledReg = 0; |
| 543 | |
| 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) |
| 547 | return true; |
| 548 | |
| 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 |
| 552 | // uses. |
| 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! |
| 557 | |
| 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; |
| 566 | |
| 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())) |
| 571 | return false; |
| 572 | const Type *AddressAccessTy = |
| 573 | cast<PointerType>(Address->getType())->getElementType(); |
| 574 | |
| 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. |
| 578 | ExtAddrMode Result; |
| 579 | AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI, AddressAccessTy, |
| 580 | MemoryInst, Result); |
| 581 | Matcher.IgnoreProfitability = true; |
| 582 | bool Success = Matcher.MatchAddr(Address, 0); |
| 583 | Success = Success; assert(Success && "Couldn't select *anything*?"); |
| 584 | |
| 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()) |
| 588 | return false; |
| 589 | |
| 590 | MatchedAddrModeInsts.clear(); |
| 591 | } |
| 592 | |
| 593 | return true; |
| 594 | } |