Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Target/X86/X86FixupBWInsts.cpp
Line
Count
Source (jump to first uncovered line)
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"
52
#include "llvm/CodeGen/LivePhysRegs.h"
53
#include "llvm/CodeGen/MachineFunctionPass.h"
54
#include "llvm/CodeGen/MachineInstrBuilder.h"
55
#include "llvm/CodeGen/MachineLoopInfo.h"
56
#include "llvm/CodeGen/MachineRegisterInfo.h"
57
#include "llvm/CodeGen/Passes.h"
58
#include "llvm/Support/Debug.h"
59
#include "llvm/Support/raw_ostream.h"
60
#include "llvm/Target/TargetInstrInfo.h"
61
using namespace llvm;
62
63
7.88k
#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
7.88k
  StringRef getPassName() const override 
{ return 7.88k
FIXUPBW_DESC7.88k
; }
105
106
7.89k
  FixupBWInstPass() : MachineFunctionPass(ID) {
107
7.89k
    initializeFixupBWInstPassPass(*PassRegistry::getPassRegistry());
108
7.89k
  }
109
110
7.87k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
111
7.87k
    AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to
112
7.87k
                                       // guide some heuristics.
113
7.87k
    MachineFunctionPass::getAnalysisUsage(AU);
114
7.87k
  }
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
7.87k
  MachineFunctionProperties getRequiredProperties() const override {
122
7.87k
    return MachineFunctionProperties().set(
123
7.87k
        MachineFunctionProperties::Property::NoVRegs);
124
7.87k
  }
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
7.89k
FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
147
148
70.8k
bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {
149
70.8k
  if (
!FixupBWInsts || 70.8k
skipFunction(*MF.getFunction())70.7k
)
150
127
    return false;
151
70.7k
152
70.7k
  this->MF = &MF;
153
70.7k
  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
154
70.7k
  OptForSize = MF.getFunction()->optForSize();
155
70.7k
  MLI = &getAnalysis<MachineLoopInfo>();
156
70.7k
  LiveRegs.init(TII->getRegisterInfo());
157
70.7k
158
70.7k
  DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
159
70.7k
160
70.7k
  // Process all basic blocks.
161
70.7k
  for (auto &MBB : MF)
162
132k
    processBasicBlock(MF, MBB);
163
70.7k
164
70.7k
  DEBUG(dbgs() << "End X86FixupBWInsts\n";);
165
70.8k
166
70.8k
  return true;
167
70.8k
}
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
6.43k
                   unsigned Reg) {
207
6.43k
  if (!LiveRegs.contains(Reg))
208
5.52k
    return false;
209
910
210
910
  unsigned Opc = MI.getOpcode(); (void)Opc;
211
910
  // These are the opcodes currently handled by the pass, if something
212
910
  // else will be added we need to ensure that new opcode has the same
213
910
  // properties.
214
910
  assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr ||
215
910
          Opc == X86::MOV16rr) &&
216
910
         "Unexpected opcode.");
217
910
218
910
  bool IsDefined = false;
219
899
  for (auto &MO: MI.implicit_operands()) {
220
899
    if (!MO.isReg())
221
0
      continue;
222
899
223
899
    assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!");
224
899
225
2.93k
    for (MCSuperRegIterator Supers(Reg, TRI, true); 
Supers.isValid()2.93k
;
++Supers2.03k
) {
226
2.08k
      if (
*Supers == MO.getReg()2.08k
) {
227
843
        if (MO.isDef())
228
792
          IsDefined = true;
229
843
        else
230
51
          return true; // SuperReg Imp-used' -> live before the MI
231
843
      }
232
2.08k
    }
233
899
  }
234
910
  // Reg is not Imp-def'ed -> it's live both before/after the instruction.
235
859
  
if (859
!IsDefined859
)
236
67
    return true;
237
792
238
792
  // Otherwise, the Reg is not live before the MI and the MOV can't
239
792
  // make it really live, so it's in fact dead even after the MI.
240
792
  return false;
