1 //===- X86OptimizeLEAs.cpp - optimize usage of LEA instructions -----------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the pass that performs some optimizations with LEA 10 // instructions in order to improve performance and code size. 11 // Currently, it does two things: 12 // 1) If there are two LEA instructions calculating addresses which only differ 13 // by displacement inside a basic block, one of them is removed. 14 // 2) Address calculations in load and store instructions are replaced by 15 // existing LEA def registers where possible. 16 // 17 //===----------------------------------------------------------------------===// 18 19 #include "MCTargetDesc/X86BaseInfo.h" 20 #include "X86.h" 21 #include "X86InstrInfo.h" 22 #include "X86Subtarget.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/DenseMapInfo.h" 25 #include "llvm/ADT/Hashing.h" 26 #include "llvm/ADT/SmallVector.h" 27 #include "llvm/ADT/Statistic.h" 28 #include "llvm/Analysis/ProfileSummaryInfo.h" 29 #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h" 30 #include "llvm/CodeGen/MachineBasicBlock.h" 31 #include "llvm/CodeGen/MachineFunction.h" 32 #include "llvm/CodeGen/MachineFunctionPass.h" 33 #include "llvm/CodeGen/MachineInstr.h" 34 #include "llvm/CodeGen/MachineInstrBuilder.h" 35 #include "llvm/CodeGen/MachineOperand.h" 36 #include "llvm/CodeGen/MachineRegisterInfo.h" 37 #include "llvm/CodeGen/MachineSizeOpts.h" 38 #include "llvm/CodeGen/TargetOpcodes.h" 39 #include "llvm/CodeGen/TargetRegisterInfo.h" 40 #include "llvm/IR/DebugInfoMetadata.h" 41 #include "llvm/IR/DebugLoc.h" 42 #include "llvm/IR/Function.h" 43 #include "llvm/MC/MCInstrDesc.h" 44 #include "llvm/Support/CommandLine.h" 45 #include "llvm/Support/Debug.h" 46 #include "llvm/Support/ErrorHandling.h" 47 #include "llvm/Support/MathExtras.h" 48 #include "llvm/Support/raw_ostream.h" 49 #include <cassert> 50 #include <cstdint> 51 #include <iterator> 52 53 using namespace llvm; 54 55 #define DEBUG_TYPE "x86-optimize-LEAs" 56 57 static cl::opt<bool> 58 DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden, 59 cl::desc("X86: Disable LEA optimizations."), 60 cl::init(false)); 61 62 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions"); 63 STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed"); 64 65 /// Returns true if two machine operands are identical and they are not 66 /// physical registers. 67 static inline bool isIdenticalOp(const MachineOperand &MO1, 68 const MachineOperand &MO2); 69 70 /// Returns true if two address displacement operands are of the same 71 /// type and use the same symbol/index/address regardless of the offset. 72 static bool isSimilarDispOp(const MachineOperand &MO1, 73 const MachineOperand &MO2); 74 75 /// Returns true if the instruction is LEA. 76 static inline bool isLEA(const MachineInstr &MI); 77 78 namespace { 79 80 /// A key based on instruction's memory operands. 81 class MemOpKey { 82 public: 83 MemOpKey(const MachineOperand *Base, const MachineOperand *Scale, 84 const MachineOperand *Index, const MachineOperand *Segment, 85 const MachineOperand *Disp) 86 : Disp(Disp) { 87 Operands[0] = Base; 88 Operands[1] = Scale; 89 Operands[2] = Index; 90 Operands[3] = Segment; 91 } 92 93 bool operator==(const MemOpKey &Other) const { 94 // Addresses' bases, scales, indices and segments must be identical. 95 for (int i = 0; i < 4; ++i) 96 if (!isIdenticalOp(*Operands[i], *Other.Operands[i])) 97 return false; 98 99 // Addresses' displacements don't have to be exactly the same. It only 100 // matters that they use the same symbol/index/address. Immediates' or 101 // offsets' differences will be taken care of during instruction 102 // substitution. 103 return isSimilarDispOp(*Disp, *Other.Disp); 104 } 105 106 // Address' base, scale, index and segment operands. 107 const MachineOperand *Operands[4]; 108 109 // Address' displacement operand. 110 const MachineOperand *Disp; 111 }; 112 113 } // end anonymous namespace 114 115 /// Provide DenseMapInfo for MemOpKey. 116 namespace llvm { 117 118 template <> struct DenseMapInfo<MemOpKey> { 119 using PtrInfo = DenseMapInfo<const MachineOperand *>; 120 121 static inline MemOpKey getEmptyKey() { 122 return MemOpKey(PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), 123 PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), 124 PtrInfo::getEmptyKey()); 125 } 126 127 static inline MemOpKey getTombstoneKey() { 128 return MemOpKey(PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), 129 PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), 130 PtrInfo::getTombstoneKey()); 131 } 132 133 static unsigned getHashValue(const MemOpKey &Val) { 134 // Checking any field of MemOpKey is enough to determine if the key is 135 // empty or tombstone. 136 assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key"); 137 assert(Val.Disp != PtrInfo::getTombstoneKey() && 138 "Cannot hash the tombstone key"); 139 140 hash_code Hash = hash_combine(*Val.Operands[0], *Val.Operands[1], 141 *Val.Operands[2], *Val.Operands[3]); 142 143 // If the address displacement is an immediate, it should not affect the 144 // hash so that memory operands which differ only be immediate displacement 145 // would have the same hash. If the address displacement is something else, 146 // we should reflect symbol/index/address in the hash. 147 switch (Val.Disp->getType()) { 148 case MachineOperand::MO_Immediate: 149 break; 150 case MachineOperand::MO_ConstantPoolIndex: 151 case MachineOperand::MO_JumpTableIndex: 152 Hash = hash_combine(Hash, Val.Disp->getIndex()); 153 break; 154 case MachineOperand::MO_ExternalSymbol: 155 Hash = hash_combine(Hash, Val.Disp->getSymbolName()); 156 break; 157 case MachineOperand::MO_GlobalAddress: 158 Hash = hash_combine(Hash, Val.Disp->getGlobal()); 159 break; 160 case MachineOperand::MO_BlockAddress: 161 Hash = hash_combine(Hash, Val.Disp->getBlockAddress()); 162 break; 163 case MachineOperand::MO_MCSymbol: 164 Hash = hash_combine(Hash, Val.Disp->getMCSymbol()); 165 break; 166 case MachineOperand::MO_MachineBasicBlock: 167 Hash = hash_combine(Hash, Val.Disp->getMBB()); 168 break; 169 default: 170 llvm_unreachable("Invalid address displacement operand"); 171 } 172 173 return (unsigned)Hash; 174 } 175 176 static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) { 177 // Checking any field of MemOpKey is enough to determine if the key is 178 // empty or tombstone. 179 if (RHS.Disp == PtrInfo::getEmptyKey()) 180 return LHS.Disp == PtrInfo::getEmptyKey(); 181 if (RHS.Disp == PtrInfo::getTombstoneKey()) 182 return LHS.Disp == PtrInfo::getTombstoneKey(); 183 return LHS == RHS; 184 } 185 }; 186 187 } // end namespace llvm 188 189 /// Returns a hash table key based on memory operands of \p MI. The 190 /// number of the first memory operand of \p MI is specified through \p N. 191 static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) { 192 assert((isLEA(MI) || MI.mayLoadOrStore()) && 193 "The instruction must be a LEA, a load or a store"); 194 return MemOpKey(&MI.getOperand(N + X86::AddrBaseReg), 195 &MI.getOperand(N + X86::AddrScaleAmt), 196 &MI.getOperand(N + X86::AddrIndexReg), 197 &MI.getOperand(N + X86::AddrSegmentReg), 198 &MI.getOperand(N + X86::AddrDisp)); 199 } 200 201 static inline bool isIdenticalOp(const MachineOperand &MO1, 202 const MachineOperand &MO2) { 203 return MO1.isIdenticalTo(MO2) && 204 (!MO1.isReg() || !Register::isPhysicalRegister(MO1.getReg())); 205 } 206 207 #ifndef NDEBUG 208 static bool isValidDispOp(const MachineOperand &MO) { 209 return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() || 210 MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB(); 211 } 212 #endif 213 214 static bool isSimilarDispOp(const MachineOperand &MO1, 215 const MachineOperand &MO2) { 216 assert(isValidDispOp(MO1) && isValidDispOp(MO2) && 217 "Address displacement operand is not valid"); 218 return (MO1.isImm() && MO2.isImm()) || 219 (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) || 220 (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) || 221 (MO1.isSymbol() && MO2.isSymbol() && 222 MO1.getSymbolName() == MO2.getSymbolName()) || 223 (MO1.isGlobal() && MO2.isGlobal() && 224 MO1.getGlobal() == MO2.getGlobal()) || 225 (MO1.isBlockAddress() && MO2.isBlockAddress() && 226 MO1.getBlockAddress() == MO2.getBlockAddress()) || 227 (MO1.isMCSymbol() && MO2.isMCSymbol() && 228 MO1.getMCSymbol() == MO2.getMCSymbol()) || 229 (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB()); 230 } 231 232 static inline bool isLEA(const MachineInstr &MI) { 233 unsigned Opcode = MI.getOpcode(); 234 return Opcode == X86::LEA16r || Opcode == X86::LEA32r || 235 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r; 236 } 237 238 namespace { 239 240 class X86OptimizeLEAPass : public MachineFunctionPass { 241 public: 242 X86OptimizeLEAPass() : MachineFunctionPass(ID) {} 243 244 StringRef getPassName() const override { return "X86 LEA Optimize"; } 245 246 /// Loop over all of the basic blocks, replacing address 247 /// calculations in load and store instructions, if it's already 248 /// been calculated by LEA. Also, remove redundant LEAs. 249 bool runOnMachineFunction(MachineFunction &MF) override; 250 251 static char ID; 252 253 void getAnalysisUsage(AnalysisUsage &AU) const override { 254 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 255 AU.addRequired<LazyMachineBlockFrequencyInfoPass>(); 256 MachineFunctionPass::getAnalysisUsage(AU); 257 } 258 259 private: 260 using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>; 261 262 /// Returns a distance between two instructions inside one basic block. 263 /// Negative result means, that instructions occur in reverse order. 264 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last); 265 266 /// Choose the best \p LEA instruction from the \p List to replace 267 /// address calculation in \p MI instruction. Return the address displacement 268 /// and the distance between \p MI and the chosen \p BestLEA in 269 /// \p AddrDispShift and \p Dist. 270 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List, 271 const MachineInstr &MI, MachineInstr *&BestLEA, 272 int64_t &AddrDispShift, int &Dist); 273 274 /// Returns the difference between addresses' displacements of \p MI1 275 /// and \p MI2. The numbers of the first memory operands for the instructions 276 /// are specified through \p N1 and \p N2. 277 int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1, 278 const MachineInstr &MI2, unsigned N2) const; 279 280 /// Returns true if the \p Last LEA instruction can be replaced by the 281 /// \p First. The difference between displacements of the addresses calculated 282 /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper 283 /// replacement of the \p Last LEA's uses with the \p First's def register. 284 bool isReplaceable(const MachineInstr &First, const MachineInstr &Last, 285 int64_t &AddrDispShift) const; 286 287 /// Find all LEA instructions in the basic block. Also, assign position 288 /// numbers to all instructions in the basic block to speed up calculation of 289 /// distance between them. 290 void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs); 291 292 /// Removes redundant address calculations. 293 bool removeRedundantAddrCalc(MemOpMap &LEAs); 294 295 /// Replace debug value MI with a new debug value instruction using register 296 /// VReg with an appropriate offset and DIExpression to incorporate the 297 /// address displacement AddrDispShift. Return new debug value instruction. 298 MachineInstr *replaceDebugValue(MachineInstr &MI, unsigned VReg, 299 int64_t AddrDispShift); 300 301 /// Removes LEAs which calculate similar addresses. 302 bool removeRedundantLEAs(MemOpMap &LEAs); 303 304 DenseMap<const MachineInstr *, unsigned> InstrPos; 305 306 MachineRegisterInfo *MRI = nullptr; 307 const X86InstrInfo *TII = nullptr; 308 const X86RegisterInfo *TRI = nullptr; 309 }; 310 311 } // end anonymous namespace 312 313 char X86OptimizeLEAPass::ID = 0; 314 315 FunctionPass *llvm::createX86OptimizeLEAs() { return new X86OptimizeLEAPass(); } 316 INITIALIZE_PASS(X86OptimizeLEAPass, DEBUG_TYPE, "X86 optimize LEA pass", false, 317 false) 318 319 int X86OptimizeLEAPass::calcInstrDist(const MachineInstr &First, 320 const MachineInstr &Last) { 321 // Both instructions must be in the same basic block and they must be 322 // presented in InstrPos. 323 assert(Last.getParent() == First.getParent() && 324 "Instructions are in different basic blocks"); 325 assert(InstrPos.find(&First) != InstrPos.end() && 326 InstrPos.find(&Last) != InstrPos.end() && 327 "Instructions' positions are undefined"); 328 329 return InstrPos[&Last] - InstrPos[&First]; 330 } 331 332 // Find the best LEA instruction in the List to replace address recalculation in 333 // MI. Such LEA must meet these requirements: 334 // 1) The address calculated by the LEA differs only by the displacement from 335 // the address used in MI. 336 // 2) The register class of the definition of the LEA is compatible with the 337 // register class of the address base register of MI. 338 // 3) Displacement of the new memory operand should fit in 1 byte if possible. 339 // 4) The LEA should be as close to MI as possible, and prior to it if 340 // possible. 341 bool X86OptimizeLEAPass::chooseBestLEA( 342 const SmallVectorImpl<MachineInstr *> &List, const MachineInstr &MI, 343 MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) { 344 const MachineFunction *MF = MI.getParent()->getParent(); 345 const MCInstrDesc &Desc = MI.getDesc(); 346 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags) + 347 X86II::getOperandBias(Desc); 348 349 BestLEA = nullptr; 350 351 // Loop over all LEA instructions. 352 for (auto DefMI : List) { 353 // Get new address displacement. 354 int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1); 355 356 // Make sure address displacement fits 4 bytes. 357 if (!isInt<32>(AddrDispShiftTemp)) 358 continue; 359 360 // Check that LEA def register can be used as MI address base. Some 361 // instructions can use a limited set of registers as address base, for 362 // example MOV8mr_NOREX. We could constrain the register class of the LEA 363 // def to suit MI, however since this case is very rare and hard to 364 // reproduce in a test it's just more reliable to skip the LEA. 365 if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) != 366 MRI->getRegClass(DefMI->getOperand(0).getReg())) 367 continue; 368 369 // Choose the closest LEA instruction from the list, prior to MI if 370 // possible. Note that we took into account resulting address displacement 371 // as well. Also note that the list is sorted by the order in which the LEAs 372 // occur, so the break condition is pretty simple. 373 int DistTemp = calcInstrDist(*DefMI, MI); 374 assert(DistTemp != 0 && 375 "The distance between two different instructions cannot be zero"); 376 if (DistTemp > 0 || BestLEA == nullptr) { 377 // Do not update return LEA, if the current one provides a displacement 378 // which fits in 1 byte, while the new candidate does not. 379 if (BestLEA != nullptr && !isInt<8>(AddrDispShiftTemp) && 380 isInt<8>(AddrDispShift)) 381 continue; 382 383 BestLEA = DefMI; 384 AddrDispShift = AddrDispShiftTemp; 385 Dist = DistTemp; 386 } 387 388 // FIXME: Maybe we should not always stop at the first LEA after MI. 389 if (DistTemp < 0) 390 break; 391 } 392 393 return BestLEA != nullptr; 394 } 395 396 // Get the difference between the addresses' displacements of the two 397 // instructions \p MI1 and \p MI2. The numbers of the first memory operands are 398 // passed through \p N1 and \p N2. 399 int64_t X86OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1, 400 unsigned N1, 401 const MachineInstr &MI2, 402 unsigned N2) const { 403 const MachineOperand &Op1 = MI1.getOperand(N1 + X86::AddrDisp); 404 const MachineOperand &Op2 = MI2.getOperand(N2 + X86::AddrDisp); 405 406 assert(isSimilarDispOp(Op1, Op2) && 407 "Address displacement operands are not compatible"); 408 409 // After the assert above we can be sure that both operands are of the same 410 // valid type and use the same symbol/index/address, thus displacement shift 411 // calculation is rather simple. 412 if (Op1.isJTI()) 413 return 0; 414 return Op1.isImm() ? Op1.getImm() - Op2.getImm() 415 : Op1.getOffset() - Op2.getOffset(); 416 } 417 418 // Check that the Last LEA can be replaced by the First LEA. To be so, 419 // these requirements must be met: 420 // 1) Addresses calculated by LEAs differ only by displacement. 421 // 2) Def registers of LEAs belong to the same class. 422 // 3) All uses of the Last LEA def register are replaceable, thus the 423 // register is used only as address base. 424 bool X86OptimizeLEAPass::isReplaceable(const MachineInstr &First, 425 const MachineInstr &Last, 426 int64_t &AddrDispShift) const { 427 assert(isLEA(First) && isLEA(Last) && 428 "The function works only with LEA instructions"); 429 430 // Make sure that LEA def registers belong to the same class. There may be 431 // instructions (like MOV8mr_NOREX) which allow a limited set of registers to 432 // be used as their operands, so we must be sure that replacing one LEA 433 // with another won't lead to putting a wrong register in the instruction. 434 if (MRI->getRegClass(First.getOperand(0).getReg()) != 435 MRI->getRegClass(Last.getOperand(0).getReg())) 436 return false; 437 438 // Get new address displacement. 439 AddrDispShift = getAddrDispShift(Last, 1, First, 1); 440 441 // Loop over all uses of the Last LEA to check that its def register is 442 // used only as address base for memory accesses. If so, it can be 443 // replaced, otherwise - no. 444 for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) { 445 MachineInstr &MI = *MO.getParent(); 446 447 // Get the number of the first memory operand. 448 const MCInstrDesc &Desc = MI.getDesc(); 449 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags); 450 451 // If the use instruction has no memory operand - the LEA is not 452 // replaceable. 453 if (MemOpNo < 0) 454 return false; 455 456 MemOpNo += X86II::getOperandBias(Desc); 457 458 // If the address base of the use instruction is not the LEA def register - 459 // the LEA is not replaceable. 460 if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO)) 461 return false; 462 463 // If the LEA def register is used as any other operand of the use 464 // instruction - the LEA is not replaceable. 465 for (unsigned i = 0; i < MI.getNumOperands(); i++) 466 if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) && 467 isIdenticalOp(MI.getOperand(i), MO)) 468 return false; 469 470 // Check that the new address displacement will fit 4 bytes. 471 if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() && 472 !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() + 473 AddrDispShift)) 474 return false; 475 } 476 477 return true; 478 } 479 480 void X86OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, 481 MemOpMap &LEAs) { 482 unsigned Pos = 0; 483 for (auto &MI : MBB) { 484 // Assign the position number to the instruction. Note that we are going to 485 // move some instructions during the optimization however there will never 486 // be a need to move two instructions before any selected instruction. So to 487 // avoid multiple positions' updates during moves we just increase position 488 // counter by two leaving a free space for instructions which will be moved. 489 InstrPos[&MI] = Pos += 2; 490 491 if (isLEA(MI)) 492 LEAs[getMemOpKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI)); 493 } 494 } 495 496 // Try to find load and store instructions which recalculate addresses already 497 // calculated by some LEA and replace their memory operands with its def 498 // register. 499 bool X86OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) { 500 bool Changed = false; 501 502 assert(!LEAs.empty()); 503 MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent(); 504 505 // Process all instructions in basic block. 506 for (auto I = MBB->begin(), E = MBB->end(); I != E;) { 507 MachineInstr &MI = *I++; 508 509 // Instruction must be load or store. 510 if (!MI.mayLoadOrStore()) 511 continue; 512 513 // Get the number of the first memory operand. 514 const MCInstrDesc &Desc = MI.getDesc(); 515 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags); 516 517 // If instruction has no memory operand - skip it. 518 if (MemOpNo < 0) 519 continue; 520 521 MemOpNo += X86II::getOperandBias(Desc); 522 523 // Do not call chooseBestLEA if there was no matching LEA 524 auto Insns = LEAs.find(getMemOpKey(MI, MemOpNo)); 525 if (Insns == LEAs.end()) 526 continue; 527 528 // Get the best LEA instruction to replace address calculation. 529 MachineInstr *DefMI; 530 int64_t AddrDispShift; 531 int Dist; 532 if (!chooseBestLEA(Insns->second, MI, DefMI, AddrDispShift, Dist)) 533 continue; 534 535 // If LEA occurs before current instruction, we can freely replace 536 // the instruction. If LEA occurs after, we can lift LEA above the 537 // instruction and this way to be able to replace it. Since LEA and the 538 // instruction have similar memory operands (thus, the same def 539 // instructions for these operands), we can always do that, without 540 // worries of using registers before their defs. 541 if (Dist < 0) { 542 DefMI->removeFromParent(); 543 MBB->insert(MachineBasicBlock::iterator(&MI), DefMI); 544 InstrPos[DefMI] = InstrPos[&MI] - 1; 545 546 // Make sure the instructions' position numbers are sane. 547 assert(((InstrPos[DefMI] == 1 && 548 MachineBasicBlock::iterator(DefMI) == MBB->begin()) || 549 InstrPos[DefMI] > 550 InstrPos[&*std::prev(MachineBasicBlock::iterator(DefMI))]) && 551 "Instruction positioning is broken"); 552 } 553 554 // Since we can possibly extend register lifetime, clear kill flags. 555 MRI->clearKillFlags(DefMI->getOperand(0).getReg()); 556 557 ++NumSubstLEAs; 558 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump();); 559 560 // Change instruction operands. 561 MI.getOperand(MemOpNo + X86::AddrBaseReg) 562 .ChangeToRegister(DefMI->getOperand(0).getReg(), false); 563 MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1); 564 MI.getOperand(MemOpNo + X86::AddrIndexReg) 565 .ChangeToRegister(X86::NoRegister, false); 566 MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift); 567 MI.getOperand(MemOpNo + X86::AddrSegmentReg) 568 .ChangeToRegister(X86::NoRegister, false); 569 570 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump();); 571 572 Changed = true; 573 } 574 575 return Changed; 576 } 577 578 MachineInstr *X86OptimizeLEAPass::replaceDebugValue(MachineInstr &MI, 579 unsigned VReg, 580 int64_t AddrDispShift) { 581 DIExpression *Expr = const_cast<DIExpression *>(MI.getDebugExpression()); 582 if (AddrDispShift != 0) 583 Expr = DIExpression::prepend(Expr, DIExpression::StackValue, AddrDispShift); 584 585 // Replace DBG_VALUE instruction with modified version. 586 MachineBasicBlock *MBB = MI.getParent(); 587 DebugLoc DL = MI.getDebugLoc(); 588 bool IsIndirect = MI.isIndirectDebugValue(); 589 const MDNode *Var = MI.getDebugVariable(); 590 if (IsIndirect) 591 assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset"); 592 return BuildMI(*MBB, MBB->erase(&MI), DL, TII->get(TargetOpcode::DBG_VALUE), 593 IsIndirect, VReg, Var, Expr); 594 } 595 596 // Try to find similar LEAs in the list and replace one with another. 597 bool X86OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) { 598 bool Changed = false; 599 600 // Loop over all entries in the table. 601 for (auto &E : LEAs) { 602 auto &List = E.second; 603 604 // Loop over all LEA pairs. 605 auto I1 = List.begin(); 606 while (I1 != List.end()) { 607 MachineInstr &First = **I1; 608 auto I2 = std::next(I1); 609 while (I2 != List.end()) { 610 MachineInstr &Last = **I2; 611 int64_t AddrDispShift; 612 613 // LEAs should be in occurrence order in the list, so we can freely 614 // replace later LEAs with earlier ones. 615 assert(calcInstrDist(First, Last) > 0 && 616 "LEAs must be in occurrence order in the list"); 617 618 // Check that the Last LEA instruction can be replaced by the First. 619 if (!isReplaceable(First, Last, AddrDispShift)) { 620 ++I2; 621 continue; 622 } 623 624 // Loop over all uses of the Last LEA and update their operands. Note 625 // that the correctness of this has already been checked in the 626 // isReplaceable function. 627 Register FirstVReg = First.getOperand(0).getReg(); 628 Register LastVReg = Last.getOperand(0).getReg(); 629 for (auto UI = MRI->use_begin(LastVReg), UE = MRI->use_end(); 630 UI != UE;) { 631 MachineOperand &MO = *UI++; 632 MachineInstr &MI = *MO.getParent(); 633 634 if (MI.isDebugValue()) { 635 // Replace DBG_VALUE instruction with modified version using the 636 // register from the replacing LEA and the address displacement 637 // between the LEA instructions. 638 replaceDebugValue(MI, FirstVReg, AddrDispShift); 639 continue; 640 } 641 642 // Get the number of the first memory operand. 643 const MCInstrDesc &Desc = MI.getDesc(); 644 int MemOpNo = 645 X86II::getMemoryOperandNo(Desc.TSFlags) + 646 X86II::getOperandBias(Desc); 647 648 // Update address base. 649 MO.setReg(FirstVReg); 650 651 // Update address disp. 652 MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp); 653 if (Op.isImm()) 654 Op.setImm(Op.getImm() + AddrDispShift); 655 else if (!Op.isJTI()) 656 Op.setOffset(Op.getOffset() + AddrDispShift); 657 } 658 659 // Since we can possibly extend register lifetime, clear kill flags. 660 MRI->clearKillFlags(FirstVReg); 661 662 ++NumRedundantLEAs; 663 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; 664 Last.dump();); 665 666 // By this moment, all of the Last LEA's uses must be replaced. So we 667 // can freely remove it. 668 assert(MRI->use_empty(LastVReg) && 669 "The LEA's def register must have no uses"); 670 Last.eraseFromParent(); 671 672 // Erase removed LEA from the list. 673 I2 = List.erase(I2); 674 675 Changed = true; 676 } 677 ++I1; 678 } 679 } 680 681 return Changed; 682 } 683 684 bool X86OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) { 685 bool Changed = false; 686 687 if (DisableX86LEAOpt || skipFunction(MF.getFunction())) 688 return false; 689 690 MRI = &MF.getRegInfo(); 691 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); 692 TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo(); 693 auto *PSI = 694 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 695 auto *MBFI = (PSI && PSI->hasProfileSummary()) ? 696 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() : 697 nullptr; 698 699 // Process all basic blocks. 700 for (auto &MBB : MF) { 701 MemOpMap LEAs; 702 InstrPos.clear(); 703 704 // Find all LEA instructions in basic block. 705 findLEAs(MBB, LEAs); 706 707 // If current basic block has no LEAs, move on to the next one. 708 if (LEAs.empty()) 709 continue; 710 711 // Remove redundant LEA instructions. 712 Changed |= removeRedundantLEAs(LEAs); 713 714 // Remove redundant address calculations. Do it only for -Os/-Oz since only 715 // a code size gain is expected from this part of the pass. 716 bool OptForSize = MF.getFunction().hasOptSize() || 717 llvm::shouldOptimizeForSize(&MBB, PSI, MBFI); 718 if (OptForSize) 719 Changed |= removeRedundantAddrCalc(LEAs); 720 } 721 722 return Changed; 723 } 724