Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveVariables.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- LiveVariables.cpp - Live Variable Analysis for Machine Code -------===//
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 LiveVariable analysis pass.  For each machine
10
// instruction in the function, this pass calculates the set of registers that
11
// are immediately dead after the instruction (i.e., the instruction calculates
12
// the value, but it is never used) and the set of registers that are used by
13
// the instruction, but are never used after the instruction (i.e., they are
14
// killed).
15
//
16
// This class computes live variables using a sparse implementation based on
17
// the machine code SSA form.  This class computes live variable information for
18
// each virtual and _register allocatable_ physical register in a function.  It
19
// uses the dominance properties of SSA form to efficiently compute live
20
// variables for virtual registers, and assumes that physical registers are only
21
// live within a single basic block (allowing it to do a single local analysis
22
// to resolve physical register lifetimes in each basic block).  If a physical
23
// register is not register allocatable, it is not tracked.  This is useful for
24
// things like the stack pointer and condition codes.
25
//
26
//===----------------------------------------------------------------------===//
27
28
#include "llvm/CodeGen/LiveVariables.h"
29
#include "llvm/ADT/DepthFirstIterator.h"
30
#include "llvm/ADT/STLExtras.h"
31
#include "llvm/ADT/SmallPtrSet.h"
32
#include "llvm/ADT/SmallSet.h"
33
#include "llvm/CodeGen/MachineInstr.h"
34
#include "llvm/CodeGen/MachineRegisterInfo.h"
35
#include "llvm/CodeGen/Passes.h"
36
#include "llvm/Config/llvm-config.h"
37
#include "llvm/Support/Debug.h"
38
#include "llvm/Support/ErrorHandling.h"
39
#include "llvm/Support/raw_ostream.h"
40
#include <algorithm>
41
using namespace llvm;
42
43
char LiveVariables::ID = 0;
44
char &llvm::LiveVariablesID = LiveVariables::ID;
45
42.3k
INITIALIZE_PASS_BEGIN(LiveVariables, "livevars",
46
42.3k
                "Live Variable Analysis", false, false)
47
42.3k
INITIALIZE_PASS_DEPENDENCY(UnreachableMachineBlockElim)
48
42.3k
INITIALIZE_PASS_END(LiveVariables, "livevars",
49
                "Live Variable Analysis", false, false)
50
51
52
35.1k
void LiveVariables::getAnalysisUsage(AnalysisUsage &AU) const {
53
35.1k
  AU.addRequiredID(UnreachableMachineBlockElimID);
54
35.1k
  AU.setPreservesAll();
55
35.1k
  MachineFunctionPass::getAnalysisUsage(AU);
56
35.1k
}
57
58
MachineInstr *
59
893k
LiveVariables::VarInfo::findKill(const MachineBasicBlock *MBB) const {
60
1.10M
  for (unsigned i = 0, e = Kills.size(); i != e; 
++i211k
)
61
897k
    if (Kills[i]->getParent() == MBB)
62
686k
      return Kills[i];
63
893k
  
return nullptr206k
;
64
893k
}
65
66
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
67
LLVM_DUMP_METHOD void LiveVariables::VarInfo::dump() const {
68
  dbgs() << "  Alive in blocks: ";
69
  for (SparseBitVector<>::iterator I = AliveBlocks.begin(),
70
           E = AliveBlocks.end(); I != E; ++I)
71
    dbgs() << *I << ", ";
72
  dbgs() << "\n  Killed by:";
73
  if (Kills.empty())
74
    dbgs() << " No instructions.\n";
75
  else {
76
    for (unsigned i = 0, e = Kills.size(); i != e; ++i)
77
      dbgs() << "\n    #" << i << ": " << *Kills[i];
78
    dbgs() << "\n";
79
  }
80
}
81
#endif
82
83
/// getVarInfo - Get (possibly creating) a VarInfo object for the given vreg.
84
129M
LiveVariables::VarInfo &LiveVariables::getVarInfo(unsigned RegIdx) {
85
129M
  assert(TargetRegisterInfo::isVirtualRegister(RegIdx) &&
86
129M
         "getVarInfo: not a virtual register!");
87
129M
  VirtRegInfo.grow(RegIdx);
88
129M
  return VirtRegInfo[RegIdx];
89
129M
}
90
91
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo& VRInfo,
92
                                            MachineBasicBlock *DefBlock,
93
                                            MachineBasicBlock *MBB,
94
38.1M
                                    std::vector<MachineBasicBlock*> &WorkList) {
95
38.1M
  unsigned BBNum = MBB->getNumber();
96
38.1M
97
38.1M
  // Check to see if this basic block is one of the killing blocks.  If so,
98
38.1M
  // remove it.
99
73.8M
  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; 
++i35.6M
)
100
39.9M
    if (VRInfo.Kills[i]->getParent() == MBB) {
101
4.28M
      VRInfo.Kills.erase(VRInfo.Kills.begin()+i);  // Erase entry
102
4.28M
      break;
103
4.28M
    }
104
38.1M
105
38.1M
  if (MBB == DefBlock) 
return4.24M
; // Terminate recursion
106
33.9M
107
33.9M
  if (VRInfo.AliveBlocks.test(BBNum))
108
13.2M
    return;  // We already know the block is live
109
20.6M
110
20.6M
  // Mark the variable known alive in this bb
111
20.6M
  VRInfo.AliveBlocks.set(BBNum);
112
20.6M
113
20.6M
  assert(MBB != &MF->front() && "Can't find reaching def for virtreg");
