Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/X86/X86OptimizeLEAs.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- X86OptimizeLEAs.cpp - optimize usage of LEA 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
//
9
// This file defines the pass that performs some optimizations with LEA
10
// instructions in order to improve performance and code size.
11
// Currently, it does two things:
12
// 1) If there are two LEA instructions calculating addresses which only differ
13
//    by displacement inside a basic block, one of them is removed.
14
// 2) Address calculations in load and store instructions are replaced by
15
//    existing LEA def registers where possible.
16
//
17
//===----------------------------------------------------------------------===//
18
19
#include "MCTargetDesc/X86BaseInfo.h"
20
#include "X86.h"
21
#include "X86InstrInfo.h"
22
#include "X86Subtarget.h"
23
#include "llvm/ADT/DenseMap.h"
24
#include "llvm/ADT/DenseMapInfo.h"
25
#include "llvm/ADT/Hashing.h"
26
#include "llvm/ADT/SmallVector.h"
27
#include "llvm/ADT/Statistic.h"
28
#include "llvm/CodeGen/MachineBasicBlock.h"
29
#include "llvm/CodeGen/MachineFunction.h"
30
#include "llvm/CodeGen/MachineFunctionPass.h"
31
#include "llvm/CodeGen/MachineInstr.h"
32
#include "llvm/CodeGen/MachineInstrBuilder.h"
33
#include "llvm/CodeGen/MachineOperand.h"
34
#include "llvm/CodeGen/MachineRegisterInfo.h"
35
#include "llvm/CodeGen/TargetOpcodes.h"
36
#include "llvm/CodeGen/TargetRegisterInfo.h"
37
#include "llvm/IR/DebugInfoMetadata.h"
38
#include "llvm/IR/DebugLoc.h"
39
#include "llvm/IR/Function.h"
40
#include "llvm/MC/MCInstrDesc.h"
41
#include "llvm/Support/CommandLine.h"
42
#include "llvm/Support/Debug.h"
43
#include "llvm/Support/ErrorHandling.h"
44
#include "llvm/Support/MathExtras.h"
45
#include "llvm/Support/raw_ostream.h"
46
#include <cassert>
47
#include <cstdint>
48
#include <iterator>
49
50
using namespace llvm;
51
52
#define DEBUG_TYPE "x86-optimize-LEAs"
53
54
static cl::opt<bool>
55
    DisableX86LEAOpt("disable-x86-lea-opt", cl::Hidden,
56
                     cl::desc("X86: Disable LEA optimizations."),
57
                     cl::init(false));
58
59
STATISTIC(NumSubstLEAs, "Number of LEA instruction substitutions");
60
STATISTIC(NumRedundantLEAs, "Number of redundant LEA instructions removed");
61
62
/// Returns true if two machine operands are identical and they are not
63
/// physical registers.
64
static inline bool isIdenticalOp(const MachineOperand &MO1,
65
                                 const MachineOperand &MO2);
66
67
/// Returns true if two address displacement operands are of the same
68
/// type and use the same symbol/index/address regardless of the offset.
69
static bool isSimilarDispOp(const MachineOperand &MO1,
70
                            const MachineOperand &MO2);
