Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LivePhysRegs.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
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 file implements the LivePhysRegs utility for tracking liveness of
11
// physical registers across machine instructions in forward or backward order.
12
// A more detailed description can be found in the corresponding header file.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/CodeGen/LivePhysRegs.h"
17
#include "llvm/CodeGen/MachineFrameInfo.h"
18
#include "llvm/CodeGen/MachineFunction.h"
19
#include "llvm/CodeGen/MachineInstrBundle.h"
20
#include "llvm/CodeGen/MachineRegisterInfo.h"
21
#include "llvm/Support/Debug.h"
22
#include "llvm/Support/raw_ostream.h"
23
using namespace llvm;
24
25
26
/// \brief Remove all registers from the set that get clobbered by the register
27
/// mask.
28
/// The clobbers set will be the list of live registers clobbered
29
/// by the regmask.
30
void LivePhysRegs::removeRegsInMask(const MachineOperand &MO,
31
282k
        SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers) {
32
282k
  SparseSet<unsigned>::iterator LRI = LiveRegs.begin();
33
7.85M
  while (
LRI != LiveRegs.end()7.85M
) {
34
7.56M
    if (
MO.clobbersPhysReg(*LRI)7.56M
) {
35
488k
      if (Clobbers)
36
467
        Clobbers->push_back(std::make_pair(*LRI, &MO));
37
488k
      LRI = LiveRegs.erase(LRI);
38
488k
    } else
39
7.08M
      ++LRI;
40
7.56M
  }
41
282k
}
42
43
/// Remove defined registers and regmask kills from the set.
44
2.30M
void LivePhysRegs::removeDefs(const MachineInstr &MI) {
45
11.0M
  for (ConstMIBundleOperands O(MI); 
O.isValid()11.0M
;
++O8.70M
) {
46
8.70M
    if (
O->isReg()8.70M
) {
47
6.45M
      if (!O->isDef())
48
3.64M
        continue;
49
2.80M
      unsigned Reg = O->getReg();
50
2.80M
      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
51
7
        continue;
52
2.80M
      removeReg(Reg);
53
8.70M
    } else 
if (2.24M
O->isRegMask()2.24M
)
54
265k
      removeRegsInMask(*O);
55
8.70M
  }
56
2.30M
}
57
58
/// Add uses to the set.
59
2.30M
void LivePhysRegs::addUses(const MachineInstr &MI) {
60
11.0M
  for (ConstMIBundleOperands O(MI); 
O.isValid()11.0M
;
++O8.70M
) {
61
8.70M
    if (
!O->isReg() || 8.70M
!O->readsReg()6.45M
)
62
5.11M
      continue;
63
3.59M
    unsigned Reg = O->getReg();
64
3.59M
    if (!TargetRegisterInfo::isPhysicalRegister(Reg))
65
507k
      continue;
66
3.08M
    addReg(Reg);
67
3.08M
  }
68
2.30M
}
69
70
/// Simulates liveness when stepping backwards over an instruction(bundle):
71
/// Remove Defs, add uses. This is the recommended way of calculating liveness.
72
2.28M
void LivePhysRegs::stepBackward(const MachineInstr &MI) {
73
2.28M
  // Remove defined registers and regmask kills from the set.
74
2.28M
  removeDefs(MI);
75
2.28M
76
2.28M
  // Add uses to the set.
77
2.28M
  addUses(MI);
78
2.28M
}
79
80
/// Simulates liveness when stepping forward over an instruction(bundle): Remove
81
/// killed-uses, add defs. This is the not recommended way, because it depends
82
/// on accurate kill flags. If possible use stepBackward() instead of this
83
/// function.
84
void LivePhysRegs::stepForward(const MachineInstr &MI,
85
8.05k
        SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> &Clobbers) {
86
8.05k
  // Remove killed registers from the set.
87
50.5k
  for (ConstMIBundleOperands O(MI); 
O.isValid()50.5k
;
++O42.5k
) {
88
42.5k
    if (
O->isReg()42.5k
) {
89
27.0k
      unsigned Reg = O->getReg();
90
27.0k
      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
91
1.58k
        continue;
92
25.4k
      
if (25.4k
O->isDef()25.4k
) {
93
8.05k
        // Note, dead defs are still recorded.  The caller should decide how to
94
8.05k
        // handle them.
95
8.05k
        Clobbers.push_back(std::make_pair(Reg, &*O));
96
25.4k
      } else {
97
17.4k
        if (!O->isKill())
98
13.2k
          continue;
99
17.4k
        assert(O->isUse());
100
4.21k
        removeReg(Reg);
101
4.21k
      }
102
42.5k
    } else 
if (15.4k
O->isRegMask()15.4k
)
103
308
      removeRegsInMask(*O, &Clobbers);
104
42.5k
  }
105
8.05k
106
8.05k
  // Add defs to the set.
107
24.9k
  for (auto Reg : Clobbers) {
108
24.9k
    // Skip dead defs.  They shouldn't be added to the set.
109
24.9k
    if (
Reg.second->isReg() && 24.9k
Reg.second->isDead()22.6k
)
110
1.38k
      continue;
111
23.5k
    addReg(Reg.first);
112
23.5k
  }
113
8.05k
}
114
115
/// Prin the currently live registers to OS.
116
0
void LivePhysRegs::print(raw_ostream &OS) const {
117
0
  OS << "Live Registers:";
118
0
  if (
!TRI0
) {
119
0
    OS << " (uninitialized)\n";
120
0
    return;
121
0
  }
122
0
123
0
  
if (0
empty()0
) {
124
0
    OS << " (empty)\n";
125
0
    return;
126
0
  }
127
0
128
0
  
for (const_iterator I = begin(), E = end(); 0
I != E0
;
++I0
)
129
0
    OS << " " << PrintReg(*I, TRI);
130
0
  OS << "\n";
131
0
}
132
133
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
134
LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
135
  dbgs() << "  " << *this;