114
20.6M
  WorkList.insert(WorkList.end(), MBB->pred_rbegin(), MBB->pred_rend());
115
20.6M
}
116
117
void LiveVariables::MarkVirtRegAliveInBlock(VarInfo &VRInfo,
118
                                            MachineBasicBlock *DefBlock,
119
7.36M
                                            MachineBasicBlock *MBB) {
120
7.36M
  std::vector<MachineBasicBlock*> WorkList;
121
7.36M
  MarkVirtRegAliveInBlock(VRInfo, DefBlock, MBB, WorkList);
122
7.36M
123
38.1M
  while (!WorkList.empty()) {
124
30.8M
    MachineBasicBlock *Pred = WorkList.back();
125
30.8M
    WorkList.pop_back();
126
30.8M
    MarkVirtRegAliveInBlock(VRInfo, DefBlock, Pred, WorkList);
127
30.8M
  }
128
7.36M
}
129
130
void LiveVariables::HandleVirtRegUse(unsigned reg, MachineBasicBlock *MBB,
131
16.0M
                                     MachineInstr &MI) {
132
16.0M
  assert(MRI->getVRegDef(reg) && "Register use before def!");
133
16.0M
134
16.0M
  unsigned BBNum = MBB->getNumber();
135
16.0M
136
16.0M
  VarInfo& VRInfo = getVarInfo(reg);
137
16.0M
138
16.0M
  // Check to see if this basic block is already a kill block.
139
16.0M
  if (!VRInfo.Kills.empty() && 
VRInfo.Kills.back()->getParent() == MBB15.2M
) {
140
12.1M
    // Yes, this register is killed in this basic block already. Increase the
141
12.1M
    // live range by updating the kill instruction.
142
12.1M
    VRInfo.Kills.back() = &MI;
143
12.1M
    return;
144
12.1M
  }
145
3.97M
146
#ifndef NDEBUG
147
  for (unsigned i = 0, e = VRInfo.Kills.size(); i != e; ++i)
148
    assert(VRInfo.Kills[i]->getParent() != MBB && "entry should be at end!");
149
#endif
150
151
3.97M
  // This situation can occur:
152
3.97M
  //
153
3.97M
  //     ,------.
154
3.97M
  //     |      |
155
3.97M
  //     |      v
156
3.97M
  //     |   t2 = phi ... t1 ...
157
3.97M
  //     |      |
158
3.97M
  //     |      v
159
3.97M
  //     |   t1 = ...
160
3.97M
  //     |  ... = ... t1 ...
161
3.97M
  //     |      |
162
3.97M
  //     `------'
163
3.97M
  //
164
3.97M
  // where there is a use in a PHI node that's a predecessor to the defining
165
3.97M
  // block. We don't want to mark all predecessors as having the value "alive"
166
3.97M
  // in this case.
167
3.97M
  if (MBB == MRI->getVRegDef(reg)->getParent()) 
return0
;
168
3.97M
169
3.97M
  // Add a new kill entry for this basic block. If this virtual register is
170
3.97M
  // already marked as alive in this basic block, that means it is alive in at
171
3.97M
  // least one of the successor blocks, it's not a kill.
172
3.97M
  if (!VRInfo.AliveBlocks.test(BBNum))
173
2.95M
    VRInfo.Kills.push_back(&MI);
174
3.97M
175
3.97M
  // Update all dominating blocks to mark them as "known live".
176
3.97M
  for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
177
9.81M
         E = MBB->pred_end(); PI != E; 
++PI5.83M
)
178
5.83M
    MarkVirtRegAliveInBlock(VRInfo, MRI->getVRegDef(reg)->getParent(), *PI);
179
3.97M
}
180
181
10.9M
void LiveVariables::HandleVirtRegDef(unsigned Reg, MachineInstr &MI) {
182
10.9M
  VarInfo &VRInfo = getVarInfo(Reg);
183
10.9M
184
10.9M
  if (VRInfo.AliveBlocks.empty())
185
10.9M
    // If vr is not alive in any block, then defaults to dead.
186
10.9M
    VRInfo.Kills.push_back(&MI);
187
10.9M
}
188
189
/// FindLastPartialDef - Return the last partial def of the specified register.
190
/// Also returns the sub-registers that're defined by the instruction.
191
MachineInstr *LiveVariables::FindLastPartialDef(unsigned Reg,
192
963k
                                            SmallSet<unsigned,4> &PartDefRegs) {
193
963k
  unsigned LastDefReg = 0;
194
963k
  unsigned LastDefDist = 0;
195
963k
  MachineInstr *LastDef = nullptr;
196
2.07M
  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs1.10M
) {
197
1.10M
    unsigned SubReg = *SubRegs;
198
1.10M
    MachineInstr *Def = PhysRegDef[SubReg];
199
1.10M
    if (!Def)
200
1.10M
      continue;
201
14
    unsigned Dist = DistanceMap[Def];
202
14
    if (Dist > LastDefDist) {
203
3
      LastDefReg  = SubReg;
204
3
      LastDef     = Def;
205
3
      LastDefDist = Dist;
206
3
    }
207
14
  }
208
963k
209
963k
  if (!LastDef)
210
963k
    return nullptr;
211
2
212
2
  PartDefRegs.insert(LastDefReg);
