]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //===-- X86FixupLEAs.cpp - use or replace 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 finds instructions that can be | |
11 | // re-written as LEA instructions in order to reduce pipeline delays. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #include "X86.h" | |
16 | #include "X86InstrInfo.h" | |
17 | #include "X86Subtarget.h" | |
18 | #include "llvm/ADT/Statistic.h" | |
19 | #include "llvm/CodeGen/LiveVariables.h" | |
20 | #include "llvm/CodeGen/MachineFunctionPass.h" | |
21 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |
22 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |
23 | #include "llvm/CodeGen/Passes.h" | |
24 | #include "llvm/Support/Debug.h" | |
25 | #include "llvm/Support/raw_ostream.h" | |
26 | #include "llvm/Target/TargetInstrInfo.h" | |
27 | using namespace llvm; | |
28 | ||
29 | #define DEBUG_TYPE "x86-fixup-LEAs" | |
30 | ||
31 | STATISTIC(NumLEAs, "Number of LEA instructions created"); | |
32 | ||
33 | namespace { | |
34 | class FixupLEAPass : public MachineFunctionPass { | |
35 | enum RegUsageState { RU_NotUsed, RU_Write, RU_Read }; | |
36 | static char ID; | |
37 | /// \brief Loop over all of the instructions in the basic block | |
38 | /// replacing applicable instructions with LEA instructions, | |
39 | /// where appropriate. | |
40 | bool processBasicBlock(MachineFunction &MF, MachineFunction::iterator MFI); | |
41 | ||
42 | const char *getPassName() const override { return "X86 LEA Fixup"; } | |
43 | ||
44 | /// \brief Given a machine register, look for the instruction | |
45 | /// which writes it in the current basic block. If found, | |
46 | /// try to replace it with an equivalent LEA instruction. | |
47 | /// If replacement succeeds, then also process the the newly created | |
48 | /// instruction. | |
49 | void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I, | |
50 | MachineFunction::iterator MFI); | |
51 | ||
52 | /// \brief Given a memory access or LEA instruction | |
53 | /// whose address mode uses a base and/or index register, look for | |
54 | /// an opportunity to replace the instruction which sets the base or index | |
55 | /// register with an equivalent LEA instruction. | |
56 | void processInstruction(MachineBasicBlock::iterator &I, | |
57 | MachineFunction::iterator MFI); | |
58 | ||
59 | /// \brief Given a LEA instruction which is unprofitable | |
60 | /// on Silvermont try to replace it with an equivalent ADD instruction | |
61 | void processInstructionForSLM(MachineBasicBlock::iterator &I, | |
62 | MachineFunction::iterator MFI); | |
63 | ||
64 | /// \brief Determine if an instruction references a machine register | |
65 | /// and, if so, whether it reads or writes the register. | |
66 | RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I); | |
67 | ||
68 | /// \brief Step backwards through a basic block, looking | |
69 | /// for an instruction which writes a register within | |
70 | /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles. | |
71 | MachineBasicBlock::iterator searchBackwards(MachineOperand &p, | |
72 | MachineBasicBlock::iterator &I, | |
73 | MachineFunction::iterator MFI); | |
74 | ||
75 | /// \brief if an instruction can be converted to an | |
76 | /// equivalent LEA, insert the new instruction into the basic block | |
77 | /// and return a pointer to it. Otherwise, return zero. | |
78 | MachineInstr *postRAConvertToLEA(MachineFunction::iterator &MFI, | |
79 | MachineBasicBlock::iterator &MBBI) const; | |
80 | ||
81 | public: | |
82 | FixupLEAPass() : MachineFunctionPass(ID) {} | |
83 | ||
84 | /// \brief Loop over all of the basic blocks, | |
85 | /// replacing instructions by equivalent LEA instructions | |
86 | /// if needed and when possible. | |
87 | bool runOnMachineFunction(MachineFunction &MF) override; | |
88 | ||
89 | private: | |
90 | MachineFunction *MF; | |
91 | const TargetMachine *TM; | |
92 | const X86InstrInfo *TII; // Machine instruction info. | |
93 | }; | |
94 | char FixupLEAPass::ID = 0; | |
95 | } | |
96 | ||
97 | MachineInstr * | |
98 | FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI, | |
99 | MachineBasicBlock::iterator &MBBI) const { | |
100 | MachineInstr *MI = MBBI; | |
101 | MachineInstr *NewMI; | |
102 | switch (MI->getOpcode()) { | |
103 | case X86::MOV32rr: | |
104 | case X86::MOV64rr: { | |
105 | const MachineOperand &Src = MI->getOperand(1); | |
106 | const MachineOperand &Dest = MI->getOperand(0); | |
107 | NewMI = BuildMI(*MF, MI->getDebugLoc(), | |
108 | TII->get(MI->getOpcode() == X86::MOV32rr ? X86::LEA32r | |
109 | : X86::LEA64r)) | |
110 | .addOperand(Dest) | |
111 | .addOperand(Src) | |
112 | .addImm(1) | |
113 | .addReg(0) | |
114 | .addImm(0) | |
115 | .addReg(0); | |
116 | MFI->insert(MBBI, NewMI); // Insert the new inst | |
117 | return NewMI; | |
118 | } | |
119 | case X86::ADD64ri32: | |
120 | case X86::ADD64ri8: | |
121 | case X86::ADD64ri32_DB: | |
122 | case X86::ADD64ri8_DB: | |
123 | case X86::ADD32ri: | |
124 | case X86::ADD32ri8: | |
125 | case X86::ADD32ri_DB: | |
126 | case X86::ADD32ri8_DB: | |
127 | case X86::ADD16ri: | |
128 | case X86::ADD16ri8: | |
129 | case X86::ADD16ri_DB: | |
130 | case X86::ADD16ri8_DB: | |
131 | if (!MI->getOperand(2).isImm()) { | |
132 | // convertToThreeAddress will call getImm() | |
133 | // which requires isImm() to be true | |
134 | return nullptr; | |
135 | } | |
136 | break; | |
137 | case X86::ADD16rr: | |
138 | case X86::ADD16rr_DB: | |
139 | if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) { | |
140 | // if src1 != src2, then convertToThreeAddress will | |
141 | // need to create a Virtual register, which we cannot do | |
142 | // after register allocation. | |
143 | return nullptr; | |
144 | } | |
145 | } | |
146 | return TII->convertToThreeAddress(MFI, MBBI, nullptr); | |
147 | } | |
148 | ||
149 | FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); } | |
150 | ||
151 | bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { | |
152 | MF = &Func; | |
153 | TM = &Func.getTarget(); | |
154 | const X86Subtarget &ST = TM->getSubtarget<X86Subtarget>(); | |
155 | if (!ST.LEAusesAG() && !ST.slowLEA()) | |
156 | return false; | |
157 | ||
158 | TII = | |
159 | static_cast<const X86InstrInfo *>(TM->getSubtargetImpl()->getInstrInfo()); | |
160 | ||
161 | DEBUG(dbgs() << "Start X86FixupLEAs\n";); | |
162 | // Process all basic blocks. | |
163 | for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) | |
164 | processBasicBlock(Func, I); | |
165 | DEBUG(dbgs() << "End X86FixupLEAs\n";); | |
166 | ||
167 | return true; | |
168 | } | |
169 | ||
170 | FixupLEAPass::RegUsageState | |
171 | FixupLEAPass::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) { | |
172 | RegUsageState RegUsage = RU_NotUsed; | |
173 | MachineInstr *MI = I; | |
174 | ||
175 | for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { | |
176 | MachineOperand &opnd = MI->getOperand(i); | |
177 | if (opnd.isReg() && opnd.getReg() == p.getReg()) { | |
178 | if (opnd.isDef()) | |
179 | return RU_Write; | |
180 | RegUsage = RU_Read; | |
181 | } | |
182 | } | |
183 | return RegUsage; | |
184 | } | |
185 | ||
186 | /// getPreviousInstr - Given a reference to an instruction in a basic | |
187 | /// block, return a reference to the previous instruction in the block, | |
188 | /// wrapping around to the last instruction of the block if the block | |
189 | /// branches to itself. | |
190 | static inline bool getPreviousInstr(MachineBasicBlock::iterator &I, | |
191 | MachineFunction::iterator MFI) { | |
192 | if (I == MFI->begin()) { | |
193 | if (MFI->isPredecessor(MFI)) { | |
194 | I = --MFI->end(); | |
195 | return true; | |
196 | } else | |
197 | return false; | |
198 | } | |
199 | --I; | |
200 | return true; | |
201 | } | |
202 | ||
203 | MachineBasicBlock::iterator | |
204 | FixupLEAPass::searchBackwards(MachineOperand &p, MachineBasicBlock::iterator &I, | |
205 | MachineFunction::iterator MFI) { | |
206 | int InstrDistance = 1; | |
207 | MachineBasicBlock::iterator CurInst; | |
208 | static const int INSTR_DISTANCE_THRESHOLD = 5; | |
209 | ||
210 | CurInst = I; | |
211 | bool Found; | |
212 | Found = getPreviousInstr(CurInst, MFI); | |
213 | while (Found && I != CurInst) { | |
214 | if (CurInst->isCall() || CurInst->isInlineAsm()) | |
215 | break; | |
216 | if (InstrDistance > INSTR_DISTANCE_THRESHOLD) | |
217 | break; // too far back to make a difference | |
218 | if (usesRegister(p, CurInst) == RU_Write) { | |
219 | return CurInst; | |
220 | } | |
221 | InstrDistance += TII->getInstrLatency( | |
222 | TM->getSubtargetImpl()->getInstrItineraryData(), CurInst); | |
223 | Found = getPreviousInstr(CurInst, MFI); | |
224 | } | |
225 | return nullptr; | |
226 | } | |
227 | ||
228 | void FixupLEAPass::processInstruction(MachineBasicBlock::iterator &I, | |
229 | MachineFunction::iterator MFI) { | |
230 | // Process a load, store, or LEA instruction. | |
231 | MachineInstr *MI = I; | |
232 | int opcode = MI->getOpcode(); | |
233 | const MCInstrDesc &Desc = MI->getDesc(); | |
234 | int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); | |
235 | if (AddrOffset >= 0) { | |
236 | AddrOffset += X86II::getOperandBias(Desc); | |
237 | MachineOperand &p = MI->getOperand(AddrOffset + X86::AddrBaseReg); | |
238 | if (p.isReg() && p.getReg() != X86::ESP) { | |
239 | seekLEAFixup(p, I, MFI); | |
240 | } | |
241 | MachineOperand &q = MI->getOperand(AddrOffset + X86::AddrIndexReg); | |
242 | if (q.isReg() && q.getReg() != X86::ESP) { | |
243 | seekLEAFixup(q, I, MFI); | |
244 | } | |
245 | } | |
246 | } | |
247 | ||
248 | void FixupLEAPass::seekLEAFixup(MachineOperand &p, | |
249 | MachineBasicBlock::iterator &I, | |
250 | MachineFunction::iterator MFI) { | |
251 | MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); | |
252 | if (MBI) { | |
253 | MachineInstr *NewMI = postRAConvertToLEA(MFI, MBI); | |
254 | if (NewMI) { | |
255 | ++NumLEAs; | |
256 | DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump();); | |
257 | // now to replace with an equivalent LEA... | |
258 | DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump();); | |
259 | MFI->erase(MBI); | |
260 | MachineBasicBlock::iterator J = | |
261 | static_cast<MachineBasicBlock::iterator>(NewMI); | |
262 | processInstruction(J, MFI); | |
263 | } | |
264 | } | |
265 | } | |
266 | ||
267 | void FixupLEAPass::processInstructionForSLM(MachineBasicBlock::iterator &I, | |
268 | MachineFunction::iterator MFI) { | |
269 | MachineInstr *MI = I; | |
270 | const int opcode = MI->getOpcode(); | |
271 | if (opcode != X86::LEA16r && opcode != X86::LEA32r && opcode != X86::LEA64r && | |
272 | opcode != X86::LEA64_32r) | |
273 | return; | |
274 | if (MI->getOperand(5).getReg() != 0 || !MI->getOperand(4).isImm() || | |
275 | !TII->isSafeToClobberEFLAGS(*MFI, I)) | |
276 | return; | |
277 | const unsigned DstR = MI->getOperand(0).getReg(); | |
278 | const unsigned SrcR1 = MI->getOperand(1).getReg(); | |
279 | const unsigned SrcR2 = MI->getOperand(3).getReg(); | |
280 | if ((SrcR1 == 0 || SrcR1 != DstR) && (SrcR2 == 0 || SrcR2 != DstR)) | |
281 | return; | |
282 | if (MI->getOperand(2).getImm() > 1) | |
283 | return; | |
284 | int addrr_opcode, addri_opcode; | |
285 | switch (opcode) { | |
85aaf69f | 286 | default: llvm_unreachable("Unexpected LEA instruction"); |
1a4d82fc JJ |
287 | case X86::LEA16r: |
288 | addrr_opcode = X86::ADD16rr; | |
289 | addri_opcode = X86::ADD16ri; | |
290 | break; | |
291 | case X86::LEA32r: | |
292 | addrr_opcode = X86::ADD32rr; | |
293 | addri_opcode = X86::ADD32ri; | |
294 | break; | |
295 | case X86::LEA64_32r: | |
296 | case X86::LEA64r: | |
297 | addrr_opcode = X86::ADD64rr; | |
298 | addri_opcode = X86::ADD64ri32; | |
299 | break; | |
1a4d82fc JJ |
300 | } |
301 | DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump();); | |
302 | DEBUG(dbgs() << "FixLEA: Replaced by: ";); | |
303 | MachineInstr *NewMI = nullptr; | |
304 | const MachineOperand &Dst = MI->getOperand(0); | |
305 | // Make ADD instruction for two registers writing to LEA's destination | |
306 | if (SrcR1 != 0 && SrcR2 != 0) { | |
307 | const MachineOperand &Src1 = MI->getOperand(SrcR1 == DstR ? 1 : 3); | |
308 | const MachineOperand &Src2 = MI->getOperand(SrcR1 == DstR ? 3 : 1); | |
309 | NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addrr_opcode)) | |
310 | .addOperand(Dst) | |
311 | .addOperand(Src1) | |
312 | .addOperand(Src2); | |
313 | MFI->insert(I, NewMI); | |
314 | DEBUG(NewMI->dump();); | |
315 | } | |
316 | // Make ADD instruction for immediate | |
317 | if (MI->getOperand(4).getImm() != 0) { | |
318 | const MachineOperand &SrcR = MI->getOperand(SrcR1 == DstR ? 1 : 3); | |
319 | NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addri_opcode)) | |
320 | .addOperand(Dst) | |
321 | .addOperand(SrcR) | |
322 | .addImm(MI->getOperand(4).getImm()); | |
323 | MFI->insert(I, NewMI); | |
324 | DEBUG(NewMI->dump();); | |
325 | } | |
326 | if (NewMI) { | |
327 | MFI->erase(I); | |
328 | I = static_cast<MachineBasicBlock::iterator>(NewMI); | |
329 | } | |
330 | } | |
331 | ||
332 | bool FixupLEAPass::processBasicBlock(MachineFunction &MF, | |
333 | MachineFunction::iterator MFI) { | |
334 | ||
335 | for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) { | |
336 | if (TM->getSubtarget<X86Subtarget>().isSLM()) | |
337 | processInstructionForSLM(I, MFI); | |
338 | else | |
339 | processInstruction(I, MFI); | |
340 | } | |
341 | return false; | |
342 | } |