LLVM  6.0.0svn
X86FixupBWInsts.cpp
Go to the documentation of this file.
1 //===-- X86FixupBWInsts.cpp - Fixup Byte or Word instructions -----------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 /// \file
10 /// This file defines the pass that looks through the machine instructions
11 /// late in the compilation, and finds byte or word instructions that
12 /// can be profitably replaced with 32 bit instructions that give equivalent
13 /// results for the bits of the results that are used. There are two possible
14 /// reasons to do this.
15 ///
16 /// One reason is to avoid false-dependences on the upper portions
17 /// of the registers. Only instructions that have a destination register
18 /// which is not in any of the source registers can be affected by this.
19 /// Any instruction where one of the source registers is also the destination
20 /// register is unaffected, because it has a true dependence on the source
21 /// register already. So, this consideration primarily affects load
22 /// instructions and register-to-register moves. It would
23 /// seem like cmov(s) would also be affected, but because of the way cmov is
24 /// really implemented by most machines as reading both the destination and
25 /// and source registers, and then "merging" the two based on a condition,
26 /// it really already should be considered as having a true dependence on the
27 /// destination register as well.
28 ///
29 /// The other reason to do this is for potential code size savings. Word
30 /// operations need an extra override byte compared to their 32 bit
31 /// versions. So this can convert many word operations to their larger
32 /// size, saving a byte in encoding. This could introduce partial register
33 /// dependences where none existed however. As an example take:
34 /// orw ax, $0x1000
35 /// addw ax, $3
36 /// now if this were to get transformed into
37 /// orw ax, $1000
38 /// addl eax, $3
39 /// because the addl encodes shorter than the addw, this would introduce
40 /// a use of a register that was only partially written earlier. On older
41 /// Intel processors this can be quite a performance penalty, so this should
42 /// probably only be done when it can be proven that a new partial dependence
43 /// wouldn't be created, or when your know a newer processor is being
44 /// targeted, or when optimizing for minimum code size.
45 ///
46 //===----------------------------------------------------------------------===//
47 
48 #include "X86.h"
49 #include "X86InstrInfo.h"
50 #include "X86Subtarget.h"
51 #include "llvm/ADT/Statistic.h"
57 #include "llvm/CodeGen/Passes.h"
59 #include "llvm/Support/Debug.h"
61 using namespace llvm;
62 
63 #define FIXUPBW_DESC "X86 Byte/Word Instruction Fixup"
64 #define FIXUPBW_NAME "x86-fixup-bw-insts"
65 
66 #define DEBUG_TYPE FIXUPBW_NAME
67 
68 // Option to allow this optimization pass to have fine-grained control.
69 static cl::opt<bool>
70  FixupBWInsts("fixup-byte-word-insts",
71  cl::desc("Change byte and word instructions to larger sizes"),
72  cl::init(true), cl::Hidden);
73 
74 namespace {
75 class FixupBWInstPass : public MachineFunctionPass {
76  /// Loop over all of the instructions in the basic block replacing applicable
77  /// byte or word instructions with better alternatives.
78  void processBasicBlock(MachineFunction &MF, MachineBasicBlock &MBB);
79 
80  /// This sets the \p SuperDestReg to the 32 bit super reg of the original
81  /// destination register of the MachineInstr passed in. It returns true if
82  /// that super register is dead just prior to \p OrigMI, and false if not.
83  bool getSuperRegDestIfDead(MachineInstr *OrigMI,
84  unsigned &SuperDestReg) 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 an eqivalent 32 bit instruction if
97  // possible. Return the replacement instruction if OK, return nullptr
98  // otherwise.
99  MachineInstr *tryReplaceInstr(MachineInstr *MI, MachineBasicBlock &MBB) const;
100 
101 public:
102  static char ID;
103 
104  StringRef getPassName() const override { return FIXUPBW_DESC; }
105 
106  FixupBWInstPass() : MachineFunctionPass(ID) {
108  }
109 
110  void getAnalysisUsage(AnalysisUsage &AU) const override {
111  AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to
112  // guide some heuristics.
114  }
115 
116  /// Loop over all of the basic blocks, replacing byte and word instructions by
117  /// equivalent 32 bit instructions where performance or code size can be
118  /// improved.
119  bool runOnMachineFunction(MachineFunction &MF) override;
120 
121  MachineFunctionProperties getRequiredProperties() const override {
124  }
125 
126 private:
127  MachineFunction *MF;
128 
129  /// Machine instruction info used throughout the class.
130  const X86InstrInfo *TII;
131 
132  /// Local member for function's OptForSize attribute.
133  bool OptForSize;
134 
135  /// Machine loop info used for guiding some heruistics.
136  MachineLoopInfo *MLI;
137 
138  /// Register Liveness information after the current instruction.
139  LivePhysRegs LiveRegs;
140 };
141 char FixupBWInstPass::ID = 0;
142 }
143 
144 INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false)
145 
146 FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
147 
148 bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {
149  if (!FixupBWInsts || skipFunction(*MF.getFunction()))
150  return false;
151 
152  this->MF = &MF;
153  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
154  OptForSize = MF.getFunction()->optForSize();
155  MLI = &getAnalysis<MachineLoopInfo>();
156  LiveRegs.init(TII->getRegisterInfo());
157 
158  DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
159 
160  // Process all basic blocks.
161  for (auto &MBB : MF)
162  processBasicBlock(MF, MBB);
163 
164  DEBUG(dbgs() << "End X86FixupBWInsts\n";);
165 
166  return true;
167 }
168 
169 /// Check if register \p Reg is live after the \p MI.
170 ///
171 /// \p LiveRegs should be in a state describing liveness information in
172 /// that exact place as this function tries to precise analysis made
173 /// by \p LiveRegs by exploiting the information about particular
174 /// instruction \p MI. \p MI is expected to be one of the MOVs handled
175 /// by the x86FixupBWInsts pass.
176 /// Note: similar to LivePhysRegs::contains this would state that
177 /// super-register is not used if only some part of it is used.
178 ///
179 /// X86 backend does not have subregister liveness tracking enabled,
180 /// so liveness information might be overly conservative. However, for
181 /// some specific instructions (this pass only cares about MOVs) we can
182 /// produce more precise results by analysing that MOV's operands.
183 ///
184 /// Indeed, if super-register is not live before the mov it means that it
185 /// was originally <read-undef> and so we are free to modify these
186 /// undef upper bits. That may happen in case where the use is in another MBB
187 /// and the vreg/physreg corresponding to the move has higher width than
188 /// necessary (e.g. due to register coalescing with a "truncate" copy).
189 /// So, it handles pattern like this:
190 ///
191 /// BB#2: derived from LLVM BB %if.then
192 /// Live Ins: %RDI
193 /// Predecessors according to CFG: BB#0
194 /// %AX<def> = MOV16rm %RDI<kill>, 1, %noreg, 0, %noreg, %EAX<imp-def>; mem:LD2[%p]
195 /// No %EAX<imp-use>
196 /// Successors according to CFG: BB#3(?%)
197 ///
198 /// BB#3: derived from LLVM BB %if.end
199 /// Live Ins: %EAX Only %AX is actually live
200 /// Predecessors according to CFG: BB#2 BB#1
201 /// %AX<def> = KILL %AX, %EAX<imp-use,kill>
202 /// RET 0, %AX
203 static bool isLive(const MachineInstr &MI,
204  const LivePhysRegs &LiveRegs,
205  const TargetRegisterInfo *TRI,
206  unsigned Reg) {
207  if (!LiveRegs.contains(Reg))
208  return false;
209 
210  unsigned Opc = MI.getOpcode(); (void)Opc;
211  // These are the opcodes currently handled by the pass, if something
212  // else will be added we need to ensure that new opcode has the same
213  // properties.
214  assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr ||
215  Opc == X86::MOV16rr) &&
216  "Unexpected opcode.");
217 
218  bool IsDefined = false;
219  for (auto &MO: MI.implicit_operands()) {
220  if (!MO.isReg())
221  continue;
222 
223  assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!");
224 
225  for (MCSuperRegIterator Supers(Reg, TRI, true); Supers.isValid(); ++Supers) {
226  if (*Supers == MO.getReg()) {
227  if (MO.isDef())
228  IsDefined = true;
229  else
230  return true; // SuperReg Imp-used' -> live before the MI
231  }
232  }
233  }
234  // Reg is not Imp-def'ed -> it's live both before/after the instruction.
235  if (!IsDefined)
236  return true;
237 
238  // Otherwise, the Reg is not live before the MI and the MOV can't
239  // make it really live, so it's in fact dead even after the MI.
240  return false;
241 }
242 
243 /// \brief Check if after \p OrigMI the only portion of super register
244 /// of the destination register of \p OrigMI that is alive is that
245 /// destination register.
246 ///
247 /// If so, return that super register in \p SuperDestReg.
248 bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI,
249  unsigned &SuperDestReg) const {
250  auto *TRI = &TII->getRegisterInfo();
251 
252  unsigned OrigDestReg = OrigMI->getOperand(0).getReg();
253  SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);
254 
255  const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);
256 
257  // Make sure that the sub-register that this instruction has as its
258  // destination is the lowest order sub-register of the super-register.
259  // If it isn't, then the register isn't really dead even if the
260  // super-register is considered dead.
261  if (SubRegIdx == X86::sub_8bit_hi)
262  return false;
263 
264  if (isLive(*OrigMI, LiveRegs, TRI, SuperDestReg))
265  return false;
266 
267  if (SubRegIdx == X86::sub_8bit) {
268  // In the case of byte registers, we also have to check that the upper
269  // byte register is also dead. That is considered to be independent of
270  // whether the super-register is dead.
271  unsigned UpperByteReg =
272  getX86SubSuperRegister(SuperDestReg, 8, /*High=*/true);
273 
274  if (isLive(*OrigMI, LiveRegs, TRI, UpperByteReg))
275  return false;
276  }
277 
278  return true;
279 }
280 
281 MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,
282  MachineInstr *MI) const {
283  unsigned NewDestReg;
284 
285  // We are going to try to rewrite this load to a larger zero-extending
286  // load. This is safe if all portions of the 32 bit super-register
287  // of the original destination register, except for the original destination
288  // register are dead. getSuperRegDestIfDead checks that.
289  if (!getSuperRegDestIfDead(MI, NewDestReg))
290  return nullptr;
291 
292  // Safe to change the instruction.
293  MachineInstrBuilder MIB =
294  BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg);
295 
296  unsigned NumArgs = MI->getNumOperands();
297  for (unsigned i = 1; i < NumArgs; ++i)
298  MIB.add(MI->getOperand(i));
299 
300  MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
301 
302  return MIB;
303 }
304 
305 MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
306  assert(MI->getNumExplicitOperands() == 2);
307  auto &OldDest = MI->getOperand(0);
308  auto &OldSrc = MI->getOperand(1);
309 
310  unsigned NewDestReg;
311  if (!getSuperRegDestIfDead(MI, NewDestReg))
312  return nullptr;
313 
314  unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);
315 
316  // This is only correct if we access the same subregister index: otherwise,
317  // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
318  auto *TRI = &TII->getRegisterInfo();
319  if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) !=
320  TRI->getSubRegIndex(NewDestReg, OldDest.getReg()))
321  return nullptr;
322 
323  // Safe to change the instruction.
324  // Don't set src flags, as we don't know if we're also killing the superreg.
325  // However, the superregister might not be defined; make it explicit that
326  // we don't care about the higher bits by reading it as Undef, and adding
327  // an imp-use on the original subregister.
328  MachineInstrBuilder MIB =
329  BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg)
330  .addReg(NewSrcReg, RegState::Undef)
331  .addReg(OldSrc.getReg(), RegState::Implicit);
332 
333  // Drop imp-defs/uses that would be redundant with the new def/use.
334  for (auto &Op : MI->implicit_operands())
335  if (Op.getReg() != (Op.isDef() ? NewDestReg : NewSrcReg))
336  MIB.add(Op);
337 
338  return MIB;
339 }
340 
341 MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,
342  MachineBasicBlock &MBB) const {
343  // See if this is an instruction of the type we are currently looking for.
344  switch (MI->getOpcode()) {
345 
346  case X86::MOV8rm:
347  // Only replace 8 bit loads with the zero extending versions if
348  // in an inner most loop and not optimizing for size. This takes
349  // an extra byte to encode, and provides limited performance upside.
350  if (MachineLoop *ML = MLI->getLoopFor(&MBB))
351  if (ML->begin() == ML->end() && !OptForSize)
352  return tryReplaceLoad(X86::MOVZX32rm8, MI);
353  break;
354 
355  case X86::MOV16rm:
356  // Always try to replace 16 bit load with 32 bit zero extending.
357  // Code size is the same, and there is sometimes a perf advantage
358  // from eliminating a false dependence on the upper portion of
359  // the register.
360  return tryReplaceLoad(X86::MOVZX32rm16, MI);
361 
362  case X86::MOV8rr:
363  case X86::MOV16rr:
364  // Always try to replace 8/16 bit copies with a 32 bit copy.
365  // Code size is either less (16) or equal (8), and there is sometimes a
366  // perf advantage from eliminating a false dependence on the upper portion
367  // of the register.
368  return tryReplaceCopy(MI);
369 
370  default:
371  // nothing to do here.
372  break;
373  }
374 
375  return nullptr;
376 }
377 
378 void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
379  MachineBasicBlock &MBB) {
380 
381  // This algorithm doesn't delete the instructions it is replacing
382  // right away. By leaving the existing instructions in place, the
383  // register liveness information doesn't change, and this makes the
384  // analysis that goes on be better than if the replaced instructions
385  // were immediately removed.
386  //
387  // This algorithm always creates a replacement instruction
388  // and notes that and the original in a data structure, until the
389  // whole BB has been analyzed. This keeps the replacement instructions
390  // from making it seem as if the larger register might be live.
392 
393  // Start computing liveness for this block. We iterate from the end to be able
394  // to update this for each instruction.
395  LiveRegs.clear();
396  // We run after PEI, so we need to AddPristinesAndCSRs.
397  LiveRegs.addLiveOuts(MBB);
398 
399  for (auto I = MBB.rbegin(); I != MBB.rend(); ++I) {
400  MachineInstr *MI = &*I;
401 
402  if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB))
403  MIReplacements.push_back(std::make_pair(MI, NewMI));
404 
405  // We're done with this instruction, update liveness for the next one.
406  LiveRegs.stepBackward(*MI);
407  }
408 
409  while (!MIReplacements.empty()) {
410  MachineInstr *MI = MIReplacements.back().first;
411  MachineInstr *NewMI = MIReplacements.back().second;
412  MIReplacements.pop_back();
413  MBB.insert(MI, NewMI);
414  MBB.erase(MI);
415  }
416 }
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...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void initializeFixupBWInstPassPass(PassRegistry &)
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:268
unsigned getReg() const
getReg - Returns the register number.
#define FIXUPBW_DESC
AnalysisUsage & addRequired()
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MCSuperRegIterator enumerates all super-registers of Reg.
bool contains(unsigned Reg) const
Returns true if register Reg is contained in the set.
Definition: LivePhysRegs.h:106
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
unsigned getNumOperands() const
Access to explicit operands of the instruction.
Definition: MachineInstr.h:293
static bool isLive(const MachineInstr &MI, const LivePhysRegs &LiveRegs, const TargetRegisterInfo *TRI, unsigned Reg)
Check if register Reg is live after the MI.
Reg
All possible values of the reg field in the ModR/M byte.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:290
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:406
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:530
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
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:34
static cl::opt< bool > FixupBWInsts("fixup-byte-word-insts", cl::desc("Change byte and word instructions to larger sizes"), cl::init(true), cl::Hidden)
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:389
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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.
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
iterator_range< mop_iterator > implicit_operands()
Definition: MachineInstr.h:346
MachineFunctionProperties & set(Property P)
Representation of each machine instruction.
Definition: MachineInstr.h:59
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:49
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#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.
const Function * getFunction() const
getFunction - Return the LLVM function that this machine code represents
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:295
void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd)
Assign this MachineInstr&#39;s memory reference descriptor list.
Properties which a MachineFunction may have at a given point in time.
mmo_iterator memoperands_end() const
Definition: MachineInstr.h:390