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