Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/MachineCopyPropagation.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MachineCopyPropagation.cpp - Machine Copy Propagation Pass ---------===//
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
//
10
// This is an extremely simple MachineInstr-level copy propagation pass.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/ADT/DenseMap.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SetVector.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/ADT/iterator_range.h"
20
#include "llvm/CodeGen/MachineBasicBlock.h"
21
#include "llvm/CodeGen/MachineFunction.h"
22
#include "llvm/CodeGen/MachineFunctionPass.h"
23
#include "llvm/CodeGen/MachineInstr.h"
24
#include "llvm/CodeGen/MachineOperand.h"
25
#include "llvm/CodeGen/MachineRegisterInfo.h"
26
#include "llvm/MC/MCRegisterInfo.h"
27
#include "llvm/Pass.h"
28
#include "llvm/Support/Debug.h"
29
#include "llvm/Support/raw_ostream.h"
30
#include "llvm/Target/TargetInstrInfo.h"
31
#include "llvm/Target/TargetRegisterInfo.h"
32
#include "llvm/Target/TargetSubtargetInfo.h"
33
#include <cassert>
34
#include <iterator>
35
36
using namespace llvm;
37
38
#define DEBUG_TYPE "machine-cp"
39
40
STATISTIC(NumDeletes, "Number of dead copies deleted");
41
42
namespace {
43
44
using RegList = SmallVector<unsigned, 4>;
45
using SourceMap = DenseMap<unsigned, RegList>;
46
using Reg2MIMap = DenseMap<unsigned, MachineInstr *>;
47
48
  class MachineCopyPropagation : public MachineFunctionPass {
49
    const TargetRegisterInfo *TRI;
50
    const TargetInstrInfo *TII;
51
    const MachineRegisterInfo *MRI;
52
53
  public:
54
    static char ID; // Pass identification, replacement for typeid
55
56
31.8k
    MachineCopyPropagation() : MachineFunctionPass(ID) {
57
31.8k
      initializeMachineCopyPropagationPass(*PassRegistry::getPassRegistry());
58
31.8k
    }
59
60
31.8k
    void getAnalysisUsage(AnalysisUsage &AU) const override {
61
31.8k
      AU.setPreservesCFG();
62
31.8k
      MachineFunctionPass::getAnalysisUsage(AU);
63
31.8k
    }
64
65
    bool runOnMachineFunction(MachineFunction &MF) override;
66
67
31.8k
    MachineFunctionProperties getRequiredProperties() const override {
68
31.8k
      return MachineFunctionProperties().set(
69
31.8k
          MachineFunctionProperties::Property::NoVRegs);
70
31.8k
    }
71
72
  private:
73
    void ClobberRegister(unsigned Reg);
74
    void ReadRegister(unsigned Reg);
75
    void CopyPropagateBlock(MachineBasicBlock &MBB);
76
    bool eraseIfRedundant(MachineInstr &Copy, unsigned Src, unsigned Def);
77
78
    /// Candidates for deletion.
79
    SmallSetVector<MachineInstr*, 8> MaybeDeadCopies;
80
81
    /// Def -> available copies map.
82
    Reg2MIMap AvailCopyMap;
83
84
    /// Def -> copies map.
85
    Reg2MIMap CopyMap;
86
87
    /// Src -> Def map
88
    SourceMap SrcMap;
89
90
    bool Changed;
91
  };
92
93
} // end anonymous namespace
94
95
char MachineCopyPropagation::ID = 0;
96
97
char &llvm::MachineCopyPropagationID = MachineCopyPropagation::ID;
98
99
INITIALIZE_PASS(MachineCopyPropagation, DEBUG_TYPE,
100
                "Machine Copy Propagation Pass", false, false)
