1 | //===-- X86FixupBWInsts.cpp - Fixup Byte or Word instructions -----------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | /// \file |
9 | /// This file defines the pass that looks through the machine instructions |
10 | /// late in the compilation, and finds byte or word instructions that |
11 | /// can be profitably replaced with 32 bit instructions that give equivalent |
12 | /// results for the bits of the results that are used. There are two possible |
13 | /// reasons to do this. |
14 | /// |
15 | /// One reason is to avoid false-dependences on the upper portions |
16 | /// of the registers. Only instructions that have a destination register |
17 | /// which is not in any of the source registers can be affected by this. |
18 | /// Any instruction where one of the source registers is also the destination |
19 | /// register is unaffected, because it has a true dependence on the source |
20 | /// register already. So, this consideration primarily affects load |
21 | /// instructions and register-to-register moves. It would |
22 | /// seem like cmov(s) would also be affected, but because of the way cmov is |
23 | /// really implemented by most machines as reading both the destination and |
24 | /// and source registers, and then "merging" the two based on a condition, |
25 | /// it really already should be considered as having a true dependence on the |
26 | /// destination register as well. |
27 | /// |
28 | /// The other reason to do this is for potential code size savings. Word |
29 | /// operations need an extra override byte compared to their 32 bit |
30 | /// versions. So this can convert many word operations to their larger |
31 | /// size, saving a byte in encoding. This could introduce partial register |
32 | /// dependences where none existed however. As an example take: |
33 | /// orw ax, $0x1000 |
34 | /// addw ax, $3 |
35 | /// now if this were to get transformed into |
36 | /// orw ax, $1000 |
37 | /// addl eax, $3 |
38 | /// because the addl encodes shorter than the addw, this would introduce |
39 | /// a use of a register that was only partially written earlier. On older |
40 | /// Intel processors this can be quite a performance penalty, so this should |
41 | /// probably only be done when it can be proven that a new partial dependence |
42 | /// wouldn't be created, or when your know a newer processor is being |
43 | /// targeted, or when optimizing for minimum code size. |
44 | /// |
45 | //===----------------------------------------------------------------------===// |
46 | |
47 | #include "X86.h" |
48 | #include "X86InstrInfo.h" |
49 | #include "X86Subtarget.h" |
50 | #include "llvm/ADT/Statistic.h" |
51 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
52 | #include "llvm/CodeGen/LazyMachineBlockFrequencyInfo.h" |
53 | #include "llvm/CodeGen/LiveRegUnits.h" |
54 | #include "llvm/CodeGen/MachineFunctionPass.h" |
55 | #include "llvm/CodeGen/MachineInstrBuilder.h" |
56 | #include "llvm/CodeGen/MachineLoopInfo.h" |
57 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
58 | #include "llvm/CodeGen/MachineSizeOpts.h" |
59 | #include "llvm/CodeGen/Passes.h" |
60 | #include "llvm/CodeGen/TargetInstrInfo.h" |
61 | #include "llvm/Support/Debug.h" |
62 | #include "llvm/Support/raw_ostream.h" |
63 | using namespace llvm; |
64 | |
65 | #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup" |
66 | #define FIXUPBW_NAME "x86-fixup-bw-insts" |
67 | |
68 | #define DEBUG_TYPE FIXUPBW_NAME |
69 | |
70 | // Option to allow this optimization pass to have fine-grained control. |
71 | static cl::opt<bool> |
72 | FixupBWInsts("fixup-byte-word-insts" , |
73 | cl::desc("Change byte and word instructions to larger sizes" ), |
74 | cl::init(Val: true), cl::Hidden); |
75 | |
76 | namespace { |
77 | class FixupBWInstPass : public MachineFunctionPass { |
78 | /// Loop over all of the instructions in the basic block replacing applicable |
79 | /// byte or word instructions with better alternatives. |
80 | void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB); |
81 | |
82 | /// This returns the 32 bit super reg of the original destination register of |
83 | /// the MachineInstr passed in, if that super register is dead just prior to |
84 | /// \p OrigMI. Otherwise it returns Register(). |
85 | Register getSuperRegDestIfDead(MachineInstr *OrigMI) const; |
86 | |
87 | /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit |
88 | /// register if it is safe to do so. Return the replacement instruction if |
89 | /// OK, otherwise return nullptr. |
90 | MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const; |
91 | |
92 | /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is |
93 | /// safe to do so. Return the replacement instruction if OK, otherwise return |
94 | /// nullptr. |
95 | MachineInstr *tryReplaceCopy(MachineInstr *MI) const; |
96 | |
97 | /// Change the MachineInstr \p MI into the equivalent extend to 32 bit |
98 | /// register if it is safe to do so. Return the replacement instruction if |
99 | /// OK, otherwise return nullptr. |
100 | MachineInstr *tryReplaceExtend(unsigned New32BitOpcode, |
101 | MachineInstr *MI) const; |
102 | |
103 | // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if |
104 | // possible. Return the replacement instruction if OK, return nullptr |
105 | // otherwise. |
106 | MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const; |
107 | |
108 | public: |
109 | static char ID; |
110 | |
111 | StringRef getPassName() const override { return FIXUPBW_DESC; } |
112 | |
113 | FixupBWInstPass() : MachineFunctionPass(ID) { } |
114 | |
115 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
116 | AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to |
117 | // guide some heuristics. |
118 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); |
119 | AU.addRequired<LazyMachineBlockFrequencyInfoPass>(); |
120 | MachineFunctionPass::getAnalysisUsage(AU); |
121 | } |
122 | |
123 | /// Loop over all of the basic blocks, replacing byte and word instructions by |
124 | /// equivalent 32 bit instructions where performance or code size can be |
125 | /// improved. |
126 | bool runOnMachineFunction(MachineFunction &MF) override; |
127 | |
128 | MachineFunctionProperties getRequiredProperties() const override { |
129 | return MachineFunctionProperties().set( |
130 | MachineFunctionProperties::Property::NoVRegs); |
131 | } |
132 | |
133 | private: |
134 | MachineFunction *MF = nullptr; |
135 | |
136 | /// Machine instruction info used throughout the class. |
137 | const X86InstrInfo *TII = nullptr; |
138 | |
139 | const TargetRegisterInfo *TRI = nullptr; |
140 | |
141 | /// Local member for function's OptForSize attribute. |
142 | bool OptForSize = false; |
143 | |
144 | /// Machine loop info used for guiding some heruistics. |
145 | MachineLoopInfo *MLI = nullptr; |
146 | |
147 | /// Register Liveness information after the current instruction. |
148 | LiveRegUnits LiveUnits; |
149 | |
150 | ProfileSummaryInfo *PSI = nullptr; |
151 | MachineBlockFrequencyInfo *MBFI = nullptr; |
152 | }; |
153 | char FixupBWInstPass::ID = 0; |
154 | } |
155 | |
156 | INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false) |
157 | |
158 | FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); } |
159 | |
160 | bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) { |
161 | if (!FixupBWInsts || skipFunction(F: MF.getFunction())) |
162 | return false; |
163 | |
164 | this->MF = &MF; |
165 | TII = MF.getSubtarget<X86Subtarget>().getInstrInfo(); |
166 | TRI = MF.getRegInfo().getTargetRegisterInfo(); |
167 | MLI = &getAnalysis<MachineLoopInfo>(); |
168 | PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); |
169 | MBFI = (PSI && PSI->hasProfileSummary()) ? |
170 | &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() : |
171 | nullptr; |
172 | LiveUnits.init(TII->getRegisterInfo()); |
173 | |
174 | LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n" ;); |
175 | |
176 | // Process all basic blocks. |
177 | for (auto &MBB : MF) |
178 | processBasicBlock(MF, MBB); |
179 | |
180 | LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n" ;); |
181 | |
182 | return true; |
183 | } |
184 | |
185 | /// Check if after \p OrigMI the only portion of super register |
186 | /// of the destination register of \p OrigMI that is alive is that |
187 | /// destination register. |
188 | /// |
189 | /// If so, return that super register in \p SuperDestReg. |
190 | Register FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI) const { |
191 | const X86RegisterInfo *TRI = &TII->getRegisterInfo(); |
192 | Register OrigDestReg = OrigMI->getOperand(i: 0).getReg(); |
193 | Register SuperDestReg = getX86SubSuperRegister(Reg: OrigDestReg, Size: 32); |
194 | assert(SuperDestReg.isValid() && "Invalid Operand" ); |
195 | |
196 | const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg); |
197 | |
198 | // Make sure that the sub-register that this instruction has as its |
199 | // destination is the lowest order sub-register of the super-register. |
200 | // If it isn't, then the register isn't really dead even if the |
201 | // super-register is considered dead. |
202 | if (SubRegIdx == X86::sub_8bit_hi) |
203 | return Register(); |
204 | |
205 | // Test all regunits of the super register that are not part of the |
206 | // sub register. If none of them are live then the super register is safe to |
207 | // use. |
208 | bool SuperIsLive = false; |
209 | auto Range = TRI->regunits(OrigDestReg); |
210 | MCRegUnitIterator I = Range.begin(), E = Range.end(); |
211 | for (MCRegUnit S : TRI->regunits(SuperDestReg)) { |
212 | I = std::lower_bound(I, E, S); |
213 | if ((I == E || *I > S) && LiveUnits.getBitVector().test(S)) { |
214 | SuperIsLive = true; |
215 | break; |
216 | } |
217 | } |
218 | if (!SuperIsLive) |
219 | return SuperDestReg; |
220 | |
221 | // If we get here, the super-register destination (or some part of it) is |
222 | // marked as live after the original instruction. |
223 | // |
224 | // The X86 backend does not have subregister liveness tracking enabled, |
225 | // so liveness information might be overly conservative. Specifically, the |
226 | // super register might be marked as live because it is implicitly defined |
227 | // by the instruction we are examining. |
228 | // |
229 | // However, for some specific instructions (this pass only cares about MOVs) |
230 | // we can produce more precise results by analysing that MOV's operands. |
231 | // |
232 | // Indeed, if super-register is not live before the mov it means that it |
233 | // was originally <read-undef> and so we are free to modify these |
234 | // undef upper bits. That may happen in case where the use is in another MBB |
235 | // and the vreg/physreg corresponding to the move has higher width than |
236 | // necessary (e.g. due to register coalescing with a "truncate" copy). |
237 | // So, we would like to handle patterns like this: |
238 | // |
239 | // %bb.2: derived from LLVM BB %if.then |
240 | // Live Ins: %rdi |
241 | // Predecessors according to CFG: %bb.0 |
242 | // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax |
243 | // ; No implicit %eax |
244 | // Successors according to CFG: %bb.3(?%) |
245 | // |
246 | // %bb.3: derived from LLVM BB %if.end |
247 | // Live Ins: %eax Only %ax is actually live |
248 | // Predecessors according to CFG: %bb.2 %bb.1 |
249 | // %ax = KILL %ax, implicit killed %eax |
250 | // RET 0, %ax |
251 | unsigned Opc = OrigMI->getOpcode(); (void)Opc; |
252 | // These are the opcodes currently known to work with the code below, if |
253 | // something // else will be added we need to ensure that new opcode has the |
254 | // same properties. |
255 | if (Opc != X86::MOV8rm && Opc != X86::MOV16rm && Opc != X86::MOV8rr && |
256 | Opc != X86::MOV16rr) |
257 | return Register(); |
258 | |
259 | bool IsDefined = false; |
260 | for (auto &MO: OrigMI->implicit_operands()) { |
261 | if (!MO.isReg()) |
262 | continue; |
263 | |
264 | assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!" ); |
265 | |
266 | if (MO.isDef() && TRI->isSuperRegisterEq(OrigDestReg, MO.getReg())) |
267 | IsDefined = true; |
268 | |
269 | // If MO is a use of any part of the destination register but is not equal |
270 | // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg. |
271 | // For example, if OrigDestReg is %al then an implicit use of %ah, %ax, |
272 | // %eax, or %rax will prevent us from using the %eax register. |
273 | if (MO.isUse() && !TRI->isSubRegisterEq(OrigDestReg, MO.getReg()) && |
274 | TRI->regsOverlap(SuperDestReg, MO.getReg())) |
275 | return Register(); |
276 | } |
277 | // Reg is not Imp-def'ed -> it's live both before/after the instruction. |
278 | if (!IsDefined) |
279 | return Register(); |
280 | |
281 | // Otherwise, the Reg is not live before the MI and the MOV can't |
282 | // make it really live, so it's in fact dead even after the MI. |
283 | return SuperDestReg; |
284 | } |
285 | |
286 | MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode, |
287 | MachineInstr *MI) const { |
288 | // We are going to try to rewrite this load to a larger zero-extending |
289 | // load. This is safe if all portions of the 32 bit super-register |
290 | // of the original destination register, except for the original destination |
291 | // register are dead. getSuperRegDestIfDead checks that. |
292 | Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI); |
293 | if (!NewDestReg) |
294 | return nullptr; |
295 | |
296 | // Safe to change the instruction. |
297 | MachineInstrBuilder MIB = |
298 | BuildMI(*MF, MIMetadata(*MI), TII->get(New32BitOpcode), NewDestReg); |
299 | |
300 | unsigned NumArgs = MI->getNumOperands(); |
301 | for (unsigned i = 1; i < NumArgs; ++i) |
302 | MIB.add(MO: MI->getOperand(i)); |
303 | |
304 | MIB.setMemRefs(MI->memoperands()); |
305 | |
306 | // If it was debug tracked, record a substitution. |
307 | if (unsigned OldInstrNum = MI->peekDebugInstrNum()) { |
308 | unsigned Subreg = TRI->getSubRegIndex(RegNo: MIB->getOperand(i: 0).getReg(), |
309 | SubRegNo: MI->getOperand(i: 0).getReg()); |
310 | unsigned NewInstrNum = MIB->getDebugInstrNum(MF&: *MF); |
311 | MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, SubReg: Subreg); |
312 | } |
313 | |
314 | return MIB; |
315 | } |
316 | |
317 | MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const { |
318 | assert(MI->getNumExplicitOperands() == 2); |
319 | auto &OldDest = MI->getOperand(i: 0); |
320 | auto &OldSrc = MI->getOperand(i: 1); |
321 | |
322 | Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI); |
323 | if (!NewDestReg) |
324 | return nullptr; |
325 | |
326 | Register NewSrcReg = getX86SubSuperRegister(Reg: OldSrc.getReg(), Size: 32); |
327 | assert(NewSrcReg.isValid() && "Invalid Operand" ); |
328 | |
329 | // This is only correct if we access the same subregister index: otherwise, |
330 | // we could try to replace "movb %ah, %al" with "movl %eax, %eax". |
331 | const X86RegisterInfo *TRI = &TII->getRegisterInfo(); |
332 | if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) != |
333 | TRI->getSubRegIndex(NewDestReg, OldDest.getReg())) |
334 | return nullptr; |
335 | |
336 | // Safe to change the instruction. |
337 | // Don't set src flags, as we don't know if we're also killing the superreg. |
338 | // However, the superregister might not be defined; make it explicit that |
339 | // we don't care about the higher bits by reading it as Undef, and adding |
340 | // an imp-use on the original subregister. |
341 | MachineInstrBuilder MIB = |
342 | BuildMI(*MF, MIMetadata(*MI), TII->get(X86::MOV32rr), NewDestReg) |
343 | .addReg(NewSrcReg, RegState::Undef) |
344 | .addReg(OldSrc.getReg(), RegState::Implicit); |
345 | |
346 | // Drop imp-defs/uses that would be redundant with the new def/use. |
347 | for (auto &Op : MI->implicit_operands()) |
348 | if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg)) |
349 | MIB.add(MO: Op); |
350 | |
351 | return MIB; |
352 | } |
353 | |
354 | MachineInstr *FixupBWInstPass::tryReplaceExtend(unsigned New32BitOpcode, |
355 | MachineInstr *MI) const { |
356 | Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI); |
357 | if (!NewDestReg) |
358 | return nullptr; |
359 | |
360 | // Don't interfere with formation of CBW instructions which should be a |
361 | // shorter encoding than even the MOVSX32rr8. It's also immune to partial |
362 | // merge issues on Intel CPUs. |
363 | if (MI->getOpcode() == X86::MOVSX16rr8 && |
364 | MI->getOperand(i: 0).getReg() == X86::AX && |
365 | MI->getOperand(i: 1).getReg() == X86::AL) |
366 | return nullptr; |
367 | |
368 | // Safe to change the instruction. |
369 | MachineInstrBuilder MIB = |
370 | BuildMI(*MF, MIMetadata(*MI), TII->get(New32BitOpcode), NewDestReg); |
371 | |
372 | unsigned NumArgs = MI->getNumOperands(); |
373 | for (unsigned i = 1; i < NumArgs; ++i) |
374 | MIB.add(MO: MI->getOperand(i)); |
375 | |
376 | MIB.setMemRefs(MI->memoperands()); |
377 | |
378 | if (unsigned OldInstrNum = MI->peekDebugInstrNum()) { |
379 | unsigned Subreg = TRI->getSubRegIndex(RegNo: MIB->getOperand(i: 0).getReg(), |
380 | SubRegNo: MI->getOperand(i: 0).getReg()); |
381 | unsigned NewInstrNum = MIB->getDebugInstrNum(MF&: *MF); |
382 | MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, SubReg: Subreg); |
383 | } |
384 | |
385 | return MIB; |
386 | } |
387 | |
388 | MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI, |
389 | MachineBasicBlock &MBB) const { |
390 | // See if this is an instruction of the type we are currently looking for. |
391 | switch (MI->getOpcode()) { |
392 | |
393 | case X86::MOV8rm: |
394 | // Replace 8-bit loads with the zero-extending version if not optimizing |
395 | // for size. The extending op is cheaper across a wide range of uarch and |
396 | // it avoids a potentially expensive partial register stall. It takes an |
397 | // extra byte to encode, however, so don't do this when optimizing for size. |
398 | if (!OptForSize) |
399 | return tryReplaceLoad(X86::New32BitOpcode: MOVZX32rm8, MI); |
400 | break; |
401 | |
402 | case X86::MOV16rm: |
403 | // Always try to replace 16 bit load with 32 bit zero extending. |
404 | // Code size is the same, and there is sometimes a perf advantage |
405 | // from eliminating a false dependence on the upper portion of |
406 | // the register. |
407 | return tryReplaceLoad(X86::New32BitOpcode: MOVZX32rm16, MI); |
408 | |
409 | case X86::MOV8rr: |
410 | case X86::MOV16rr: |
411 | // Always try to replace 8/16 bit copies with a 32 bit copy. |
412 | // Code size is either less (16) or equal (8), and there is sometimes a |
413 | // perf advantage from eliminating a false dependence on the upper portion |
414 | // of the register. |
415 | return tryReplaceCopy(MI); |
416 | |
417 | case X86::MOVSX16rr8: |
418 | return tryReplaceExtend(X86::New32BitOpcode: MOVSX32rr8, MI); |
419 | case X86::MOVSX16rm8: |
420 | return tryReplaceExtend(X86::New32BitOpcode: MOVSX32rm8, MI); |
421 | case X86::MOVZX16rr8: |
422 | return tryReplaceExtend(X86::New32BitOpcode: MOVZX32rr8, MI); |
423 | case X86::MOVZX16rm8: |
424 | return tryReplaceExtend(X86::New32BitOpcode: MOVZX32rm8, MI); |
425 | |
426 | default: |
427 | // nothing to do here. |
428 | break; |
429 | } |
430 | |
431 | return nullptr; |
432 | } |
433 | |
434 | void FixupBWInstPass::processBasicBlock(MachineFunction &MF, |
435 | MachineBasicBlock &MBB) { |
436 | |
437 | // This algorithm doesn't delete the instructions it is replacing |
438 | // right away. By leaving the existing instructions in place, the |
439 | // register liveness information doesn't change, and this makes the |
440 | // analysis that goes on be better than if the replaced instructions |
441 | // were immediately removed. |
442 | // |
443 | // This algorithm always creates a replacement instruction |
444 | // and notes that and the original in a data structure, until the |
445 | // whole BB has been analyzed. This keeps the replacement instructions |
446 | // from making it seem as if the larger register might be live. |
447 | SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements; |
448 | |
449 | // Start computing liveness for this block. We iterate from the end to be able |
450 | // to update this for each instruction. |
451 | LiveUnits.clear(); |
452 | // We run after PEI, so we need to AddPristinesAndCSRs. |
453 | LiveUnits.addLiveOuts(MBB); |
454 | |
455 | OptForSize = MF.getFunction().hasOptSize() || |
456 | llvm::shouldOptimizeForSize(MBB: &MBB, PSI, MBFI); |
457 | |
458 | for (MachineInstr &MI : llvm::reverse(C&: MBB)) { |
459 | if (MachineInstr *NewMI = tryReplaceInstr(MI: &MI, MBB)) |
460 | MIReplacements.push_back(Elt: std::make_pair(x: &MI, y&: NewMI)); |
461 | |
462 | // We're done with this instruction, update liveness for the next one. |
463 | LiveUnits.stepBackward(MI); |
464 | } |
465 | |
466 | while (!MIReplacements.empty()) { |
467 | MachineInstr *MI = MIReplacements.back().first; |
468 | MachineInstr *NewMI = MIReplacements.back().second; |
469 | MIReplacements.pop_back(); |
470 | MBB.insert(I: MI, MI: NewMI); |
471 | MBB.erase(I: MI); |
472 | } |
473 | } |
474 | |