Index: llvm/lib/Target/X86/X86.h =================================================================== --- llvm/lib/Target/X86/X86.h +++ llvm/lib/Target/X86/X86.h @@ -143,7 +143,7 @@ void initializeX86ExecutionDomainFixPass(PassRegistry &); void initializeX86FlagsCopyLoweringPassPass(PassRegistry &); void initializeX86SpeculativeLoadHardeningPassPass(PassRegistry &); - +void initializeOptimizeLEAPassPass(PassRegistry &); } // End llvm namespace #endif Index: llvm/lib/Target/X86/X86MemOpKey.h =================================================================== --- /dev/null +++ llvm/lib/Target/X86/X86MemOpKey.h @@ -0,0 +1,172 @@ +//=- X86MemOpKey.h - A key based on instruction's memory operands. --*- C++ -*-=// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// A key based on instruction's memory operands. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_LIB_TARGET_X86_X86MEMOPKEY_H +#define LLVM_LIB_TARGET_X86_X86MEMOPKEY_H + +#include "llvm/ADT/DenseMapInfo.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/CodeGen/MachineOperand.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" + +/// Returns true if two machine operands are identical and they are not +/// physical registers. +static inline bool isIdenticalOp(const llvm::MachineOperand &MO1, + const llvm::MachineOperand &MO2); + +/// Returns true if two address displacement operands are of the same +/// type and use the same symbol/index/address regardless of the offset. +static bool isSimilarDispOp(const llvm::MachineOperand &MO1, + const llvm::MachineOperand &MO2); + +namespace { + +/// A key based on instruction's memory operands. +class MemOpKey { +public: + MemOpKey(const llvm::MachineOperand *Base, const llvm::MachineOperand *Scale, + const llvm::MachineOperand *Index, const llvm::MachineOperand *Segment, + const llvm::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; + + // Addresses' displacements don't have to be exactly the same. It only + // matters that they use the same symbol/index/address. Immediates' or + // offsets' differences will be taken care of during instruction + // substitution. + return isSimilarDispOp(*Disp, *Other.Disp); + } + + // Address' base, scale, index and segment operands. + const llvm::MachineOperand *Operands[4]; + + // Address' displacement operand. + const llvm::MachineOperand *Disp; +}; + +} // end anonymous namespace + +/// Provide DenseMapInfo for MemOpKey. +namespace llvm { + +template <> struct DenseMapInfo { + using PtrInfo = DenseMapInfo; + + static inline MemOpKey getEmptyKey() { + return MemOpKey(PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), + PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), + PtrInfo::getEmptyKey()); + } + + static inline MemOpKey getTombstoneKey() { + return MemOpKey(PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), + PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), + PtrInfo::getTombstoneKey()); + } + + static unsigned getHashValue(const MemOpKey &Val) { + // Checking any field of MemOpKey is enough to determine if the key is + // empty or tombstone. + assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key"); + assert(Val.Disp != PtrInfo::getTombstoneKey() && + "Cannot hash the tombstone key"); + + hash_code Hash = hash_combine(*Val.Operands[0], *Val.Operands[1], + *Val.Operands[2], *Val.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 something else, + // we should reflect symbol/index/address in the hash. + switch (Val.Disp->getType()) { + case MachineOperand::MO_Immediate: + break; + case MachineOperand::MO_ConstantPoolIndex: + case MachineOperand::MO_JumpTableIndex: + Hash = hash_combine(Hash, Val.Disp->getIndex()); + break; + case MachineOperand::MO_ExternalSymbol: + Hash = hash_combine(Hash, Val.Disp->getSymbolName()); + break; + case MachineOperand::MO_GlobalAddress: + Hash = hash_combine(Hash, Val.Disp->getGlobal()); + break; + case MachineOperand::MO_BlockAddress: + Hash = hash_combine(Hash, Val.Disp->getBlockAddress()); + break; + case MachineOperand::MO_MCSymbol: + Hash = hash_combine(Hash, Val.Disp->getMCSymbol()); + break; + case MachineOperand::MO_MachineBasicBlock: + Hash = hash_combine(Hash, Val.Disp->getMBB()); + break; + default: + llvm_unreachable("Invalid address displacement operand"); + } + + return (unsigned)Hash; + } + + static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) { + // Checking any field of MemOpKey is enough to determine if the key is + // empty or tombstone. + if (RHS.Disp == PtrInfo::getEmptyKey()) + return LHS.Disp == PtrInfo::getEmptyKey(); + if (RHS.Disp == PtrInfo::getTombstoneKey()) + return LHS.Disp == PtrInfo::getTombstoneKey(); + return LHS == RHS; + } +}; + +} // end namespace llvm + +static inline bool isIdenticalOp(const llvm::MachineOperand &MO1, + const llvm::MachineOperand &MO2) { + return MO1.isIdenticalTo(MO2) && + (!MO1.isReg() || !llvm::Register::isPhysicalRegister(MO1.getReg())); +} + +#ifndef NDEBUG +static bool isValidDispOp(const llvm::MachineOperand &MO) { + return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() || + MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB(); +} +#endif + +static bool isSimilarDispOp(const llvm::MachineOperand &MO1, + const llvm::MachineOperand &MO2) { + assert(isValidDispOp(MO1) && isValidDispOp(MO2) && + "Address displacement operand is not valid"); + return (MO1.isImm() && MO2.isImm()) || + (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) || + (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) || + (MO1.isSymbol() && MO2.isSymbol() && + MO1.getSymbolName() == MO2.getSymbolName()) || + (MO1.isGlobal() && MO2.isGlobal() && + MO1.getGlobal() == MO2.getGlobal()) || + (MO1.isBlockAddress() && MO2.isBlockAddress() && + MO1.getBlockAddress() == MO2.getBlockAddress()) || + (MO1.isMCSymbol() && MO2.isMCSymbol() && + MO1.getMCSymbol() == MO2.getMCSymbol()) || + (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB()); +} +#endif // LLVM_LIB_TARGET_X86_X86MEMOPKEY_H Index: llvm/lib/Target/X86/X86OptimizeLEAs.cpp =================================================================== --- llvm/lib/Target/X86/X86OptimizeLEAs.cpp +++ llvm/lib/Target/X86/X86OptimizeLEAs.cpp @@ -43,6 +43,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" +#include "X86MemOpKey.h" #include #include #include @@ -59,130 +60,9 @@ STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions"); STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed"); -/// Returns true if two machine operands are identical and they are not -/// physical registers. -static inline bool isIdenticalOp(const MachineOperand &MO1, - const MachineOperand &MO2); - -/// Returns true if two address displacement operands are of the same -/// type and use the same symbol/index/address regardless of the offset. -static bool isSimilarDispOp(const MachineOperand &MO1, - const MachineOperand &MO2); - /// Returns true if the instruction is LEA. static inline bool isLEA(const MachineInstr &MI); -namespace { - -/// 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; - - // Addresses' displacements don't have to be exactly the same. It only - // matters that they use the same symbol/index/address. Immediates' or - // offsets' differences will be taken care of during instruction - // substitution. - return isSimilarDispOp(*Disp, *Other.Disp); - } - - // Address' base, scale, index and segment operands. - const MachineOperand *Operands[4]; - - // Address' displacement operand. - const MachineOperand *Disp; -}; - -} // end anonymous namespace - -/// Provide DenseMapInfo for MemOpKey. -namespace llvm { - -template <> struct DenseMapInfo { - using PtrInfo = DenseMapInfo; - - static inline MemOpKey getEmptyKey() { - return MemOpKey(PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), - PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(), - PtrInfo::getEmptyKey()); - } - - static inline MemOpKey getTombstoneKey() { - return MemOpKey(PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), - PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(), - PtrInfo::getTombstoneKey()); - } - - static unsigned getHashValue(const MemOpKey &Val) { - // Checking any field of MemOpKey is enough to determine if the key is - // empty or tombstone. - assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key"); - assert(Val.Disp != PtrInfo::getTombstoneKey() && - "Cannot hash the tombstone key"); - - hash_code Hash = hash_combine(*Val.Operands[0], *Val.Operands[1], - *Val.Operands[2], *Val.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 something else, - // we should reflect symbol/index/address in the hash. - switch (Val.Disp->getType()) { - case MachineOperand::MO_Immediate: - break; - case MachineOperand::MO_ConstantPoolIndex: - case MachineOperand::MO_JumpTableIndex: - Hash = hash_combine(Hash, Val.Disp->getIndex()); - break; - case MachineOperand::MO_ExternalSymbol: - Hash = hash_combine(Hash, Val.Disp->getSymbolName()); - break; - case MachineOperand::MO_GlobalAddress: - Hash = hash_combine(Hash, Val.Disp->getGlobal()); - break; - case MachineOperand::MO_BlockAddress: - Hash = hash_combine(Hash, Val.Disp->getBlockAddress()); - break; - case MachineOperand::MO_MCSymbol: - Hash = hash_combine(Hash, Val.Disp->getMCSymbol()); - break; - case MachineOperand::MO_MachineBasicBlock: - Hash = hash_combine(Hash, Val.Disp->getMBB()); - break; - default: - llvm_unreachable("Invalid address displacement operand"); - } - - return (unsigned)Hash; - } - - static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) { - // Checking any field of MemOpKey is enough to determine if the key is - // empty or tombstone. - if (RHS.Disp == PtrInfo::getEmptyKey()) - return LHS.Disp == PtrInfo::getEmptyKey(); - if (RHS.Disp == PtrInfo::getTombstoneKey()) - return LHS.Disp == PtrInfo::getTombstoneKey(); - return LHS == RHS; - } -}; - -} // end namespace llvm - /// 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) { @@ -195,37 +75,6 @@ &MI.getOperand(N + X86::AddrDisp)); } -static inline bool isIdenticalOp(const MachineOperand &MO1, - const MachineOperand &MO2) { - return MO1.isIdenticalTo(MO2) && - (!MO1.isReg() || !Register::isPhysicalRegister(MO1.getReg())); -} - -#ifndef NDEBUG -static bool isValidDispOp(const MachineOperand &MO) { - return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() || - MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB(); -} -#endif - -static bool isSimilarDispOp(const MachineOperand &MO1, - const MachineOperand &MO2) { - assert(isValidDispOp(MO1) && isValidDispOp(MO2) && - "Address displacement operand is not valid"); - return (MO1.isImm() && MO2.isImm()) || - (MO1.isCPI() && MO2.isCPI() && MO1.getIndex() == MO2.getIndex()) || - (MO1.isJTI() && MO2.isJTI() && MO1.getIndex() == MO2.getIndex()) || - (MO1.isSymbol() && MO2.isSymbol() && - MO1.getSymbolName() == MO2.getSymbolName()) || - (MO1.isGlobal() && MO2.isGlobal() && - MO1.getGlobal() == MO2.getGlobal()) || - (MO1.isBlockAddress() && MO2.isBlockAddress() && - MO1.getBlockAddress() == MO2.getBlockAddress()) || - (MO1.isMCSymbol() && MO2.isMCSymbol() && - MO1.getMCSymbol() == MO2.getMCSymbol()) || - (MO1.isMBB() && MO2.isMBB() && MO1.getMBB() == MO2.getMBB()); -} - static inline bool isLEA(const MachineInstr &MI) { unsigned Opcode = MI.getOpcode(); return Opcode == X86::LEA16r || Opcode == X86::LEA32r || @@ -245,6 +94,7 @@ /// been calculated by LEA. Also, remove redundant LEAs. bool runOnMachineFunction(MachineFunction &MF) override; + static char ID; private: using MemOpMap = DenseMap>; @@ -296,7 +146,6 @@ const X86InstrInfo *TII; const X86RegisterInfo *TRI; - static char ID; }; } // end anonymous namespace @@ -304,6 +153,8 @@ char OptimizeLEAPass::ID = 0; FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); } +INITIALIZE_PASS(OptimizeLEAPass, DEBUG_TYPE, + "X86 optimize LEA pass", false, false) int OptimizeLEAPass::calcInstrDist(const MachineInstr &First, const MachineInstr &Last) { Index: llvm/lib/Target/X86/X86TargetMachine.cpp =================================================================== --- llvm/lib/Target/X86/X86TargetMachine.cpp +++ llvm/lib/Target/X86/X86TargetMachine.cpp @@ -81,6 +81,7 @@ initializeX86SpeculativeLoadHardeningPassPass(PR); initializeX86FlagsCopyLoweringPassPass(PR); initializeX86CondBrFoldingPassPass(PR); + initializeOptimizeLEAPassPass(PR); } static std::unique_ptr createTLOF(const Triple &TT) {