Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/ReachingDefAnalysis.cpp
Line
Count
Source
1
//===---- ReachingDefAnalysis.cpp - Reaching Def Analysis ---*- C++ -*-----===//
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
#include "llvm/CodeGen/ReachingDefAnalysis.h"
10
#include "llvm/CodeGen/TargetRegisterInfo.h"
11
#include "llvm/CodeGen/TargetSubtargetInfo.h"
12
13
using namespace llvm;
14
15
#define DEBUG_TYPE "reaching-deps-analysis"
16
17
char ReachingDefAnalysis::ID = 0;
18
INITIALIZE_PASS(ReachingDefAnalysis, DEBUG_TYPE, "ReachingDefAnalysis", false,
19
                true)
20
21
void ReachingDefAnalysis::enterBasicBlock(
22
564k
    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
23
564k
24
564k
  MachineBasicBlock *MBB = TraversedMBB.MBB;
25
564k
  unsigned MBBNumber = MBB->getNumber();
26
564k
  assert(MBBNumber < MBBReachingDefs.size() &&
27
564k
         "Unexpected basic block number.");
28
564k
  MBBReachingDefs[MBBNumber].resize(NumRegUnits);
29
564k
30
564k
  // Reset instruction counter in each basic block.
31
564k
  CurInstr = 0;
32
564k
33
564k
  // Set up LiveRegs to represent registers entering MBB.
34
564k
  // Default values are 'nothing happened a long time ago'.
35
564k
  if (LiveRegs.empty())
36
564k
    LiveRegs.assign(NumRegUnits, ReachingDefDefaultVal);
37
564k
38
564k
  // This is the entry block.
39
564k
  if (MBB->pred_empty()) {
40
361k
    for (const auto &LI : MBB->liveins()) {
41
1.01M
      for (MCRegUnitIterator Unit(LI.PhysReg, TRI); Unit.isValid(); 
++Unit653k
) {
42
653k
        // Treat function live-ins as if they were defined just before the first
43
653k
        // instruction.  Usually, function arguments are set up immediately
44
653k
        // before the call.
45
653k
        LiveRegs[*Unit] = -1;
46
653k
        MBBReachingDefs[MBBNumber][*Unit].push_back(LiveRegs[*Unit]);
47
653k
      }
48
361k
    }
49
160k
    LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << ": entry\n");
50
160k
    return;
51
160k
  }
52
403k
53
403k
  // Try to coalesce live-out registers from predecessors.
54
634k
  
for (MachineBasicBlock *pred : MBB->predecessors())403k
{
55
634k
    assert(unsigned(pred->getNumber()) < MBBOutRegsInfos.size() &&
56
634k
           "Should have pre-allocated MBBInfos for all MBBs");
57
634k
    const LiveRegsDefInfo &Incoming = MBBOutRegsInfos[pred->getNumber()];
58
634k
    // Incoming is null if this is a backedge from a BB
59
634k
    // we haven't processed yet
60
634k
    if (Incoming.empty())
61
20.6k
      continue;
62
613k
63
88.7M
    
for (unsigned Unit = 0; 613k
Unit != NumRegUnits;
++Unit88.1M
) {
64
88.1M
      // Use the most recent predecessor def for each register.
65
88.1M
      LiveRegs[Unit] = std::max(LiveRegs[Unit], Incoming[Unit]);
66
88.1M
      if ((LiveRegs[Unit] != ReachingDefDefaultVal))
67
16.8M
        MBBReachingDefs[MBBNumber][Unit].push_back(LiveRegs[Unit]);
68
88.1M
    }
69
613k
  }
70
403k
71
403k
  LLVM_DEBUG(dbgs() << printMBBReference(*MBB)
72
403k
                    << (!TraversedMBB.IsDone ? ": incomplete\n"
73
403k
                                             : ": all preds known\n"));