213
11
  for (unsigned i = 0, e = LastDef->getNumOperands(); i != e; 
++i9
) {
214
9
    MachineOperand &MO = LastDef->getOperand(i);
215
9
    if (!MO.isReg() || !MO.isDef() || 
MO.getReg() == 06
)
216
3
      continue;
217
6
    unsigned DefReg = MO.getReg();
218
6
    if (TRI->isSubRegister(Reg, DefReg)) {
219
3
      for (MCSubRegIterator SubRegs(DefReg, TRI, /*IncludeSelf=*/true);
220
18
           SubRegs.isValid(); 
++SubRegs15
)
221
15
        PartDefRegs.insert(*SubRegs);
222
3
    }
223
6
  }
224
2
  return LastDef;
225
2
}
226
227
/// HandlePhysRegUse - Turn previous partial def's into read/mod/writes. Add
228
/// implicit defs to a machine instruction if there was an earlier def of its
229
/// super-register.
230
6.33M
void LiveVariables::HandlePhysRegUse(unsigned Reg, MachineInstr &MI) {
231
6.33M
  MachineInstr *LastDef = PhysRegDef[Reg];
232
6.33M
  // If there was a previous use or a "full" def all is well.
233
6.33M
  if (!LastDef && 
!PhysRegUse[Reg]970k
) {
234
963k
    // Otherwise, the last sub-register def implicitly defines this register.
235
963k
    // e.g.
236
963k
    // AH =
237
963k
    // AL = ... implicit-def EAX, implicit killed AH
238
963k
    //    = AH
239
963k
    // ...
240
963k
    //    = EAX
241
963k
    // All of the sub-registers must have been defined before the use of Reg!
242
963k
    SmallSet<unsigned, 4> PartDefRegs;
243
963k
    MachineInstr *LastPartialDef = FindLastPartialDef(Reg, PartDefRegs);
244
963k
    // If LastPartialDef is NULL, it must be using a livein register.
245
963k
    if (LastPartialDef) {
246
3
      LastPartialDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
247
3
                                                           true/*IsImp*/));
248
3
      PhysRegDef[Reg] = LastPartialDef;
249
3
      SmallSet<unsigned, 8> Processed;
250
18
      for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs15
) {
251
15
        unsigned SubReg = *SubRegs;
252
15
        if (Processed.count(SubReg))
253
0
          continue;
254
15
        if (PartDefRegs.count(SubReg))
255
15
          continue;
256
0
        // This part of Reg was defined before the last partial def. It's killed
257
0
        // here.
258
0
        LastPartialDef->addOperand(MachineOperand::CreateReg(SubReg,
259
0
                                                             false/*IsDef*/,
260
0
                                                             true/*IsImp*/));
261
0
        PhysRegDef[SubReg] = LastPartialDef;
262
0
        for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); ++SS)
263
0
          Processed.insert(*SS);
264
0
      }
265
3
    }
266
5.36M
  } else if (LastDef && 
!PhysRegUse[Reg]5.36M
&&
267
5.36M
             
!LastDef->findRegisterDefOperand(Reg)5.35M
)
268
209
    // Last def defines the super register, add an implicit def of reg.
269
209
    LastDef->addOperand(MachineOperand::CreateReg(Reg, true/*IsDef*/,
270
209
                                                  true/*IsImp*/));
271
6.33M
272
6.33M
  // Remember this use.
273
6.33M
  for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
274
18.6M
       SubRegs.isValid(); 
++SubRegs12.3M
)
275
12.3M
    PhysRegUse[*SubRegs] = &MI;
276
6.33M
}
277
278
/// FindLastRefOrPartRef - Return the last reference or partial reference of
279
/// the specified register.
280
276
MachineInstr *LiveVariables::FindLastRefOrPartRef(unsigned Reg) {
281
276
  MachineInstr *LastDef = PhysRegDef[Reg];
282
276
  MachineInstr *LastUse = PhysRegUse[Reg];
283
276
  if (!LastDef && 
!LastUse0
)
284
0
    return nullptr;
285
276
286
276
  MachineInstr *LastRefOrPartRef = LastUse ? LastUse : 
LastDef0
;
287
276
  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
288
276
  unsigned LastPartDefDist = 0;
289
370
  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs94
) {
290
94
    unsigned SubReg = *SubRegs;
291
94
    MachineInstr *Def = PhysRegDef[SubReg];
292
94
    if (Def && Def != LastDef) {
293
78
      // There was a def of this sub-register in between. This is a partial
294
78
      // def, keep track of the last one.
295
78
      unsigned Dist = DistanceMap[Def];
296
78
      if (Dist > LastPartDefDist)
297
39
        LastPartDefDist = Dist;
298
78
    } else 
if (MachineInstr *16
Use16
= PhysRegUse[SubReg]) {
299
16
      unsigned Dist = DistanceMap[Use];
300
16
      if (Dist > LastRefOrPartRefDist) {
301
0
        LastRefOrPartRefDist = Dist;
302
0
        LastRefOrPartRef = Use;
303
0
      }
304
16
    }
305
94
  }
306
276
307
276
  return LastRefOrPartRef;