71
72
/// Returns true if the instruction is LEA.
73
static inline bool isLEA(const MachineInstr &MI);
74
75
namespace {
76
77
/// A key based on instruction's memory operands.
78
class MemOpKey {
79
public:
80
  MemOpKey(const MachineOperand *Base, const MachineOperand *Scale,
81
           const MachineOperand *Index, const MachineOperand *Segment,
82
           const MachineOperand *Disp)
83
722k
      : Disp(Disp) {
84
722k
    Operands[0] = Base;
85
722k
    Operands[1] = Scale;
86
722k
    Operands[2] = Index;
87
722k
    Operands[3] = Segment;
88
722k
  }
89
90
19.1k
  bool operator==(const MemOpKey &Other) const {
91
19.1k
    // Addresses' bases, scales, indices and segments must be identical.
92
41.1k
    for (int i = 0; i < 4; 
++i21.9k
)
93
35.6k
      if (!isIdenticalOp(*Operands[i], *Other.Operands[i]))
94
13.7k
        return false;
95
19.1k
96
19.1k
    // Addresses' displacements don't have to be exactly the same. It only
97
19.1k
    // matters that they use the same symbol/index/address. Immediates' or
98
19.1k
    // offsets' differences will be taken care of during instruction
99
19.1k
    // substitution.
100
19.1k
    
return isSimilarDispOp(*Disp, *Other.Disp)5.47k
;
101
19.1k
  }
102
103
  // Address' base, scale, index and segment operands.
104
  const MachineOperand *Operands[4];
105
106
  // Address' displacement operand.
107
  const MachineOperand *Disp;
108
};
109
110
} // end anonymous namespace
111
112
/// Provide DenseMapInfo for MemOpKey.
113
namespace llvm {
114
115
template <> struct DenseMapInfo<MemOpKey> {
116
  using PtrInfo = DenseMapInfo<const MachineOperand *>;
117
118
383k
  static inline MemOpKey getEmptyKey() {
119
383k
    return MemOpKey(PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(),
120
383k
                    PtrInfo::getEmptyKey(), PtrInfo::getEmptyKey(),
121
383k
                    PtrInfo::getEmptyKey());
122
383k
  }
123
124
258k
  static inline MemOpKey getTombstoneKey() {
125
258k
    return MemOpKey(PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(),
126
258k
                    PtrInfo::getTombstoneKey(), PtrInfo::getTombstoneKey(),
127
258k
                    PtrInfo::getTombstoneKey());
128
258k
  }
129
130
84.3k
  static unsigned getHashValue(const MemOpKey &Val) {
131
84.3k
    // Checking any field of MemOpKey is enough to determine if the key is
132
84.3k
    // empty or tombstone.
133
84.3k
    assert(Val.Disp != PtrInfo::getEmptyKey() && "Cannot hash the empty key");
134
84.3k
    assert(Val.Disp != PtrInfo::getTombstoneKey() &&
135
84.3k
           "Cannot hash the tombstone key");
136
84.3k
137
84.3k
    hash_code Hash = hash_combine(*Val.Operands[0], *Val.Operands[1],
138
84.3k
                                  *Val.Operands[2], *Val.Operands[3]);
139
84.3k
140
84.3k
    // If the address displacement is an immediate, it should not affect the
141
84.3k
    // hash so that memory operands which differ only be immediate displacement
142
84.3k
    // would have the same hash. If the address displacement is something else,
143
84.3k
    // we should reflect symbol/index/address in the hash.
144
84.3k
    switch (Val.Disp->getType()) {
145
84.3k
    case MachineOperand::MO_Immediate:
146
37.2k
      break;
147
84.3k
    case MachineOperand::MO_ConstantPoolIndex:
148
214
    case MachineOperand::MO_JumpTableIndex:
149
214
      Hash = hash_combine(Hash, Val.Disp->getIndex());
150
214
      break;
151
214
    case MachineOperand::MO_ExternalSymbol:
152
3
      Hash = hash_combine(Hash, Val.Disp->getSymbolName());
153
3
      break;
154
46.8k
    case MachineOperand::MO_GlobalAddress:
155
46.8k
      Hash = hash_combine(Hash, Val.Disp->getGlobal());
156
46.8k
      break;
157
214
    case MachineOperand::MO_BlockAddress:
158
12
      Hash = hash_combine(Hash, Val.Disp->getBlockAddress());
159
12
      break;
160
214
    case MachineOperand::MO_MCSymbol:
161
14
      Hash = hash_combine(Hash, Val.Disp->getMCSymbol());
162
14
      break;
163
214
    case MachineOperand::MO_MachineBasicBlock:
164
8
      Hash = hash_combine(Hash, Val.Disp->getMBB());
165
8
      break;
166
214
    default:
167
0
      llvm_unreachable("Invalid address displacement operand");
168
84.3k
    }
169
84.3k
170
84.3k
    return (unsigned)Hash;
171
84.3k
  }
172
173
6.64M
  static bool isEqual(const MemOpKey &LHS, const MemOpKey &RHS) {
174
6.64M
    // Checking any field of MemOpKey is enough to determine if the key is
175
6.64M
    // empty or tombstone.
176
6.64M
    if (RHS.Disp == PtrInfo::getEmptyKey())
177
6.45M
      return LHS.Disp == PtrInfo::getEmptyKey();
178
190k
    if (RHS.Disp == PtrInfo::getTombstoneKey())
179
171k
      return LHS.Disp == PtrInfo::getTombstoneKey();
180
19.1k
    return LHS == RHS;
181
19.1k
  }
182
};
183
184
} // end namespace llvm
185
186
/// Returns a hash table key based on memory operands of \p MI. The
187
/// number of the first memory operand of \p MI is specified through \p N.
188
81.5k
static inline MemOpKey getMemOpKey(const MachineInstr &MI, unsigned N) {
189
81.5k
  assert((isLEA(MI) || MI.mayLoadOrStore()) &&
190
81.5k
         "The instruction must be a LEA, a load or a store");
191
81.5k
  return MemOpKey(&MI.getOperand(N + X86::AddrBaseReg),
192
81.5k
                  &MI.getOperand(N + X86::AddrScaleAmt),
193
81.5k
                  &MI.getOperand(N + X86::AddrIndexReg),
194
81.5k
                  &MI.getOperand(N + X86::AddrSegmentReg),
195
81.5k
                  &MI.getOperand(N + X86::AddrDisp));
196
81.5k
}
197
198
static inline bool isIdenticalOp(const MachineOperand &MO1,
199
38.6k
                                 const MachineOperand &MO2) {
200
38.6k
  return MO1.isIdenticalTo(MO2) &&
201
38.6k
         
(34.4k
!MO1.isReg()34.4k
||
202
34.4k
          
!TargetRegisterInfo::isPhysicalRegister(MO1.getReg())25.0k
);
203
38.6k
}
204
205
#ifndef NDEBUG
206
static bool isValidDispOp(const MachineOperand &MO) {
207
  return MO.isImm() || MO.isCPI() || MO.isJTI() || MO.isSymbol() ||
208
         MO.isGlobal() || MO.isBlockAddress() || MO.isMCSymbol() || MO.isMBB();
209
}
210
#endif
211
212
static bool isSimilarDispOp(const MachineOperand &MO1,
213
5.47k
                            const MachineOperand &MO2) {
214
5.47k
  assert(isValidDispOp(MO1) && isValidDispOp(MO2) &&
215
5.47k
         "Address displacement operand is not valid");
216
5.47k
  return (MO1.isImm() && 
MO2.isImm()4.49k
) ||
217
5.47k
         
(971
MO1.isCPI()971
&&
MO2.isCPI()0
&&
MO1.getIndex() == MO2.getIndex()0
) ||
218
5.47k
         
(971
MO1.isJTI()971
&&
MO2.isJTI()0
&&
MO1.getIndex() == MO2.getIndex()0
) ||
219
5.47k
         
(971
MO1.isSymbol()971
&&
MO2.isSymbol()0
&&
220
971
          
MO1.getSymbolName() == MO2.getSymbolName()0
) ||
221
5.47k
         
(971
MO1.isGlobal()971
&&
MO2.isGlobal()971
&&
222
971
          MO1.getGlobal() == MO2.getGlobal()) ||
223
5.47k
         
(882
MO1.isBlockAddress()882
&&
MO2.isBlockAddress()0
&&
224
882
          
MO1.getBlockAddress() == MO2.getBlockAddress()0
) ||
225
5.47k
         
(882
MO1.isMCSymbol()882
&&
MO2.isMCSymbol()0
&&
226
882
          
MO1.getMCSymbol() == MO2.getMCSymbol()0
) ||
227
5.47k
         
(882
MO1.isMBB()882
&&
MO2.isMBB()0
&&
MO1.getMBB() == MO2.getMBB()0
);
228
5.47k
}
229
230
3.17M
static inline bool isLEA(const MachineInstr &MI) {
231
3.17M
  unsigned Opcode = MI.getOpcode();
232
3.17M
  return 
Opcode == X86::LEA16r3.17M
|| Opcode == X86::LEA32r ||
233
3.17M
         
Opcode == X86::LEA64r3.15M
||
Opcode == X86::LEA64_32r3.09M
;
234
3.17M
}
235
236
namespace {
237
238
class OptimizeLEAPass : public MachineFunctionPass {
239
public:
240
11.3k
  OptimizeLEAPass() : MachineFunctionPass(ID) {}
241
242
146k
  StringRef getPassName() const override { return "X86 LEA Optimize"; }
243
244
  /// Loop over all of the basic blocks, replacing address
245
  /// calculations in load and store instructions, if it's already
246
  /// been calculated by LEA. Also, remove redundant LEAs.
247
  bool runOnMachineFunction(MachineFunction &MF) override;
248
249
private:
250
  using MemOpMap = DenseMap<MemOpKey, SmallVector<MachineInstr *, 16>>;
251
252
  /// Returns a distance between two instructions inside one basic block.
253
  /// Negative result means, that instructions occur in reverse order.
254
  int calcInstrDist(const MachineInstr &First, const MachineInstr &Last);
255
256
  /// Choose the best \p LEA instruction from the \p List to replace
257
  /// address calculation in \p MI instruction. Return the address displacement
258
  /// and the distance between \p MI and the chosen \p BestLEA in
259
  /// \p AddrDispShift and \p Dist.
260
  bool chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
261
                     const MachineInstr &MI, MachineInstr *&BestLEA,
262
                     int64_t &AddrDispShift, int &Dist);
263
264
  /// Returns the difference between addresses' displacements of \p MI1
265
  /// and \p MI2. The numbers of the first memory operands for the instructions
266
  /// are specified through \p N1 and \p N2.
267
  int64_t getAddrDispShift(const MachineInstr &MI1, unsigned N1,
268
                           const MachineInstr &MI2, unsigned N2) const;
269
270
  /// Returns true if the \p Last LEA instruction can be replaced by the
271
  /// \p First. The difference between displacements of the addresses calculated
272
  /// by these LEAs is returned in \p AddrDispShift. It'll be used for proper
273
  /// replacement of the \p Last LEA's uses with the \p First's def register.
274
  bool isReplaceable(const MachineInstr &First, const MachineInstr &Last,
275
                     int64_t &AddrDispShift) const;
276
277
  /// Find all LEA instructions in the basic block. Also, assign position
278
  /// numbers to all instructions in the basic block to speed up calculation of
279
  /// distance between them.
280
  void findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs);
