Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveRegMatrix.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveRegMatrix.cpp - Track register interference --------------------===//
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 defines the LiveRegMatrix analysis pass.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/CodeGen/LiveRegMatrix.h"
14
#include "RegisterCoalescer.h"
15
#include "llvm/ADT/Statistic.h"
16
#include "llvm/CodeGen/LiveInterval.h"
17
#include "llvm/CodeGen/LiveIntervalUnion.h"
18
#include "llvm/CodeGen/LiveIntervals.h"
19
#include "llvm/CodeGen/MachineFunction.h"
20
#include "llvm/CodeGen/TargetRegisterInfo.h"
21
#include "llvm/CodeGen/TargetSubtargetInfo.h"
22
#include "llvm/CodeGen/VirtRegMap.h"
23
#include "llvm/MC/LaneBitmask.h"
24
#include "llvm/MC/MCRegisterInfo.h"
25
#include "llvm/Pass.h"
26
#include "llvm/Support/Debug.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include <cassert>
29
30
using namespace llvm;
31
32
#define DEBUG_TYPE "regalloc"
33
34
STATISTIC(NumAssigned   , "Number of registers assigned");
35
STATISTIC(NumUnassigned , "Number of registers unassigned");
36
37
char LiveRegMatrix::ID = 0;
38
102k
INITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix",
39
102k
                      "Live Register Matrix", false, false)
40
102k
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
41
102k
INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
42
102k
INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
43
                    "Live Register Matrix", false, false)
44
45
35.9k
LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
46
47
35.9k
void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
48
35.9k
  AU.setPreservesAll();
49
35.9k
  AU.addRequiredTransitive<LiveIntervals>();
50
35.9k
  AU.addRequiredTransitive<VirtRegMap>();
51
35.9k
  MachineFunctionPass::getAnalysisUsage(AU);
52
35.9k
}
53
54
509k
bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
55
509k
  TRI = MF.getSubtarget().getRegisterInfo();
56
509k
  LIS = &getAnalysis<LiveIntervals>();
57
509k
  VRM = &getAnalysis<VirtRegMap>();
58
509k
59
509k
  unsigned NumRegUnits = TRI->getNumRegUnits();
60
509k
  if (NumRegUnits != Matrix.size())
61
33.9k
    Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
62
509k
  Matrix.init(LIUAlloc, NumRegUnits);
63
509k
64
509k
  // Make sure no stale queries get reused.
65
509k
  invalidateVirtRegs();
66
509k
  return false;
67
509k
}
68
69
509k
void LiveRegMatrix::releaseMemory() {
70
99.9M
  for (unsigned i = 0, e = Matrix.size(); i != e; 
++i99.4M
) {
71
99.4M
    Matrix[i].clear();
72
99.4M
    // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
73
99.4M
    // have anything important to clear and LiveRegMatrix's runOnFunction()
74
99.4M
    // does a std::unique_ptr::reset anyways.
75
99.4M
  }
76
509k
}
77
78
template <typename Callable>
79
static bool foreachUnit(const TargetRegisterInfo *TRI,
80
                        LiveInterval &VRegInterval, unsigned PhysReg,
81
123M
                        Callable Func) {
82
123M
  if (VRegInterval.hasSubRanges()) {
83
4.34M
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); 
++Units3.05M
) {
84
3.59M
      unsigned Unit = (*Units).first;
85
3.59M
      LaneBitmask Mask = (*Units).second;
86
5.81M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87
5.81M
        if ((S.LaneMask & Mask).any()) {
88
2.62M
          if (Func(Unit, S))
89
539k
            return true;
90
2.08M
          break;
91
2.08M
        }
92
5.81M
      }
93
3.59M
    }
94
122M
  } else {
95
203M
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units81.5M
) {
96
131M
      if (Func(*Units, VRegInterval))
97
49.7M
        return true;
98
131M
    }
99
122M
  }
100
123M
  
return false73.0M
;
101
123M
}
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::assign(llvm::LiveInterval&, unsigned int)::$_0>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::assign(llvm::LiveInterval&, unsigned int)::$_0)
Line
Count
Source
81
8.39M
                        Callable Func) {
82
8.39M
  if (VRegInterval.hasSubRanges()) {
83
314k
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); 
++Units241k
) {
84
241k
      unsigned Unit = (*Units).first;
85
241k
      LaneBitmask Mask = (*Units).second;
86
563k
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87
563k
        if ((S.LaneMask & Mask).any()) {
88
232k
          if (Func(Unit, S))
89
0
            return true;
90
232k
          break;
91
232k
        }
92
563k
      }
