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/MachineBlockFrequencyInfo.h"
55#include "llvm/CodeGen/MachineFunctionPass.h"
56#include "llvm/CodeGen/MachineInstrBuilder.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"
63using 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.
71static 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
76namespace {
77class X86FixupBWInstImpl {
78public:
79 X86FixupBWInstImpl(ProfileSummaryInfo *PSI, MachineBlockFrequencyInfo *MBFI)
80 : PSI(PSI), MBFI(MBFI) {}
81 bool runOnMachineFunction(MachineFunction &MF);
82
83private:
84 /// Loop over all of the instructions in the basic block replacing applicable
85 /// byte or word instructions with better alternatives.
86 void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
87
88 /// This returns the 32 bit super reg of the original destination register of
89 /// the MachineInstr passed in, if that super register is dead just prior to
90 /// \p OrigMI. Otherwise it returns Register().
91 Register getSuperRegDestIfDead(MachineInstr *OrigMI) const;
92
93 /// Change the MachineInstr \p MI into the equivalent extending load to 32 bit
94 /// register if it is safe to do so. Return the replacement instruction if
95 /// OK, otherwise return nullptr.
96 MachineInstr *tryReplaceLoad(unsigned New32BitOpcode, MachineInstr *MI) const;
97
98 /// Change the MachineInstr \p MI into the equivalent 32-bit copy if it is
99 /// safe to do so. Return the replacement instruction if OK, otherwise return
100 /// nullptr.
101 MachineInstr *tryReplaceCopy(MachineInstr *MI) const;
102
103 /// Change the MachineInstr \p MI into the equivalent extend to 32 bit
104 /// register if it is safe to do so. Return the replacement instruction if
105 /// OK, otherwise return nullptr.
106 MachineInstr *tryReplaceExtend(unsigned New32BitOpcode,
107 MachineInstr *MI) const;
108
109 // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if
110 // possible. Return the replacement instruction if OK, return nullptr
111 // otherwise.
112 MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const;
113
114 MachineFunction *MF = nullptr;
115
116 /// Machine instruction info used throughout the class.
117 const X86InstrInfo *TII = nullptr;
118
119 const TargetRegisterInfo *TRI = nullptr;
120
121 /// Local member for function's OptForSize attribute.
122 bool OptForSize = false;
123
124 /// Register Liveness information after the current instruction.
125 LiveRegUnits LiveUnits;
126
127 ProfileSummaryInfo *PSI = nullptr;
128 MachineBlockFrequencyInfo *MBFI = nullptr;
129};
130
131class X86FixupBWInstLegacy : public MachineFunctionPass {
132public:
133 static char ID;
134
135 StringRef getPassName() const override { return FIXUPBW_DESC; }
136
137 X86FixupBWInstLegacy() : MachineFunctionPass(ID) {}
138
139 void getAnalysisUsage(AnalysisUsage &AU) const override {
140 AU.addRequired<ProfileSummaryInfoWrapperPass>();
141 AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
142 MachineFunctionPass::getAnalysisUsage(AU);
143 }
144
145 /// Loop over all of the basic blocks, replacing byte and word instructions by
146 /// equivalent 32 bit instructions where performance or code size can be
147 /// improved.
148 bool runOnMachineFunction(MachineFunction &MF) override;
149
150 MachineFunctionProperties getRequiredProperties() const override {
151 return MachineFunctionProperties().setNoVRegs();
152 }
153};
154
155char X86FixupBWInstLegacy::ID = 0;
156
157} // namespace
158
159INITIALIZE_PASS(X86FixupBWInstLegacy, FIXUPBW_NAME, FIXUPBW_DESC, false, false)
160
161FunctionPass *llvm::createX86FixupBWInstsLegacyPass() {
162 return new X86FixupBWInstLegacy();
163}
164
165bool X86FixupBWInstImpl::runOnMachineFunction(MachineFunction &MF) {
166 if (!FixupBWInsts)
167 return false;
168
169 this->MF = &MF;
170 TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
171 TRI = MF.getRegInfo().getTargetRegisterInfo();
172 LiveUnits.init(TRI: 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.
190Register X86FixupBWInstImpl::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(RegNo: SuperDestReg, SubRegNo: 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(Reg: OrigDestReg);
210 MCRegUnitIterator I = Range.begin(), E = Range.end();
211 for (MCRegUnit S : TRI->regunits(Reg: SuperDestReg)) {
212 I = std::lower_bound(first: I, last: E, val: S);
213 if ((I == E || *I > S) &&
214 LiveUnits.getBitVector().test(Idx: static_cast<unsigned>(S))) {
215 SuperIsLive = true;
216 break;
217 }
218 }
219 if (!SuperIsLive)
220 return SuperDestReg;
221
222 // If we get here, the super-register destination (or some part of it) is
223 // marked as live after the original instruction.
224 //
225 // The X86 backend does not have subregister liveness tracking enabled,
226 // so liveness information might be overly conservative. Specifically, the
227 // super register might be marked as live because it is implicitly defined
228 // by the instruction we are examining.
229 //
230 // However, for some specific instructions (this pass only cares about MOVs)
231 // we can produce more precise results by analysing that MOV's operands.
232 //
233 // Indeed, if super-register is not live before the mov it means that it
234 // was originally <read-undef> and so we are free to modify these
235 // undef upper bits. That may happen in case where the use is in another MBB
236 // and the vreg/physreg corresponding to the move has higher width than
237 // necessary (e.g. due to register coalescing with a "truncate" copy).
238 // So, we would like to handle patterns like this:
239 //
240 // %bb.2: derived from LLVM BB %if.then
241 // Live Ins: %rdi
242 // Predecessors according to CFG: %bb.0
243 // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax
244 // ; No implicit %eax
245 // Successors according to CFG: %bb.3(?%)
246 //
247 // %bb.3: derived from LLVM BB %if.end
248 // Live Ins: %eax Only %ax is actually live
249 // Predecessors according to CFG: %bb.2 %bb.1
250 // %ax = KILL %ax, implicit killed %eax
251 // RET 0, %ax
252 unsigned Opc = OrigMI->getOpcode();
253 // These are the opcodes currently known to work with the code below, if
254 // something // else will be added we need to ensure that new opcode has the
255 // same properties.
256 if (Opc != X86::MOV8rm && Opc != X86::MOV16rm && Opc != X86::MOV8rr &&
257 Opc != X86::MOV16rr)
258 return Register();
259
260 bool IsDefined = false;
261 for (auto &MO: OrigMI->implicit_operands()) {
262 if (!MO.isReg())
263 continue;
264
265 if (MO.isDef() && TRI->isSuperRegisterEq(RegA: OrigDestReg, RegB: MO.getReg()))
266 IsDefined = true;
267
268 // If MO is a use of any part of the destination register but is not equal
269 // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.
270 // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,
271 // %eax, or %rax will prevent us from using the %eax register.
272 if (MO.isUse() && !TRI->isSubRegisterEq(RegA: OrigDestReg, RegB: MO.getReg()) &&
273 TRI->regsOverlap(RegA: SuperDestReg, RegB: MO.getReg()))
274 return Register();
275 }
276 // Reg is not Imp-def'ed -> it's live both before/after the instruction.
277 if (!IsDefined)
278 return Register();
279
280 // Otherwise, the Reg is not live before the MI and the MOV can't
281 // make it really live, so it's in fact dead even after the MI.
282 return SuperDestReg;
283}
284
285MachineInstr *X86FixupBWInstImpl::tryReplaceLoad(unsigned New32BitOpcode,
286 MachineInstr *MI) const {
287 // We are going to try to rewrite this load to a larger zero-extending
288 // load. This is safe if all portions of the 32 bit super-register
289 // of the original destination register, except for the original destination
290 // register are dead. getSuperRegDestIfDead checks that.
291 Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI);
292 if (!NewDestReg)
293 return nullptr;
294
295 // Safe to change the instruction.
296 MachineInstrBuilder MIB =
297 BuildMI(MF&: *MF, MIMD: MIMetadata(*MI), MCID: TII->get(Opcode: New32BitOpcode), DestReg: NewDestReg);
298
299 unsigned NumArgs = MI->getNumOperands();
300 for (unsigned i = 1; i < NumArgs; ++i)
301 MIB.add(MO: MI->getOperand(i));
302
303 MIB.setMemRefs(MI->memoperands());
304
305 // If it was debug tracked, record a substitution.
306 if (unsigned OldInstrNum = MI->peekDebugInstrNum()) {
307 unsigned Subreg = TRI->getSubRegIndex(RegNo: MIB->getOperand(i: 0).getReg(),
308 SubRegNo: MI->getOperand(i: 0).getReg());
309 unsigned NewInstrNum = MIB->getDebugInstrNum(MF&: *MF);
310 MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, SubReg: Subreg);
311 }
312
313 return MIB;
314}
315
316MachineInstr *X86FixupBWInstImpl::tryReplaceCopy(MachineInstr *MI) const {
317 assert(MI->getNumExplicitOperands() == 2);
318 auto &OldDest = MI->getOperand(i: 0);
319 auto &OldSrc = MI->getOperand(i: 1);
320
321 Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI);
322 if (!NewDestReg)
323 return nullptr;
324
325 Register NewSrcReg = getX86SubSuperRegister(Reg: OldSrc.getReg(), Size: 32);
326 assert(NewSrcReg.isValid() && "Invalid Operand");
327
328 // This is only correct if we access the same subregister index: otherwise,
329 // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
330 const X86RegisterInfo *TRI = &TII->getRegisterInfo();
331 if (TRI->getSubRegIndex(RegNo: NewSrcReg, SubRegNo: OldSrc.getReg()) !=
332 TRI->getSubRegIndex(RegNo: NewDestReg, SubRegNo: OldDest.getReg()))
333 return nullptr;
334
335 // Safe to change the instruction.
336 // Don't set src flags, as we don't know if we're also killing the superreg.
337 // However, the superregister might not be defined; make it explicit that
338 // we don't care about the higher bits by reading it as Undef, and adding
339 // an imp-use on the original subregister.
340 MachineInstrBuilder MIB =
341 BuildMI(MF&: *MF, MIMD: MIMetadata(*MI), MCID: TII->get(Opcode: X86::MOV32rr), DestReg: NewDestReg)
342 .addReg(RegNo: NewSrcReg, Flags: RegState::Undef)
343 .addReg(RegNo: OldSrc.getReg(), Flags: RegState::Implicit);
344
345 // Drop imp-defs/uses that would be redundant with the new def/use.
346 for (auto &Op : MI->implicit_operands())
347 if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg))
348 MIB.add(MO: Op);
349
350 return MIB;
351}
352
353MachineInstr *X86FixupBWInstImpl::tryReplaceExtend(unsigned New32BitOpcode,
354 MachineInstr *MI) const {
355 Register NewDestReg = getSuperRegDestIfDead(OrigMI: MI);
356 if (!NewDestReg)
357 return nullptr;
358
359 // Don't interfere with formation of CBW instructions which should be a
360 // shorter encoding than even the MOVSX32rr8. It's also immune to partial
361 // merge issues on Intel CPUs.
362 if (MI->getOpcode() == X86::MOVSX16rr8 &&
363 MI->getOperand(i: 0).getReg() == X86::AX &&
364 MI->getOperand(i: 1).getReg() == X86::AL)
365 return nullptr;
366
367 // Safe to change the instruction.
368 MachineInstrBuilder MIB =
369 BuildMI(MF&: *MF, MIMD: MIMetadata(*MI), MCID: TII->get(Opcode: New32BitOpcode), DestReg: NewDestReg);
370
371 unsigned NumArgs = MI->getNumOperands();
372 for (unsigned i = 1; i < NumArgs; ++i)
373 MIB.add(MO: MI->getOperand(i));
374
375 MIB.setMemRefs(MI->memoperands());
376
377 if (unsigned OldInstrNum = MI->peekDebugInstrNum()) {
378 unsigned Subreg = TRI->getSubRegIndex(RegNo: MIB->getOperand(i: 0).getReg(),
379 SubRegNo: MI->getOperand(i: 0).getReg());
380 unsigned NewInstrNum = MIB->getDebugInstrNum(MF&: *MF);
381 MF->makeDebugValueSubstitution({OldInstrNum, 0}, {NewInstrNum, 0}, SubReg: Subreg);
382 }
383
384 return MIB;
385}
386
387MachineInstr *
388X86FixupBWInstImpl::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(New32BitOpcode: X86::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(New32BitOpcode: X86::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(New32BitOpcode: X86::MOVSX32rr8, MI);
419 case X86::MOVSX16rm8:
420 return tryReplaceExtend(New32BitOpcode: X86::MOVSX32rm8, MI);
421 case X86::MOVZX16rr8:
422 return tryReplaceExtend(New32BitOpcode: X86::MOVZX32rr8, MI);
423 case X86::MOVZX16rm8:
424 return tryReplaceExtend(New32BitOpcode: X86::MOVZX32rm8, MI);
425
426 default:
427 // nothing to do here.
428 break;
429 }
430
431 return nullptr;
432}
433
434void X86FixupBWInstImpl::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 = llvm::shouldOptimizeForSize(MBB: &MBB, PSI, MBFI);
456
457 for (MachineInstr &MI : llvm::reverse(C&: MBB)) {
458 if (MachineInstr *NewMI = tryReplaceInstr(MI: &MI, MBB))
459 MIReplacements.push_back(Elt: std::make_pair(x: &MI, y&: NewMI));
460
461 // We're done with this instruction, update liveness for the next one.
462 LiveUnits.stepBackward(MI);
463 }
464
465 while (!MIReplacements.empty()) {
466 MachineInstr *MI = MIReplacements.back().first;
467 MachineInstr *NewMI = MIReplacements.back().second;
468 MIReplacements.pop_back();
469 MBB.insert(I: MI, MI: NewMI);
470 MBB.erase(I: MI);
471 }
472}
473
474bool X86FixupBWInstLegacy::runOnMachineFunction(MachineFunction &MF) {
475 if (skipFunction(F: MF.getFunction()))
476 return false;
477 ProfileSummaryInfo *PSI =
478 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
479 MachineBlockFrequencyInfo *MBFI =
480 (PSI && PSI->hasProfileSummary())
481 ? &getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI()
482 : nullptr;
483 X86FixupBWInstImpl Impl(PSI, MBFI);
484 return Impl.runOnMachineFunction(MF);
485}
486
487PreservedAnalyses
488X86FixupBWInstsPass::run(MachineFunction &MF,
489 MachineFunctionAnalysisManager &MFAM) {
490 ProfileSummaryInfo *PSI =
491 MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
492 .getCachedResult<ProfileSummaryAnalysis>(
493 IR&: *MF.getFunction().getParent());
494 MachineBlockFrequencyInfo *MBFI = nullptr;
495 if (PSI && PSI->hasProfileSummary())
496 MBFI = &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF);
497 X86FixupBWInstImpl Impl(PSI, MBFI);
498 bool Changed = Impl.runOnMachineFunction(MF);
499 return Changed ? getMachineFunctionPassPreservedAnalyses()
500 .preserveSet<CFGAnalyses>()
501 : PreservedAnalyses::all();
502}
503