281
282
  /// Removes redundant address calculations.
283
  bool removeRedundantAddrCalc(MemOpMap &LEAs);
284
285
  /// Replace debug value MI with a new debug value instruction using register
286
  /// VReg with an appropriate offset and DIExpression to incorporate the
287
  /// address displacement AddrDispShift. Return new debug value instruction.
288
  MachineInstr *replaceDebugValue(MachineInstr &MI, unsigned VReg,
289
                                  int64_t AddrDispShift);
290
291
  /// Removes LEAs which calculate similar addresses.
292
  bool removeRedundantLEAs(MemOpMap &LEAs);
293
294
  DenseMap<const MachineInstr *, unsigned> InstrPos;
295
296
  MachineRegisterInfo *MRI;
297
  const X86InstrInfo *TII;
298
  const X86RegisterInfo *TRI;
299
300
  static char ID;
301
};
302
303
} // end anonymous namespace
304
305
char OptimizeLEAPass::ID = 0;
306
307
11.4k
FunctionPass *llvm::createX86OptimizeLEAs() { return new OptimizeLEAPass(); }
308
309
int OptimizeLEAPass::calcInstrDist(const MachineInstr &First,
310
58
                                   const MachineInstr &Last) {
311
58
  // Both instructions must be in the same basic block and they must be
312
58
  // presented in InstrPos.
313
58
  assert(Last.getParent() == First.getParent() &&
314
58
         "Instructions are in different basic blocks");
315
58
  assert(InstrPos.find(&First) != InstrPos.end() &&
316
58
         InstrPos.find(&Last) != InstrPos.end() &&
317
58
         "Instructions' positions are undefined");
318
58
319
58
  return InstrPos[&Last] - InstrPos[&First];
320
58
}
321
322
// Find the best LEA instruction in the List to replace address recalculation in
323
// MI. Such LEA must meet these requirements:
324
// 1) The address calculated by the LEA differs only by the displacement from
325
//    the address used in MI.
326
// 2) The register class of the definition of the LEA is compatible with the
327
//    register class of the address base register of MI.
328
// 3) Displacement of the new memory operand should fit in 1 byte if possible.
329
// 4) The LEA should be as close to MI as possible, and prior to it if
330
//    possible.
331
bool OptimizeLEAPass::chooseBestLEA(const SmallVectorImpl<MachineInstr *> &List,
332
                                    const MachineInstr &MI,
333
                                    MachineInstr *&BestLEA,
334
56
                                    int64_t &AddrDispShift, int &Dist) {
335
56
  const MachineFunction *MF = MI.getParent()->getParent();
336
56
  const MCInstrDesc &Desc = MI.getDesc();
337
56
  int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags) +