93
241k
    }
94
8.32M
  } else {
95
18.0M
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units9.72M
) {
96
9.72M
      if (Func(*Units, VRegInterval))
97
0
        return true;
98
9.72M
    }
99
8.32M
  }
100
8.39M
  return false;
101
8.39M
}
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::unassign(llvm::LiveInterval&)::$_1>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::unassign(llvm::LiveInterval&)::$_1)
Line
Count
Source
81
574k
                        Callable Func) {
82
574k
  if (VRegInterval.hasSubRanges()) {
83
3.80k
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); 
++Units3.08k
) {
84
3.08k
      unsigned Unit = (*Units).first;
85
3.08k
      LaneBitmask Mask = (*Units).second;
86
4.58k
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87
4.58k
        if ((S.LaneMask & Mask).any()) {
88
1.86k
          if (Func(Unit, S))
89
0
            return true;
90
1.86k
          break;
91
1.86k
        }
92
4.58k
      }
93
3.08k
    }
94
574k
  } else {
95
1.38M
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units809k
) {
96
809k
      if (Func(*Units, VRegInterval))
97
0
        return true;
98
809k
    }
99
574k
  }
100
574k
  return false;
101
574k
}
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::checkRegUnitInterference(llvm::LiveInterval&, unsigned int)::$_2>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::checkRegUnitInterference(llvm::LiveInterval&, unsigned int)::$_2)
Line
Count
Source
81
58.2M
                        Callable Func) {
82
58.2M
  if (VRegInterval.hasSubRanges()) {
83
2.85M
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); 
++Units2.24M
) {
84
2.24M
      unsigned Unit = (*Units).first;
85
2.24M
      LaneBitmask Mask = (*Units).second;
86
3.62M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87
3.62M
        if ((S.LaneMask & Mask).any()) {
88
1.58M
          if (Func(Unit, S))
89
1.03k
            return true;
90
1.58M
          break;
91
1.58M
        }
92
3.62M
      }
93
2.24M
    }
94
57.6M
  } else {
95
119M
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units61.9M
) {
96
64.0M
      if (Func(*Units, VRegInterval))
97
2.13M
        return true;
98
64.0M
    }
99
57.6M
  }
100
58.2M
  
return false56.1M
;
101
58.2M
}
LiveRegMatrix.cpp:bool foreachUnit<llvm::LiveRegMatrix::checkInterference(llvm::LiveInterval&, unsigned int)::$_3>(llvm::TargetRegisterInfo const*, llvm::LiveInterval&, unsigned int, llvm::LiveRegMatrix::checkInterference(llvm::LiveInterval&, unsigned int)::$_3)
Line
Count
Source
81
56.1M
                        Callable Func) {
82
56.1M
  if (VRegInterval.hasSubRanges()) {
83
1.17M
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); Units.isValid(); 
++Units559k
) {
84
1.09M
      unsigned Unit = (*Units).first;
85
1.09M
      LaneBitmask Mask = (*Units).second;
86
1.62M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
87
1.62M
        if ((S.LaneMask & Mask).any()) {
88
803k
          if (Func(Unit, S))
89
538k
            return true;
90
264k
          break;
91
264k
        }
92
1.62M
      }
93
1.09M
    }
94
55.5M
  } else {
95
64.6M
    for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units9.12M
) {
96
56.7M
      if (Func(*Units, VRegInterval))
97
47.6M
        return true;
98
56.7M
    }
99
55.5M
  }
100
56.1M
  
return false7.93M
;
101
56.1M
}
102
103
8.39M
void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
104
8.39M
  LLVM_DEBUG(dbgs() << "assigning " << printReg(VirtReg.reg, TRI) << " to "
105
8.39M
                    << printReg(PhysReg, TRI) << ':');
106
8.39M
  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
107
8.39M
  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
108
8.39M
109
8.39M
  foreachUnit(
110
9.95M
      TRI, VirtReg, PhysReg, [&](unsigned Unit, const LiveRange &Range) {
111
9.95M
        LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI) << ' ' << Range);
112
9.95M
        Matrix[Unit].unify(VirtReg, Range);
113
9.95M
        return false;
114
9.95M
      });
115
8.39M
116
8.39M
  ++NumAssigned;
117
8.39M
  LLVM_DEBUG(dbgs() << '\n');
118
8.39M
}
119
120
574k
void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
121
574k
  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
122
574k
  LLVM_DEBUG(dbgs() << "unassigning " << printReg(VirtReg.reg, TRI) << " from "
123
574k
                    << printReg(PhysReg, TRI) << ':');
