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