Index: lib/Target/X86/X86OptimizeLEAs.cpp =================================================================== --- lib/Target/X86/X86OptimizeLEAs.cpp +++ lib/Target/X86/X86OptimizeLEAs.cpp @@ -31,17 +31,111 @@ #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" +#include + using namespace llvm; #define DEBUG_TYPE "x86-optimize-LEAs" -static cl::opt EnableX86LEAOpt("enable-x86-lea-opt", cl::Hidden, - cl::desc("X86: Enable LEA optimizations."), - cl::init(false)); +static cl::opt + DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden, + cl::desc("X86: Disable LEA optimizations."), + cl::init(false)); STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions"); STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed"); +class MemOpKey; + +/// \brief Returns a hash table key based on memory operands of \p MI. The +/// number of the first memory operand of \p MI is specified through \p N. +static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N); + +/// \brief Returns true if two machine operands are identical and they are not +/// physical registers. +static inline bool isIdenticalOp(const MachineOperand &MO1, + const MachineOperand &MO2); + +// A key based on instruction's memory operands. +class MemOpKey { +public: + MemOpKey(const MachineOperand *Base, const MachineOperand *Scale, + const MachineOperand *Index, const MachineOperand *Segment, + const MachineOperand *Disp) + : Disp(Disp) { + Operands[0] = Base; + Operands[1] = Scale; + Operands[2] = Index; + Operands[3] = Segment; + } + + bool operator==(const MemOpKey &Other) const { + // Addresses' bases, scales, indices and segments must be identical. + for (int i = 0; i < 4; ++i) + if (!isIdenticalOp(*Operands[i], *Other.Operands[i])) + return false; + + assert((Disp->isImm() || Disp->isGlobal()) && + (Other.Disp->isImm() || Other.Disp->isGlobal()) && + "Address displacement operand is always an immediate or a global"); + + // Addresses' displacements must be either immediates or the same global. + if ((Disp->isImm() && Other.Disp->isImm()) || + (Disp->isGlobal() && Other.Disp->isGlobal() && + Disp->getGlobal() == Other.Disp->getGlobal())) + return true; + + return false; + } + + const MachineOperand *Operands[4]; + const MachineOperand *Disp; +}; + +// A hash for MemOpKey. +namespace std { +template <> struct hash { + size_t operator()(const MemOpKey &Key) const { + size_t Hash = hash_value(*Key.Operands[0]); + Hash |= hash_value(*Key.Operands[1]) << 32; + Hash |= hash_value(*Key.Operands[2]) >> 32; + Hash |= hash_value(*Key.Operands[3]); + + // If the address displacement is an immediate, it should not affect the + // hash so that memory operands which differ only be immediate displacement + // would have the same hash. If the address displacement is a global, we + // should reflect this global in the hash. + if (Key.Disp->isGlobal()) + Hash |= hash_value(Key.Disp->getGlobal()); + + Hash += ~(Hash << 32); + Hash ^= (Hash >> 22); + Hash += ~(Hash << 13); + Hash ^= (Hash >> 8); + Hash += (Hash << 3); + Hash ^= (Hash >> 15); + Hash += ~(Hash << 27); + Hash ^= (Hash >> 31); + return Hash; + } +}; +} + +static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) { + return MemOpKey(&MI.getOperand(N + X86::AddrBaseReg), + &MI.getOperand(N + X86::AddrScaleAmt), + &MI.getOperand(N + X86::AddrIndexReg), + &MI.getOperand(N + X86::AddrSegmentReg), + &MI.getOperand(N + X86::AddrDisp)); +} + +static inline bool isIdenticalOp(const MachineOperand &MO1, + const MachineOperand &MO2) { + return MO1.isIdenticalTo(MO2) && + (!MO1.isReg() || + !TargetRegisterInfo::isPhysicalRegister(MO1.getReg())); +} + namespace { class OptimizeLEAPass : public MachineFunctionPass { public: @@ -55,51 +149,47 @@ bool runOnMachineFunction(MachineFunction &MF) override; private: + typedef std::unordered_map> + MemOpMap; + /// \brief Returns a distance between two instructions inside one basic block. /// Negative result means, that instructions occur in reverse order. int calcInstrDist(const MachineInstr &First, const MachineInstr &Last); /// \brief Choose the best \p LEA instruction from the \p List to replace /// address calculation in \p MI instruction. Return the address displacement - /// and the distance between \p MI and the choosen \p LEA in \p AddrDispShift - /// and \p Dist. + /// and the distance between \p MI and the choosen \p BestLEA in + /// \p AddrDispShift and \p Dist. bool chooseBestLEA(const SmallVectorImpl &List, - const MachineInstr &MI, MachineInstr *&LEA, + const MachineInstr &MI, MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist); - /// \brief Returns true if two machine operand are identical and they are not - /// physical registers. - bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2); + /// \brief Returns the difference between addresses' displacements of \p MI1 + /// and \p MI2. The numbers of the first memory operands for the instructions + /// are specified through \p N1 and \p N2. + int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1, + const MachineInstr &MI2, unsigned N2) const; /// \brief Returns true if the instruction is LEA. - bool isLEA(const MachineInstr &MI); + inline bool isLEA(const MachineInstr &MI) const; /// \brief Returns true if the \p Last LEA instruction can be replaced by the /// \p First. The difference between displacements of the addresses calculated /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper /// replacement of the \p Last LEA's uses with the \p First's def register. bool isReplaceable(const MachineInstr &First, const MachineInstr &Last, - int64_t &AddrDispShift); - - /// \brief Returns true if two instructions have memory operands that only - /// differ by displacement. The numbers of the first memory operands for both - /// instructions are specified through \p N1 and \p N2. The address - /// displacement is returned through AddrDispShift. - bool isSimilarMemOp(const MachineInstr &MI1, unsigned N1, - const MachineInstr &MI2, unsigned N2, - int64_t &AddrDispShift); + int64_t &AddrDispShift) const; /// \brief Find all LEA instructions in the basic block. Also, assign position /// numbers to all instructions in the basic block to speed up calculation of /// distance between them. - void findLEAs(const MachineBasicBlock &MBB, - SmallVectorImpl &List); + void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs); /// \brief Removes redundant address calculations. - bool removeRedundantAddrCalc(const SmallVectorImpl &List); + bool removeRedundantAddrCalc(MemOpMap &LEAs); /// \brief Removes LEAs which calculate similar addresses. - bool removeRedundantLEAs(SmallVectorImpl &List); + bool removeRedundantLEAs(MemOpMap &LEAs); DenseMap InstrPos; @@ -137,22 +227,20 @@ // 4) The LEA should be as close to MI as possible, and prior to it if // possible. bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl &List, - const MachineInstr &MI, MachineInstr *&LEA, + const MachineInstr &MI, + MachineInstr *&BestLEA, int64_t &AddrDispShift, int &Dist) { const MachineFunction *MF = MI.getParent()->getParent(); const MCInstrDesc &Desc = MI.getDesc(); int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) + X86II::getOperandBias(Desc); - LEA = nullptr; + BestLEA = nullptr; // Loop over all LEA instructions. for (auto DefMI : List) { - int64_t AddrDispShiftTemp = 0; - - // Compare instructions memory operands. - if (!isSimilarMemOp(MI, MemOpNo, *DefMI, 1, AddrDispShiftTemp)) - continue; + // Get new address displacement. + int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1); // Make sure address displacement fits 4 bytes. if (!isInt<32>(AddrDispShiftTemp)) @@ -174,14 +262,14 @@ int DistTemp = calcInstrDist(*DefMI, MI); assert(DistTemp != 0 && "The distance between two different instructions cannot be zero"); - if (DistTemp > 0 || LEA == nullptr) { + if (DistTemp > 0 || BestLEA == nullptr) { // Do not update return LEA, if the current one provides a displacement // which fits in 1 byte, while the new candidate does not. - if (LEA != nullptr && !isInt<8>(AddrDispShiftTemp) && + if (BestLEA != nullptr && !isInt<8>(AddrDispShiftTemp) && isInt<8>(AddrDispShift)) continue; - LEA = DefMI; + BestLEA = DefMI; AddrDispShift = AddrDispShiftTemp; Dist = DistTemp; } @@ -191,17 +279,28 @@ break; } - return LEA != nullptr; + return BestLEA != nullptr; } -bool OptimizeLEAPass::isIdenticalOp(const MachineOperand &MO1, - const MachineOperand &MO2) { - return MO1.isIdenticalTo(MO2) && - (!MO1.isReg() || - !TargetRegisterInfo::isPhysicalRegister(MO1.getReg())); +// Get the difference between the addresses' displacements of the two +// instructions \p MI1 and \p MI2. The numbers of the first memory operands are +// passed through \p N1 and \p N2. +int64_t OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1, unsigned N1, + const MachineInstr &MI2, + unsigned N2) const { + // Address displacement operands may differ by a constant. + const MachineOperand &Op1 = MI1.getOperand(N1 + X86::AddrDisp); + const MachineOperand &Op2 = MI2.getOperand(N2 + X86::AddrDisp); + if (Op1.isImm() && Op2.isImm()) + return Op1.getImm() - Op2.getImm(); + else if (Op1.isGlobal() && Op2.isGlobal() && + Op1.getGlobal() == Op2.getGlobal()) + return Op1.getOffset() - Op2.getOffset(); + else + llvm_unreachable("Invalid address displacement operand"); } -bool OptimizeLEAPass::isLEA(const MachineInstr &MI) { +inline bool OptimizeLEAPass::isLEA(const MachineInstr &MI) const { unsigned Opcode = MI.getOpcode(); return Opcode == X86::LEA16r || Opcode == X86::LEA32r || Opcode == X86::LEA64r || Opcode == X86::LEA64_32r; @@ -215,13 +314,12 @@ // register is used only as address base. bool OptimizeLEAPass::isReplaceable(const MachineInstr &First, const MachineInstr &Last, - int64_t &AddrDispShift) { + int64_t &AddrDispShift) const { assert(isLEA(First) && isLEA(Last) && "The function works only with LEA instructions"); - // Compare instructions' memory operands. - if (!isSimilarMemOp(Last, 1, First, 1, AddrDispShift)) - return false; + // Get new address displacement. + AddrDispShift = getAddrDispShift(Last, 1, First, 1); // Make sure that LEA def registers belong to the same class. There may be // instructions (like MOV8mr_NOREX) which allow a limited set of registers to @@ -270,36 +368,7 @@ return true; } -// Check if MI1 and MI2 have memory operands which represent addresses that -// differ only by displacement. -bool OptimizeLEAPass::isSimilarMemOp(const MachineInstr &MI1, unsigned N1, - const MachineInstr &MI2, unsigned N2, - int64_t &AddrDispShift) { - // Address base, scale, index and segment operands must be identical. - static const int IdenticalOpNums[] = {X86::AddrBaseReg, X86::AddrScaleAmt, - X86::AddrIndexReg, X86::AddrSegmentReg}; - for (auto &N : IdenticalOpNums) - if (!isIdenticalOp(MI1.getOperand(N1 + N), MI2.getOperand(N2 + N))) - return false; - - // Address displacement operands may differ by a constant. - const MachineOperand *Op1 = &MI1.getOperand(N1 + X86::AddrDisp); - const MachineOperand *Op2 = &MI2.getOperand(N2 + X86::AddrDisp); - if (!isIdenticalOp(*Op1, *Op2)) { - if (Op1->isImm() && Op2->isImm()) - AddrDispShift = Op1->getImm() - Op2->getImm(); - else if (Op1->isGlobal() && Op2->isGlobal() && - Op1->getGlobal() == Op2->getGlobal()) - AddrDispShift = Op1->getOffset() - Op2->getOffset(); - else - return false; - } - - return true; -} - -void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, - SmallVectorImpl &List) { +void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs) { unsigned Pos = 0; for (auto &MI : MBB) { // Assign the position number to the instruction. Note that we are going to @@ -310,19 +379,18 @@ InstrPos[&MI] = Pos += 2; if (isLEA(MI)) - List.push_back(const_cast(&MI)); + LEAs[getMemOpKey(MI, 1)].push_back(const_cast(&MI)); } } // Try to find load and store instructions which recalculate addresses already // calculated by some LEA and replace their memory operands with its def // register. -bool OptimizeLEAPass::removeRedundantAddrCalc( - const SmallVectorImpl &List) { +bool OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) { bool Changed = false; - assert(List.size() > 0); - MachineBasicBlock *MBB = List[0]->getParent(); + assert(!LEAs.empty()); + MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent(); // Process all instructions in basic block. for (auto I = MBB->begin(), E = MBB->end(); I != E;) { @@ -347,7 +415,8 @@ MachineInstr *DefMI; int64_t AddrDispShift; int Dist; - if (!chooseBestLEA(List, MI, DefMI, AddrDispShift, Dist)) + if (!chooseBestLEA(LEAs[getMemOpKey(MI, MemOpNo)], MI, DefMI, AddrDispShift, + Dist)) continue; // If LEA occurs before current instruction, we can freely replace @@ -393,75 +462,80 @@ } // Try to find similar LEAs in the list and replace one with another. -bool -OptimizeLEAPass::removeRedundantLEAs(SmallVectorImpl &List) { +bool OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) { bool Changed = false; - // Loop over all LEA pairs. - auto I1 = List.begin(); - while (I1 != List.end()) { - MachineInstr &First = **I1; - auto I2 = std::next(I1); - while (I2 != List.end()) { - MachineInstr &Last = **I2; - int64_t AddrDispShift; - - // LEAs should be in occurence order in the list, so we can freely - // replace later LEAs with earlier ones. - assert(calcInstrDist(First, Last) > 0 && - "LEAs must be in occurence order in the list"); - - // Check that the Last LEA instruction can be replaced by the First. - if (!isReplaceable(First, Last, AddrDispShift)) { - ++I2; - continue; + // Loop over all entries in the table. + for (auto &E : LEAs) { + auto &List = E.second; + + // Loop over all LEA pairs. + auto I1 = List.begin(); + while (I1 != List.end()) { + MachineInstr &First = **I1; + auto I2 = std::next(I1); + while (I2 != List.end()) { + MachineInstr &Last = **I2; + int64_t AddrDispShift; + + // LEAs should be in occurence order in the list, so we can freely + // replace later LEAs with earlier ones. + assert(calcInstrDist(First, Last) > 0 && + "LEAs must be in occurence order in the list"); + + // Check that the Last LEA instruction can be replaced by the First. + if (!isReplaceable(First, Last, AddrDispShift)) { + ++I2; + continue; + } + + // Loop over all uses of the Last LEA and update their operands. Note + // that the correctness of this has already been checked in the + // isReplaceable function. + for (auto UI = MRI->use_begin(Last.getOperand(0).getReg()), + UE = MRI->use_end(); + UI != UE;) { + MachineOperand &MO = *UI++; + MachineInstr &MI = *MO.getParent(); + + // Get the number of the first memory operand. + const MCInstrDesc &Desc = MI.getDesc(); + int MemOpNo = + X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) + + X86II::getOperandBias(Desc); + + // Update address base. + MO.setReg(First.getOperand(0).getReg()); + + // Update address disp. + MachineOperand *Op = &MI.getOperand(MemOpNo + X86::AddrDisp); + if (Op->isImm()) + Op->setImm(Op->getImm() + AddrDispShift); + else if (Op->isGlobal()) + Op->setOffset(Op->getOffset() + AddrDispShift); + else + llvm_unreachable("Invalid address displacement operand"); + } + + // Since we can possibly extend register lifetime, clear kill flags. + MRI->clearKillFlags(First.getOperand(0).getReg()); + + ++NumRedundantLEAs; + DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; Last.dump();); + + // By this moment, all of the Last LEA's uses must be replaced. So we + // can freely remove it. + assert(MRI->use_empty(Last.getOperand(0).getReg()) && + "The LEA's def register must have no uses"); + Last.eraseFromParent(); + + // Erase removed LEA from the list. + I2 = List.erase(I2); + + Changed = true; } - - // Loop over all uses of the Last LEA and update their operands. Note that - // the correctness of this has already been checked in the isReplaceable - // function. - for (auto UI = MRI->use_begin(Last.getOperand(0).getReg()), - UE = MRI->use_end(); - UI != UE;) { - MachineOperand &MO = *UI++; - MachineInstr &MI = *MO.getParent(); - - // Get the number of the first memory operand. - const MCInstrDesc &Desc = MI.getDesc(); - int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) + - X86II::getOperandBias(Desc); - - // Update address base. - MO.setReg(First.getOperand(0).getReg()); - - // Update address disp. - MachineOperand *Op = &MI.getOperand(MemOpNo + X86::AddrDisp); - if (Op->isImm()) - Op->setImm(Op->getImm() + AddrDispShift); - else if (Op->isGlobal()) - Op->setOffset(Op->getOffset() + AddrDispShift); - else - llvm_unreachable("Invalid address displacement operand"); - } - - // Since we can possibly extend register lifetime, clear kill flags. - MRI->clearKillFlags(First.getOperand(0).getReg()); - - ++NumRedundantLEAs; - DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; Last.dump();); - - // By this moment, all of the Last LEA's uses must be replaced. So we can - // freely remove it. - assert(MRI->use_empty(Last.getOperand(0).getReg()) && - "The LEA's def register must have no uses"); - Last.eraseFromParent(); - - // Erase removed LEA from the list. - I2 = List.erase(I2); - - Changed = true; + ++I1; } - ++I1; } return Changed; @@ -471,7 +545,7 @@ bool Changed = false; // Perform this optimization only if we care about code size. - if (!EnableX86LEAOpt || !MF.getFunction()->optForSize()) + if (DisableX86LEAOpt || !MF.getFunction()->optForSize()) return false; MRI = &MF.getRegInfo(); @@ -480,7 +554,7 @@ // Process all basic blocks. for (auto &MBB : MF) { - SmallVector LEAs; + MemOpMap LEAs; InstrPos.clear(); // Find all LEA instructions in basic block. Index: test/CodeGen/X86/lea-opt.ll =================================================================== --- test/CodeGen/X86/lea-opt.ll +++ test/CodeGen/X86/lea-opt.ll @@ -1,4 +1,4 @@ -; RUN: llc < %s -mtriple=x86_64-linux -enable-x86-lea-opt | FileCheck %s +; RUN: llc < %s -mtriple=x86_64-linux | FileCheck %s %struct.anon1 = type { i32, i32, i32 } %struct.anon2 = type { i32, [32 x i32], i32 }