136
}
137
#endif
138
139
bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
140
3.44M
                             unsigned Reg) const {
141
3.44M
  if (LiveRegs.count(Reg))
142
2.64M
    return false;
143
807k
  
if (807k
MRI.isReserved(Reg)807k
)
144
280k
    return false;
145
4.34M
  
for (MCRegAliasIterator R(Reg, TRI, false); 526k
R.isValid()4.34M
;
++R3.82M
) {
146
3.83M
    if (LiveRegs.count(*R))
147
13.4k
      return false;
148
3.83M
  }
149
512k
  return true;
150
3.44M
}
151
152
/// Add live-in registers of basic block \p MBB to \p LiveRegs.
153
787k
void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
154
3.61M
  for (const auto &LI : MBB.liveins()) {
155
3.61M
    unsigned Reg = LI.PhysReg;
156
3.61M
    LaneBitmask Mask = LI.LaneMask;
157
3.61M
    MCSubRegIndexIterator S(Reg, TRI);
158
3.61M
    assert(Mask.any() && "Invalid livein mask");
159
3.61M
    if (
Mask.all() || 3.61M
!S.isValid()11.5k
) {
160
3.61M
      addReg(Reg);
161
3.61M
      continue;
162
3.61M
    }
163
10.4k
    
for (; 1.44k
S.isValid()10.4k
;
++S8.98k
) {
164
8.98k
      unsigned SI = S.getSubRegIndex();
165
8.98k
      if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
166
6.02k
        addReg(S.getSubReg());
167
8.98k
    }
168
3.61M
  }
169
787k
}
170
171
/// Adds all callee saved registers to \p LiveRegs.
172
static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
173
603k
                               const MachineFunction &MF) {
174
603k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
175
10.6M
  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); 
CSR && 10.6M
*CSR10.6M
;
++CSR10.0M
)
176
10.0M
    LiveRegs.addReg(*CSR);
177
603k
}
178
179
422k
void LivePhysRegs::addPristines(const MachineFunction &MF) {
180
422k
  const MachineFrameInfo &MFI = MF.getFrameInfo();
181
422k
  if (!MFI.isCalleeSavedInfoValid())
182
3.94k
    return;
183
418k
  /// This function will usually be called on an empty object, handle this
184
418k
  /// as a special case.
185
418k
  
if (418k
empty()418k
) {
186
415k
    /// Add all callee saved regs, then remove the ones that are saved and
187
415k
    /// restored.
188
415k
    addCalleeSavedRegs(*this, MF);
189
415k
    /// Remove the ones that are not saved/restored; they are pristine.
190
415k
    for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
191
3.55M
      removeReg(Info.getReg());
192
415k
    return;
193
415k
  }
194
3.67k
  /// If a callee-saved register that is not pristine is already present
195
3.67k
  /// in the set, we should make sure that it stays in it. Precompute the
196
3.67k
  /// set of pristine registers in a separate object.
197
3.67k
  /// Add all callee saved regs, then remove the ones that are saved+restored.
198
3.67k
  LivePhysRegs Pristine(*TRI);
199
3.67k
  addCalleeSavedRegs(Pristine, MF);
200
3.67k
  /// Remove the ones that are not saved/restored; they are pristine.
201
3.67k
  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
202
9.65k
    Pristine.removeReg(Info.getReg());
203
3.67k
  for (MCPhysReg R : Pristine)
204
125k
    addReg(R);
205
422k
}
206
207
632k
void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
208
632k
  if (
!MBB.succ_empty()632k
) {
209
587k
    // To get the live-outs we simply merge the live-ins of all successors.
210
587k
    for (const MachineBasicBlock *Succ : MBB.successors())
211
780k
      addBlockLiveIns(*Succ);
212
632k
  } else 
if (44.5k
MBB.isReturnBlock()44.5k
) {
213
42.0k
    // For the return block: Add all callee saved registers that are saved and
214
42.0k
    // restored (somewhere); This does not include callee saved registers that
215
42.0k
    // are unused and hence not saved and restored; they are called pristine.
216
42.0k
    const MachineFunction &MF = *MBB.getParent();
217
42.0k
    const MachineFrameInfo &MFI = MF.getFrameInfo();
218
42.0k
    if (
MFI.isCalleeSavedInfoValid()42.0k
) {
219
42.0k
      for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
220
177k
        
if (177k
Info.isRestored()177k
)
221
177k
          addReg(Info.getReg());
222
42.0k
    }
223
44.5k
  }
