1 //===-- X86OptimizeLEAs.cpp - optimize usage of LEA instructions ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the pass that performs some optimizations with LEA
11 // instructions in order to improve code size.
12 // Currently, it does two things:
13 // 1) If there are two LEA instructions calculating addresses which only differ
14 // by displacement inside a basic block, one of them is removed.
15 // 2) Address calculations in load and store instructions are replaced by
16 // existing LEA def registers where possible.
18 //===----------------------------------------------------------------------===//
21 #include "X86InstrInfo.h"
22 #include "X86Subtarget.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/CodeGen/LiveVariables.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstrBuilder.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/Passes.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
32 #include "llvm/Target/TargetInstrInfo.h"
36 #define DEBUG_TYPE "x86-optimize-LEAs"
38 static cl::opt<bool> EnableX86LEAOpt("enable-x86-lea-opt", cl::Hidden,
39 cl::desc("X86: Enable LEA optimizations."),
42 STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
43 STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");
46 class OptimizeLEAPass : public MachineFunctionPass {
48 OptimizeLEAPass() : MachineFunctionPass(ID) {}
50 const char *getPassName() const override { return "X86 LEA Optimize"; }
52 /// \brief Loop over all of the basic blocks, replacing address
53 /// calculations in load and store instructions, if it's already
54 /// been calculated by LEA. Also, remove redundant LEAs.
55 bool runOnMachineFunction(MachineFunction &MF) override;
58 /// \brief Returns a distance between two instructions inside one basic block.
59 /// Negative result means, that instructions occur in reverse order.
60 int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
62 /// \brief Choose the best \p LEA instruction from the \p List to replace
63 /// address calculation in \p MI instruction. Return the address displacement
64 /// and the distance between \p MI and the choosen \p LEA in \p AddrDispShift
66 bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
67 const MachineInstr &MI, MachineInstr *&LEA,
68 int64_t &AddrDispShift, int &Dist);
70 /// \brief Returns true if two machine operand are identical and they are not
71 /// physical registers.
72 bool isIdenticalOp(const MachineOperand &MO1, const MachineOperand &MO2);
74 /// \brief Returns true if the instruction is LEA.
75 bool isLEA(const MachineInstr &MI);
77 /// \brief Returns true if the \p Last LEA instruction can be replaced by the
78 /// \p First. The difference between displacements of the addresses calculated
79 /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
80 /// replacement of the \p Last LEA's uses with the \p First's def register.
81 bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
82 int64_t &AddrDispShift);
84 /// \brief Returns true if two instructions have memory operands that only
85 /// differ by displacement. The numbers of the first memory operands for both
86 /// instructions are specified through \p N1 and \p N2. The address
87 /// displacement is returned through AddrDispShift.
88 bool isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
89 const MachineInstr &MI2, unsigned N2,
90 int64_t &AddrDispShift);
92 /// \brief Find all LEA instructions in the basic block. Also, assign position
93 /// numbers to all instructions in the basic block to speed up calculation of
94 /// distance between them.
95 void findLEAs(const MachineBasicBlock &MBB,
96 SmallVectorImpl<MachineInstr *> &List);
98 /// \brief Removes redundant address calculations.
99 bool removeRedundantAddrCalc(const SmallVectorImpl<MachineInstr *> &List);
101 /// \brief Removes LEAs which calculate similar addresses.
102 bool removeRedundantLEAs(SmallVectorImpl<MachineInstr *> &List);
104 DenseMap<const MachineInstr *, unsigned> InstrPos;
106 MachineRegisterInfo *MRI;
107 const X86InstrInfo *TII;
108 const X86RegisterInfo *TRI;
112 char OptimizeLEAPass::ID = 0;
115 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
117 int OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
118 const MachineInstr &Last) {
119 // Both instructions must be in the same basic block and they must be
120 // presented in InstrPos.
121 assert(Last.getParent() == First.getParent() &&
122 "Instructions are in different basic blocks");
123 assert(InstrPos.find(&First) != InstrPos.end() &&
124 InstrPos.find(&Last) != InstrPos.end() &&
125 "Instructions' positions are undefined");
127 return InstrPos[&Last] - InstrPos[&First];
130 // Find the best LEA instruction in the List to replace address recalculation in
131 // MI. Such LEA must meet these requirements:
132 // 1) The address calculated by the LEA differs only by the displacement from
133 // the address used in MI.
134 // 2) The register class of the definition of the LEA is compatible with the
135 // register class of the address base register of MI.
136 // 3) Displacement of the new memory operand should fit in 1 byte if possible.
137 // 4) The LEA should be as close to MI as possible, and prior to it if
139 bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
140 const MachineInstr &MI, MachineInstr *&LEA,
141 int64_t &AddrDispShift, int &Dist) {
142 const MachineFunction *MF = MI.getParent()->getParent();
143 const MCInstrDesc &Desc = MI.getDesc();
144 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) +
145 X86II::getOperandBias(Desc);
149 // Loop over all LEA instructions.
150 for (auto DefMI : List) {
151 int64_t AddrDispShiftTemp = 0;
153 // Compare instructions memory operands.
154 if (!isSimilarMemOp(MI, MemOpNo, *DefMI, 1, AddrDispShiftTemp))
157 // Make sure address displacement fits 4 bytes.
158 if (!isInt<32>(AddrDispShiftTemp))
161 // Check that LEA def register can be used as MI address base. Some
162 // instructions can use a limited set of registers as address base, for
163 // example MOV8mr_NOREX. We could constrain the register class of the LEA
164 // def to suit MI, however since this case is very rare and hard to
165 // reproduce in a test it's just more reliable to skip the LEA.
166 if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) !=
167 MRI->getRegClass(DefMI->getOperand(0).getReg()))
170 // Choose the closest LEA instruction from the list, prior to MI if
171 // possible. Note that we took into account resulting address displacement
172 // as well. Also note that the list is sorted by the order in which the LEAs
173 // occur, so the break condition is pretty simple.
174 int DistTemp = calcInstrDist(*DefMI, MI);
175 assert(DistTemp != 0 &&
176 "The distance between two different instructions cannot be zero");
177 if (DistTemp > 0 || LEA == nullptr) {
178 // Do not update return LEA, if the current one provides a displacement
179 // which fits in 1 byte, while the new candidate does not.
180 if (LEA != nullptr && !isInt<8>(AddrDispShiftTemp) &&
181 isInt<8>(AddrDispShift))
185 AddrDispShift = AddrDispShiftTemp;
189 // FIXME: Maybe we should not always stop at the first LEA after MI.
194 return LEA != nullptr;
197 bool OptimizeLEAPass::isIdenticalOp(const MachineOperand &MO1,
198 const MachineOperand &MO2) {
199 return MO1.isIdenticalTo(MO2) &&
201 !TargetRegisterInfo::isPhysicalRegister(MO1.getReg()));
204 bool OptimizeLEAPass::isLEA(const MachineInstr &MI) {
205 unsigned Opcode = MI.getOpcode();
206 return Opcode == X86::LEA16r || Opcode == X86::LEA32r ||
207 Opcode == X86::LEA64r || Opcode == X86::LEA64_32r;
210 // Check that the Last LEA can be replaced by the First LEA. To be so,
211 // these requirements must be met:
212 // 1) Addresses calculated by LEAs differ only by displacement.
213 // 2) Def registers of LEAs belong to the same class.
214 // 3) All uses of the Last LEA def register are replaceable, thus the
215 // register is used only as address base.
216 bool OptimizeLEAPass::isReplaceable(const MachineInstr &First,
217 const MachineInstr &Last,
218 int64_t &AddrDispShift) {
219 assert(isLEA(First) && isLEA(Last) &&
220 "The function works only with LEA instructions");
222 // Compare instructions' memory operands.
223 if (!isSimilarMemOp(Last, 1, First, 1, AddrDispShift))
226 // Make sure that LEA def registers belong to the same class. There may be
227 // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
228 // be used as their operands, so we must be sure that replacing one LEA
229 // with another won't lead to putting a wrong register in the instruction.
230 if (MRI->getRegClass(First.getOperand(0).getReg()) !=
231 MRI->getRegClass(Last.getOperand(0).getReg()))
234 // Loop over all uses of the Last LEA to check that its def register is
235 // used only as address base for memory accesses. If so, it can be
236 // replaced, otherwise - no.
237 for (auto &MO : MRI->use_operands(Last.getOperand(0).getReg())) {
238 MachineInstr &MI = *MO.getParent();
240 // Get the number of the first memory operand.
241 const MCInstrDesc &Desc = MI.getDesc();
242 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode());
244 // If the use instruction has no memory operand - the LEA is not
249 MemOpNo += X86II::getOperandBias(Desc);
251 // If the address base of the use instruction is not the LEA def register -
252 // the LEA is not replaceable.
253 if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))
256 // If the LEA def register is used as any other operand of the use
257 // instruction - the LEA is not replaceable.
258 for (unsigned i = 0; i < MI.getNumOperands(); i++)
259 if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&
260 isIdenticalOp(MI.getOperand(i), MO))
263 // Check that the new address displacement will fit 4 bytes.
264 if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() &&
265 !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() +
273 // Check if MI1 and MI2 have memory operands which represent addresses that
274 // differ only by displacement.
275 bool OptimizeLEAPass::isSimilarMemOp(const MachineInstr &MI1, unsigned N1,
276 const MachineInstr &MI2, unsigned N2,
277 int64_t &AddrDispShift) {
278 // Address base, scale, index and segment operands must be identical.
279 static const int IdenticalOpNums[] = {X86::AddrBaseReg, X86::AddrScaleAmt,
280 X86::AddrIndexReg, X86::AddrSegmentReg};
281 for (auto &N : IdenticalOpNums)
282 if (!isIdenticalOp(MI1.getOperand(N1 + N), MI2.getOperand(N2 + N)))
285 // Address displacement operands may differ by a constant.
286 const MachineOperand *Op1 = &MI1.getOperand(N1 + X86::AddrDisp);
287 const MachineOperand *Op2 = &MI2.getOperand(N2 + X86::AddrDisp);
288 if (!isIdenticalOp(*Op1, *Op2)) {
289 if (Op1->isImm() && Op2->isImm())
290 AddrDispShift = Op1->getImm() - Op2->getImm();
291 else if (Op1->isGlobal() && Op2->isGlobal() &&
292 Op1->getGlobal() == Op2->getGlobal())
293 AddrDispShift = Op1->getOffset() - Op2->getOffset();
301 void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB,
302 SmallVectorImpl<MachineInstr *> &List) {
304 for (auto &MI : MBB) {
305 // Assign the position number to the instruction. Note that we are going to
306 // move some instructions during the optimization however there will never
307 // be a need to move two instructions before any selected instruction. So to
308 // avoid multiple positions' updates during moves we just increase position
309 // counter by two leaving a free space for instructions which will be moved.
310 InstrPos[&MI] = Pos += 2;
313 List.push_back(const_cast<MachineInstr *>(&MI));
317 // Try to find load and store instructions which recalculate addresses already
318 // calculated by some LEA and replace their memory operands with its def
320 bool OptimizeLEAPass::removeRedundantAddrCalc(
321 const SmallVectorImpl<MachineInstr *> &List) {
322 bool Changed = false;
324 assert(List.size() > 0);
325 MachineBasicBlock *MBB = List[0]->getParent();
327 // Process all instructions in basic block.
328 for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
329 MachineInstr &MI = *I++;
330 unsigned Opcode = MI.getOpcode();
332 // Instruction must be load or store.
333 if (!MI.mayLoadOrStore())
336 // Get the number of the first memory operand.
337 const MCInstrDesc &Desc = MI.getDesc();
338 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, Opcode);
340 // If instruction has no memory operand - skip it.
344 MemOpNo += X86II::getOperandBias(Desc);
346 // Get the best LEA instruction to replace address calculation.
348 int64_t AddrDispShift;
350 if (!chooseBestLEA(List, MI, DefMI, AddrDispShift, Dist))
353 // If LEA occurs before current instruction, we can freely replace
354 // the instruction. If LEA occurs after, we can lift LEA above the
355 // instruction and this way to be able to replace it. Since LEA and the
356 // instruction have similar memory operands (thus, the same def
357 // instructions for these operands), we can always do that, without
358 // worries of using registers before their defs.
360 DefMI->removeFromParent();
361 MBB->insert(MachineBasicBlock::iterator(&MI), DefMI);
362 InstrPos[DefMI] = InstrPos[&MI] - 1;
364 // Make sure the instructions' position numbers are sane.
365 assert(((InstrPos[DefMI] == 1 && DefMI == MBB->begin()) ||
367 InstrPos[std::prev(MachineBasicBlock::iterator(DefMI))]) &&
368 "Instruction positioning is broken");
371 // Since we can possibly extend register lifetime, clear kill flags.
372 MRI->clearKillFlags(DefMI->getOperand(0).getReg());
375 DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););
377 // Change instruction operands.
378 MI.getOperand(MemOpNo + X86::AddrBaseReg)
379 .ChangeToRegister(DefMI->getOperand(0).getReg(), false);
380 MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1);
381 MI.getOperand(MemOpNo + X86::AddrIndexReg)
382 .ChangeToRegister(X86::NoRegister, false);
383 MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);
384 MI.getOperand(MemOpNo + X86::AddrSegmentReg)
385 .ChangeToRegister(X86::NoRegister, false);
387 DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
395 // Try to find similar LEAs in the list and replace one with another.
397 OptimizeLEAPass::removeRedundantLEAs(SmallVectorImpl<MachineInstr *> &List) {
398 bool Changed = false;
400 // Loop over all LEA pairs.
401 auto I1 = List.begin();
402 while (I1 != List.end()) {
403 MachineInstr &First = **I1;
404 auto I2 = std::next(I1);
405 while (I2 != List.end()) {
406 MachineInstr &Last = **I2;
407 int64_t AddrDispShift;
409 // LEAs should be in occurence order in the list, so we can freely
410 // replace later LEAs with earlier ones.
411 assert(calcInstrDist(First, Last) > 0 &&
412 "LEAs must be in occurence order in the list");
414 // Check that the Last LEA instruction can be replaced by the First.
415 if (!isReplaceable(First, Last, AddrDispShift)) {
420 // Loop over all uses of the Last LEA and update their operands. Note that
421 // the correctness of this has already been checked in the isReplaceable
423 for (auto UI = MRI->use_begin(Last.getOperand(0).getReg()),
426 MachineOperand &MO = *UI++;
427 MachineInstr &MI = *MO.getParent();
429 // Get the number of the first memory operand.
430 const MCInstrDesc &Desc = MI.getDesc();
431 int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags, MI.getOpcode()) +
432 X86II::getOperandBias(Desc);
434 // Update address base.
435 MO.setReg(First.getOperand(0).getReg());
437 // Update address disp.
438 MachineOperand *Op = &MI.getOperand(MemOpNo + X86::AddrDisp);
440 Op->setImm(Op->getImm() + AddrDispShift);
441 else if (Op->isGlobal())
442 Op->setOffset(Op->getOffset() + AddrDispShift);
444 llvm_unreachable("Invalid address displacement operand");
447 // Since we can possibly extend register lifetime, clear kill flags.
448 MRI->clearKillFlags(First.getOperand(0).getReg());
451 DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; Last.dump(););
453 // By this moment, all of the Last LEA's uses must be replaced. So we can
455 assert(MRI->use_empty(Last.getOperand(0).getReg()) &&
456 "The LEA's def register must have no uses");
457 Last.eraseFromParent();
459 // Erase removed LEA from the list.
470 bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
471 bool Changed = false;
473 // Perform this optimization only if we care about code size.
474 if (!EnableX86LEAOpt || !MF.getFunction()->optForSize())
477 MRI = &MF.getRegInfo();
478 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
479 TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
481 // Process all basic blocks.
482 for (auto &MBB : MF) {
483 SmallVector<MachineInstr *, 16> LEAs;
486 // Find all LEA instructions in basic block.
489 // If current basic block has no LEAs, move on to the next one.
493 // Remove redundant LEA instructions. The optimization may have a negative
494 // effect on performance, so do it only for -Oz.
495 if (MF.getFunction()->optForMinSize())
496 Changed |= removeRedundantLEAs(LEAs);
498 // Remove redundant address calculations.
499 Changed |= removeRedundantAddrCalc(LEAs);