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