Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/X86/X86FixupBWInsts.cpp
Line
Count
Source (jump to first uncovered line)
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/CodeGen/LivePhysRegs.h"
52
#include "llvm/CodeGen/MachineFunctionPass.h"
53
#include "llvm/CodeGen/MachineInstrBuilder.h"
54
#include "llvm/CodeGen/MachineLoopInfo.h"
55
#include "llvm/CodeGen/MachineRegisterInfo.h"
56
#include "llvm/CodeGen/Passes.h"
57
#include "llvm/CodeGen/TargetInstrInfo.h"
58
#include "llvm/Support/Debug.h"
59
#include "llvm/Support/raw_ostream.h"
60
using namespace llvm;
61
62
146k
#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
146k
  StringRef getPassName() const override { return FIXUPBW_DESC; }
104
105
11.4k
  FixupBWInstPass() : MachineFunctionPass(ID) { }
106
107
11.3k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
108
11.3k
    AU.addRequired<MachineLoopInfo>(); // Machine loop info is used to
109
11.3k
                                       // guide some heuristics.
110
11.3k
    MachineFunctionPass::getAnalysisUsage(AU);
111
11.3k
  }
112
113
  /// Loop over all of the basic blocks, replacing byte and word instructions by
114
  /// equivalent 32 bit instructions where performance or code size can be
115
  /// improved.
116
  bool runOnMachineFunction(MachineFunction &MF) override;
117
118
11.3k
  MachineFunctionProperties getRequiredProperties() const override {
119
11.3k
    return MachineFunctionProperties().set(
120
11.3k
        MachineFunctionProperties::Property::NoVRegs);
121
11.3k
  }
122
123
private:
124
  MachineFunction *MF;
125
126
  /// Machine instruction info used throughout the class.
127
  const X86InstrInfo *TII;
128
129
  /// Local member for function's OptForSize attribute.
130
  bool OptForSize;
131
132
  /// Machine loop info used for guiding some heruistics.
133
  MachineLoopInfo *MLI;
134
135
  /// Register Liveness information after the current instruction.
136
  LivePhysRegs LiveRegs;