308
276
}
309
310
36.3M
bool LiveVariables::HandlePhysRegKill(unsigned Reg, MachineInstr *MI) {
311
36.3M
  MachineInstr *LastDef = PhysRegDef[Reg];
312
36.3M
  MachineInstr *LastUse = PhysRegUse[Reg];
313
36.3M
  if (!LastDef && 
!LastUse8.87M
)
314
4.74M
    return false;
315
31.5M
316
31.5M
  MachineInstr *LastRefOrPartRef = LastUse ? 
LastUse26.8M
:
LastDef4.76M
;
317
31.5M
  unsigned LastRefOrPartRefDist = DistanceMap[LastRefOrPartRef];
318
31.5M
  // The whole register is used.
319
31.5M
  // AL =
320
31.5M
  // AH =
321
31.5M
  //
322
31.5M
  //    = AX
323
31.5M
  //    = AL, implicit killed AX
324
31.5M
  // AX =
325
31.5M
  //
326
31.5M
  // Or whole register is defined, but not used at all.
327
31.5M
  // dead AX =
328
31.5M
  // ...
329
31.5M
  // AX =
330
31.5M
  //
331
31.5M
  // Or whole register is defined, but only partly used.
332
31.5M
  // dead AX = implicit-def AL
333
31.5M
  //    = killed AL
334
31.5M
  // AX =
335
31.5M
  MachineInstr *LastPartDef = nullptr;
336
31.5M
  unsigned LastPartDefDist = 0;
337
31.5M
  SmallSet<unsigned, 8> PartUses;
338
60.7M
  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs29.1M
) {
339
29.1M
    unsigned SubReg = *SubRegs;
340
29.1M
    MachineInstr *Def = PhysRegDef[SubReg];
341
29.1M
    if (Def && 
Def != LastDef25.7M
) {
342
667k
      // There was a def of this sub-register in between. This is a partial
343
667k
      // def, keep track of the last one.
344
667k
      unsigned Dist = DistanceMap[Def];
345
667k
      if (Dist > LastPartDefDist) {
346
564k
        LastPartDefDist = Dist;
347
564k
        LastPartDef = Def;
348
564k
      }
349
667k
      continue;
350
667k
    }
351
28.4M
    if (MachineInstr *Use = PhysRegUse[SubReg]) {
352
68.6M
      for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true); SS.isValid();
353
41.9M
           ++SS)
354
41.9M
        PartUses.insert(*SS);
355
26.6M
      unsigned Dist = DistanceMap[Use];
356
26.6M
      if (Dist > LastRefOrPartRefDist) {
357
276
        LastRefOrPartRefDist = Dist;
358
276
        LastRefOrPartRef = Use;
359
276
      }
360
26.6M
    }
361
28.4M
  }
362
31.5M
363
31.5M
  if (!PhysRegUse[Reg]) {
364
4.76M
    // Partial uses. Mark register def dead and add implicit def of
365
4.76M
    // sub-registers which are used.
366
4.76M
    // dead EAX  = op  implicit-def AL
367
4.76M
    // That is, EAX def is dead but AL def extends pass it.
368
4.76M
    PhysRegDef[Reg]->addRegisterDead(Reg, TRI, true);
369
6.54M
    for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs1.77M
) {
370
1.77M
      unsigned SubReg = *SubRegs;
371
1.77M
      if (!PartUses.count(SubReg))
372
1.77M
        continue;
373
275
      bool NeedDef = true;
374
276
      if (
PhysRegDef[Reg] == PhysRegDef[SubReg]275
) {
375
276
        MachineOperand *MO = PhysRegDef[Reg]->findRegisterDefOperand(SubReg);
376
276
        if (MO) {
377
276
          NeedDef = false;
378
276
          assert(!MO->isDead());
379
276
        }
380
276
      }
381
275
      if (NeedDef)
382
0
        PhysRegDef[Reg]->addOperand(MachineOperand::CreateReg(SubReg,
383
0
                                                 true/*IsDef*/, true/*IsImp*/));
384
275
      MachineInstr *LastSubRef = FindLastRefOrPartRef(SubReg);
385
275
      if (LastSubRef)
386
276
        LastSubRef->addRegisterKilled(SubReg, TRI, true);
387
18.4E
      else {
388
18.4E
        LastRefOrPartRef->addRegisterKilled(SubReg, TRI, true);
389
18.4E
        for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
390
18.4E
             SS.isValid(); 
++SS0
)
391
0
          PhysRegUse[*SS] = LastRefOrPartRef;
392
18.4E
      }
393
369
      for (MCSubRegIterator SS(SubReg, TRI); SS.isValid(); 
++SS94
)
394
94
        PartUses.erase(*SS);
395
275
    }
396
26.8M
  } else if (LastRefOrPartRef == PhysRegDef[Reg] && 
LastRefOrPartRef != MI0
) {
397
0
    if (LastPartDef)
398
0
      // The last partial def kills the register.
399
0
      LastPartDef->addOperand(MachineOperand::CreateReg(Reg, false/*IsDef*/,
400
0
                                                true/*IsImp*/, true/*IsKill*/));
401
0
    else {
402
0
      MachineOperand *MO =
403
0
        LastRefOrPartRef->findRegisterDefOperand(Reg, false, false, TRI);
404
0
      bool NeedEC = MO->isEarlyClobber() && MO->getReg() != Reg;
405
0
      // If the last reference is the last def, then it's not used at all.
406
0
      // That is, unless we are currently processing the last reference itself.
407
0
      LastRefOrPartRef->addRegisterDead(Reg, TRI, true);
408
0
      if (NeedEC) {
409
0
        // If we are adding a subreg def and the superreg def is marked early
410
0
        // clobber, add an early clobber marker to the subreg def.
411
0
        MO = LastRefOrPartRef->findRegisterDefOperand(Reg);
412
0
        if (MO)
413
0
          MO->setIsEarlyClobber();
414
0
      }
415
0
    }
416
0
  } else
417
26.8M
    LastRefOrPartRef->addRegisterKilled(Reg, TRI, true);
418
31.5M
  return true;