338
56
                X86II::getOperandBias(Desc);
339
56
340
56
  BestLEA = nullptr;
341
56
342
56
  // Loop over all LEA instructions.
343
58
  for (auto DefMI : List) {
344
58
    // Get new address displacement.
345
58
    int64_t AddrDispShiftTemp = getAddrDispShift(MI, MemOpNo, *DefMI, 1);
346
58
347
58
    // Make sure address displacement fits 4 bytes.
348
58
    if (!isInt<32>(AddrDispShiftTemp))
349
0
      continue;
350
58
351
58
    // Check that LEA def register can be used as MI address base. Some
352
58
    // instructions can use a limited set of registers as address base, for
353
58
    // example MOV8mr_NOREX. We could constrain the register class of the LEA
354
58
    // def to suit MI, however since this case is very rare and hard to
355
58
    // reproduce in a test it's just more reliable to skip the LEA.
356
58
    if (TII->getRegClass(Desc, MemOpNo + X86::AddrBaseReg, TRI, *MF) !=
357
58
        MRI->getRegClass(DefMI->getOperand(0).getReg()))
358
0
      continue;
359
58
360
58
    // Choose the closest LEA instruction from the list, prior to MI if
361
58
    // possible. Note that we took into account resulting address displacement
362
58
    // as well. Also note that the list is sorted by the order in which the LEAs
363
58
    // occur, so the break condition is pretty simple.
364
58
    int DistTemp = calcInstrDist(*DefMI, MI);
365
58
    assert(DistTemp != 0 &&
366
58
           "The distance between two different instructions cannot be zero");
367
58
    if (DistTemp > 0 || 
BestLEA == nullptr14
) {
368
58
      // Do not update return LEA, if the current one provides a displacement
369
58
      // which fits in 1 byte, while the new candidate does not.
370
58
      if (BestLEA != nullptr && 
!isInt<8>(AddrDispShiftTemp)2
&&
371
58
          
isInt<8>(AddrDispShift)1
)
372
1
        continue;
373
57
374
57
      BestLEA = DefMI;
375
57
      AddrDispShift = AddrDispShiftTemp;
376
57
      Dist = DistTemp;
377
57
    }
378
58
379
58
    // FIXME: Maybe we should not always stop at the first LEA after MI.
380
58
    
if (57
DistTemp < 057
)
381
14
      break;
382
57
  }