74
403k
}
75
76
void ReachingDefAnalysis::leaveBasicBlock(
77
564k
    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
78
564k
  assert(!LiveRegs.empty() && "Must enter basic block first.");
79
564k
  unsigned MBBNumber = TraversedMBB.MBB->getNumber();
80
564k
  assert(MBBNumber < MBBOutRegsInfos.size() &&
81
564k
         "Unexpected basic block number.");
82
564k
  // Save register clearances at end of MBB - used by enterBasicBlock().
83
564k
  MBBOutRegsInfos[MBBNumber] = LiveRegs;
84
564k
85
564k
  // While processing the basic block, we kept `Def` relative to the start
86
564k
  // of the basic block for convenience. However, future use of this information
87
564k
  // only cares about the clearance from the end of the block, so adjust
88
564k
  // everything to be relative to the end of the basic block.
89
564k
  for (int &OutLiveReg : MBBOutRegsInfos[MBBNumber])
90
81.6M
    OutLiveReg -= CurInstr;
91
564k
  LiveRegs.clear();
92
564k
}
93
94
3.64M
void ReachingDefAnalysis::processDefs(MachineInstr *MI) {
95
3.64M
  assert(!MI->isDebugInstr() && "Won't process debug instructions");
96
3.64M
97
3.64M
  unsigned MBBNumber = MI->getParent()->getNumber();
98
3.64M
  assert(MBBNumber < MBBReachingDefs.size() &&
99
3.64M
         "Unexpected basic block number.");
100
3.64M
  const MCInstrDesc &MCID = MI->getDesc();
101
3.64M
  for (unsigned i = 0,
102
3.64M
                e = MI->isVariadic() ? 
MI->getNumOperands()199k
:
MCID.getNumDefs()3.44M
;
103
6.29M
       i != e; 
++i2.65M
) {
104
2.65M
    MachineOperand &MO = MI->getOperand(i);
105
2.65M
    if (!MO.isReg() || 
!MO.getReg()2.48M
)
106
199k
      continue;
107
2.45M
    if (MO.isUse())
108
240k
      continue;
109
6.69M
    
for (MCRegUnitIterator Unit(MO.getReg(), TRI); 2.21M
Unit.isValid();
++Unit4.47M
) {
110
4.47M
      // This instruction explicitly defines the current reg unit.
111
4.47M
      LLVM_DEBUG(dbgs() << printReg(MO.getReg(), TRI) << ":\t" << CurInstr
112
4.47M
                        << '\t' << *MI);
113
4.47M
114
4.47M
      // How many instructions since this reg unit was last written?
115
4.47M
      LiveRegs[*Unit] = CurInstr;
116
4.47M
      MBBReachingDefs[MBBNumber][*Unit].push_back(CurInstr);
117
4.47M
    }
118
2.21M
  }
119
3.64M
  InstIds[MI] = CurInstr;
120
3.64M
  ++CurInstr;
121
3.64M
}
122
123
void ReachingDefAnalysis::processBasicBlock(
124
564k
    const LoopTraversal::TraversedMBBInfo &TraversedMBB) {
125
564k
  enterBasicBlock(TraversedMBB);
126
3.64M
  for (MachineInstr &MI : *TraversedMBB.MBB) {
127
3.64M
    if (!MI.isDebugInstr())
128
3.64M
      processDefs(&MI);
129
3.64M
  }
130
564k
  leaveBasicBlock(TraversedMBB);
131
564k
}
132
133
160k
bool ReachingDefAnalysis::runOnMachineFunction(MachineFunction &mf) {
134
160k
  if (skipFunction(mf.getFunction()))
135
207
    return false;
136
160k
  MF = &mf;
137
160k
  TRI = MF->getSubtarget().getRegisterInfo();
138
160k
139
160k
  LiveRegs.clear();
140
160k
  NumRegUnits = TRI->getNumRegUnits();
141
160k
142
160k
  MBBReachingDefs.resize(mf.getNumBlockIDs());
143
160k
144
160k
  LLVM_DEBUG(dbgs() << "********** REACHING DEFINITION ANALYSIS **********\n");
145
160k
146
160k
  // Initialize the MBBOutRegsInfos
147
160k
  MBBOutRegsInfos.resize(mf.getNumBlockIDs());
148
160k
149
160k
  // Traverse the basic blocks.
150
160k
  LoopTraversal Traversal;
151
160k
  LoopTraversal::TraversalOrder TraversedMBBOrder = Traversal.traverse(mf);
152
564k
  for (LoopTraversal::TraversedMBBInfo TraversedMBB : TraversedMBBOrder) {
153
564k
    processBasicBlock(TraversedMBB);
154
564k
  }
155
160k
156
160k
  // Sorting all reaching defs found for a ceartin reg unit in a given BB.
157
503k
  for (MBBDefsInfo &MBBDefs : MBBReachingDefs) {
158
503k
    for (MBBRegUnitDefs &RegUnitDefs : MBBDefs)
159
71.9M
      llvm::sort(RegUnitDefs);
160
503k
  }
161
160k
162
160k
  return false;
163
160k
}
164
165
160k
void ReachingDefAnalysis::releaseMemory() {
166
160k
  // Clear the internal vectors.
167
160k
  MBBOutRegsInfos.clear();
168
160k
  MBBReachingDefs.clear();
169
160k
  InstIds.clear();
170
160k
}
171
172
53.0k
int ReachingDefAnalysis::getReachingDef(MachineInstr *MI, int PhysReg) {
173
53.0k
  assert(InstIds.count(MI) && "Unexpected machine instuction.");
174
53.0k
  int InstId = InstIds[MI];
175
53.0k
  int DefRes = ReachingDefDefaultVal;
176
53.0k
  unsigned MBBNumber = MI->getParent()->getNumber();
177
53.0k
  assert(MBBNumber < MBBReachingDefs.size() &&
178
53.0k
         "Unexpected basic block number.");
179
53.0k
  int LatestDef = ReachingDefDefaultVal;
180
107k
  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); 
++Unit53.9k
) {
181
536k
    for (int Def : MBBReachingDefs[MBBNumber][*Unit]) {
182
536k
      if (Def >= InstId)
183
35.2k
        break;
184
501k
      DefRes = Def;
185
501k
    }
186
53.9k
    LatestDef = std::max(LatestDef, DefRes);
187
53.9k
  }
188
53.0k
  return LatestDef;
189
53.0k
}
190
191
10.3k
int ReachingDefAnalysis::getClearance(MachineInstr *MI, MCPhysReg PhysReg) {
192
10.3k
  assert(InstIds.count(MI) && "Unexpected machine instuction.");
193
10.3k
  return InstIds[MI] - getReachingDef(MI, PhysReg);
194
10.3k
}