419
31.5M
}
420
421
1.50M
void LiveVariables::HandleRegMask(const MachineOperand &MO) {
422
1.50M
  // Call HandlePhysRegKill() for all live registers clobbered by Mask.
423
1.50M
  // Clobbered registers are always dead, sp there is no need to use
424
1.50M
  // HandlePhysRegDef().
425
880M
  for (unsigned Reg = 1, NumRegs = TRI->getNumRegs(); Reg != NumRegs; 
++Reg878M
) {
426
878M
    // Skip dead regs.
427
878M
    if (!PhysRegDef[Reg] && 
!PhysRegUse[Reg]869M
)
428
868M
      continue;
429
10.3M
    // Skip mask-preserved regs.
430
10.3M
    if (!MO.clobbersPhysReg(Reg))
431
1.17M
      continue;
432
9.18M
    // Kill the largest clobbered super-register.
433
9.18M
    // This avoids needless implicit operands.
434
9.18M
    unsigned Super = Reg;
435
37.4M
    for (MCSuperRegIterator SR(Reg, TRI); SR.isValid(); 
++SR28.2M
)
436
28.2M
      if ((PhysRegDef[*SR] || 
PhysRegUse[*SR]21.9M
) &&
MO.clobbersPhysReg(*SR)6.95M
)
437
6.95M
        Super = *SR;
438
9.18M
    HandlePhysRegKill(Super, nullptr);
439
9.18M
  }
440
1.50M
}
441
442
void LiveVariables::HandlePhysRegDef(unsigned Reg, MachineInstr *MI,
443
17.6M
                                     SmallVectorImpl<unsigned> &Defs) {
444
17.6M
  // What parts of the register are previously defined?
445
17.6M
  SmallSet<unsigned, 32> Live;
446
17.6M
  if (PhysRegDef[Reg] || 
PhysRegUse[Reg]6.42M
) {
447
12.9M
    for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
448
35.2M
         SubRegs.isValid(); 
++SubRegs22.3M
)
449
22.3M
      Live.insert(*SubRegs);
450
12.9M
  } else {
451
9.25M
    for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs4.51M
) {
452
4.51M
      unsigned SubReg = *SubRegs;
453
4.51M
      // If a register isn't itself defined, but all parts that make up of it
454
4.51M
      // are defined, then consider it also defined.
455
4.51M
      // e.g.
456
4.51M
      // AL =
457
4.51M
      // AH =
458
4.51M
      //    = AX
459
4.51M
      if (Live.count(SubReg))
460
16.2k
        continue;
461
4.49M
      if (PhysRegDef[SubReg] || 
PhysRegUse[SubReg]4.46M
) {
462
46.5k
        for (MCSubRegIterator SS(SubReg, TRI, /*IncludeSelf=*/true);
463
109k
             SS.isValid(); 
++SS62.9k
)
464
62.9k
          Live.insert(*SS);
465
46.5k
      }
466
4.49M
    }
467
4.74M
  }
468
17.6M
469
17.6M
  // Start from the largest piece, find the last time any part of the register
470
17.6M
  // is referenced.
471
17.6M
  HandlePhysRegKill(Reg, MI);
472
17.6M
  // Only some of the sub-registers are used.
473
31.5M
  for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); 
++SubRegs13.8M
) {
474
13.8M
    unsigned SubReg = *SubRegs;
475
13.8M
    if (!Live.count(SubReg))
476
4.45M
      // Skip if this sub-register isn't defined.
477
4.45M
      continue;
478
9.43M
    HandlePhysRegKill(SubReg, MI);
479
9.43M
  }
480
17.6M
481
17.6M
  if (MI)
482
7.58M
    Defs.push_back(Reg);  // Remember this def.
483
17.6M
}
484
485
void LiveVariables::UpdatePhysRegDefs(MachineInstr &MI,
486
24.0M
                                      SmallVectorImpl<unsigned> &Defs) {
487
31.6M
  while (!Defs.empty()) {
488
7.58M
    unsigned Reg = Defs.back();
489
7.58M
    Defs.pop_back();
490
7.58M
    for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
491
21.4M
         SubRegs.isValid(); 
++SubRegs13.9M
) {
492
13.9M
      unsigned SubReg = *SubRegs;
493
13.9M
      PhysRegDef[SubReg] = &MI;
494
13.9M
      PhysRegUse[SubReg]  = nullptr;
495
13.9M
    }
496
7.58M
  }