101
102
/// Remove any entry in \p Map where the register is a subregister or equal to
103
/// a register contained in \p Regs.
104
static void removeRegsFromMap(Reg2MIMap &Map, const RegList &Regs,
105
1.51M
                              const TargetRegisterInfo &TRI) {
106
1.53M
  for (unsigned Reg : Regs) {
107
1.53M
    // Source of copy is no longer available for propagation.
108
4.43M
    for (MCSubRegIterator SR(Reg, &TRI, true); 
SR.isValid()4.43M
;
++SR2.89M
)
109
2.89M
      Map.erase(*SR);
110
1.53M
  }
111
1.51M
}
112
113
/// Remove any entry in \p Map that is marked clobbered in \p RegMask.
114
/// The map will typically have a lot fewer entries than the regmask clobbers,
115
/// so this is more efficient than iterating the clobbered registers and calling
116
/// ClobberRegister() on them.
117
static void removeClobberedRegsFromMap(Reg2MIMap &Map,
118
4.50M
                                       const MachineOperand &RegMask) {
119
19.8M
  for (Reg2MIMap::iterator I = Map.begin(), E = Map.end(), Next; I != E;
120
15.3M
       
I = Next15.3M
) {
121
15.3M
    Next = std::next(I);
122
15.3M
    unsigned Reg = I->first;
123
15.3M
    if (RegMask.clobbersPhysReg(Reg))
124
8.63M
      Map.erase(I);
125
15.3M
  }
126
4.50M
}
127
128
24.0M
void MachineCopyPropagation::ClobberRegister(unsigned Reg) {
129
168M
  for (MCRegAliasIterator AI(Reg, TRI, true); 
AI.isValid()168M
;
++AI144M
) {
130
144M
    CopyMap.erase(*AI);
131
144M
    AvailCopyMap.erase(*AI);
132
144M
133
144M
    SourceMap::iterator SI = SrcMap.find(*AI);
134
144M
    if (
SI != SrcMap.end()144M
) {
135
832k
      removeRegsFromMap(AvailCopyMap, SI->second, *TRI);
136
832k
      SrcMap.erase(SI);
137
832k
    }
138
144M
  }
139
24.0M
}
140
141
32.8M
void MachineCopyPropagation::ReadRegister(unsigned Reg) {
142
32.8M
  // If 'Reg' is defined by a copy, the copy is no longer a candidate
143
32.8M
  // for elimination.
144
225M
  for (MCRegAliasIterator AI(Reg, TRI, true); 
AI.isValid()225M
;
++AI193M
) {
145
193M
    Reg2MIMap::iterator CI = CopyMap.find(*AI);
146
193M
    if (
CI != CopyMap.end()193M
) {
147
6.73M
      DEBUG(dbgs() << "MCP: Copy is used - not dead: "; CI->second->dump());
148
6.73M
      MaybeDeadCopies.remove(CI->second);
149
6.73M
    }
150
193M
  }
151
32.8M
}
152
153
/// Return true if \p PreviousCopy did copy register \p Src to register \p Def.
154
/// This fact may have been obscured by sub register usage or may not be true at
155
/// all even though Src and Def are subregisters of the registers used in
156
/// PreviousCopy. e.g.
157
/// isNopCopy("ecx = COPY eax", AX, CX) == true
158
/// isNopCopy("ecx = COPY eax", AH, CL) == false
159
static bool isNopCopy(const MachineInstr &PreviousCopy, unsigned Src,
160
173k
                      unsigned Def, const TargetRegisterInfo *TRI) {
161
173k
  unsigned PreviousSrc = PreviousCopy.getOperand(1).getReg();
162
173k
  unsigned PreviousDef = PreviousCopy.getOperand(0).getReg();
163
173k
  if (
Src == PreviousSrc173k
) {
164
154k
    assert(Def == PreviousDef);
165
154k
    return true;
166
154k
  }
167
19.6k
  
if (19.6k
!TRI->isSubRegister(PreviousSrc, Src)19.6k
)
168
19.6k
    return false;
169
47
  unsigned SubIdx = TRI->getSubRegIndex(PreviousSrc, Src);
170
47
  return SubIdx == TRI->getSubRegIndex(PreviousDef, Def);
171
47
}
172
173
/// Remove instruction \p Copy if there exists a previous copy that copies the
174
/// register \p Src to the register \p Def; This may happen indirectly by
175
/// copying the super registers.
176
bool MachineCopyPropagation::eraseIfRedundant(MachineInstr &Copy, unsigned Src,
177
7.60M
                                              unsigned Def) {
178
7.60M
  // Avoid eliminating a copy from/to a reserved registers as we cannot predict
179
7.60M
  // the value (Example: The sparc zero register is writable but stays zero).
180
7.60M
  if (
MRI->isReserved(Src) || 7.60M
MRI->isReserved(Def)7.10M
)
181
1.00M
    return false;
182
6.60M
183
6.60M
  // Search for an existing copy.
184
6.60M
  Reg2MIMap::iterator CI = AvailCopyMap.find(Def);
185
6.60M
  if (CI == AvailCopyMap.end())
186
6.42M
    return false;
187
173k
188
173k
  // Check that the existing copy uses the correct sub registers.
189
173k
  MachineInstr &PrevCopy = *CI->second;
190
173k
  if (!isNopCopy(PrevCopy, Src, Def, TRI))
191
19.6k
    return false;
192
154k
193
154k
  
DEBUG154k
(dbgs() << "MCP: copy is a NOP, removing: "; Copy.dump());
194
154k
195
154k
  // Copy was redundantly redefining either Src or Def. Remove earlier kill
196
154k
  // flags between Copy and PrevCopy because the value will be reused now.
197
154k
  assert(Copy.isCopy());
198
154k
  unsigned CopyDef = Copy.getOperand(0).getReg();
199
154k
  assert(CopyDef == Src || CopyDef == Def);
200
154k
  for (MachineInstr &MI :
201
154k
       make_range(PrevCopy.getIterator(), Copy.getIterator()))
202
639k
    MI.clearRegisterKills(CopyDef, TRI);
203
7.60M
204
7.60M
  Copy.eraseFromParent();
205
7.60M
  Changed = true;
206
7.60M
  ++NumDeletes;
207
7.60M
  return true;
208
7.60M
}
209
210
3.97M
void MachineCopyPropagation::CopyPropagateBlock(MachineBasicBlock &MBB) {
211
3.97M
  DEBUG(dbgs() << "MCP: CopyPropagateBlock " << MBB.getName() << "\n");
212
3.97M
213
28.1M
  for (MachineBasicBlock::iterator I = MBB.begin(), E = MBB.end(); 
I != E28.1M
; ) {
214
24.2M
    MachineInstr *MI = &*I;
215
24.2M
    ++I;
216
24.2M
217
24.2M
    if (
MI->isCopy()24.2M
) {
218
3.87M
      unsigned Def = MI->getOperand(0).getReg();
219
3.87M
      unsigned Src = MI->getOperand(1).getReg();
220
3.87M
221
3.87M
      assert(!TargetRegisterInfo::isVirtualRegister(Def) &&
222
3.87M
             !TargetRegisterInfo::isVirtualRegister(Src) &&
223
3.87M
             "MachineCopyPropagation should be run after register allocation!");
224
3.87M
225
3.87M
      // The two copies cancel out and the source of the first copy
226
3.87M
      // hasn't been overridden, eliminate the second one. e.g.
227
3.87M
      //  %ECX<def> = COPY %EAX
228
3.87M
      //  ... nothing clobbered EAX.
229
3.87M
      //  %EAX<def> = COPY %ECX
230
3.87M
      // =>
231
3.87M
      //  %ECX<def> = COPY %EAX
232
3.87M
      //
233
3.87M
      // or
234
3.87M
      //
235
3.87M
      //  %ECX<def> = COPY %EAX
236
3.87M
      //  ... nothing clobbered EAX.
237
3.87M
      //  %ECX<def> = COPY %EAX
238
3.87M
      // =>
239
3.87M
      //  %ECX<def> = COPY %EAX
240
3.87M
      if (
eraseIfRedundant(*MI, Def, Src) || 3.87M
eraseIfRedundant(*MI, Src, Def)3.72M
)
241
154k
        continue;
242
3.72M
243
3.72M
      // If Src is defined by a previous copy, the previous copy cannot be
244
3.72M
      // eliminated.
245
3.72M
      ReadRegister(Src);
246
155k
      for (const MachineOperand &MO : MI->implicit_operands()) {
247
155k
        if (
!MO.isReg() || 155k
!MO.readsReg()155k
)
248
97.0k
          continue;
249
58.4k
        unsigned Reg = MO.getReg();
250
58.4k
        if (!Reg)
251
0
          continue;
252
58.4k
        ReadRegister(Reg);
253
58.4k
      }
254
3.72M
255
3.72M
      DEBUG(dbgs() << "MCP: Copy is a deletion candidate: "; MI->dump());
256
3.72M
257
3.72M
      // Copy is now a candidate for deletion.
258
3.72M
      if (!MRI->isReserved(Def))
259
3.72M
        MaybeDeadCopies.insert(MI);
260
3.72M
261
3.72M
      // If 'Def' is previously source of another copy, then this earlier copy's
262
3.72M
      // source is no longer available. e.g.
263
3.72M
      // %xmm9<def> = copy %xmm2
264
3.72M
      // ...
265
3.72M
      // %xmm2<def> = copy %xmm0
266
3.72M
      // ...
267
3.72M
      // %xmm2<def> = copy %xmm9
268
3.72M
      ClobberRegister(Def);
269
155k
      for (const MachineOperand &MO : MI->implicit_operands()) {
270
155k
        if (
!MO.isReg() || 155k
!MO.isDef()155k
)
271
58.4k
          continue;
272
97.0k
        unsigned Reg = MO.getReg();
273
97.0k
        if (!Reg)
274
0
          continue;
275
97.0k
        ClobberRegister(Reg);
276
97.0k
      }
277
3.72M
278
3.72M
      // Remember Def is defined by the copy.
279
10.7M
      for (MCSubRegIterator SR(Def, TRI, /*IncludeSelf=*/true); SR.isValid();
280
6.98M
           
++SR6.98M
) {
281
6.98M
        CopyMap[*SR] = MI;
282
6.98M
        AvailCopyMap[*SR] = MI;
283
6.98M
      }
284
3.72M
285
3.72M
      // Remember source that's copied to Def. Once it's clobbered, then
286
3.72M
      // it's no longer available for copy propagation.
287
3.72M
      RegList &DestList = SrcMap[Src];
288
3.72M
      if (!is_contained(DestList, Def))
289
3.05M
        DestList.push_back(Def);
290
3.87M
291
3.87M
      continue;
292
3.87M
    }
293
20.3M
294
20.3M
    // Not a copy.
295
20.3M
    SmallVector<unsigned, 2> Defs;
296
20.3M
    const MachineOperand *RegMask = nullptr;
297
75.4M
    for (const MachineOperand &MO : MI->operands()) {
298
75.4M
      if (MO.isRegMask())
299
2.25M
        RegMask = &MO;
300
75.4M
      if (!MO.isReg())
301
25.3M
        continue;
302
50.0M
      unsigned Reg = MO.getReg();
303
50.0M
      if (!Reg)
304
734k
        continue;
305
49.3M
306
50.0M
      assert(!TargetRegisterInfo::isVirtualRegister(Reg) &&
307
49.3M
             "MachineCopyPropagation should be run after register allocation!");
308
49.3M
309
49.3M
      if (
MO.isDef()49.3M
) {
310
20.2M
        Defs.push_back(Reg);
311
20.2M
        continue;
312
29.0M
      } else 
if (29.0M
MO.readsReg()29.0M
)
313
29.0M
        ReadRegister(Reg);
314
75.4M
    }
315
20.3M
316
20.3M
    // The instruction has a register mask operand which means that it clobbers
317
20.3M
    // a large set of registers.  Treat clobbered registers the same way as
318
20.3M
    // defined registers.
319
20.3M
    if (
RegMask20.3M
) {
320
2.25M
      // Erase any MaybeDeadCopies whose destination register is clobbered.
321
2.25M
      for (SmallSetVector<MachineInstr *, 8>::iterator DI =
322
2.25M
               MaybeDeadCopies.begin();
323
3.63M
           
DI != MaybeDeadCopies.end()3.63M
;) {
324
1.38M
        MachineInstr *MaybeDead = *DI;
325
1.38M
        unsigned Reg = MaybeDead->getOperand(0).getReg();
326
1.38M
        assert(!MRI->isReserved(Reg));
327
1.38M
328
1.38M
        if (
!RegMask->clobbersPhysReg(Reg)1.38M
) {
329
1.38M
          ++DI;
330
1.38M
          continue;
331
1.38M
        }
332
42
333
42
        
DEBUG42
(dbgs() << "MCP: Removing copy due to regmask clobbering: ";
334
42
              MaybeDead->dump());
335
42
336
42
        // erase() will return the next valid iterator pointing to the next
337
42
        // element after the erased one.
338
42
        DI = MaybeDeadCopies.erase(DI);
339
42
        MaybeDead->eraseFromParent();
340
42
        Changed = true;
341
42
        ++NumDeletes;
342
42
      }
343
2.25M
344
2.25M
      removeClobberedRegsFromMap(AvailCopyMap, *RegMask);
345
2.25M
      removeClobberedRegsFromMap(CopyMap, *RegMask);
346
2.25M
      for (SourceMap::iterator I = SrcMap.begin(), E = SrcMap.end(), Next;
347
6.43M
           
I != E6.43M
;
I = Next4.18M
) {
348
4.18M
        Next = std::next(I);
349
4.18M
        if (
RegMask->clobbersPhysReg(I->first)4.18M
) {
350
678k
          removeRegsFromMap(AvailCopyMap, I->second, *TRI);
351
678k
          SrcMap.erase(I);
352
678k
        }
353
4.18M
      }
354
2.25M
    }
355
20.3M
356
20.3M
    // Any previous copy definition or reading the Defs is no longer available.
357
20.3M
    for (unsigned Reg : Defs)
358
20.2M
      ClobberRegister(Reg);
359
24.2M
  }
360
3.97M
361
3.97M
  // If MBB doesn't have successors, delete the copies whose defs are not used.
362
3.97M
  // If MBB does have successors, then conservative assume the defs are live-out
363
3.97M
  // since we don't want to trust live-in lists.
364
3.97M
  if (
MBB.succ_empty()3.97M
) {
365
5.70k
    for (MachineInstr *MaybeDead : MaybeDeadCopies) {
366
5.70k
      assert(!MRI->isReserved(MaybeDead->getOperand(0).getReg()));
367
5.70k
      MaybeDead->eraseFromParent();
368
5.70k
      Changed = true;
369
5.70k
      ++NumDeletes;
370
5.70k
    }
371
804k
  }
372
3.97M
373
3.97M
  MaybeDeadCopies.clear();
374
3.97M
  AvailCopyMap.clear();
375
3.97M
  CopyMap.clear();
376
3.97M
  SrcMap.clear();
377
3.97M
}
378
379
587k
bool MachineCopyPropagation::runOnMachineFunction(MachineFunction &MF) {
380
587k
  if (skipFunction(*MF.getFunction()))
381
44
    return false;
382
587k
383
587k
  Changed = false;
384
587k
385
587k
  TRI = MF.getSubtarget().getRegisterInfo();
386
587k
  TII = MF.getSubtarget().getInstrInfo();
387
587k
  MRI = &MF.getRegInfo();
388
587k
389
587k
  for (MachineBasicBlock &MBB : MF)
390
3.97M
    CopyPropagateBlock(MBB);
391
587k
392
587k
  return Changed;
393
587k
}