383
56
384
56
  return BestLEA != nullptr;
385
56
}
386
387
// Get the difference between the addresses' displacements of the two
388
// instructions \p MI1 and \p MI2. The numbers of the first memory operands are
389
// passed through \p N1 and \p N2.
390
int64_t OptimizeLEAPass::getAddrDispShift(const MachineInstr &MI1, unsigned N1,
391
                                          const MachineInstr &MI2,
392
7.00k
                                          unsigned N2) const {
393
7.00k
  const MachineOperand &Op1 = MI1.getOperand(N1 + X86::AddrDisp);
394
7.00k
  const MachineOperand &Op2 = MI2.getOperand(N2 + X86::AddrDisp);
395
7.00k
396
7.00k
  assert(isSimilarDispOp(Op1, Op2) &&
397
7.00k
         "Address displacement operands are not compatible");
398
7.00k
399
7.00k
  // After the assert above we can be sure that both operands are of the same
400
7.00k
  // valid type and use the same symbol/index/address, thus displacement shift
401
7.00k
  // calculation is rather simple.
402
7.00k
  if (Op1.isJTI())
403
0
    return 0;
404
7.00k
  return Op1.isImm() ? 
Op1.getImm() - Op2.getImm()6.00k
405
7.00k
                     : 
Op1.getOffset() - Op2.getOffset()1.00k
;
406
7.00k
}
407
408
// Check that the Last LEA can be replaced by the First LEA. To be so,
409
// these requirements must be met:
410
// 1) Addresses calculated by LEAs differ only by displacement.
411
// 2) Def registers of LEAs belong to the same class.
412
// 3) All uses of the Last LEA def register are replaceable, thus the
413
//    register is used only as address base.
414
bool OptimizeLEAPass::isReplaceable(const MachineInstr &First,
415
                                    const MachineInstr &Last,
416
6.97k
                                    int64_t &AddrDispShift) const {
417
6.97k
  assert(isLEA(First) && isLEA(Last) &&
418
6.97k
         "The function works only with LEA instructions");
419
6.97k
420
6.97k
  // Make sure that LEA def registers belong to the same class. There may be
421
6.97k
  // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
422
6.97k
  // be used as their operands, so we must be sure that replacing one LEA
423
6.97k
  // with another won't lead to putting a wrong register in the instruction.
424
6.97k
  if (MRI->getRegClass(First.getOperand(0).getReg()) !=
425
6.97k
      MRI->getRegClass(Last.getOperand(0).getReg()))
426
30
    return false;
427
6.94k
428
6.94k
  // Get new address displacement.
429
6.94k
  AddrDispShift = getAddrDispShift(Last, 1, First, 1);
430
6.94k
431
6.94k
  // Loop over all uses of the Last LEA to check that its def register is
432
6.94k
  // used only as address base for memory accesses. If so, it can be
433
6.94k
  // replaced, otherwise - no.
434
6.98k
  for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) {
435
6.98k
    MachineInstr &MI = *MO.getParent();
436
6.98k
437
6.98k
    // Get the number of the first memory operand.
438
6.98k
    const MCInstrDesc &Desc = MI.getDesc();
439
6.98k
    int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);
