LLVM  9.0.0svn
X86FixupBWInsts.cpp
Go to the documentation of this file.
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"
56 #include "llvm/CodeGen/Passes.h"
58 #include "llvm/Support/Debug.h"
60 using namespace llvm;
61 
62 #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup"
63 #define FIXUPBW_NAME "x86-fixup-bw-insts"
64 
65 #define DEBUG_TYPE FIXUPBW_NAME
66 
67 // Option to allow this optimization pass to have fine-grained control.
68 static cl::opt<bool>
69  FixupBWInsts("fixup-byte-word-insts",
70  cl::desc("Change byte and word instructions to larger sizes"),
71  cl::init(true), cl::Hidden);
72 
73 namespace {
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);
78 
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;
84 
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;
89 
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
92  /// nullptr.
93  MachineInstr *tryReplaceCopy(MachineInstr *MI) const;
94 
95  // Change the MachineInstr \p MI into an eqivalent 32 bit instruction if
96  // possible. Return the replacement instruction if OK, return nullptr
97  // otherwise.
98  MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const;
99 
100 public:
101  static char ID;
102 
103  StringRef getPassName() const override { return FIXUPBW_DESC; }
104 
105  FixupBWInstPass() : MachineFunctionPass(ID) {
107  }
108 
109  void getAnalysisUsage(AnalysisUsage &AU) const override {
110  AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to
111  // guide some heuristics.
113  }
114 
115  /// Loop over all of the basic blocks, replacing byte and word instructions by
116  /// equivalent 32 bit instructions where performance or code size can be
117  /// improved.
118  bool runOnMachineFunction(MachineFunction &MF) override;
119 
120  MachineFunctionProperties getRequiredProperties() const override {
123  }
124 
125 private:
126  MachineFunction *MF;
127 
128  /// Machine instruction info used throughout the class.
129  const X86InstrInfo *TII;
130 
131  /// Local member for function's OptForSize attribute.
132  bool OptForSize;
133 
134  /// Machine loop info used for guiding some heruistics.
135  MachineLoopInfo *MLI;
136 
137  /// Register Liveness information after the current instruction.
138  LivePhysRegs LiveRegs;
139 };
140 char FixupBWInstPass::ID = 0;
141 }
142 
143 INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false)
144 
145 FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
146 
147 bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {
148  if (!FixupBWInsts || skipFunction(MF.getFunction()))
149  return false;
150 
151  this->MF = &MF;
152  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
153  OptForSize = MF.getFunction().optForSize();
154  MLI = &getAnalysis<MachineLoopInfo>();
155  LiveRegs.init(TII->getRegisterInfo());
156 
157  LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
158 
159  // Process all basic blocks.
160  for (auto &MBB : MF)
161  processBasicBlock(MF, MBB);
162 
163  LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";);
164 
165  return true;
166 }
167 
168 /// Check if after \p OrigMI the only portion of super register
169 /// of the destination register of \p OrigMI that is alive is that
170 /// destination register.
171 ///
172 /// If so, return that super register in \p SuperDestReg.
173 bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI,
174  unsigned &SuperDestReg) const {
175  auto *TRI = &TII->getRegisterInfo();
176 
177  unsigned OrigDestReg = OrigMI->getOperand(0).getReg();
178  SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);
179 
180  const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);
181 
182  // Make sure that the sub-register that this instruction has as its
183  // destination is the lowest order sub-register of the super-register.
184  // If it isn't, then the register isn't really dead even if the
185  // super-register is considered dead.
186  if (SubRegIdx == X86::sub_8bit_hi)
187  return false;
188 
189  // If neither the destination-super register nor any applicable subregisters
190  // are live after this instruction, then the super register is safe to use.
191  if (!LiveRegs.contains(SuperDestReg)) {
192  // If the original destination register was not the low 8-bit subregister
193  // then the super register check is sufficient.
194  if (SubRegIdx != X86::sub_8bit)
195  return true;
196  // If the original destination register was the low 8-bit subregister and
197  // we also need to check the 16-bit subregister and the high 8-bit
198  // subregister.
199  if (!LiveRegs.contains(getX86SubSuperRegister(OrigDestReg, 16)) &&
200  !LiveRegs.contains(getX86SubSuperRegister(SuperDestReg, 8,
201  /*High=*/true)))
202  return true;
203  // Otherwise, we have a little more checking to do.
204  }
205 
206  // If we get here, the super-register destination (or some part of it) is
207  // marked as live after the original instruction.
208  //
209  // The X86 backend does not have subregister liveness tracking enabled,
210  // so liveness information might be overly conservative. Specifically, the
211  // super register might be marked as live because it is implicitly defined
212  // by the instruction we are examining.
213  //
214  // However, for some specific instructions (this pass only cares about MOVs)
215  // we can produce more precise results by analysing that MOV's operands.
216  //
217  // Indeed, if super-register is not live before the mov it means that it
218  // was originally <read-undef> and so we are free to modify these
219  // undef upper bits. That may happen in case where the use is in another MBB
220  // and the vreg/physreg corresponding to the move has higher width than
221  // necessary (e.g. due to register coalescing with a "truncate" copy).
222  // So, we would like to handle patterns like this:
223  //
224  // %bb.2: derived from LLVM BB %if.then
225  // Live Ins: %rdi
226  // Predecessors according to CFG: %bb.0
227  // %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax
228  // ; No implicit %eax
229  // Successors according to CFG: %bb.3(?%)
230  //
231  // %bb.3: derived from LLVM BB %if.end
232  // Live Ins: %eax Only %ax is actually live
233  // Predecessors according to CFG: %bb.2 %bb.1
234  // %ax = KILL %ax, implicit killed %eax
235  // RET 0, %ax
236  unsigned Opc = OrigMI->getOpcode(); (void)Opc;
237  // These are the opcodes currently handled by the pass, if something
238  // else will be added we need to ensure that new opcode has the same
239  // properties.
240  assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr ||
241  Opc == X86::MOV16rr) &&
242  "Unexpected opcode.");
243 
244  bool IsDefined = false;
245  for (auto &MO: OrigMI->implicit_operands()) {
246  if (!MO.isReg())
247  continue;
248 
249  assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!");
250 
251  if (MO.isDef() && TRI->isSuperRegisterEq(OrigDestReg, MO.getReg()))
252  IsDefined = true;
253 
254  // If MO is a use of any part of the destination register but is not equal
255  // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.
256  // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,
257  // %eax, or %rax will prevent us from using the %eax register.
258  if (MO.isUse() && !TRI->isSubRegisterEq(OrigDestReg, MO.getReg()) &&
259  TRI->regsOverlap(SuperDestReg, MO.getReg()))
260  return false;
261  }
262  // Reg is not Imp-def'ed -> it's live both before/after the instruction.
263  if (!IsDefined)
264  return false;
265 
266  // Otherwise, the Reg is not live before the MI and the MOV can't
267  // make it really live, so it's in fact dead even after the MI.
268  return true;
269 }
270 
271 MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,
272  MachineInstr *MI) const {
273  unsigned NewDestReg;
274 
275  // We are going to try to rewrite this load to a larger zero-extending
276  // load. This is safe if all portions of the 32 bit super-register
277  // of the original destination register, except for the original destination
278  // register are dead. getSuperRegDestIfDead checks that.
279  if (!getSuperRegDestIfDead(MI, NewDestReg))
280  return nullptr;
281 
282  // Safe to change the instruction.
283  MachineInstrBuilder MIB =
284  BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg);
285 
286  unsigned NumArgs = MI->getNumOperands();
287  for (unsigned i = 1; i < NumArgs; ++i)
288  MIB.add(MI->getOperand(i));
289 
290  MIB.setMemRefs(MI->memoperands());
291 
292  return MIB;
293 }
294 
295 MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
296  assert(MI->getNumExplicitOperands() == 2);
297  auto &OldDest = MI->getOperand(0);
298  auto &OldSrc = MI->getOperand(1);
299 
300  unsigned NewDestReg;
301  if (!getSuperRegDestIfDead(MI, NewDestReg))
302  return nullptr;
303 
304  unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);
305 
306  // This is only correct if we access the same subregister index: otherwise,
307  // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
308  auto *TRI = &TII->getRegisterInfo();
309  if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) !=
310  TRI->getSubRegIndex(NewDestReg, OldDest.getReg()))
311  return nullptr;
312 
313  // Safe to change the instruction.
314  // Don't set src flags, as we don't know if we're also killing the superreg.
315  // However, the superregister might not be defined; make it explicit that
316  // we don't care about the higher bits by reading it as Undef, and adding
317  // an imp-use on the original subregister.
318  MachineInstrBuilder MIB =
319  BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg)
320  .addReg(NewSrcReg, RegState::Undef)
321  .addReg(OldSrc.getReg(), RegState::Implicit);
322 
323  // Drop imp-defs/uses that would be redundant with the new def/use.
324  for (auto &Op : MI->implicit_operands())
325  if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg))
326  MIB.add(Op);
327 
328  return MIB;
329 }
330 
331 MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,
332  MachineBasicBlock &MBB) const {
333  // See if this is an instruction of the type we are currently looking for.
334  switch (MI->getOpcode()) {
335 
336  case X86::MOV8rm:
337  // Only replace 8 bit loads with the zero extending versions if
338  // in an inner most loop and not optimizing for size. This takes
339  // an extra byte to encode, and provides limited performance upside.
340  if (MachineLoop *ML = MLI->getLoopFor(&MBB))
341  if (ML->begin() == ML->end() && !OptForSize)
342  return tryReplaceLoad(X86::MOVZX32rm8, MI);
343  break;
344 
345  case X86::MOV16rm:
346  // Always try to replace 16 bit load with 32 bit zero extending.
347  // Code size is the same, and there is sometimes a perf advantage
348  // from eliminating a false dependence on the upper portion of
349  // the register.
350  return tryReplaceLoad(X86::MOVZX32rm16, MI);
351 
352  case X86::MOV8rr:
353  case X86::MOV16rr:
354  // Always try to replace 8/16 bit copies with a 32 bit copy.
355  // Code size is either less (16) or equal (8), and there is sometimes a
356  // perf advantage from eliminating a false dependence on the upper portion
357  // of the register.
358  return tryReplaceCopy(MI);
359 
360  default:
361  // nothing to do here.
362  break;
363  }
364 
365  return nullptr;
366 }
367 
368 void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
369  MachineBasicBlock &MBB) {
370 
371  // This algorithm doesn't delete the instructions it is replacing
372  // right away. By leaving the existing instructions in place, the
373  // register liveness information doesn't change, and this makes the
374  // analysis that goes on be better than if the replaced instructions
375  // were immediately removed.
376  //
377  // This algorithm always creates a replacement instruction
378  // and notes that and the original in a data structure, until the
379  // whole BB has been analyzed. This keeps the replacement instructions
380  // from making it seem as if the larger register might be live.
382 
383  // Start computing liveness for this block. We iterate from the end to be able
384  // to update this for each instruction.
385  LiveRegs.clear();
386  // We run after PEI, so we need to AddPristinesAndCSRs.
387  LiveRegs.addLiveOuts(MBB);
388 
389  for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) {
390  MachineInstr *MI = &*I;
391 
392  if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB))
393  MIReplacements.push_back(std::make_pair(MI, NewMI));
394 
395  // We're done with this instruction, update liveness for the next one.
396  LiveRegs.stepBackward(*MI);
397  }
398 
399  while (!MIReplacements.empty()) {
400  MachineInstr *MI = MIReplacements.back().first;
401  MachineInstr *NewMI = MIReplacements.back().second;
402  MIReplacements.pop_back();
403  MBB.insert(MI, NewMI);
404  MBB.erase(MI);
405  }
406 }
const MachineInstrBuilder & setMemRefs(ArrayRef< MachineMemOperand *> MMOs) const
const MachineInstrBuilder & add(const MachineOperand &MO) const
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
#define FIXUPBW_NAME
FunctionPass * createX86FixupBWInsts()
Return a Machine IR pass that selectively replaces certain byte and word instructions by equivalent 3...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void initializeFixupBWInstPassPass(PassRegistry &)
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:382
unsigned getReg() const
getReg - Returns the register number.
#define FIXUPBW_DESC
unsigned const TargetRegisterInfo * TRI
AnalysisUsage & addRequired()
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
reverse_iterator rend()
reverse_iterator rbegin()
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:515
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Represent the analysis usage information of a pass.
bool optForSize() const
Optimize this function for size (-Os) or minimum size (-Oz).
Definition: Function.h:597
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
unsigned getNumExplicitOperands() const
Returns the number of non-implicit operands.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:33
static cl::opt< bool > FixupBWInsts("fixup-byte-word-insts", cl::desc("Change byte and word instructions to larger sizes"), cl::init(true), cl::Hidden)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:839
const Function & getFunction() const
Return the LLVM function that this machine code represents.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned getX86SubSuperRegister(unsigned, unsigned, bool High=false)
Returns the sub or super register of a specific X86 register.
iterator_range< mop_iterator > implicit_operands()
Definition: MachineInstr.h:472
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:63
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define I(x, y, z)
Definition: MD5.cpp:58
const MachineInstrBuilder & addReg(unsigned RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
Properties which a MachineFunction may have at a given point in time.