124
574k
  VRM->clearVirt(VirtReg.reg);
125
574k
126
574k
  foreachUnit(TRI, VirtReg, PhysReg,
127
811k
              [&](unsigned Unit, const LiveRange &Range) {
128
811k
                LLVM_DEBUG(dbgs() << ' ' << printRegUnit(Unit, TRI));
129
811k
                Matrix[Unit].extract(VirtReg, Range);
130
811k
                return false;
131
811k
              });
132
574k
133
574k
  ++NumUnassigned;
134
574k
  LLVM_DEBUG(dbgs() << '\n');
135
574k
}
136
137
919k
bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
138
1.37M
  for (MCRegUnitIterator Unit(PhysReg, TRI); Unit.isValid(); 
++Unit454k
) {
139
940k
    if (!Matrix[*Unit].empty())
140
485k
      return true;
141
940k
  }
142
919k
  
return false433k
;
143
919k
}
144
145
bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
146
107M
                                             unsigned PhysReg) {
147
107M
  // Check if the cached information is valid.
148
107M
  // The same BitVector can be reused for all PhysRegs.
149
107M
  // We could cache multiple VirtRegs if it becomes necessary.
150
107M
  if (RegMaskVirtReg != VirtReg.reg || 
RegMaskTag != UserTag97.9M
) {
151
9.28M
    RegMaskVirtReg = VirtReg.reg;
152
9.28M
    RegMaskTag = UserTag;
153
9.28M
    RegMaskUsable.clear();
154
9.28M
    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
155
9.28M
  }
156
107M
157
107M
  // The BitVector is indexed by PhysReg, not register unit.
158
107M
  // Regmask interference is more fine grained than regunits.
159
107M
  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
160
107M
  return !RegMaskUsable.empty() && 
(68.1M
!PhysReg68.1M
||
!RegMaskUsable.test(PhysReg)68.1M
);
161
107M
}
162
163
bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
164
58.2M
                                             unsigned PhysReg) {
165
58.2M
  if (VirtReg.empty())
166
0
    return false;
167
58.2M
  CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
168
58.2M
169
58.2M
  bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
170
65.6M
                                                       const LiveRange &Range) {
171
65.6M
    const LiveRange &UnitRange = LIS->getRegUnit(Unit);
172
65.6M
    return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
173
65.6M
  });
174
58.2M
  return Result;
175
58.2M
}
176
177
LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
178
76.0M
                                               unsigned RegUnit) {
179
76.0M
  LiveIntervalUnion::Query &Q = Queries[RegUnit];
180
76.0M
  Q.init(UserTag, LR, Matrix[RegUnit]);
181
76.0M
  return Q;
182
76.0M
}
183
184
LiveRegMatrix::InterferenceKind
185
106M
LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
186
106M
  if (VirtReg.empty())
187
10.3k
    return IK_Free;
188
106M
189
106M
  // Regmask interference is the fastest check.
190
106M
  if (checkRegMaskInterference(VirtReg, PhysReg))
191
47.9M
    return IK_RegMask;
192
58.2M
193
58.2M
  // Check for fixed interference.
194
58.2M
  if (checkRegUnitInterference(VirtReg, PhysReg))
195
2.13M
    return IK_RegUnit;
196
56.1M
197
56.1M
  // Check the matrix for virtual register interference.
198
56.1M
  bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
199
57.5M
                                  [&](unsigned Unit, const LiveRange &LR) {
200
57.5M
    return query(LR, Unit).checkInterference();
201
57.5M
  });
202
56.1M
  if (Interference)
203
48.1M
    return IK_VirtReg;
204
7.93M
205
7.93M
  return IK_Free;
206
7.93M
}
207
208
bool LiveRegMatrix::checkInterference(SlotIndex Start, SlotIndex End,
209
37.2k
                                      unsigned PhysReg) {
210
37.2k
  // Construct artificial live range containing only one segment [Start, End).
211
37.2k
  VNInfo valno(0, Start);
212
37.2k
  LiveRange::Segment Seg(Start, End, &valno);
213
37.2k
  LiveRange LR;
214
37.2k
  LR.addSegment(Seg);
215
37.2k
216
37.2k
  // Check for interference with that segment
217
89.9k
  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); 
++Units52.7k
) {
218
71.2k
    if (query(LR, *Units).checkInterference())
219
18.5k
      return true;
220
71.2k
  }
221
37.2k
  
return false18.7k
;
222
37.2k
}