241
792
}
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
3.91k
                                            unsigned &SuperDestReg) const {
250
3.91k
  auto *TRI = &TII->getRegisterInfo();
251
3.91k
252
3.91k
  unsigned OrigDestReg = OrigMI->getOperand(0).getReg();
253
3.91k
  SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);
254
3.91k
255
3.91k
  const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);
256
3.91k
257
3.91k
  // Make sure that the sub-register that this instruction has as its
258
3.91k
  // destination is the lowest order sub-register of the super-register.
259
3.91k
  // If it isn't, then the register isn't really dead even if the
260
3.91k
  // super-register is considered dead.
261
3.91k
  if (SubRegIdx == X86::sub_8bit_hi)
262
73
    return false;
263
3.83k
264
3.83k
  
if (3.83k
isLive(*OrigMI, LiveRegs, TRI, SuperDestReg)3.83k
)
265
51
    return false;
266
3.78k
267
3.78k
  
if (3.78k
SubRegIdx == X86::sub_8bit3.78k
) {
268
2.60k
    // In the case of byte registers, we also have to check that the upper
269
2.60k
    // byte register is also dead. That is considered to be independent of
270
2.60k
    // whether the super-register is dead.
271
2.60k
    unsigned UpperByteReg =
272
2.60k
        getX86SubSuperRegister(SuperDestReg, 8, /*High=*/true);
273
2.60k
274
2.60k
    if (isLive(*OrigMI, LiveRegs, TRI, UpperByteReg))
275
67
      return false;
276
3.71k
  }
277
3.71k
278
3.71k
  return true;
279
3.71k
}
280
281
MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,
282
1.71k
                                              MachineInstr *MI) const {
283
1.71k
  unsigned NewDestReg;
284
1.71k
285
1.71k
  // We are going to try to rewrite this load to a larger zero-extending
286
1.71k
  // load.  This is safe if all portions of the 32 bit super-register
287
1.71k
  // of the original destination register, except for the original destination
288
1.71k
  // register are dead. getSuperRegDestIfDead checks that.
289
1.71k
  if (!getSuperRegDestIfDead(MI, NewDestReg))
290
8
    return nullptr;
291
1.71k
292
1.71k
  // Safe to change the instruction.
293
1.71k
  MachineInstrBuilder MIB =
294
1.71k
      BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg);
295
1.71k
296
1.71k
  unsigned NumArgs = MI->getNumOperands();
297
10.6k
  for (unsigned i = 1; 
i < NumArgs10.6k
;
++i8.89k
)
298
8.89k
    MIB.add(MI->getOperand(i));
299
1.71k
300
1.71k
  MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
301
1.71k
302
1.71k
  return MIB;
303
1.71k
}
304
305
2.19k
MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
306
2.19k
  assert(MI->getNumExplicitOperands() == 2);
307
2.19k
  auto &OldDest = MI->getOperand(0);
308
2.19k
  auto &OldSrc = MI->getOperand(1);
309
2.19k
310
2.19k
  unsigned NewDestReg;
311
2.19k
  if (!getSuperRegDestIfDead(MI, NewDestReg))
312
183
    return nullptr;
313
2.00k
314
2.00k
  unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);
315
2.00k
316
2.00k
  // This is only correct if we access the same subregister index: otherwise,
317
2.00k
  // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
318
2.00k
  auto *TRI = &TII->getRegisterInfo();
319
2.00k
  if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) !=
320
2.00k
      TRI->getSubRegIndex(NewDestReg, OldDest.getReg()))
321
30
    return nullptr;
322
1.97k
323
1.97k
  // Safe to change the instruction.
324
1.97k
  // Don't set src flags, as we don't know if we're also killing the superreg.
325
1.97k
  // However, the superregister might not be defined; make it explicit that
326
1.97k
  // we don't care about the higher bits by reading it as Undef, and adding
327
1.97k
  // an imp-use on the original subregister.
328
1.97k
  MachineInstrBuilder MIB =
329
1.97k
      BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg)
330
1.97k
          .addReg(NewSrcReg, RegState::Undef)
331
1.97k
          .addReg(OldSrc.getReg(), RegState::Implicit);
