1 //===-- X86OptimizeLEAs.cpp - optimize usage of LEA instructions ----------===// 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 defines the pass that performs some optimizations with LEA 11 // instructions in order to improve code size. 12 // Currently, it does one thing: 13 // 1) Address calculations in load and store instructions are replaced by 14 // existing LEA def registers where possible. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "X86.h" 19 #include "X86InstrInfo.h" 20 #include "X86Subtarget.h" 21 #include "llvm/ADT/Statistic.h" 22 #include "llvm/CodeGen/LiveVariables.h" 23 #include "llvm/CodeGen/MachineFunctionPass.h" 24 #include "llvm/CodeGen/MachineInstrBuilder.h" 25 #include "llvm/CodeGen/MachineRegisterInfo.h" 26 #include "llvm/CodeGen/Passes.h" 27 #include "llvm/IR/Function.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include "llvm/Target/TargetInstrInfo.h" 31 32 using namespace llvm; 33 34 #define DEBUG_TYPE "x86-optimize-LEAs" 35 36 static cl::opt<bool> EnableX86LEAOpt("enable-x86-lea-opt", cl::Hidden, 37 cl::desc("X86: Enable LEA optimizations."), 38 cl::init(false)); 39 40 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions"); 41 42 namespace { 43 class OptimizeLEAPass : public MachineFunctionPass { 44 public: 45 OptimizeLEAPass() : MachineFunctionPass(ID) {} 46 47 const char *getPassName() const override { return "X86 LEA Optimize"; } 48 49 /// \brief Loop over all of the basic blocks, replacing address 50 /// calculations in load and store instructions, if it's already 51 /// been calculated by LEA. Also, remove redundant LEAs. 52 bool runOnMachineFunction(MachineFunction &MF) override; 53 54 private: 55 /// \brief Returns a distance between two instructions inside one basic block. 56 /// Negative result means, that instructions occur in reverse order. 57 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last); 58 59 /// \brief Choose the best \p LEA instruction from the \p List to replace 60 /// address calculation in \p MI instruction. Return the address displacement 61 /// and the distance between \p MI and the choosen \p LEA in \p AddrDispShift 62 /// and \p Dist. 63 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List, 64 const MachineInstr &MI, MachineInstr *&LEA, 65 int64_t &AddrDispShift, int &Dist); 66 67 /// \brief Returns true if two machine operand are identical and they are not 68 /// physical registers. 69 bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2); 70 71 /// \brief Returns true if the instruction is LEA. 72 bool isLEA(const MachineInstr &MI); 73 74 /// \brief Returns true if two instructions have memory operands that only 75 /// differ by displacement. The numbers of the first memory operands for both 76 /// instructions are specified through \p N1 and \p N2. The address 77 /// displacement is returned through AddrDispShift. 78 bool isSimilarMemOp(const MachineInstr &MI1, unsigned N1, 79 const MachineInstr &MI2, unsigned N2, 80 int64_t &AddrDispShift); 81 82 /// \brief Find all LEA instructions in the basic block. 83 void findLEAs(const MachineBasicBlock &MBB, 84 SmallVectorImpl<MachineInstr *> &List); 85 86 /// \brief Removes redundant address calculations. 87 bool removeRedundantAddrCalc(const SmallVectorImpl<MachineInstr *> &List); 88 89 MachineRegisterInfo *MRI; 90 const X86InstrInfo *TII; 91 const X86RegisterInfo *TRI; 92 93 static char ID; 94 }; 95 char OptimizeLEAPass::ID = 0; 96 } 97 98 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); } 99 100 int OptimizeLEAPass::calcInstrDist(const MachineInstr &First, 101 const MachineInstr &Last) { 102 const MachineBasicBlock *MBB = First.getParent(); 103 104 // Both instructions must be in the same basic block. 105 assert(Last.getParent() == MBB && 106 "Instructions are in different basic blocks"); 107 108 return std::distance(MBB->begin(), MachineBasicBlock::const_iterator(&Last)) - 109 std::distance(MBB->begin(), MachineBasicBlock::const_iterator(&First)); 110 } 111 112 // Find the best LEA instruction in the List to replace address recalculation in 113 // MI. Such LEA must meet these requirements: 114 // 1) The address calculated by the LEA differs only by the displacement from 115 // the address used in MI. 116 // 2) The register class of the definition of the LEA is compatible with the 117 // register class of the address base register of MI. 118 // 3) Displacement of the new memory operand should fit in 1 byte if possible. 119 // 4) The LEA should be as close to MI as possible, and prior to it if 120 // possible. 121 bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List, 122 const MachineInstr &MI, MachineInstr *&LEA, 123 int64_t &AddrDispShift, int &Dist) { 124 const MachineFunction *MF = MI.getParent()->getParent(); 125 const MCInstrDesc &Desc = MI.getDesc(); 126 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) + 127 X86II::getOperandBias(Desc); 128 129 LEA = nullptr; 130 131 // Loop over all LEA instructions. 132 for (auto DefMI : List) { 133 int64_t AddrDispShiftTemp = 0; 134 135 // Compare instructions memory operands. 136 if (!isSimilarMemOp(MI, MemOpNo, *DefMI, 1, AddrDispShiftTemp)) 137 continue; 138 139 // Make sure address displacement fits 4 bytes. 140 if (!isInt<32>(AddrDispShiftTemp)) 141 continue; 142 143 // Check that LEA def register can be used as MI address base. Some 144 // instructions can use a limited set of registers as address base, for 145 // example MOV8mr_NOREX. We could constrain the register class of the LEA 146 // def to suit MI, however since this case is very rare and hard to 147 // reproduce in a test it's just more reliable to skip the LEA. 148 if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) != 149 MRI->getRegClass(DefMI->getOperand(0).getReg())) 150 continue; 151 152 // Choose the closest LEA instruction from the list, prior to MI if 153 // possible. Note that we took into account resulting address displacement 154 // as well. Also note that the list is sorted by the order in which the LEAs 155 // occur, so the break condition is pretty simple. 156 int DistTemp = calcInstrDist(*DefMI, MI); 157 assert(DistTemp != 0 && 158 "The distance between two different instructions cannot be zero"); 159 if (DistTemp > 0 || LEA == nullptr) { 160 // Do not update return LEA, if the current one provides a displacement 161 // which fits in 1 byte, while the new candidate does not. 162 if (LEA != nullptr && !isInt<8>(AddrDispShiftTemp) && 163 isInt<8>(AddrDispShift)) 164 continue; 165 166 LEA = DefMI; 167 AddrDispShift = AddrDispShiftTemp; 168 Dist = DistTemp; 169 } 170 171 // FIXME: Maybe we should not always stop at the first LEA after MI. 172 if (DistTemp < 0) 173 break; 174 } 175 176 return LEA != nullptr; 177 } 178 179 bool OptimizeLEAPass::isIdenticalOp(const MachineOperand &MO1, 180 const MachineOperand &MO2) { 181 return MO1.isIdenticalTo(MO2) && 182 (!MO1.isReg() || 183 !TargetRegisterInfo::isPhysicalRegister(MO1.getReg())); 184 } 185 186 bool OptimizeLEAPass::isLEA(const MachineInstr &MI) { 187 unsigned Opcode = MI.getOpcode(); 188 return Opcode == X86::LEA16r || Opcode == X86::LEA32r || 189 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r; 190 } 191 192 // Check if MI1 and MI2 have memory operands which represent addresses that 193 // differ only by displacement. 194 bool OptimizeLEAPass::isSimilarMemOp(const MachineInstr &MI1, unsigned N1, 195 const MachineInstr &MI2, unsigned N2, 196 int64_t &AddrDispShift) { 197 // Address base, scale, index and segment operands must be identical. 198 static const int IdenticalOpNums[] = {X86::AddrBaseReg, X86::AddrScaleAmt, 199 X86::AddrIndexReg, X86::AddrSegmentReg}; 200 for (auto &N : IdenticalOpNums) 201 if (!isIdenticalOp(MI1.getOperand(N1 + N), MI2.getOperand(N2 + N))) 202 return false; 203 204 // Address displacement operands may differ by a constant. 205 const MachineOperand *Op1 = &MI1.getOperand(N1 + X86::AddrDisp); 206 const MachineOperand *Op2 = &MI2.getOperand(N2 + X86::AddrDisp); 207 if (!isIdenticalOp(*Op1, *Op2)) { 208 if (Op1->isImm() && Op2->isImm()) 209 AddrDispShift = Op1->getImm() - Op2->getImm(); 210 else if (Op1->isGlobal() && Op2->isGlobal() && 211 Op1->getGlobal() == Op2->getGlobal()) 212 AddrDispShift = Op1->getOffset() - Op2->getOffset(); 213 else 214 return false; 215 } 216 217 return true; 218 } 219 220 void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, 221 SmallVectorImpl<MachineInstr *> &List) { 222 for (auto &MI : MBB) { 223 if (isLEA(MI)) 224 List.push_back(const_cast<MachineInstr *>(&MI)); 225 } 226 } 227 228 // Try to find load and store instructions which recalculate addresses already 229 // calculated by some LEA and replace their memory operands with its def 230 // register. 231 bool OptimizeLEAPass::removeRedundantAddrCalc( 232 const SmallVectorImpl<MachineInstr *> &List) { 233 bool Changed = false; 234 235 assert(List.size() > 0); 236 MachineBasicBlock *MBB = List[0]->getParent(); 237 238 // Process all instructions in basic block. 239 for (auto I = MBB->begin(), E = MBB->end(); I != E;) { 240 MachineInstr &MI = *I++; 241 unsigned Opcode = MI.getOpcode(); 242 243 // Instruction must be load or store. 244 if (!MI.mayLoadOrStore()) 245 continue; 246 247 // Get the number of the first memory operand. 248 const MCInstrDesc &Desc = MI.getDesc(); 249 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, Opcode); 250 251 // If instruction has no memory operand - skip it. 252 if (MemOpNo < 0) 253 continue; 254 255 MemOpNo += X86II::getOperandBias(Desc); 256 257 // Get the best LEA instruction to replace address calculation. 258 MachineInstr *DefMI; 259 int64_t AddrDispShift; 260 int Dist; 261 if (!chooseBestLEA(List, MI, DefMI, AddrDispShift, Dist)) 262 continue; 263 264 // If LEA occurs before current instruction, we can freely replace 265 // the instruction. If LEA occurs after, we can lift LEA above the 266 // instruction and this way to be able to replace it. Since LEA and the 267 // instruction have similar memory operands (thus, the same def 268 // instructions for these operands), we can always do that, without 269 // worries of using registers before their defs. 270 if (Dist < 0) { 271 DefMI->removeFromParent(); 272 MBB->insert(MachineBasicBlock::iterator(&MI), DefMI); 273 } 274 275 // Since we can possibly extend register lifetime, clear kill flags. 276 MRI->clearKillFlags(DefMI->getOperand(0).getReg()); 277 278 ++NumSubstLEAs; 279 DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump();); 280 281 // Change instruction operands. 282 MI.getOperand(MemOpNo + X86::AddrBaseReg) 283 .ChangeToRegister(DefMI->getOperand(0).getReg(), false); 284 MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1); 285 MI.getOperand(MemOpNo + X86::AddrIndexReg) 286 .ChangeToRegister(X86::NoRegister, false); 287 MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift); 288 MI.getOperand(MemOpNo + X86::AddrSegmentReg) 289 .ChangeToRegister(X86::NoRegister, false); 290 291 DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump();); 292 293 Changed = true; 294 } 295 296 return Changed; 297 } 298 299 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) { 300 bool Changed = false; 301 302 // Perform this optimization only if we care about code size. 303 if (!EnableX86LEAOpt || !MF.getFunction()->optForSize()) 304 return false; 305 306 MRI = &MF.getRegInfo(); 307 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); 308 TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo(); 309 310 // Process all basic blocks. 311 for (auto &MBB : MF) { 312 SmallVector<MachineInstr *, 16> LEAs; 313 314 // Find all LEA instructions in basic block. 315 findLEAs(MBB, LEAs); 316 317 // If current basic block has no LEAs, move on to the next one. 318 if (LEAs.empty()) 319 continue; 320 321 // Remove redundant address calculations. 322 Changed |= removeRedundantAddrCalc(LEAs); 323 } 324 325 return Changed; 326 } 327