440
6.98k
441
6.98k
    // If the use instruction has no memory operand - the LEA is not
442
6.98k
    // replaceable.
443
6.98k
    if (MemOpNo < 0)
444
4.70k
      return false;
445
2.27k
446
2.27k
    MemOpNo += X86II::getOperandBias(Desc);
447
2.27k
448
2.27k
    // If the address base of the use instruction is not the LEA def register -
449
2.27k
    // the LEA is not replaceable.
450
2.27k
    if (!isIdenticalOp(MI.getOperand(MemOpNo + X86::AddrBaseReg), MO))
451
2.12k
      return false;
452
147
453
147
    // If the LEA def register is used as any other operand of the use
454
147
    // instruction - the LEA is not replaceable.
455
1.04k
    
for (unsigned i = 0; 147
i < MI.getNumOperands();
i++894
)
456
894
      if (i != (unsigned)(MemOpNo + X86::AddrBaseReg) &&
457
894
          
isIdenticalOp(MI.getOperand(i), MO)747
)
458
0
        return false;
459
147
460
147
    // Check that the new address displacement will fit 4 bytes.
461
147
    if (MI.getOperand(MemOpNo + X86::AddrDisp).isImm() &&
462
147
        !isInt<32>(MI.getOperand(MemOpNo + X86::AddrDisp).getImm() +
463
147
                   AddrDispShift))
464
0
      return false;
465
147
  }
466
6.94k
467
6.94k
  
return true112
;
468
6.94k
}
469
470
397k
void OptimizeLEAPass::findLEAs(const MachineBasicBlock &MBB, MemOpMap &LEAs) {
471
397k
  unsigned Pos = 0;
472
3.17M
  for (auto &MI : MBB) {
473
3.17M
    // Assign the position number to the instruction. Note that we are going to
474
3.17M
    // move some instructions during the optimization however there will never
475
3.17M
    // be a need to move two instructions before any selected instruction. So to
476
3.17M
    // avoid multiple positions' updates during moves we just increase position
477
3.17M
    // counter by two leaving a free space for instructions which will be moved.
478
3.17M
    InstrPos[&MI] = Pos += 2;
479
3.17M
480
3.17M
    if (isLEA(MI))
481
81.2k
      LEAs[getMemOpKey(MI, 1)].push_back(const_cast<MachineInstr *>(&MI));
482
3.17M
  }
483
397k
}
484
485
// Try to find load and store instructions which recalculate addresses already
486
// calculated by some LEA and replace their memory operands with its def
487
// register.
488
221
bool OptimizeLEAPass::removeRedundantAddrCalc(MemOpMap &LEAs) {
489
221
  bool Changed = false;
490
221
491
221
  assert(!LEAs.empty());
492
221
  MachineBasicBlock *MBB = (*LEAs.begin()->second.begin())->getParent();
493
221
494
221
  // Process all instructions in basic block.
495
3.55k
  for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
496
3.33k
    MachineInstr &MI = *I++;
497
3.33k
498
3.33k
    // Instruction must be load or store.
499
3.33k
    if (!MI.mayLoadOrStore())
500
3.02k
      continue;
501
304
502
304
    // Get the number of the first memory operand.
503
304
    const MCInstrDesc &Desc = MI.getDesc();
504
304
    int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);
505
304
506
304
    // If instruction has no memory operand - skip it.
507
304
    if (MemOpNo < 0)
508
16
      continue;
509
288
510
288
    MemOpNo += X86II::getOperandBias(Desc);
511
288
512
288
    // Do not call chooseBestLEA if there was no matching LEA
513
288
    auto Insns = LEAs.find(getMemOpKey(MI, MemOpNo));
514
288
    if (Insns == LEAs.end())
515
232
      continue;
516
56
517
56
    // Get the best LEA instruction to replace address calculation.
518
56
    MachineInstr *DefMI;
519
56
    int64_t AddrDispShift;
520
56
    int Dist;