332
1.97k
333
1.97k
  // Drop imp-defs/uses that would be redundant with the new def/use.
334
1.97k
  for (auto &Op : MI->implicit_operands())
335
820
    
if (820
Op.getReg() != (Op.isDef() ? 820
NewDestReg264
:
NewSrcReg556
))
336
101
      MIB.add(Op);
337
2.19k
338
2.19k
  return MIB;
339
2.19k
}
340
341
MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,
342
878k
                                               MachineBasicBlock &MBB) const {
343
878k
  // See if this is an instruction of the type we are currently looking for.
344
878k
  switch (MI->getOpcode()) {
345
878k
346
3.24k
  case X86::MOV8rm:
347
3.24k
    // Only replace 8 bit loads with the zero extending versions if
348
3.24k
    // in an inner most loop and not optimizing for size. This takes
349
3.24k
    // an extra byte to encode, and provides limited performance upside.
350
3.24k
    if (MachineLoop *ML = MLI->getLoopFor(&MBB))
351
922
      
if (922
ML->begin() == ML->end() && 922
!OptForSize802
)
352
802
        return tryReplaceLoad(X86::MOVZX32rm8, MI);
353
2.44k
    break;
354
2.44k
355
917
  case X86::MOV16rm:
356
917
    // Always try to replace 16 bit load with 32 bit zero extending.
357
917
    // Code size is the same, and there is sometimes a perf advantage
358
917
    // from eliminating a false dependence on the upper portion of
359
917
    // the register.
360
917
    return tryReplaceLoad(X86::MOVZX32rm16, MI);
361
2.44k
362
2.19k
  case X86::MOV8rr:
363
2.19k
  case X86::MOV16rr:
364
2.19k
    // Always try to replace 8/16 bit copies with a 32 bit copy.
365
2.19k
    // Code size is either less (16) or equal (8), and there is sometimes a
366
2.19k
    // perf advantage from eliminating a false dependence on the upper portion
367
2.19k
    // of the register.
368
2.19k
    return tryReplaceCopy(MI);
369
2.19k
370
872k
  default:
371
872k
    // nothing to do here.
372
872k
    break;
373
874k
  }
374
874k
375
874k
  return nullptr;
376
874k
}
377
378
void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
379
132k
                                        MachineBasicBlock &MBB) {
380
132k
381
132k
  // This algorithm doesn't delete the instructions it is replacing
382
132k
  // right away.  By leaving the existing instructions in place, the
383
132k
  // register liveness information doesn't change, and this makes the
384
132k
  // analysis that goes on be better than if the replaced instructions
385
132k
  // were immediately removed.
386
132k
  //
387
132k
  // This algorithm always creates a replacement instruction
388
132k
  // and notes that and the original in a data structure, until the
389
132k
  // whole BB has been analyzed.  This keeps the replacement instructions
390
132k
  // from making it seem as if the larger register might be live.
391
132k
  SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements;
392
132k
393
132k
  // Start computing liveness for this block. We iterate from the end to be able
394
132k
  // to update this for each instruction.
395
132k
  LiveRegs.clear();
396
132k
  // We run after PEI, so we need to AddPristinesAndCSRs.
397
132k
  LiveRegs.addLiveOuts(MBB);
398
132k
399
1.01M
  for (auto I = MBB.rbegin(); 
I != MBB.rend()1.01M
;
++I878k
) {
400
878k
    MachineInstr *MI = &*I;
401
878k
402
878k
    if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB))
403
3.68k
      MIReplacements.push_back(std::make_pair(MI, NewMI));
404
878k
405
878k
    // We're done with this instruction, update liveness for the next one.
406
878k
    LiveRegs.stepBackward(*MI);
407
878k
  }
408
132k
409
136k
  while (
!MIReplacements.empty()136k
) {
410
3.68k
    MachineInstr *MI = MIReplacements.back().first;
411
3.68k
    MachineInstr *NewMI = MIReplacements.back().second;
412
3.68k
    MIReplacements.pop_back();
413
3.68k
    MBB.insert(MI, NewMI);
414
3.68k
    MBB.erase(MI);
415
3.68k
  }
416
132k
}