1 //===-- X86FixupBWInsts.cpp - Fixup Byte or Word instructions -----------===//
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
7 //===----------------------------------------------------------------------===//
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.
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.
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:
35 /// now if this were to get transformed into
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.
45 //===----------------------------------------------------------------------===//
48 #include "X86InstrInfo.h"
49 #include "X86Subtarget.h"
50 #include "llvm/ADT/Statistic.h"
51 #include "llvm/CodeGen/LivePhysRegs.h"
52 #include "llvm/CodeGen/MachineFunctionPass.h"
53 #include "llvm/CodeGen/MachineInstrBuilder.h"
54 #include "llvm/CodeGen/MachineLoopInfo.h"
55 #include "llvm/CodeGen/MachineRegisterInfo.h"
56 #include "llvm/CodeGen/Passes.h"
57 #include "llvm/CodeGen/TargetInstrInfo.h"
58 #include "llvm/Support/Debug.h"
59 #include "llvm/Support/raw_ostream.h"
62 #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup"
63 #define FIXUPBW_NAME "x86-fixup-bw-insts"
65 #define DEBUG_TYPE FIXUPBW_NAME
67 // Option to allow this optimization pass to have fine-grained control.
69 FixupBWInsts("fixup-byte-word-insts",
70 cl::desc("Change byte and word instructions to larger sizes"),
71 cl::init(true), cl::Hidden
);
74 class FixupBWInstPass
: public MachineFunctionPass
{
75 /// Loop over all of the instructions in the basic block replacing applicable
76 /// byte or word instructions with better alternatives.
77 void processBasicBlock(MachineFunction
&MF
, MachineBasicBlock
&MBB
);
79 /// This sets the \p SuperDestReg to the 32 bit super reg of the original
80 /// destination register of the MachineInstr passed in. It returns true if
81 /// that super register is dead just prior to \p OrigMI, and false if not.
82 bool getSuperRegDestIfDead(MachineInstr
*OrigMI
,
83 unsigned &SuperDestReg
) const;
85 /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit
86 /// register if it is safe to do so. Return the replacement instruction if
87 /// OK, otherwise return nullptr.
88 MachineInstr
*tryReplaceLoad(unsigned New32BitOpcode
, MachineInstr
*MI
) const;
90 /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is
91 /// safe to do so. Return the replacement instruction if OK, otherwise return
93 MachineInstr
*tryReplaceCopy(MachineInstr
*MI
) const;
95 // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if
96 // possible. Return the replacement instruction if OK, return nullptr
98 MachineInstr
*tryReplaceInstr(MachineInstr
*MI
, MachineBasicBlock
&MBB
) const;
103 StringRef
getPassName() const override
{ return FIXUPBW_DESC
; }
105 FixupBWInstPass() : MachineFunctionPass(ID
) { }
107 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
108 AU
.addRequired
<MachineLoopInfo
>(); // Machine loop info is used to
109 // guide some heuristics.
110 MachineFunctionPass::getAnalysisUsage(AU
);
113 /// Loop over all of the basic blocks, replacing byte and word instructions by
114 /// equivalent 32 bit instructions where performance or code size can be
116 bool runOnMachineFunction(MachineFunction
&MF
) override
;
118 MachineFunctionProperties
getRequiredProperties() const override
{
119 return MachineFunctionProperties().set(
120 MachineFunctionProperties::Property::NoVRegs
);
126 /// Machine instruction info used throughout the class.
127 const X86InstrInfo
*TII
;
129 /// Local member for function's OptForSize attribute.
132 /// Machine loop info used for guiding some heruistics.
133 MachineLoopInfo
*MLI
;
135 /// Register Liveness information after the current instruction.
136 LivePhysRegs LiveRegs
;
138 char FixupBWInstPass::ID
= 0;
141 INITIALIZE_PASS(FixupBWInstPass
, FIXUPBW_NAME
, FIXUPBW_DESC
, false, false)
143 FunctionPass
*llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
145 bool FixupBWInstPass::runOnMachineFunction(MachineFunction
&MF
) {
146 if (!FixupBWInsts
|| skipFunction(MF
.getFunction()))
150 TII
= MF
.getSubtarget
<X86Subtarget
>().getInstrInfo();
151 OptForSize
= MF
.getFunction().hasOptSize();
152 MLI
= &getAnalysis
<MachineLoopInfo
>();
153 LiveRegs
.init(TII
->getRegisterInfo());
155 LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
157 // Process all basic blocks.
159 processBasicBlock(MF
, MBB
);
161 LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";);
166 /// Check if after \p OrigMI the only portion of super register
167 /// of the destination register of \p OrigMI that is alive is that
168 /// destination register.
170 /// If so, return that super register in \p SuperDestReg.
171 bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr
*OrigMI
,
172 unsigned &SuperDestReg
) const {
173 auto *TRI
= &TII
->getRegisterInfo();
175 unsigned OrigDestReg
= OrigMI
->getOperand(0).getReg();
176 SuperDestReg
= getX86SubSuperRegister(OrigDestReg
, 32);
178 const auto SubRegIdx
= TRI
->getSubRegIndex(SuperDestReg
, OrigDestReg
);
180 // Make sure that the sub-register that this instruction has as its
181 // destination is the lowest order sub-register of the super-register.
182 // If it isn't, then the register isn't really dead even if the
183 // super-register is considered dead.
184 if (SubRegIdx
== X86::sub_8bit_hi
)
187 // If neither the destination-super register nor any applicable subregisters
188 // are live after this instruction, then the super register is safe to use.
189 if (!LiveRegs
.contains(SuperDestReg
)) {
190 // If the original destination register was not the low 8-bit subregister
191 // then the super register check is sufficient.
192 if (SubRegIdx
!= X86::sub_8bit
)
194 // If the original destination register was the low 8-bit subregister and
195 // we also need to check the 16-bit subregister and the high 8-bit
197 if (!LiveRegs
.contains(getX86SubSuperRegister(OrigDestReg
, 16)) &&
198 !LiveRegs
.contains(getX86SubSuperRegister(SuperDestReg
, 8,
201 // Otherwise, we have a little more checking to do.
204 // If we get here, the super-register destination (or some part of it) is
205 // marked as live after the original instruction.
207 // The X86 backend does not have subregister liveness tracking enabled,
208 // so liveness information might be overly conservative. Specifically, the
209 // super register might be marked as live because it is implicitly defined
210 // by the instruction we are examining.
212 // However, for some specific instructions (this pass only cares about MOVs)
213 // we can produce more precise results by analysing that MOV's operands.
215 // Indeed, if super-register is not live before the mov it means that it
216 // was originally <read-undef> and so we are free to modify these
217 // undef upper bits. That may happen in case where the use is in another MBB
218 // and the vreg/physreg corresponding to the move has higher width than
219 // necessary (e.g. due to register coalescing with a "truncate" copy).
220 // So, we would like to handle patterns like this:
222 // %bb.2: derived from LLVM BB %if.then
224 // Predecessors according to CFG: %bb.0
225 // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax
226 // ; No implicit %eax
227 // Successors according to CFG: %bb.3(?%)
229 // %bb.3: derived from LLVM BB %if.end
230 // Live Ins: %eax Only %ax is actually live
231 // Predecessors according to CFG: %bb.2 %bb.1
232 // %ax = KILL %ax, implicit killed %eax
234 unsigned Opc
= OrigMI
->getOpcode(); (void)Opc
;
235 // These are the opcodes currently handled by the pass, if something
236 // else will be added we need to ensure that new opcode has the same
238 assert((Opc
== X86::MOV8rm
|| Opc
== X86::MOV16rm
|| Opc
== X86::MOV8rr
||
239 Opc
== X86::MOV16rr
) &&
240 "Unexpected opcode.");
242 bool IsDefined
= false;
243 for (auto &MO
: OrigMI
->implicit_operands()) {
247 assert((MO
.isDef() || MO
.isUse()) && "Expected Def or Use only!");
249 if (MO
.isDef() && TRI
->isSuperRegisterEq(OrigDestReg
, MO
.getReg()))
252 // If MO is a use of any part of the destination register but is not equal
253 // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.
254 // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,
255 // %eax, or %rax will prevent us from using the %eax register.
256 if (MO
.isUse() && !TRI
->isSubRegisterEq(OrigDestReg
, MO
.getReg()) &&
257 TRI
->regsOverlap(SuperDestReg
, MO
.getReg()))
260 // Reg is not Imp-def'ed -> it's live both before/after the instruction.
264 // Otherwise, the Reg is not live before the MI and the MOV can't
265 // make it really live, so it's in fact dead even after the MI.
269 MachineInstr
*FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode
,
270 MachineInstr
*MI
) const {
273 // We are going to try to rewrite this load to a larger zero-extending
274 // load. This is safe if all portions of the 32 bit super-register
275 // of the original destination register, except for the original destination
276 // register are dead. getSuperRegDestIfDead checks that.
277 if (!getSuperRegDestIfDead(MI
, NewDestReg
))
280 // Safe to change the instruction.
281 MachineInstrBuilder MIB
=
282 BuildMI(*MF
, MI
->getDebugLoc(), TII
->get(New32BitOpcode
), NewDestReg
);
284 unsigned NumArgs
= MI
->getNumOperands();
285 for (unsigned i
= 1; i
< NumArgs
; ++i
)
286 MIB
.add(MI
->getOperand(i
));
288 MIB
.setMemRefs(MI
->memoperands());
293 MachineInstr
*FixupBWInstPass::tryReplaceCopy(MachineInstr
*MI
) const {
294 assert(MI
->getNumExplicitOperands() == 2);
295 auto &OldDest
= MI
->getOperand(0);
296 auto &OldSrc
= MI
->getOperand(1);
299 if (!getSuperRegDestIfDead(MI
, NewDestReg
))
302 unsigned NewSrcReg
= getX86SubSuperRegister(OldSrc
.getReg(), 32);
304 // This is only correct if we access the same subregister index: otherwise,
305 // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
306 auto *TRI
= &TII
->getRegisterInfo();
307 if (TRI
->getSubRegIndex(NewSrcReg
, OldSrc
.getReg()) !=
308 TRI
->getSubRegIndex(NewDestReg
, OldDest
.getReg()))
311 // Safe to change the instruction.
312 // Don't set src flags, as we don't know if we're also killing the superreg.
313 // However, the superregister might not be defined; make it explicit that
314 // we don't care about the higher bits by reading it as Undef, and adding
315 // an imp-use on the original subregister.
316 MachineInstrBuilder MIB
=
317 BuildMI(*MF
, MI
->getDebugLoc(), TII
->get(X86::MOV32rr
), NewDestReg
)
318 .addReg(NewSrcReg
, RegState::Undef
)
319 .addReg(OldSrc
.getReg(), RegState::Implicit
);
321 // Drop imp-defs/uses that would be redundant with the new def/use.
322 for (auto &Op
: MI
->implicit_operands())
323 if (Op
.getReg() != (Op
.isDef() ? NewDestReg
: NewSrcReg
))
329 MachineInstr
*FixupBWInstPass::tryReplaceInstr(MachineInstr
*MI
,
330 MachineBasicBlock
&MBB
) const {
331 // See if this is an instruction of the type we are currently looking for.
332 switch (MI
->getOpcode()) {
335 // Only replace 8 bit loads with the zero extending versions if
336 // in an inner most loop and not optimizing for size. This takes
337 // an extra byte to encode, and provides limited performance upside.
338 if (MachineLoop
*ML
= MLI
->getLoopFor(&MBB
))
339 if (ML
->begin() == ML
->end() && !OptForSize
)
340 return tryReplaceLoad(X86::MOVZX32rm8
, MI
);
344 // Always try to replace 16 bit load with 32 bit zero extending.
345 // Code size is the same, and there is sometimes a perf advantage
346 // from eliminating a false dependence on the upper portion of
348 return tryReplaceLoad(X86::MOVZX32rm16
, MI
);
352 // Always try to replace 8/16 bit copies with a 32 bit copy.
353 // Code size is either less (16) or equal (8), and there is sometimes a
354 // perf advantage from eliminating a false dependence on the upper portion
356 return tryReplaceCopy(MI
);
359 // nothing to do here.
366 void FixupBWInstPass::processBasicBlock(MachineFunction
&MF
,
367 MachineBasicBlock
&MBB
) {
369 // This algorithm doesn't delete the instructions it is replacing
370 // right away. By leaving the existing instructions in place, the
371 // register liveness information doesn't change, and this makes the
372 // analysis that goes on be better than if the replaced instructions
373 // were immediately removed.
375 // This algorithm always creates a replacement instruction
376 // and notes that and the original in a data structure, until the
377 // whole BB has been analyzed. This keeps the replacement instructions
378 // from making it seem as if the larger register might be live.
379 SmallVector
<std::pair
<MachineInstr
*, MachineInstr
*>, 8> MIReplacements
;
381 // Start computing liveness for this block. We iterate from the end to be able
382 // to update this for each instruction.
384 // We run after PEI, so we need to AddPristinesAndCSRs.
385 LiveRegs
.addLiveOuts(MBB
);
387 for (auto I
= MBB
.rbegin(); I
!= MBB
.rend(); ++I
) {
388 MachineInstr
*MI
= &*I
;
390 if (MachineInstr
*NewMI
= tryReplaceInstr(MI
, MBB
))
391 MIReplacements
.push_back(std::make_pair(MI
, NewMI
));
393 // We're done with this instruction, update liveness for the next one.
394 LiveRegs
.stepBackward(*MI
);
397 while (!MIReplacements
.empty()) {
398 MachineInstr
*MI
= MIReplacements
.back().first
;
399 MachineInstr
*NewMI
= MIReplacements
.back().second
;
400 MIReplacements
.pop_back();
401 MBB
.insert(MI
, NewMI
);