521
56
    if (!chooseBestLEA(Insns->second, MI, DefMI, AddrDispShift, Dist))
522
0
      continue;
523
56
524
56
    // If LEA occurs before current instruction, we can freely replace
525
56
    // the instruction. If LEA occurs after, we can lift LEA above the
526
56
    // instruction and this way to be able to replace it. Since LEA and the
527
56
    // instruction have similar memory operands (thus, the same def
528
56
    // instructions for these operands), we can always do that, without
529
56
    // worries of using registers before their defs.
530
56
    if (Dist < 0) {
531
14
      DefMI->removeFromParent();
532
14
      MBB->insert(MachineBasicBlock::iterator(&MI), DefMI);
533
14
      InstrPos[DefMI] = InstrPos[&MI] - 1;
534
14
535
14
      // Make sure the instructions' position numbers are sane.
536
14
      assert(((InstrPos[DefMI] == 1 &&
537
14
               MachineBasicBlock::iterator(DefMI) == MBB->begin()) ||
538
14
              InstrPos[DefMI] >
539
14
                  InstrPos[&*std::prev(MachineBasicBlock::iterator(DefMI))]) &&
540
14
             "Instruction positioning is broken");
541
14
    }
542
56
543
56
    // Since we can possibly extend register lifetime, clear kill flags.
544
56
    MRI->clearKillFlags(DefMI->getOperand(0).getReg());
545
56
546
56
    ++NumSubstLEAs;
547
56
    LLVM_DEBUG(dbgs() << "OptimizeLEAs: Candidate to replace: "; MI.dump(););
548
56
549
56
    // Change instruction operands.
550
56
    MI.getOperand(MemOpNo + X86::AddrBaseReg)
551
56
        .ChangeToRegister(DefMI->getOperand(0).getReg(), false);
552
56
    MI.getOperand(MemOpNo + X86::AddrScaleAmt).ChangeToImmediate(1);
553
56
    MI.getOperand(MemOpNo + X86::AddrIndexReg)
554
56
        .ChangeToRegister(X86::NoRegister, false);
555
56
    MI.getOperand(MemOpNo + X86::AddrDisp).ChangeToImmediate(AddrDispShift);
556
56
    MI.getOperand(MemOpNo + X86::AddrSegmentReg)
557
56
        .ChangeToRegister(X86::NoRegister, false);
558
56
559
56
    LLVM_DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
560
56
561
56
    Changed = true;
562
56
  }
563
221
564
221
  return Changed;