497
24.0M
}
498
499
void LiveVariables::runOnInstr(MachineInstr &MI,
500
24.0M
                               SmallVectorImpl<unsigned> &Defs) {
501
24.0M
  assert(!MI.isDebugInstr());
502
24.0M
  // Process all of the operands of the instruction...
503
24.0M
  unsigned NumOperandsToProcess = MI.getNumOperands();
504
24.0M
505
24.0M
  // Unless it is a PHI node.  In this case, ONLY process the DEF, not any
506
24.0M
  // of the uses.  They will be handled in other basic blocks.
507
24.0M
  if (MI.isPHI())
508
633k
    NumOperandsToProcess = 1;
509
24.0M
510
24.0M
  // Clear kill and dead markers. LV will recompute them.
511
24.0M
  SmallVector<unsigned, 4> UseRegs;
512
24.0M
  SmallVector<unsigned, 4> DefRegs;
513
24.0M
  SmallVector<unsigned, 1> RegMasks;
514
101M
  for (unsigned i = 0; i != NumOperandsToProcess; 
++i77.3M
) {
515
77.3M
    MachineOperand &MO = MI.getOperand(i);
516
77.3M
    if (MO.isRegMask()) {
517
1.50M
      RegMasks.push_back(i);
518
1.50M
      continue;
519
1.50M
    }
520
75.8M
    if (!MO.isReg() || 
MO.getReg() == 053.1M
)
521
24.4M
      continue;
522
51.3M
    unsigned MOReg = MO.getReg();
523
51.3M
    if (MO.isUse()) {
524
28.4M
      if (!(TargetRegisterInfo::isPhysicalRegister(MOReg) &&
525
28.4M
            
MRI->isReserved(MOReg)12.2M
))
526
22.5M
        MO.setIsKill(false);
527
28.4M
      if (MO.readsReg())
528
28.3M
        UseRegs.push_back(MOReg);
529
28.4M
    } else {
530
22.9M
      assert(MO.isDef());
531
22.9M
      // FIXME: We should not remove any dead flags. However the MIPS RDDSP
532
22.9M
      // instruction needs it at the moment: http://llvm.org/PR27116.
533
22.9M
      if (TargetRegisterInfo::isPhysicalRegister(MOReg) &&
534
22.9M
          
!MRI->isReserved(MOReg)11.9M
)
535
7.58M
        MO.setIsDead(false);
536
22.9M
      DefRegs.push_back(MOReg);
537
22.9M
    }
538
51.3M
  }
539
24.0M
540
24.0M
  MachineBasicBlock *MBB = MI.getParent();
541
24.0M
  // Process all uses.
542
52.4M
  for (unsigned i = 0, e = UseRegs.size(); i != e; 
++i28.3M
) {
543
28.3M
    unsigned MOReg = UseRegs[i];
544
28.3M
    if (TargetRegisterInfo::isVirtualRegister(MOReg))
545
16.0M
      HandleVirtRegUse(MOReg, MBB, MI);
546
12.2M
    else if (!MRI->isReserved(MOReg))
547
6.33M
      HandlePhysRegUse(MOReg, MI);
548
28.3M
  }
549
24.0M
550
24.0M
  // Process all masked registers. (Call clobbers).
551
25.5M
  for (unsigned i = 0, e = RegMasks.size(); i != e; 
++i1.50M
)
552
1.50M
    HandleRegMask(MI.getOperand(RegMasks[i]));
553
24.0M
554
24.0M
  // Process all defs.
555
47.0M
  for (unsigned i = 0, e = DefRegs.size(); i != e; 
++i22.9M
) {
556
22.9M
    unsigned MOReg = DefRegs[i];
557
22.9M
    if (TargetRegisterInfo::isVirtualRegister(MOReg))
558
10.9M
      HandleVirtRegDef(MOReg, MI);
559
11.9M
    else if (!MRI->isReserved(MOReg))
560
7.58M
      HandlePhysRegDef(MOReg, &MI, Defs);
561
22.9M
  }
562
24.0M
  UpdatePhysRegDefs(MI, Defs);
563
24.0M
}
564
565
2.69M
void LiveVariables::runOnBlock(MachineBasicBlock *MBB, const unsigned NumRegs) {
566
2.69M
  // Mark live-in registers as live-in.
567
2.69M
  SmallVector<unsigned, 4> Defs;
568
2.69M
  for (const auto &LI : MBB->liveins()) {
569
1.00M
    assert(TargetRegisterInfo::isPhysicalRegister(LI.PhysReg) &&
570
1.00M
           "Cannot have a live-in virtual register!");
571
1.00M
    HandlePhysRegDef(LI.PhysReg, nullptr, Defs);
572
1.00M
  }
573
2.69M
574
2.69M
  // Loop over all of the instructions, processing them.
575
2.69M
  DistanceMap.clear();
576
2.69M
  unsigned Dist = 0;
577
24.0M
  for (MachineInstr &MI : *MBB) {
578
24.0M
    if (MI.isDebugInstr())
579
5.07k
      continue;
580
24.0M
    DistanceMap.insert(std::make_pair(&MI, Dist++));
581
24.0M
582
24.0M
    runOnInstr(MI, Defs);
583
24.0M
  }
584
2.69M
585
2.69M
  // Handle any virtual assignments from PHI nodes which might be at the
586
2.69M
  // bottom of this basic block.  We check all of our successor blocks to see
587
2.69M
  // if they have PHI nodes, and if so, we simulate an assignment at the end
588
2.69M
  // of the current block.
589
2.69M
  if (!PHIVarInfo[MBB->getNumber()].empty()) {
590
982k
    SmallVectorImpl<unsigned> &VarInfoVec = PHIVarInfo[MBB->getNumber()];
591
982k
592
982k
    for (SmallVectorImpl<unsigned>::iterator I = VarInfoVec.begin(),
593
2.50M
           E = VarInfoVec.end(); I != E; 
++I1.52M
)
594
1.52M
      // Mark it alive only in the block we are representing.
595
1.52M
      MarkVirtRegAliveInBlock(getVarInfo(*I),MRI->getVRegDef(*I)->getParent(),
596
1.52M
                              MBB);
597
982k
  }
598
2.69M
599
2.69M
  // MachineCSE may CSE instructions which write to non-allocatable physical
600
2.69M
  // registers across MBBs. Remember if any reserved register is liveout.
601
2.69M
  SmallSet<unsigned, 4> LiveOuts;
602
2.69M
  for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
603
6.01M
         SE = MBB->succ_end(); SI != SE; 
++SI3.32M
) {
604
3.32M
    MachineBasicBlock *SuccMBB = *SI;
605
3.32M
    if (SuccMBB->isEHPad())
606
27.3k
      continue;
607
3.29M
    for (const auto &LI : SuccMBB->liveins()) {
608
2.69k
      if (!TRI->isInAllocatableClass(LI.PhysReg))
609
2.67k
        // Ignore other live-ins, e.g. those that are live into landing pads.
610
2.67k
        LiveOuts.insert(LI.PhysReg);
611
2.69k
    }
612
3.29M
  }
