1 //===-- X86FixupLEAs.cpp - use or replace 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 finds instructions that can be
11 // re-written as LEA instructions in order to reduce pipeline delays.
12 // When optimizing for size it replaces suitable LEAs with INC or DEC.
14 //===----------------------------------------------------------------------===//
17 #include "X86InstrInfo.h"
18 #include "X86Subtarget.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/CodeGen/LiveVariables.h"
21 #include "llvm/CodeGen/MachineFunctionPass.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/CodeGen/Passes.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Target/TargetInstrInfo.h"
30 #define DEBUG_TYPE "x86-fixup-LEAs"
32 STATISTIC(NumLEAs, "Number of LEA instructions created");
35 class FixupLEAPass : public MachineFunctionPass {
36 enum RegUsageState { RU_NotUsed, RU_Write, RU_Read };
38 /// \brief Loop over all of the instructions in the basic block
39 /// replacing applicable instructions with LEA instructions,
40 /// where appropriate.
41 bool processBasicBlock(MachineFunction &MF, MachineFunction::iterator MFI);
43 const char *getPassName() const override { return "X86 LEA Fixup"; }
45 /// \brief Given a machine register, look for the instruction
46 /// which writes it in the current basic block. If found,
47 /// try to replace it with an equivalent LEA instruction.
48 /// If replacement succeeds, then also process the newly created
50 void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I,
51 MachineFunction::iterator MFI);
53 /// \brief Given a memory access or LEA instruction
54 /// whose address mode uses a base and/or index register, look for
55 /// an opportunity to replace the instruction which sets the base or index
56 /// register with an equivalent LEA instruction.
57 void processInstruction(MachineBasicBlock::iterator &I,
58 MachineFunction::iterator MFI);
60 /// \brief Given a LEA instruction which is unprofitable
61 /// on Silvermont try to replace it with an equivalent ADD instruction
62 void processInstructionForSLM(MachineBasicBlock::iterator &I,
63 MachineFunction::iterator MFI);
65 /// \brief Look for LEAs that add 1 to reg or subtract 1 from reg
66 /// and convert them to INC or DEC respectively.
67 bool fixupIncDec(MachineBasicBlock::iterator &I,
68 MachineFunction::iterator MFI) const;
70 /// \brief Determine if an instruction references a machine register
71 /// and, if so, whether it reads or writes the register.
72 RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I);
74 /// \brief Step backwards through a basic block, looking
75 /// for an instruction which writes a register within
76 /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles.
77 MachineBasicBlock::iterator searchBackwards(MachineOperand &p,
78 MachineBasicBlock::iterator &I,
79 MachineFunction::iterator MFI);
81 /// \brief if an instruction can be converted to an
82 /// equivalent LEA, insert the new instruction into the basic block
83 /// and return a pointer to it. Otherwise, return zero.
84 MachineInstr *postRAConvertToLEA(MachineFunction::iterator &MFI,
85 MachineBasicBlock::iterator &MBBI) const;
88 FixupLEAPass() : MachineFunctionPass(ID) {}
90 /// \brief Loop over all of the basic blocks,
91 /// replacing instructions by equivalent LEA instructions
92 /// if needed and when possible.
93 bool runOnMachineFunction(MachineFunction &MF) override;
97 const X86InstrInfo *TII; // Machine instruction info.
101 char FixupLEAPass::ID = 0;
105 FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI,
106 MachineBasicBlock::iterator &MBBI) const {
107 MachineInstr *MI = MBBI;
109 switch (MI->getOpcode()) {
112 const MachineOperand &Src = MI->getOperand(1);
113 const MachineOperand &Dest = MI->getOperand(0);
114 NewMI = BuildMI(*MF, MI->getDebugLoc(),
115 TII->get(MI->getOpcode() == X86::MOV32rr ? X86::LEA32r
123 MFI->insert(MBBI, NewMI); // Insert the new inst
128 case X86::ADD64ri32_DB:
129 case X86::ADD64ri8_DB:
132 case X86::ADD32ri_DB:
133 case X86::ADD32ri8_DB:
136 case X86::ADD16ri_DB:
137 case X86::ADD16ri8_DB:
138 if (!MI->getOperand(2).isImm()) {
139 // convertToThreeAddress will call getImm()
140 // which requires isImm() to be true
145 case X86::ADD16rr_DB:
146 if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) {
147 // if src1 != src2, then convertToThreeAddress will
148 // need to create a Virtual register, which we cannot do
149 // after register allocation.
153 return TII->convertToThreeAddress(MFI, MBBI, nullptr);
156 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); }
158 bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) {
160 const X86Subtarget &ST = Func.getSubtarget<X86Subtarget>();
161 OptIncDec = !ST.slowIncDec() || Func.getFunction()->optForMinSize();
162 OptLEA = ST.LEAusesAG() || ST.slowLEA();
164 if (!OptLEA && !OptIncDec)
167 TII = ST.getInstrInfo();
169 DEBUG(dbgs() << "Start X86FixupLEAs\n";);
170 // Process all basic blocks.
171 for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I)
172 processBasicBlock(Func, I);
173 DEBUG(dbgs() << "End X86FixupLEAs\n";);
178 FixupLEAPass::RegUsageState
179 FixupLEAPass::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) {
180 RegUsageState RegUsage = RU_NotUsed;
181 MachineInstr *MI = I;
183 for (unsigned int i = 0; i < MI->getNumOperands(); ++i) {
184 MachineOperand &opnd = MI->getOperand(i);
185 if (opnd.isReg() && opnd.getReg() == p.getReg()) {
194 /// getPreviousInstr - Given a reference to an instruction in a basic
195 /// block, return a reference to the previous instruction in the block,
196 /// wrapping around to the last instruction of the block if the block
197 /// branches to itself.
198 static inline bool getPreviousInstr(MachineBasicBlock::iterator &I,
199 MachineFunction::iterator MFI) {
200 if (I == MFI->begin()) {
201 if (MFI->isPredecessor(&*MFI)) {
211 MachineBasicBlock::iterator
212 FixupLEAPass::searchBackwards(MachineOperand &p, MachineBasicBlock::iterator &I,
213 MachineFunction::iterator MFI) {
214 int InstrDistance = 1;
215 MachineBasicBlock::iterator CurInst;
216 static const int INSTR_DISTANCE_THRESHOLD = 5;
220 Found = getPreviousInstr(CurInst, MFI);
221 while (Found && I != CurInst) {
222 if (CurInst->isCall() || CurInst->isInlineAsm())
224 if (InstrDistance > INSTR_DISTANCE_THRESHOLD)
225 break; // too far back to make a difference
226 if (usesRegister(p, CurInst) == RU_Write) {
229 InstrDistance += TII->getInstrLatency(
230 MF->getSubtarget().getInstrItineraryData(), CurInst);
231 Found = getPreviousInstr(CurInst, MFI);
236 static inline bool isLEA(const int opcode) {
237 return opcode == X86::LEA16r || opcode == X86::LEA32r ||
238 opcode == X86::LEA64r || opcode == X86::LEA64_32r;
241 /// isLEASimpleIncOrDec - Does this LEA have one these forms:
242 /// lea %reg, 1(%reg)
243 /// lea %reg, -1(%reg)
244 static inline bool isLEASimpleIncOrDec(MachineInstr *LEA) {
245 unsigned SrcReg = LEA->getOperand(1 + X86::AddrBaseReg).getReg();
246 unsigned DstReg = LEA->getOperand(0).getReg();
247 unsigned AddrDispOp = 1 + X86::AddrDisp;
248 return SrcReg == DstReg &&
249 LEA->getOperand(1 + X86::AddrIndexReg).getReg() == 0 &&
250 LEA->getOperand(1 + X86::AddrSegmentReg).getReg() == 0 &&
251 LEA->getOperand(AddrDispOp).isImm() &&
252 (LEA->getOperand(AddrDispOp).getImm() == 1 ||
253 LEA->getOperand(AddrDispOp).getImm() == -1);
256 bool FixupLEAPass::fixupIncDec(MachineBasicBlock::iterator &I,
257 MachineFunction::iterator MFI) const {
258 MachineInstr *MI = I;
259 int Opcode = MI->getOpcode();
263 if (isLEASimpleIncOrDec(MI) && TII->isSafeToClobberEFLAGS(*MFI, I)) {
265 bool isINC = MI->getOperand(4).getImm() == 1;
268 NewOpcode = isINC ? X86::INC16r : X86::DEC16r;
272 NewOpcode = isINC ? X86::INC32r : X86::DEC32r;
275 NewOpcode = isINC ? X86::INC64r : X86::DEC64r;
279 MachineInstr *NewMI =
280 BuildMI(*MFI, I, MI->getDebugLoc(), TII->get(NewOpcode))
281 .addOperand(MI->getOperand(0))
282 .addOperand(MI->getOperand(1));
284 I = static_cast<MachineBasicBlock::iterator>(NewMI);
290 void FixupLEAPass::processInstruction(MachineBasicBlock::iterator &I,
291 MachineFunction::iterator MFI) {
292 // Process a load, store, or LEA instruction.
293 MachineInstr *MI = I;
294 int opcode = MI->getOpcode();
295 const MCInstrDesc &Desc = MI->getDesc();
296 int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode);
297 if (AddrOffset >= 0) {
298 AddrOffset += X86II::getOperandBias(Desc);
299 MachineOperand &p = MI->getOperand(AddrOffset + X86::AddrBaseReg);
300 if (p.isReg() && p.getReg() != X86::ESP) {
301 seekLEAFixup(p, I, MFI);
303 MachineOperand &q = MI->getOperand(AddrOffset + X86::AddrIndexReg);
304 if (q.isReg() && q.getReg() != X86::ESP) {
305 seekLEAFixup(q, I, MFI);
310 void FixupLEAPass::seekLEAFixup(MachineOperand &p,
311 MachineBasicBlock::iterator &I,
312 MachineFunction::iterator MFI) {
313 MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI);
315 MachineInstr *NewMI = postRAConvertToLEA(MFI, MBI);
318 DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump(););
319 // now to replace with an equivalent LEA...
320 DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump(););
322 MachineBasicBlock::iterator J =
323 static_cast<MachineBasicBlock::iterator>(NewMI);
324 processInstruction(J, MFI);
329 void FixupLEAPass::processInstructionForSLM(MachineBasicBlock::iterator &I,
330 MachineFunction::iterator MFI) {
331 MachineInstr *MI = I;
332 const int opcode = MI->getOpcode();
335 if (MI->getOperand(5).getReg() != 0 || !MI->getOperand(4).isImm() ||
336 !TII->isSafeToClobberEFLAGS(*MFI, I))
338 const unsigned DstR = MI->getOperand(0).getReg();
339 const unsigned SrcR1 = MI->getOperand(1).getReg();
340 const unsigned SrcR2 = MI->getOperand(3).getReg();
341 if ((SrcR1 == 0 || SrcR1 != DstR) && (SrcR2 == 0 || SrcR2 != DstR))
343 if (MI->getOperand(2).getImm() > 1)
345 int addrr_opcode, addri_opcode;
348 llvm_unreachable("Unexpected LEA instruction");
350 addrr_opcode = X86::ADD16rr;
351 addri_opcode = X86::ADD16ri;
354 addrr_opcode = X86::ADD32rr;
355 addri_opcode = X86::ADD32ri;
359 addrr_opcode = X86::ADD64rr;
360 addri_opcode = X86::ADD64ri32;
363 DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump(););
364 DEBUG(dbgs() << "FixLEA: Replaced by: ";);
365 MachineInstr *NewMI = nullptr;
366 const MachineOperand &Dst = MI->getOperand(0);
367 // Make ADD instruction for two registers writing to LEA's destination
368 if (SrcR1 != 0 && SrcR2 != 0) {
369 const MachineOperand &Src1 = MI->getOperand(SrcR1 == DstR ? 1 : 3);
370 const MachineOperand &Src2 = MI->getOperand(SrcR1 == DstR ? 3 : 1);
371 NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addrr_opcode))
375 MFI->insert(I, NewMI);
376 DEBUG(NewMI->dump(););
378 // Make ADD instruction for immediate
379 if (MI->getOperand(4).getImm() != 0) {
380 const MachineOperand &SrcR = MI->getOperand(SrcR1 == DstR ? 1 : 3);
381 NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addri_opcode))
384 .addImm(MI->getOperand(4).getImm());
385 MFI->insert(I, NewMI);
386 DEBUG(NewMI->dump(););
390 I = static_cast<MachineBasicBlock::iterator>(NewMI);
394 bool FixupLEAPass::processBasicBlock(MachineFunction &MF,
395 MachineFunction::iterator MFI) {
397 for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) {
399 if (fixupIncDec(I, MFI))
403 if (MF.getSubtarget<X86Subtarget>().isSLM())
404 processInstructionForSLM(I, MFI);
406 processInstruction(I, MFI);