224
632k
}
225
226
611k
void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
227
611k
  const MachineFunction &MF = *MBB.getParent();
228
611k
  if (
!MBB.succ_empty()611k
) {
229
415k
    addPristines(MF);
230
415k
    addLiveOutsNoPristines(MBB);
231
611k
  } else 
if (195k
MBB.isReturnBlock()195k
) {
232
185k
    // For the return block: Add all callee saved registers.
233
185k
    const MachineFrameInfo &MFI = MF.getFrameInfo();
234
185k
    if (MFI.isCalleeSavedInfoValid())
235
184k
      addCalleeSavedRegs(*this, MF);
236
195k
  }
237
611k
}
238
239
7.36k
void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
240
7.36k
  const MachineFunction &MF = *MBB.getParent();
241
7.36k
  addPristines(MF);
242
7.36k
  addBlockLiveIns(MBB);
243
7.36k
}
244
245
void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
246
213k
                          const MachineBasicBlock &MBB) {
247
213k
  const MachineFunction &MF = *MBB.getParent();
248
213k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
249
213k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
250
213k
  LiveRegs.init(TRI);
251
213k
  LiveRegs.addLiveOutsNoPristines(MBB);
252
213k
  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
253
602k
    LiveRegs.stepBackward(MI);
254
213k
}
255
256
213k
void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
257
213k
  assert(MBB.livein_empty() && "Expected empty live-in list");
258
213k
  const MachineFunction &MF = *MBB.getParent();
259
213k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
260
213k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
261
2.38M
  for (MCPhysReg Reg : LiveRegs) {
262
2.38M
    if (MRI.isReserved(Reg))
263
279k
      continue;
264
2.10M
    // Skip the register if we are about to add one of its super registers.
265
2.10M
    bool ContainsSuperReg = false;
266
5.69M
    for (MCSuperRegIterator SReg(Reg, &TRI); 
SReg.isValid()5.69M
;
++SReg3.58M
) {
267
4.62M
      if (
LiveRegs.contains(*SReg) && 4.62M
!MRI.isReserved(*SReg)1.04M
) {
268
1.04M
        ContainsSuperReg = true;
269
1.04M
        break;
270
1.04M
      }
271
4.62M
    }
272
2.10M
    if (ContainsSuperReg)
273
1.04M
      continue;
274
1.06M
    MBB.addLiveIn(Reg);
275
1.06M
  }
276
213k
}
277
278
3.67k
void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
279
3.67k
  const MachineFunction &MF = *MBB.getParent();
280
3.67k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
281
3.67k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
282
3.67k
283
3.67k
  // We walk through the block backwards and start with the live outs.
284
3.67k
  LivePhysRegs LiveRegs;
285
3.67k
  LiveRegs.init(TRI);
286
3.67k
  LiveRegs.addLiveOutsNoPristines(MBB);
287
3.67k
288
22.4k
  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
289
22.4k
    // Recompute dead flags.
290
126k
    for (MIBundleOperands MO(MI); 
MO.isValid()126k
;
++MO104k
) {
291
104k
      if (
!MO->isReg() || 104k
!MO->isDef()69.1k
||
MO->isDebug()20.8k
)
292
83.5k
        continue;
293
20.8k
294
20.8k
      unsigned Reg = MO->getReg();
295
20.8k
      if (Reg == 0)
296
0
        continue;
297
20.8k
      assert(TargetRegisterInfo::isPhysicalRegister(Reg));
298
20.8k
299
20.8k
      bool IsNotLive = LiveRegs.available(MRI, Reg);
300
20.8k
      MO->setIsDead(IsNotLive);
301
20.8k
    }
302
22.4k
303
22.4k
    // Step backward over defs.
304
22.4k
    LiveRegs.removeDefs(MI);
305
22.4k
306
22.4k
    // Recompute kill flags.
307
126k
    for (MIBundleOperands MO(MI); 
MO.isValid()126k
;
++MO104k
) {
308
104k
      if (
!MO->isReg() || 104k
!MO->readsReg()69.1k
||
MO->isDebug()48.1k
)
309
56.2k
        continue;
310
48.1k
311
48.1k
      unsigned Reg = MO->getReg();
312
48.1k
      if (Reg == 0)
313
14.4k
        continue;
314
48.1k
      assert(TargetRegisterInfo::isPhysicalRegister(Reg));
315
33.7k
316
33.7k
      bool IsNotLive = LiveRegs.available(MRI, Reg);
317
33.7k
      MO->setIsKill(IsNotLive);
318
33.7k
    }
319
22.4k
320
22.4k
    // Complete the stepbackward.
321
22.4k
    LiveRegs.addUses(MI);
322
22.4k
  }
323
3.67k
}
324
325
void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
326
82.0k
                                MachineBasicBlock &MBB) {
327
82.0k
  computeLiveIns(LiveRegs, MBB);
328
82.0k
  addLiveIns(MBB, LiveRegs);
329
82.0k
}