Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LivePhysRegs.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- LivePhysRegs.cpp - Live Physical Register Set --------------------===//
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 implements the LivePhysRegs utility for tracking liveness of
10
// physical registers across machine instructions in forward or backward order.
11
// A more detailed description can be found in the corresponding header file.
12
//
13
//===----------------------------------------------------------------------===//
14
15
#include "llvm/CodeGen/LivePhysRegs.h"
16
#include "llvm/CodeGen/MachineFrameInfo.h"
17
#include "llvm/CodeGen/MachineFunction.h"
18
#include "llvm/CodeGen/MachineInstrBundle.h"
19
#include "llvm/CodeGen/MachineRegisterInfo.h"
20
#include "llvm/Config/llvm-config.h"
21
#include "llvm/Support/Debug.h"
22
#include "llvm/Support/raw_ostream.h"
23
using namespace llvm;
24
25
26
/// 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
393k
    SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> *Clobbers) {
32
393k
  RegisterSet::iterator LRI = LiveRegs.begin();
33
12.5M
  while (LRI != LiveRegs.end()) {
34
12.1M
    if (MO.clobbersPhysReg(*LRI)) {
35
1.24M
      if (Clobbers)
36
933
        Clobbers->push_back(std::make_pair(*LRI, &MO));
37
1.24M
      LRI = LiveRegs.erase(LRI);
38
1.24M
    } else
39
10.8M
      ++LRI;
40
12.1M
  }
41
393k
}
42
43
/// Remove defined registers and regmask kills from the set.
44
4.09M
void LivePhysRegs::removeDefs(const MachineInstr &MI) {
45
20.1M
  for (ConstMIBundleOperands O(MI); O.isValid(); 
++O16.0M
) {
46
16.0M
    if (O->isReg()) {
47
11.8M
      if (!O->isDef() || 
O->isDebug()4.77M
)
48
7.05M
        continue;
49
4.77M
      unsigned Reg = O->getReg();
50
4.77M
      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
51
7
        continue;
52
4.77M
      removeReg(Reg);
53
4.77M
    } else 
if (4.22M
O->isRegMask()4.22M
)
54
350k
      removeRegsInMask(*O);
55
16.0M
  }
56
4.09M
}
57
58
/// Add uses to the set.
59
4.09M
void LivePhysRegs::addUses(const MachineInstr &MI) {
60
20.1M
  for (ConstMIBundleOperands O(MI); O.isValid(); 
++O16.0M
) {
61
16.0M
    if (!O->isReg() || 
!O->readsReg()11.8M
||
O->isDebug()6.86M
)
62
9.20M
      continue;
63
6.85M
    unsigned Reg = O->getReg();
64
6.85M
    if (!TargetRegisterInfo::isPhysicalRegister(Reg))
65
1.37M
      continue;
66
5.48M
    addReg(Reg);
67
5.48M
  }
68
4.09M
}
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
4.04M
void LivePhysRegs::stepBackward(const MachineInstr &MI) {
73
4.04M
  // Remove defined registers and regmask kills from the set.
74
4.04M
  removeDefs(MI);
75
4.04M
76
4.04M
  // Add uses to the set.
77
4.04M
  addUses(MI);
78
4.04M
}
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
12.2k
    SmallVectorImpl<std::pair<MCPhysReg, const MachineOperand*>> &Clobbers) {
86
12.2k
  // Remove killed registers from the set.
87
78.0k
  for (ConstMIBundleOperands O(MI); O.isValid(); 
++O65.7k
) {
88
65.7k
    if (O->isReg() && 
!O->isDebug()42.7k
) {
89
42.7k
      unsigned Reg = O->getReg();
90
42.7k
      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
91
2.30k
        continue;
92
40.4k
      if (O->isDef()) {
93
13.1k
        // Note, dead defs are still recorded.  The caller should decide how to
94
13.1k
        // handle them.
95
13.1k
        Clobbers.push_back(std::make_pair(Reg, &*O));
96
27.3k
      } else {
97
27.3k
        if (!O->isKill())
98
20.8k
          continue;
99
6.46k
        assert(O->isUse());
100
6.46k
        removeReg(Reg);
101
6.46k
      }
102
40.4k
    } else 
if (22.9k
O->isRegMask()22.9k
)
103
854
      removeRegsInMask(*O, &Clobbers);
104
65.7k
  }
105
12.2k
106
12.2k
  // Add defs to the set.
107
30.2k
  for (auto Reg : Clobbers) {
108
30.2k
    // Skip dead defs and registers clobbered by regmasks. They shouldn't
109
30.2k
    // be added to the set.
110
30.2k
    if (Reg.second->isReg() && 
Reg.second->isDead()27.7k
)
111
2.31k
      continue;
112
27.8k
    if (Reg.second->isRegMask() &&
113
27.8k
        
MachineOperand::clobbersPhysReg(Reg.second->getRegMask(), Reg.first)2.43k
)
114
2.43k
      continue;
115
25.4k
    addReg(Reg.first);
116
25.4k
  }
117
12.2k
}
118
119
/// Prin the currently live registers to OS.
120
0
void LivePhysRegs::print(raw_ostream &OS) const {
121
0
  OS << "Live Registers:";
122
0
  if (!TRI) {
123
0
    OS << " (uninitialized)\n";
124
0
    return;
125
0
  }
126
0
127
0
  if (empty()) {
128
0
    OS << " (empty)\n";
129
0
    return;
130
0
  }
131
0
132
0
  for (const_iterator I = begin(), E = end(); I != E; ++I)
133
0
    OS << " " << printReg(*I, TRI);
134
0
  OS << "\n";
135
0
}
136
137
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
138
LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
139
  dbgs() << "  " << *this;
