749 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file defines the pass that performs some optimizations with LEA10// 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 differ13// by displacement inside a basic block, one of them is removed.14// 2) Address calculations in load and store instructions are replaced by15// 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 53using namespace llvm;54 55#define DEBUG_TYPE "x86-optimize-LEAs"56 57static cl::opt<bool>58 DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden,59 cl::desc("X86: Disable LEA optimizations."),60 cl::init(false));61 62STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");63STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");64 65/// Returns true if two machine operands are identical and they are not66/// physical registers.67static inline bool isIdenticalOp(const MachineOperand &MO1,68 const MachineOperand &MO2);69 70/// Returns true if two address displacement operands are of the same71/// type and use the same symbol/index/address regardless of the offset.72static bool isSimilarDispOp(const MachineOperand &MO1,73 const MachineOperand &MO2);74 75/// Returns true if the instruction is LEA.76static inline bool isLEA(const MachineInstr &MI);77 78namespace {79 80/// A key based on instruction's memory operands.81class MemOpKey {82public: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 only100 // matters that they use the same symbol/index/address. Immediates' or101 // offsets' differences will be taken care of during instruction102 // 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 namespace114 115namespace llvm {116 117/// Provide DenseMapInfo for MemOpKey.118template <> 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 is135 // 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 the144 // hash so that memory operands which differ only be immediate displacement145 // 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 is178 // 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 llvm188 189/// Returns a hash table key based on memory operands of \p MI. The190/// number of the first memory operand of \p MI is specified through \p N.191static 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 201static inline bool isIdenticalOp(const MachineOperand &MO1,202 const MachineOperand &MO2) {203 return MO1.isIdenticalTo(MO2) && (!MO1.isReg() || !MO1.getReg().isPhysical());204}205 206#ifndef NDEBUG207static bool isValidDispOp(const MachineOperand &MO) {208 return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||209 MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();210}211#endif212 213static bool isSimilarDispOp(const MachineOperand &MO1,214 const MachineOperand &MO2) {215 assert(isValidDispOp(MO1) && isValidDispOp(MO2) &&216 "Address displacement operand is not valid");217 return (MO1.isImm() && MO2.isImm()) ||218 (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) ||219 (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) ||220 (MO1.isSymbol() && MO2.isSymbol() &&221 MO1.getSymbolName() == MO2.getSymbolName()) ||222 (MO1.isGlobal() && MO2.isGlobal() &&223 MO1.getGlobal() == MO2.getGlobal()) ||224 (MO1.isBlockAddress() && MO2.isBlockAddress() &&225 MO1.getBlockAddress() == MO2.getBlockAddress()) ||226 (MO1.isMCSymbol() && MO2.isMCSymbol() &&227 MO1.getMCSymbol() == MO2.getMCSymbol()) ||228 (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB());229}230 231static inline bool isLEA(const MachineInstr &MI) {232 unsigned Opcode = MI.getOpcode();233 return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||234 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;235}236 237namespace {238 239class X86OptimizeLEAPass : public MachineFunctionPass {240public:241 X86OptimizeLEAPass() : MachineFunctionPass(ID) {}242 243 StringRef getPassName() const override { return "X86 LEA Optimize"; }244 245 /// Loop over all of the basic blocks, replacing address246 /// calculations in load and store instructions, if it's already247 /// been calculated by LEA. Also, remove redundant LEAs.248 bool runOnMachineFunction(MachineFunction &MF) override;249 250 static char ID;251 252 void getAnalysisUsage(AnalysisUsage &AU) const override {253 AU.addRequired<ProfileSummaryInfoWrapperPass>();254 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();255 MachineFunctionPass::getAnalysisUsage(AU);256 }257 258private:259 using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>;260 261 /// Returns a distance between two instructions inside one basic block.262 /// Negative result means, that instructions occur in reverse order.263 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);264 265 /// Choose the best \p LEA instruction from the \p List to replace266 /// address calculation in \p MI instruction. Return the address displacement267 /// and the distance between \p MI and the chosen \p BestLEA in268 /// \p AddrDispShift and \p Dist.269 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,270 const MachineInstr &MI, MachineInstr *&BestLEA,271 int64_t &AddrDispShift, int &Dist);272 273 /// Returns the difference between addresses' displacements of \p MI1274 /// and \p MI2. The numbers of the first memory operands for the instructions275 /// are specified through \p N1 and \p N2.276 int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,277 const MachineInstr &MI2, unsigned N2) const;278 279 /// Returns true if the \p Last LEA instruction can be replaced by the280 /// \p First. The difference between displacements of the addresses calculated281 /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper282 /// replacement of the \p Last LEA's uses with the \p First's def register.283 bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,284 int64_t &AddrDispShift) const;285 286 /// Find all LEA instructions in the basic block. Also, assign position287 /// numbers to all instructions in the basic block to speed up calculation of288 /// distance between them.289 void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);290 291 /// Removes redundant address calculations.292 bool removeRedundantAddrCalc(MemOpMap &LEAs);293 294 /// Replace debug value MI with a new debug value instruction using register295 /// VReg with an appropriate offset and DIExpression to incorporate the296 /// address displacement AddrDispShift. Return new debug value instruction.297 MachineInstr *replaceDebugValue(MachineInstr &MI, Register OldReg,298 Register NewReg, int64_t AddrDispShift);299 300 /// Removes LEAs which calculate similar addresses.301 bool removeRedundantLEAs(MemOpMap &LEAs);302 303 DenseMap<const MachineInstr *, unsigned> InstrPos;304 305 MachineRegisterInfo *MRI = nullptr;306 const X86InstrInfo *TII = nullptr;307 const X86RegisterInfo *TRI = nullptr;308};309 310} // end anonymous namespace311 312char X86OptimizeLEAPass::ID = 0;313 314FunctionPass *llvm::createX86OptimizeLEAs() { return new X86OptimizeLEAPass(); }315INITIALIZE_PASS(X86OptimizeLEAPass, DEBUG_TYPE, "X86 optimize LEA pass", false,316 false)317 318int X86OptimizeLEAPass::calcInstrDist(const MachineInstr &First,319 const MachineInstr &Last) {320 // Both instructions must be in the same basic block and they must be321 // presented in InstrPos.322 assert(Last.getParent() == First.getParent() &&323 "Instructions are in different basic blocks");324 assert(InstrPos.contains(&First) && InstrPos.contains(&Last) &&325 "Instructions' positions are undefined");326 327 return InstrPos[&Last] - InstrPos[&First];328}329 330// Find the best LEA instruction in the List to replace address recalculation in331// MI. Such LEA must meet these requirements:332// 1) The address calculated by the LEA differs only by the displacement from333// the address used in MI.334// 2) The register class of the definition of the LEA is compatible with the335// register class of the address base register of MI.336// 3) Displacement of the new memory operand should fit in 1 byte if possible.337// 4) The LEA should be as close to MI as possible, and prior to it if338// possible.339bool X86OptimizeLEAPass::chooseBestLEA(340 const SmallVectorImpl<MachineInstr *> &List, const MachineInstr &MI,341 MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) {342 const MCInstrDesc &Desc = MI.getDesc();343 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags) +344 X86II::getOperandBias(Desc);345 346 BestLEA = nullptr;347 348 // Loop over all LEA instructions.349 for (auto *DefMI : List) {350 // Get new address displacement.351 int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1);352 353 // Make sure address displacement fits 4 bytes.354 if (!isInt<32>(AddrDispShiftTemp))355 continue;356 357 // Check that LEA def register can be used as MI address base. Some358 // instructions can use a limited set of registers as address base, for359 // example MOV8mr_NOREX. We could constrain the register class of the LEA360 // def to suit MI, however since this case is very rare and hard to361 // reproduce in a test it's just more reliable to skip the LEA.362 if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg) !=363 MRI->getRegClass(DefMI->getOperand(0).getReg()))364 continue;365 366 // Choose the closest LEA instruction from the list, prior to MI if367 // possible. Note that we took into account resulting address displacement368 // as well. Also note that the list is sorted by the order in which the LEAs369 // occur, so the break condition is pretty simple.370 int DistTemp = calcInstrDist(*DefMI, MI);371 assert(DistTemp != 0 &&372 "The distance between two different instructions cannot be zero");373 if (DistTemp > 0 || BestLEA == nullptr) {374 // Do not update return LEA, if the current one provides a displacement375 // which fits in 1 byte, while the new candidate does not.376 if (BestLEA != nullptr && !isInt<8>(AddrDispShiftTemp) &&377 isInt<8>(AddrDispShift))378 continue;379 380 BestLEA = DefMI;381 AddrDispShift = AddrDispShiftTemp;382 Dist = DistTemp;383 }384 385 // FIXME: Maybe we should not always stop at the first LEA after MI.386 if (DistTemp < 0)387 break;388 }389 390 return BestLEA != nullptr;391}392 393// Get the difference between the addresses' displacements of the two394// instructions \p MI1 and \p MI2. The numbers of the first memory operands are395// passed through \p N1 and \p N2.396int64_t X86OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1,397 unsigned N1,398 const MachineInstr &MI2,399 unsigned N2) const {400 const MachineOperand &Op1 = MI1.getOperand(N1 + X86::AddrDisp);401 const MachineOperand &Op2 = MI2.getOperand(N2 + X86::AddrDisp);402 403 assert(isSimilarDispOp(Op1, Op2) &&404 "Address displacement operands are not compatible");405 406 // After the assert above we can be sure that both operands are of the same407 // valid type and use the same symbol/index/address, thus displacement shift408 // calculation is rather simple.409 if (Op1.isJTI())410 return 0;411 return Op1.isImm() ? Op1.getImm() - Op2.getImm()412 : Op1.getOffset() - Op2.getOffset();413}414 415// Check that the Last LEA can be replaced by the First LEA. To be so,416// these requirements must be met:417// 1) Addresses calculated by LEAs differ only by displacement.418// 2) Def registers of LEAs belong to the same class.419// 3) All uses of the Last LEA def register are replaceable, thus the420// register is used only as address base.421bool X86OptimizeLEAPass::isReplaceable(const MachineInstr &First,422 const MachineInstr &Last,423 int64_t &AddrDispShift) const {424 assert(isLEA(First) && isLEA(Last) &&425 "The function works only with LEA instructions");426 427 // Make sure that LEA def registers belong to the same class. There may be428 // instructions (like MOV8mr_NOREX) which allow a limited set of registers to429 // be used as their operands, so we must be sure that replacing one LEA430 // with another won't lead to putting a wrong register in the instruction.431 if (MRI->getRegClass(First.getOperand(0).getReg()) !=432 MRI->getRegClass(Last.getOperand(0).getReg()))433 return false;434 435 // Get new address displacement.436 AddrDispShift = getAddrDispShift(Last, 1, First, 1);437 438 // Loop over all uses of the Last LEA to check that its def register is439 // used only as address base for memory accesses. If so, it can be440 // replaced, otherwise - no.441 for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) {442 MachineInstr &MI = *MO.getParent();443 444 // Get the number of the first memory operand.445 const MCInstrDesc &Desc = MI.getDesc();446 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);447 448 // If the use instruction has no memory operand - the LEA is not449 // replaceable.450 if (MemOpNo < 0)451 return false;452 453 MemOpNo += X86II::getOperandBias(Desc);454 455 // If the address base of the use instruction is not the LEA def register -456 // the LEA is not replaceable.457 if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))458 return false;459 460 // If the LEA def register is used as any other operand of the use461 // instruction - the LEA is not replaceable.462 for (unsigned i = 0; i < MI.getNumOperands(); i++)463 if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&464 isIdenticalOp(MI.getOperand(i), MO))465 return false;466 467 // Check that the new address displacement will fit 4 bytes.468 if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() &&469 !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() +470 AddrDispShift))471 return false;472 }473 474 return true;475}476 477void X86OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB,478 MemOpMap &LEAs) {479 unsigned Pos = 0;480 for (auto &MI : MBB) {481 // Assign the position number to the instruction. Note that we are going to482 // move some instructions during the optimization however there will never483 // be a need to move two instructions before any selected instruction. So to484 // avoid multiple positions' updates during moves we just increase position485 // counter by two leaving a free space for instructions which will be moved.486 InstrPos[&MI] = Pos += 2;487 488 if (isLEA(MI))489 LEAs[getMemOpKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI));490 }491}492 493// Try to find load and store instructions which recalculate addresses already494// calculated by some LEA and replace their memory operands with its def495// register.496bool X86OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) {497 bool Changed = false;498 499 assert(!LEAs.empty());500 MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent();501 502 // Process all instructions in basic block.503 for (MachineInstr &MI : llvm::make_early_inc_range(*MBB)) {504 // Instruction must be load or store.505 if (!MI.mayLoadOrStore())506 continue;507 508 // Get the number of the first memory operand.509 const MCInstrDesc &Desc = MI.getDesc();510 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);511 512 // If instruction has no memory operand - skip it.513 if (MemOpNo < 0)514 continue;515 516 MemOpNo += X86II::getOperandBias(Desc);517 518 // Do not call chooseBestLEA if there was no matching LEA519 auto Insns = LEAs.find(getMemOpKey(MI, MemOpNo));520 if (Insns == LEAs.end())521 continue;522 523 // Get the best LEA instruction to replace address calculation.524 MachineInstr *DefMI;525 int64_t AddrDispShift;526 int Dist;527 if (!chooseBestLEA(Insns->second, MI, DefMI, AddrDispShift, Dist))528 continue;529 530 // If LEA occurs before current instruction, we can freely replace531 // the instruction. If LEA occurs after, we can lift LEA above the532 // instruction and this way to be able to replace it. Since LEA and the533 // instruction have similar memory operands (thus, the same def534 // instructions for these operands), we can always do that, without535 // worries of using registers before their defs.536 if (Dist < 0) {537 DefMI->removeFromParent();538 MBB->insert(MachineBasicBlock::iterator(&MI), DefMI);539 InstrPos[DefMI] = InstrPos[&MI] - 1;540 541 // Make sure the instructions' position numbers are sane.542 assert(((InstrPos[DefMI] == 1 &&543 MachineBasicBlock::iterator(DefMI) == MBB->begin()) ||544 InstrPos[DefMI] >545 InstrPos[&*std::prev(MachineBasicBlock::iterator(DefMI))]) &&546 "Instruction positioning is broken");547 }548 549 // Since we can possibly extend register lifetime, clear kill flags.550 MRI->clearKillFlags(DefMI->getOperand(0).getReg());551 552 ++NumSubstLEAs;553 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););554 555 // Change instruction operands.556 MI.getOperand(MemOpNo + X86::AddrBaseReg)557 .ChangeToRegister(DefMI->getOperand(0).getReg(), false);558 MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1);559 MI.getOperand(MemOpNo + X86::AddrIndexReg)560 .ChangeToRegister(X86::NoRegister, false);561 MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);562 MI.getOperand(MemOpNo + X86::AddrSegmentReg)563 .ChangeToRegister(X86::NoRegister, false);564 565 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););566 567 Changed = true;568 }569 570 return Changed;571}572 573MachineInstr *X86OptimizeLEAPass::replaceDebugValue(MachineInstr &MI,574 Register OldReg,575 Register NewReg,576 int64_t AddrDispShift) {577 const DIExpression *Expr = MI.getDebugExpression();578 if (AddrDispShift != 0) {579 if (MI.isNonListDebugValue()) {580 Expr =581 DIExpression::prepend(Expr, DIExpression::StackValue, AddrDispShift);582 } else {583 // Update the Expression, appending an offset of `AddrDispShift` to the584 // Op corresponding to `OldReg`.585 SmallVector<uint64_t, 3> Ops;586 DIExpression::appendOffset(Ops, AddrDispShift);587 for (MachineOperand &Op : MI.getDebugOperandsForReg(OldReg)) {588 unsigned OpIdx = MI.getDebugOperandIndex(&Op);589 Expr = DIExpression::appendOpsToArg(Expr, Ops, OpIdx);590 }591 }592 }593 594 // Replace DBG_VALUE instruction with modified version.595 MachineBasicBlock *MBB = MI.getParent();596 DebugLoc DL = MI.getDebugLoc();597 bool IsIndirect = MI.isIndirectDebugValue();598 const MDNode *Var = MI.getDebugVariable();599 unsigned Opcode = MI.isNonListDebugValue() ? TargetOpcode::DBG_VALUE600 : TargetOpcode::DBG_VALUE_LIST;601 if (IsIndirect)602 assert(MI.getDebugOffset().getImm() == 0 &&603 "DBG_VALUE with nonzero offset");604 SmallVector<MachineOperand, 4> NewOps;605 // If we encounter an operand using the old register, replace it with an606 // operand that uses the new register; otherwise keep the old operand.607 auto replaceOldReg = [OldReg, NewReg](const MachineOperand &Op) {608 if (Op.isReg() && Op.getReg() == OldReg)609 return MachineOperand::CreateReg(NewReg, false, false, false, false,610 false, false, false, false, false,611 /*IsRenamable*/ true);612 return Op;613 };614 for (const MachineOperand &Op : MI.debug_operands())615 NewOps.push_back(replaceOldReg(Op));616 return BuildMI(*MBB, MBB->erase(&MI), DL, TII->get(Opcode), IsIndirect,617 NewOps, Var, Expr);618}619 620// Try to find similar LEAs in the list and replace one with another.621bool X86OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) {622 bool Changed = false;623 624 // Loop over all entries in the table.625 for (auto &E : LEAs) {626 auto &List = E.second;627 628 // Loop over all LEA pairs.629 auto I1 = List.begin();630 while (I1 != List.end()) {631 MachineInstr &First = **I1;632 auto I2 = std::next(I1);633 while (I2 != List.end()) {634 MachineInstr &Last = **I2;635 int64_t AddrDispShift;636 637 // LEAs should be in occurrence order in the list, so we can freely638 // replace later LEAs with earlier ones.639 assert(calcInstrDist(First, Last) > 0 &&640 "LEAs must be in occurrence order in the list");641 642 // Check that the Last LEA instruction can be replaced by the First.643 if (!isReplaceable(First, Last, AddrDispShift)) {644 ++I2;645 continue;646 }647 648 // Loop over all uses of the Last LEA and update their operands. Note649 // that the correctness of this has already been checked in the650 // isReplaceable function.651 Register FirstVReg = First.getOperand(0).getReg();652 Register LastVReg = Last.getOperand(0).getReg();653 // We use MRI->use_empty here instead of the combination of654 // llvm::make_early_inc_range and MRI->use_operands because we could655 // replace two or more uses in a debug instruction in one iteration, and656 // that would deeply confuse llvm::make_early_inc_range.657 while (!MRI->use_empty(LastVReg)) {658 MachineOperand &MO = *MRI->use_begin(LastVReg);659 MachineInstr &MI = *MO.getParent();660 661 if (MI.isDebugValue()) {662 // Replace DBG_VALUE instruction with modified version using the663 // register from the replacing LEA and the address displacement664 // between the LEA instructions.665 replaceDebugValue(MI, LastVReg, FirstVReg, AddrDispShift);666 continue;667 }668 669 // Get the number of the first memory operand.670 const MCInstrDesc &Desc = MI.getDesc();671 int MemOpNo =672 X86II::getMemoryOperandNo(Desc.TSFlags) +673 X86II::getOperandBias(Desc);674 675 // Update address base.676 MO.setReg(FirstVReg);677 678 // Update address disp.679 MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp);680 if (Op.isImm())681 Op.setImm(Op.getImm() + AddrDispShift);682 else if (!Op.isJTI())683 Op.setOffset(Op.getOffset() + AddrDispShift);684 }685 686 // Since we can possibly extend register lifetime, clear kill flags.687 MRI->clearKillFlags(FirstVReg);688 689 ++NumRedundantLEAs;690 LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: ";691 Last.dump(););692 693 // By this moment, all of the Last LEA's uses must be replaced. So we694 // can freely remove it.695 assert(MRI->use_empty(LastVReg) &&696 "The LEA's def register must have no uses");697 Last.eraseFromParent();698 699 // Erase removed LEA from the list.700 I2 = List.erase(I2);701 702 Changed = true;703 }704 ++I1;705 }706 }707 708 return Changed;709}710 711bool X86OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {712 bool Changed = false;713 714 if (DisableX86LEAOpt || skipFunction(MF.getFunction()))715 return false;716 717 MRI = &MF.getRegInfo();718 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();719 TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();720 auto *PSI =721 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();722 auto *MBFI = (PSI && PSI->hasProfileSummary()) ?723 &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() :724 nullptr;725 726 // Process all basic blocks.727 for (auto &MBB : MF) {728 MemOpMap LEAs;729 InstrPos.clear();730 731 // Find all LEA instructions in basic block.732 findLEAs(MBB, LEAs);733 734 // If current basic block has no LEAs, move on to the next one.735 if (LEAs.empty())736 continue;737 738 // Remove redundant LEA instructions.739 Changed |= removeRedundantLEAs(LEAs);740 741 // Remove redundant address calculations. Do it only for -Os/-Oz since only742 // a code size gain is expected from this part of the pass.743 if (llvm::shouldOptimizeForSize(&MBB, PSI, MBFI))744 Changed |= removeRedundantAddrCalc(LEAs);745 }746 747 return Changed;748}749