137
};
138
char FixupBWInstPass::ID = 0;
139
}
140
141
INITIALIZE_PASS(FixupBWInstPass, FIXUPBW_NAME, FIXUPBW_DESC, false, false)
142
143
11.3k
FunctionPass *llvm::createX86FixupBWInsts() { return new FixupBWInstPass(); }
144
145
135k
bool FixupBWInstPass::runOnMachineFunction(MachineFunction &MF) {
146
135k
  if (!FixupBWInsts || 
skipFunction(MF.getFunction())135k
)
147
296
    return false;
148
135k
149
135k
  this->MF = &MF;
150
135k
  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
151
135k
  OptForSize = MF.getFunction().hasOptSize();
152
135k
  MLI = &getAnalysis<MachineLoopInfo>();
153
135k
  LiveRegs.init(TII->getRegisterInfo());
154
135k
155
135k
  LLVM_DEBUG(dbgs() << "Start X86FixupBWInsts\n";);
156
135k
157
135k
  // Process all basic blocks.
158
135k
  for (auto &MBB : MF)
159
384k
    processBasicBlock(MF, MBB);
160
135k
161
135k
  LLVM_DEBUG(dbgs() << "End X86FixupBWInsts\n";);
162
135k
163
135k
  return true;
164
135k
}
165
166
/// Check if after \p OrigMI the only portion of super register
167
/// of the destination register of \p OrigMI that is alive is that
168
/// destination register.
169
///
170
/// If so, return that super register in \p SuperDestReg.
171
bool FixupBWInstPass::getSuperRegDestIfDead(MachineInstr *OrigMI,
172
6.23k
                                            unsigned &SuperDestReg) const {
173
6.23k
  auto *TRI = &TII->getRegisterInfo();
174
6.23k
175
6.23k
  unsigned OrigDestReg = OrigMI->getOperand(0).getReg();
176
6.23k
  SuperDestReg = getX86SubSuperRegister(OrigDestReg, 32);
177
6.23k
178
6.23k
  const auto SubRegIdx = TRI->getSubRegIndex(SuperDestReg, OrigDestReg);
179
6.23k
180
6.23k
  // Make sure that the sub-register that this instruction has as its
181
6.23k
  // destination is the lowest order sub-register of the super-register.
182
6.23k
  // If it isn't, then the register isn't really dead even if the
183
6.23k
  // super-register is considered dead.
184
6.23k
  if (SubRegIdx == X86::sub_8bit_hi)
185
46
    return false;
186
6.18k
187
6.18k
  // If neither the destination-super register nor any applicable subregisters
188
6.18k
  // are live after this instruction, then the super register is safe to use.
189
6.18k
  if (!LiveRegs.contains(SuperDestReg)) {
190
5.15k
    // If the original destination register was not the low 8-bit subregister
191
5.15k
    // then the super register check is sufficient.
192
5.15k
    if (SubRegIdx != X86::sub_8bit)
193
885
      return true;
194
4.27k
    // If the original destination register was the low 8-bit subregister and
195
4.27k
    // we also need to check the 16-bit subregister and the high 8-bit
196
4.27k
    // subregister.
197
4.27k
    if (!LiveRegs.contains(getX86SubSuperRegister(OrigDestReg, 16)) &&
198
4.27k
        !LiveRegs.contains(getX86SubSuperRegister(SuperDestReg, 8,
199
4.27k
                                                  /*High=*/true)))
200
4.20k
      return true;
201
1.09k
    // Otherwise, we have a little more checking to do.
202
1.09k
  }
203
1.09k
204
1.09k
  // If we get here, the super-register destination (or some part of it) is
205
1.09k
  // marked as live after the original instruction.
206
1.09k
  //
207
1.09k
  // The X86 backend does not have subregister liveness tracking enabled,
208
1.09k
  // so liveness information might be overly conservative. Specifically, the
209
1.09k
  // super register might be marked as live because it is implicitly defined
210
1.09k
  // by the instruction we are examining.
211
1.09k
  //
212
1.09k
  // However, for some specific instructions (this pass only cares about MOVs)
213
1.09k
  // we can produce more precise results by analysing that MOV's operands.
214
1.09k
  //
215
1.09k
  // Indeed, if super-register is not live before the mov it means that it
216
1.09k
  // was originally <read-undef> and so we are free to modify these
217
1.09k
  // undef upper bits. That may happen in case where the use is in another MBB
218
1.09k
  // and the vreg/physreg corresponding to the move has higher width than
219
1.09k
  // necessary (e.g. due to register coalescing with a "truncate" copy).
220
1.09k
  // So, we would like to handle patterns like this:
221
1.09k
  //
222
1.09k
  //   %bb.2: derived from LLVM BB %if.then
223
1.09k
  //   Live Ins: %rdi
224
1.09k
  //   Predecessors according to CFG: %bb.0
225
1.09k
  //   %ax<def> = MOV16rm killed %rdi, 1, %noreg, 0, %noreg, implicit-def %eax
226
1.09k
  //                                 ; No implicit %eax
227
1.09k
  //   Successors according to CFG: %bb.3(?%)
228
1.09k
  //
229
1.09k
  //   %bb.3: derived from LLVM BB %if.end
230
1.09k
  //   Live Ins: %eax                            Only %ax is actually live
231
1.09k
  //   Predecessors according to CFG: %bb.2 %bb.1
232
1.09k
  //   %ax = KILL %ax, implicit killed %eax
233
1.09k
  //   RET 0, %ax
234
1.09k
  unsigned Opc = OrigMI->getOpcode(); (void)Opc;
235
1.09k
  // These are the opcodes currently handled by the pass, if something
236
1.09k
  // else will be added we need to ensure that new opcode has the same
237
1.09k
  // properties.
238
1.09k
  assert((Opc == X86::MOV8rm || Opc == X86::MOV16rm || Opc == X86::MOV8rr ||
239
1.09k
          Opc == X86::MOV16rr) &&
240
1.09k
         "Unexpected opcode.");
241
1.09k
242
1.09k
  bool IsDefined = false;
243
1.09k
  for (auto &MO: OrigMI->implicit_operands()) {
244
1.06k
    if (!MO.isReg())
245
0
      continue;
246
1.06k
247
1.06k
    assert((MO.isDef() || MO.isUse()) && "Expected Def or Use only!");
248
1.06k
249
1.06k
    if (MO.isDef() && 
TRI->isSuperRegisterEq(OrigDestReg, MO.getReg())996
)
250
996
        IsDefined = true;
251
1.06k
252
1.06k
    // If MO is a use of any part of the destination register but is not equal
253
1.06k
    // to OrigDestReg or one of its subregisters, we cannot use SuperDestReg.
254
1.06k
    // For example, if OrigDestReg is %al then an implicit use of %ah, %ax,
255
1.06k
    // %eax, or %rax will prevent us from using the %eax register.
256
1.06k
    if (MO.isUse() && 
!TRI->isSubRegisterEq(OrigDestReg, MO.getReg())70
&&
257
1.06k
        
TRI->regsOverlap(SuperDestReg, MO.getReg())70
)
258
35
      return false;
259
1.06k
  }
260
1.09k
  // Reg is not Imp-def'ed -> it's live both before/after the instruction.
261
1.09k
  
if (1.06k
!IsDefined1.06k
)
262
67
    return false;
263
994
264
994
  // Otherwise, the Reg is not live before the MI and the MOV can't
265
994
  // make it really live, so it's in fact dead even after the MI.
266
994
  return true;
267
994
}
268
269
MachineInstr *FixupBWInstPass::tryReplaceLoad(unsigned New32BitOpcode,
270
2.72k
                                              MachineInstr *MI) const {
271
2.72k
  unsigned NewDestReg;
272
2.72k
273
2.72k
  // We are going to try to rewrite this load to a larger zero-extending
274
2.72k
  // load.  This is safe if all portions of the 32 bit super-register
275
2.72k
  // of the original destination register, except for the original destination
276
2.72k
  // register are dead. getSuperRegDestIfDead checks that.
277
2.72k
  if (!getSuperRegDestIfDead(MI, NewDestReg))
278
4
    return nullptr;
279
2.71k
280
2.71k
  // Safe to change the instruction.
281
2.71k
  MachineInstrBuilder MIB =
282
2.71k
      BuildMI(*MF, MI->getDebugLoc(), TII->get(New32BitOpcode), NewDestReg);
283
2.71k
284
2.71k
  unsigned NumArgs = MI->getNumOperands();
285
16.9k
  for (unsigned i = 1; i < NumArgs; 
++i14.2k
)
286
14.2k
    MIB.add(MI->getOperand(i));
287
2.71k
288
2.71k
  MIB.setMemRefs(MI->memoperands());
289
2.71k
290
2.71k
  return MIB;
291
2.71k
}
292
293
3.51k
MachineInstr *FixupBWInstPass::tryReplaceCopy(MachineInstr *MI) const {
294
3.51k
  assert(MI->getNumExplicitOperands() == 2);
295
3.51k
  auto &OldDest = MI->getOperand(0);
296
3.51k
  auto &OldSrc = MI->getOperand(1);
297
3.51k
298
3.51k
  unsigned NewDestReg;
299
3.51k
  if (!getSuperRegDestIfDead(MI, NewDestReg))
300
144
    return nullptr;
301
3.36k
302
3.36k
  unsigned NewSrcReg = getX86SubSuperRegister(OldSrc.getReg(), 32);
303
3.36k
304
3.36k
  // This is only correct if we access the same subregister index: otherwise,
305
3.36k
  // we could try to replace "movb %ah, %al" with "movl %eax, %eax".
306
3.36k
  auto *TRI = &TII->getRegisterInfo();
307
3.36k
  if (TRI->getSubRegIndex(NewSrcReg, OldSrc.getReg()) !=
308
3.36k
      TRI->getSubRegIndex(NewDestReg, OldDest.getReg()))
309
35
    return nullptr;
310
3.33k
311
3.33k
  // Safe to change the instruction.
312
3.33k
  // Don't set src flags, as we don't know if we're also killing the superreg.
313
3.33k
  // However, the superregister might not be defined; make it explicit that
314
3.33k
  // we don't care about the higher bits by reading it as Undef, and adding
315
3.33k
  // an imp-use on the original subregister.
316
3.33k
  MachineInstrBuilder MIB =
317
3.33k
      BuildMI(*MF, MI->getDebugLoc(), TII->get(X86::MOV32rr), NewDestReg)
318
3.33k
          .addReg(NewSrcReg, RegState::Undef)
319
3.33k
          .addReg(OldSrc.getReg(), RegState::Implicit);
320
3.33k
321
3.33k
  // Drop imp-defs/uses that would be redundant with the new def/use.
322
3.33k
  for (auto &Op : MI->implicit_operands())
323
1.15k
    if (Op.getReg() != (Op.isDef() ? 
NewDestReg335
:
NewSrcReg816
))
324
292
      MIB.add(Op);
325
3.33k
326
3.33k
  return MIB;
327
3.33k
}
328
329
MachineInstr *FixupBWInstPass::tryReplaceInstr(MachineInstr *MI,
330
2.55M
                                               MachineBasicBlock &MBB) const {
331
2.55M
  // See if this is an instruction of the type we are currently looking for.
332
2.55M
  switch (MI->getOpcode()) {
333
2.55M
334
2.55M
  case X86::MOV8rm:
335
7.54k
    // Only replace 8 bit loads with the zero extending versions if
336
7.54k
    // in an inner most loop and not optimizing for size. This takes
337
7.54k
    // an extra byte to encode, and provides limited performance upside.
338
7.54k
    if (MachineLoop *ML = MLI->getLoopFor(&MBB))
339
2.08k
      if (ML->begin() == ML->end() && 
!OptForSize1.56k
)
340
1.56k
        return tryReplaceLoad(X86::MOVZX32rm8, MI);
341
5.98k
    break;
342
5.98k
343
5.98k
  case X86::MOV16rm:
344
1.15k
    // Always try to replace 16 bit load with 32 bit zero extending.
345
1.15k
    // Code size is the same, and there is sometimes a perf advantage
346
1.15k
    // from eliminating a false dependence on the upper portion of
347
1.15k
    // the register.
348
1.15k
    return tryReplaceLoad(X86::MOVZX32rm16, MI);
349
5.98k
350
5.98k
  case X86::MOV8rr:
351
3.51k
  case X86::MOV16rr:
352
3.51k
    // Always try to replace 8/16 bit copies with a 32 bit copy.
353
3.51k
    // Code size is either less (16) or equal (8), and there is sometimes a
354
3.51k
    // perf advantage from eliminating a false dependence on the upper portion
355
3.51k
    // of the register.
356
3.51k
    return tryReplaceCopy(MI);
357
3.51k
358
2.54M
  default:
359
2.54M
    // nothing to do here.
360
2.54M
    break;
361
2.55M
  }
362
2.55M
363
2.55M
  return nullptr;
364
2.55M
}
365
366
void FixupBWInstPass::processBasicBlock(MachineFunction &MF,
367
384k
                                        MachineBasicBlock &MBB) {
368
384k
369
384k
  // This algorithm doesn't delete the instructions it is replacing
370
384k
  // right away.  By leaving the existing instructions in place, the
371
384k
  // register liveness information doesn't change, and this makes the
372
384k
  // analysis that goes on be better than if the replaced instructions
373
384k
  // were immediately removed.
374
384k
  //
375
384k
  // This algorithm always creates a replacement instruction
376
384k
  // and notes that and the original in a data structure, until the
377
384k
  // whole BB has been analyzed.  This keeps the replacement instructions
378
384k
  // from making it seem as if the larger register might be live.
379
384k
  SmallVector<std::pair<MachineInstr *, MachineInstr *>, 8> MIReplacements;
380
384k
381
384k
  // Start computing liveness for this block. We iterate from the end to be able
382
384k
  // to update this for each instruction.
383
384k
  LiveRegs.clear();
384
384k
  // We run after PEI, so we need to AddPristinesAndCSRs.
385
384k
  LiveRegs.addLiveOuts(MBB);
386
384k
387
2.94M
  for (auto I = MBB.rbegin(); I != MBB.rend(); 
++I2.55M
) {
388
2.55M
    MachineInstr *MI = &*I;
389
2.55M
390
2.55M
    if (MachineInstr *NewMI = tryReplaceInstr(MI, MBB))
391
6.05k
      MIReplacements.push_back(std::make_pair(MI, NewMI));
392
2.55M
393
2.55M
    // We're done with this instruction, update liveness for the next one.
394
2.55M
    LiveRegs.stepBackward(*MI);
395
2.55M
  }
396
384k
397
390k
  while (!MIReplacements.empty()) {
398
6.05k
    MachineInstr *MI = MIReplacements.back().first;
399
6.05k
    MachineInstr *NewMI = MIReplacements.back().second;
400
6.05k
    MIReplacements.pop_back();
401
6.05k
    MBB.insert(MI, NewMI);
402
6.05k
    MBB.erase(MI);
403
6.05k
  }
404
384k
}