• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
OptimizeLEAPass()45   OptimizeLEAPass() : MachineFunctionPass(ID) {}
46 
getPassName() const47   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 
createX86OptimizeLEAs()98 FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
99 
calcInstrDist(const MachineInstr & First,const MachineInstr & Last)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.
chooseBestLEA(const SmallVectorImpl<MachineInstr * > & List,const MachineInstr & MI,MachineInstr * & LEA,int64_t & AddrDispShift,int & Dist)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 
isIdenticalOp(const MachineOperand & MO1,const MachineOperand & MO2)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 
isLEA(const MachineInstr & MI)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.
isSimilarMemOp(const MachineInstr & MI1,unsigned N1,const MachineInstr & MI2,unsigned N2,int64_t & AddrDispShift)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 
findLEAs(const MachineBasicBlock & MBB,SmallVectorImpl<MachineInstr * > & List)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.
removeRedundantAddrCalc(const SmallVectorImpl<MachineInstr * > & List)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 
runOnMachineFunction(MachineFunction & MF)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