140
}
141
#endif
142
143
bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
144
3.77M
                             MCPhysReg Reg) const {
145
3.77M
  if (LiveRegs.count(Reg))
146
2.46M
    return false;
147
1.30M
  if (MRI.isReserved(Reg))
148
360k
    return false;
149
9.97M
  
for (MCRegAliasIterator R(Reg, TRI, false); 945k
R.isValid();
++R9.02M
) {
150
9.04M
    if (LiveRegs.count(*R))
151
20.5k
      return false;
152
9.04M
  }
153
945k
  
return true925k
;
154
945k
}
155
156
/// Add live-in registers of basic block \p MBB to \p LiveRegs.
157
972k
void LivePhysRegs::addBlockLiveIns(const MachineBasicBlock &MBB) {
158
4.15M
  for (const auto &LI : MBB.liveins()) {
159
4.15M
    MCPhysReg Reg = LI.PhysReg;
160
4.15M
    LaneBitmask Mask = LI.LaneMask;
161
4.15M
    MCSubRegIndexIterator S(Reg, TRI);
162
4.15M
    assert(Mask.any() && "Invalid livein mask");
163
4.15M
    if (Mask.all() || 
!S.isValid()35.7k
) {
164
4.15M
      addReg(Reg);
165
4.15M
      continue;
166
4.15M
    }
167
29.9k
    
for (; 3.61k
S.isValid();
++S26.3k
) {
168
26.3k
      unsigned SI = S.getSubRegIndex();
169
26.3k
      if ((Mask & TRI->getSubRegIndexLaneMask(SI)).any())
170
19.7k
        addReg(S.getSubReg());
171
26.3k
    }
172
3.61k
  }
173
972k
}
174
175
/// Adds all callee saved registers to \p LiveRegs.
176
static void addCalleeSavedRegs(LivePhysRegs &LiveRegs,
177
873k
                               const MachineFunction &MF) {
178
873k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
179
12.7M
  for (const MCPhysReg *CSR = MRI.getCalleeSavedRegs(); 
CSR12.7M
&& *CSR;
++CSR11.8M
)
180
11.8M
    LiveRegs.addReg(*CSR);
181
873k
}
182
183
880k
void LivePhysRegs::addPristines(const MachineFunction &MF) {
184
880k
  const MachineFrameInfo &MFI = MF.getFrameInfo();
185
880k
  if (!MFI.isCalleeSavedInfoValid())
186
6.37k
    return;
187
873k
  /// This function will usually be called on an empty object, handle this
188
873k
  /// as a special case.
189
873k
  if (empty()) {
190
867k
    /// Add all callee saved regs, then remove the ones that are saved and
191
867k
    /// restored.
192
867k
    addCalleeSavedRegs(*this, MF);
193
867k
    /// Remove the ones that are not saved/restored; they are pristine.
194
867k
    for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
195
3.87M
      removeReg(Info.getReg());
196
867k
    return;
197
867k
  }
198
5.87k
  /// If a callee-saved register that is not pristine is already present
199
5.87k
  /// in the set, we should make sure that it stays in it. Precompute the
200
5.87k
  /// set of pristine registers in a separate object.
201
5.87k
  /// Add all callee saved regs, then remove the ones that are saved+restored.
202
5.87k
  LivePhysRegs Pristine(*TRI);
203
5.87k
  addCalleeSavedRegs(Pristine, MF);
204
5.87k
  /// Remove the ones that are not saved/restored; they are pristine.
205
5.87k
  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
206
21.7k
    Pristine.removeReg(Info.getReg());
207
5.87k
  for (MCPhysReg R : Pristine)
208
189k
    addReg(R);
209
5.87k
}
210
211
1.05M
void LivePhysRegs::addLiveOutsNoPristines(const MachineBasicBlock &MBB) {
212
1.05M
  // To get the live-outs we simply merge the live-ins of all successors.
213
1.05M
  for (const MachineBasicBlock *Succ : MBB.successors())
214
960k
    addBlockLiveIns(*Succ);
215
1.05M
  if (MBB.isReturnBlock()) {
216
383k
    // Return blocks are a special case because we currently don't mark up
217
383k
    // return instructions completely: specifically, there is no explicit
218
383k
    // use for callee-saved registers. So we add all callee saved registers
219
383k
    // that are saved and restored (somewhere). This does not include
220
383k
    // callee saved registers that are unused and hence not saved and
221
383k
    // restored; they are called pristine.
222
383k
    // FIXME: PEI should add explicit markings to return instructions
223
383k
    // instead of implicitly handling them here.
224
383k
    const MachineFunction &MF = *MBB.getParent();
225
383k
    const MachineFrameInfo &MFI = MF.getFrameInfo();
226
383k
    if (MFI.isCalleeSavedInfoValid()) {
227
381k
      for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
228
697k
        if (Info.isRestored())
229
686k
          addReg(Info.getReg());
230
381k
    }
231
383k
  }
232
1.05M
}
233
234
868k
void LivePhysRegs::addLiveOuts(const MachineBasicBlock &MBB) {
235
868k
  const MachineFunction &MF = *MBB.getParent();
236
868k
  addPristines(MF);
237
868k
  addLiveOutsNoPristines(MBB);
238
868k
}
239
240
11.9k
void LivePhysRegs::addLiveIns(const MachineBasicBlock &MBB) {
241
11.9k
  const MachineFunction &MF = *MBB.getParent();
242
11.9k
  addPristines(MF);
243
11.9k
  addBlockLiveIns(MBB);
244
11.9k
}
245
246
void llvm::computeLiveIns(LivePhysRegs &LiveRegs,
247
180k
                          const MachineBasicBlock &MBB) {
248
180k
  const MachineFunction &MF = *MBB.getParent();
249
180k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
250
180k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
251
180k
  LiveRegs.init(TRI);
252
180k
  LiveRegs.addLiveOutsNoPristines(MBB);
253
180k
  for (const MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend()))
