Coverage Report

Created: 2017-10-03 07:32

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