613
2.69M
614
2.69M
  // Loop over PhysRegDef / PhysRegUse, killing any registers that are
615
2.69M
  // available at the end of the basic block.
616
1.58G
  for (unsigned i = 0; i != NumRegs; 
++i1.58G
)
617
1.58G
    if ((PhysRegDef[i] || 
PhysRegUse[i]1.57G
) &&
!LiveOuts.count(i)9.10M
)
618
9.10M
      HandlePhysRegDef(i, nullptr, Defs);
619
2.69M
}
620
621
495k
bool LiveVariables::runOnMachineFunction(MachineFunction &mf) {
622
495k
  MF = &mf;
623
495k
  MRI = &mf.getRegInfo();
624
495k
  TRI = MF->getSubtarget().getRegisterInfo();
625
495k
626
495k
  const unsigned NumRegs = TRI->getNumRegs();
627
495k
  PhysRegDef.assign(NumRegs, nullptr);
628
495k
  PhysRegUse.assign(NumRegs, nullptr);
629
495k
  PHIVarInfo.resize(MF->getNumBlockIDs());
630
495k
  PHIJoins.clear();
631
495k
632
495k
  // FIXME: LiveIntervals will be updated to remove its dependence on
633
495k
  // LiveVariables to improve compilation time and eliminate bizarre pass
634
495k
  // dependencies. Until then, we can't change much in -O0.
635
495k
  if (!MRI->isSSA())
636
0
    report_fatal_error("regalloc=... not currently supported with -O0");
637
495k
638
495k
  analyzePHINodes(mf);
639
495k
640
495k
  // Calculate live variable information in depth first order on the CFG of the
641
495k
  // function.  This guarantees that we will see the definition of a virtual
642
495k
  // register before its uses due to dominance properties of SSA (except for PHI
643
495k
  // nodes, which are treated as a special case).
644
495k
  MachineBasicBlock *Entry = &MF->front();
645
495k
  df_iterator_default_set<MachineBasicBlock*,16> Visited;
646
495k
647
2.69M
  for (MachineBasicBlock *MBB : depth_first_ext(Entry, Visited)) {
648
2.69M
    runOnBlock(MBB, NumRegs);
649
2.69M
650
2.69M
    PhysRegDef.assign(NumRegs, nullptr);
651
2.69M
    PhysRegUse.assign(NumRegs, nullptr);
652
2.69M
  }
653
495k
654
495k
  // Convert and transfer the dead / killed information we have gathered into
655
495k
  // VirtRegInfo onto MI's.
656
17.3M
  for (unsigned i = 0, e1 = VirtRegInfo.size(); i != e1; 
++i16.8M
) {
657
16.8M
    const unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
658
26.4M
    for (unsigned j = 0, e2 = VirtRegInfo[Reg].Kills.size(); j != e2; 
++j9.63M
)
659
9.63M
      if (VirtRegInfo[Reg].Kills[j] == MRI->getVRegDef(Reg))
660
26.0k
        VirtRegInfo[Reg].Kills[j]->addRegisterDead(Reg, TRI);
661
9.60M
      else
662
9.60M
        VirtRegInfo[Reg].Kills[j]->addRegisterKilled(Reg, TRI);
663
16.8M
  }
664
495k
665
495k
  // Check to make sure there are no unreachable blocks in the MC CFG for the
666
495k
  // function.  If so, it is due to a bug in the instruction selector or some
667
495k
  // other part of the code generator if this happens.
668
#ifndef NDEBUG
669
  for(MachineFunction::iterator i = MF->begin(), e = MF->end(); i != e; ++i)
670
    assert(Visited.count(&*i) != 0 && "unreachable basic block found");
671
#endif
672
673
495k
  PhysRegDef.clear();
674
495k
  PhysRegUse.clear();
675
495k
  PHIVarInfo.clear();
676
495k
677
495k
  return false;
678
495k
}
679
680
/// replaceKillInstruction - Update register kill info by replacing a kill
681
/// instruction with a new one.
682
void LiveVariables::replaceKillInstruction(unsigned Reg, MachineInstr &OldMI,
683
154k
                                           MachineInstr &NewMI) {
684
154k
  VarInfo &VI = getVarInfo(Reg);
685
154k
  std::replace(VI.Kills.begin(), VI.Kills.end(), &OldMI, &NewMI);
686
154k
}
687
688
/// removeVirtualRegistersKilled - Remove all killed info for the specified
689
/// instruction.
690
632k
void LiveVariables::removeVirtualRegistersKilled(MachineInstr &MI) {
691
4.31M
  for (unsigned i = 0, e = MI.getNumOperands(); i != e; 
++i3.68M
) {
692
3.68M
    MachineOperand &MO = MI.getOperand(i);
693
3.68M
    if (MO.isReg() && 
MO.isKill()2.15M
) {
694
0
      MO.setIsKill(false);
695
0
      unsigned Reg = MO.getReg();
696
0
      if (TargetRegisterInfo::isVirtualRegister(Reg)) {
697
0
        bool removed = getVarInfo(Reg).removeKill(MI);
698
0
        assert(removed && "kill not in register's VarInfo?");
699
0
        (void)removed;
700
0
      }
701
0
    }
702
3.68M
  }
703
632k
}
704
705
/// analyzePHINodes - Gather information about the PHI nodes in here. In
706
/// particular, we want to map the variable information of a virtual register
707
/// which is used in a PHI node. We map that to the BB the vreg is coming from.
708
///
709
495k
void LiveVariables::analyzePHINodes(const MachineFunction& Fn) {
710
495k
  for (const auto &MBB : Fn)
711
3.27M
    
for (const auto &BBI : MBB)2.69M
{
712
3.27M
      if (!BBI.isPHI())
713
2.64M
        break;
714
2.16M
      
for (unsigned i = 1, e = BBI.getNumOperands(); 633k
i != e;
i += 21.52M
)
715
1.52M
        if (BBI.getOperand(i).readsReg())
716
1.52M
          PHIVarInfo[BBI.getOperand(i + 1).getMBB()->getNumber()]
717
1.52M
            .push_back(BBI.getOperand(i).getReg());
718
633k
    }
719
495k
}
720
721
bool LiveVariables::VarInfo::isLiveIn(const MachineBasicBlock &MBB,
722
                                      unsigned Reg,
723
177k
                                      MachineRegisterInfo &MRI) {
724
177k
  unsigned Num = MBB.getNumber();
725
177k
726
177k
  // Reg is live-through.
727
177k
  if (AliveBlocks.test(Num))
728
33.3k
    return true;
729
143k
730
143k
  // Registers defined in MBB cannot be live in.
731
143k
  const MachineInstr *Def = MRI.getVRegDef(Reg);
732
143k
  if (Def && Def->getParent() == &MBB)
733
10
    return false;
734
143k
735
143k
 // Reg was not defined in MBB, was it killed here?
736
143k
  return findKill(&MBB);
737
143k
}
738
739
1.80M
bool LiveVariables::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB) {
740
1.80M
  LiveVariables::VarInfo &VI = getVarInfo(Reg);
741
1.80M
742
1.80M
  SmallPtrSet<const MachineBasicBlock *, 8> Kills;
743
3.04M
  for (unsigned i = 0, e = VI.Kills.size(); i != e; 
++i1.23M
)
744
1.23M
    Kills.insert(VI.Kills[i]->getParent());
745
1.80M
746
1.80M
  // Loop over all of the successors of the basic block, checking to see if
747
1.80M
  // the value is either live in the block, or if it is killed in the block.
748
2.48M
  for (const MachineBasicBlock *SuccMBB : MBB.successors()) {
749
2.48M
    // Is it alive in this successor?
750
2.48M
    unsigned SuccIdx = SuccMBB->getNumber();
751
2.48M
    if (VI.AliveBlocks.test(SuccIdx))
752
260k
      return true;
753
2.22M
    // Or is it live because there is a use in a successor that kills it?
754
2.22M
    if (Kills.count(SuccMBB))
755
55.5k
      return true;
756
2.22M
  }
757
1.80M
758
1.80M
  
return false1.48M
;
759
1.80M
}
760
761
/// addNewBlock - Add a new basic block BB as an empty succcessor to DomBB. All
762
/// variables that are live out of DomBB will be marked as passing live through
763
/// BB.
764
void LiveVariables::addNewBlock(MachineBasicBlock *BB,
765
                                MachineBasicBlock *DomBB,
766
142k
                                MachineBasicBlock *SuccBB) {
767
142k
  const unsigned NumNew = BB->getNumber();
768
142k
769
142k
  DenseSet<unsigned> Defs, Kills;
770
142k
771
142k
  MachineBasicBlock::iterator BBI = SuccBB->begin(), BBE = SuccBB->end();
772
332k
  for (; BBI != BBE && 
BBI->isPHI()331k
;
++BBI190k
) {
773
190k
    // Record the def of the PHI node.
774
190k
    Defs.insert(BBI->getOperand(0).getReg());
775
190k
776
190k
    // All registers used by PHI nodes in SuccBB must be live through BB.
777
1.52M
    for (unsigned i = 1, e = BBI->getNumOperands(); i != e; 
i += 21.33M
)
778
1.33M
      if (BBI->getOperand(i+1).getMBB() == BB)
779
192k
        getVarInfo(BBI->getOperand(i).getReg()).AliveBlocks.set(NumNew);
780
190k
  }
781
142k
782
142k
  // Record all vreg defs and kills of all instructions in SuccBB.
783
1.14M
  for (; BBI != BBE; 
++BBI1.00M
) {
784
1.00M
    for (MachineInstr::mop_iterator I = BBI->operands_begin(),
785
4.16M
         E = BBI->operands_end(); I != E; 
++I3.15M
) {
786
3.15M
      if (I->isReg() && 
TargetRegisterInfo::isVirtualRegister(I->getReg())2.24M
) {
787
1.03M
        if (I->isDef())
788
337k
          Defs.insert(I->getReg());
789
701k
        else if (I->isKill())
790
436k
          Kills.insert(I->getReg());
791
1.03M
      }
792
3.15M
    }
793
1.00M
  }
794
142k
795
142k
  // Update info for all live variables
796
94.3M
  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; 
++i94.1M
) {
797
94.1M
    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
798
94.1M
799
94.1M
    // If the Defs is defined in the successor it can't be live in BB.
800
94.1M
    if (Defs.count(Reg))
801
528k
      continue;
802
93.6M
803
93.6M
    // If the register is either killed in or live through SuccBB it's also live
804
93.6M
    // through BB.
805
93.6M
    VarInfo &VI = getVarInfo(Reg);
806
93.6M
    if (Kills.count(Reg) || 
VI.AliveBlocks.test(SuccBB->getNumber())93.5M
)
807
1.57M
      VI.AliveBlocks.set(NumNew);
808
93.6M
  }
809
142k
}