254
587k
    LiveRegs.stepBackward(MI);
255
180k
}
256
257
180k
void llvm::addLiveIns(MachineBasicBlock &MBB, const LivePhysRegs &LiveRegs) {
258
180k
  assert(MBB.livein_empty() && "Expected empty live-in list");
259
180k
  const MachineFunction &MF = *MBB.getParent();
260
180k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
261
180k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
262
2.23M
  for (MCPhysReg Reg : LiveRegs) {
263
2.23M
    if (MRI.isReserved(Reg))
264
270k
      continue;
265
1.96M
    // Skip the register if we are about to add one of its super registers.
266
1.96M
    bool ContainsSuperReg = false;
267
4.77M
    for (MCSuperRegIterator SReg(Reg, &TRI); SReg.isValid(); 
++SReg2.80M
) {
268
3.85M
      if (LiveRegs.contains(*SReg) && 
!MRI.isReserved(*SReg)1.04M
) {
269
1.04M
        ContainsSuperReg = true;
270
1.04M
        break;
271
1.04M
      }
272
3.85M
    }
273
1.96M
    if (ContainsSuperReg)
274
1.04M
      continue;
275
916k
    MBB.addLiveIn(Reg);
276
916k
  }
277
180k
}
278
279
5.89k
void llvm::recomputeLivenessFlags(MachineBasicBlock &MBB) {
280
5.89k
  const MachineFunction &MF = *MBB.getParent();
281
5.89k
  const MachineRegisterInfo &MRI = MF.getRegInfo();
282
5.89k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
283
5.89k
284
5.89k
  // We walk through the block backwards and start with the live outs.
285
5.89k
  LivePhysRegs LiveRegs;
286
5.89k
  LiveRegs.init(TRI);
287
5.89k
  LiveRegs.addLiveOutsNoPristines(MBB);
288
5.89k
289
43.2k
  for (MachineInstr &MI : make_range(MBB.rbegin(), MBB.rend())) {
290
43.2k
    // Recompute dead flags.
291
246k
    for (MIBundleOperands MO(MI); MO.isValid(); 
++MO202k
) {
292
202k
      if (!MO->isReg() || 
!MO->isDef()131k
||
MO->isDebug()40.5k
)
293
162k
        continue;
294
40.5k
295
40.5k
      unsigned Reg = MO->getReg();
296
40.5k
      if (Reg == 0)
297
0
        continue;
298
40.5k
      assert(TargetRegisterInfo::isPhysicalRegister(Reg));
299
40.5k
300
40.5k
      bool IsNotLive = LiveRegs.available(MRI, Reg);
301
40.5k
      MO->setIsDead(IsNotLive);
302
40.5k
    }
303
43.2k
304
43.2k
    // Step backward over defs.
305
43.2k
    LiveRegs.removeDefs(MI);
306
43.2k
307
43.2k
    // Recompute kill flags.
308
246k
    for (MIBundleOperands MO(MI); MO.isValid(); 
++MO202k
) {
309
202k
      if (!MO->isReg() || 
!MO->readsReg()131k
||
MO->isDebug()90.7k
)
310
112k
        continue;
311
90.7k
312
90.7k
      unsigned Reg = MO->getReg();
313
90.7k
      if (Reg == 0)
314
27.7k
        continue;
315
62.9k
      assert(TargetRegisterInfo::isPhysicalRegister(Reg));
316
62.9k
317
62.9k
      bool IsNotLive = LiveRegs.available(MRI, Reg);
318
62.9k
      MO->setIsKill(IsNotLive);
319
62.9k
    }
320
43.2k
321
43.2k
    // Complete the stepbackward.
322
43.2k
    LiveRegs.addUses(MI);
323
43.2k
  }
324
5.89k
}
325
326
void llvm::computeAndAddLiveIns(LivePhysRegs &LiveRegs,
327
79.7k
                                MachineBasicBlock &MBB) {
328
79.7k
  computeLiveIns(LiveRegs, MBB);
329
79.7k
  addLiveIns(MBB, LiveRegs);
330
79.7k
}