565
221
}
566
567
MachineInstr *OptimizeLEAPass::replaceDebugValue(MachineInstr &MI,
568
                                                 unsigned VReg,
569
1
                                                 int64_t AddrDispShift) {
570
1
  DIExpression *Expr = const_cast<DIExpression *>(MI.getDebugExpression());
571
1
  if (AddrDispShift != 0)
572
1
    Expr = DIExpression::prepend(Expr, DIExpression::StackValue, AddrDispShift);
573
1
574
1
  // Replace DBG_VALUE instruction with modified version.
575
1
  MachineBasicBlock *MBB = MI.getParent();
576
1
  DebugLoc DL = MI.getDebugLoc();
577
1
  bool IsIndirect = MI.isIndirectDebugValue();
578
1
  const MDNode *Var = MI.getDebugVariable();
579
1
  if (IsIndirect)
580
1
    assert(MI.getOperand(1).getImm() == 0 && "DBG_VALUE with nonzero offset");
581
1
  return BuildMI(*MBB, MBB->erase(&MI), DL, TII->get(TargetOpcode::DBG_VALUE),
582
1
                 IsIndirect, VReg, Var, Expr);
583
1
}
584
585
// Try to find similar LEAs in the list and replace one with another.
586
48.3k
bool OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) {
587
48.3k
  bool Changed = false;
588
48.3k
589
48.3k
  // Loop over all entries in the table.
590
76.6k
  for (auto &E : LEAs) {
591
76.6k
    auto &List = E.second;
592
76.6k
593
76.6k
    // Loop over all LEA pairs.
594
76.6k
    auto I1 = List.begin();
595
157k
    while (I1 != List.end()) {
596
81.1k
      MachineInstr &First = **I1;
597
81.1k
      auto I2 = std::next(I1);
598
88.0k
      while (I2 != List.end()) {
599
6.97k
        MachineInstr &Last = **I2;
600
6.97k
        int64_t AddrDispShift;
601
6.97k
602
6.97k
        // LEAs should be in occurrence order in the list, so we can freely
603
6.97k
        // replace later LEAs with earlier ones.
604
6.97k
        assert(calcInstrDist(First, Last) > 0 &&
605
6.97k
               "LEAs must be in occurrence order in the list");
606
6.97k
607
6.97k
        // Check that the Last LEA instruction can be replaced by the First.
608
6.97k
        if (!isReplaceable(First, Last, AddrDispShift)) {
609
6.86k
          ++I2;
610
6.86k
          continue;
611
6.86k
        }
612
112
613
112
        // Loop over all uses of the Last LEA and update their operands. Note
614
112
        // that the correctness of this has already been checked in the
615
112
        // isReplaceable function.
616
112
        unsigned FirstVReg = First.getOperand(0).getReg();
617
112
        unsigned LastVReg = Last.getOperand(0).getReg();
618
112
        for (auto UI = MRI->use_begin(LastVReg), UE = MRI->use_end();
619
260
             UI != UE;) {
620
148
          MachineOperand &MO = *UI++;
621
148
          MachineInstr &MI = *MO.getParent();
622
148
623
148
          if (MI.isDebugValue()) {
624
1
            // Replace DBG_VALUE instruction with modified version using the
625
1
            // register from the replacing LEA and the address displacement
626
1
            // between the LEA instructions.
627
1
            replaceDebugValue(MI, FirstVReg, AddrDispShift);
628
1
            continue;
629
1
          }
630
147
631
147
          // Get the number of the first memory operand.
632
147
          const MCInstrDesc &Desc = MI.getDesc();
633
147
          int MemOpNo =
634
147
              X86II::getMemoryOperandNo(Desc.TSFlags) +
635
147
              X86II::getOperandBias(Desc);
636
147
637
147
          // Update address base.
638
147
          MO.setReg(FirstVReg);
639
147
640
147
          // Update address disp.
641
147
          MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp);
642
147
          if (Op.isImm())
643
147
            Op.setImm(Op.getImm() + AddrDispShift);
644
0
          else if (!Op.isJTI())
645
0
            Op.setOffset(Op.getOffset() + AddrDispShift);
646
147
        }
647
112
648
112
        // Since we can possibly extend register lifetime, clear kill flags.
649
112
        MRI->clearKillFlags(FirstVReg);
650
112
651
112
        ++NumRedundantLEAs;
652
112
        LLVM_DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: ";
653
112
                   Last.dump(););
654
112
655
112
        // By this moment, all of the Last LEA's uses must be replaced. So we
656
112
        // can freely remove it.
657
112
        assert(MRI->use_empty(LastVReg) &&
658
112
               "The LEA's def register must have no uses");
659
112
        Last.eraseFromParent();
660
112
661
112
        // Erase removed LEA from the list.
662
112
        I2 = List.erase(I2);
663
112
664
112
        Changed = true;
665
112
      }
666
81.1k
      ++I1;
667
81.1k
    }
668
76.6k
  }
669
48.3k
670
48.3k
  return Changed;
671
48.3k
}
672
673
135k
bool OptimizeLEAPass::runOnMachineFunction(MachineFunction &MF) {
674
135k
  bool Changed = false;
675
135k
676
135k
  if (DisableX86LEAOpt || 
skipFunction(MF.getFunction())135k
)
677
211
    return false;
678
135k
679
135k
  MRI = &MF.getRegInfo();
680
135k
  TII = MF.getSubtarget<X86Subtarget>().getInstrInfo();
681
135k
  TRI = MF.getSubtarget<X86Subtarget>().getRegisterInfo();
682
135k
683
135k
  // Process all basic blocks.
684
397k
  for (auto &MBB : MF) {
685
397k
    MemOpMap LEAs;
686
397k
    InstrPos.clear();
687
397k
688
397k
    // Find all LEA instructions in basic block.
689
397k
    findLEAs(MBB, LEAs);
690
397k
691
397k
    // If current basic block has no LEAs, move on to the next one.
692
397k
    if (LEAs.empty())
693
348k
      continue;
694
48.3k
695
48.3k
    // Remove redundant LEA instructions.
696
48.3k
    Changed |= removeRedundantLEAs(LEAs);
697
48.3k
698
48.3k
    // Remove redundant address calculations. Do it only for -Os/-Oz since only
699
48.3k
    // a code size gain is expected from this part of the pass.
700
48.3k
    if (MF.getFunction().hasOptSize())
701
221
      Changed |= removeRedundantAddrCalc(LEAs);
702
48.3k
  }
703
135k
704
135k
  return Changed;
705
135k
}