Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/LiveRegMatrix.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveRegMatrix.cpp - Track register interference --------------------===//
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 defines the LiveRegMatrix analysis pass.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/CodeGen/LiveRegMatrix.h"
15
#include "RegisterCoalescer.h"
16
#include "llvm/ADT/Statistic.h"
17
#include "llvm/CodeGen/LiveInterval.h"
18
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
19
#include "llvm/CodeGen/LiveIntervalUnion.h"
20
#include "llvm/CodeGen/MachineFunction.h"
21
#include "llvm/CodeGen/VirtRegMap.h"
22
#include "llvm/MC/LaneBitmask.h"
23
#include "llvm/MC/MCRegisterInfo.h"
24
#include "llvm/Pass.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/raw_ostream.h"
27
#include "llvm/Target/TargetRegisterInfo.h"
28
#include "llvm/Target/TargetSubtargetInfo.h"
29
#include <cassert>
30
31
using namespace llvm;
32
33
#define DEBUG_TYPE "regalloc"
34
35
STATISTIC(NumAssigned   , "Number of registers assigned");
36
STATISTIC(NumUnassigned , "Number of registers unassigned");
37
38
char LiveRegMatrix::ID = 0;
39
36.7k
INITIALIZE_PASS_BEGIN36.7k
(LiveRegMatrix, "liveregmatrix",
40
36.7k
                      "Live Register Matrix", false, false)
41
36.7k
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
42
36.7k
INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
43
36.7k
INITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix",
44
                    "Live Register Matrix", false, false)
45
46
31.7k
LiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID) {}
47
48
31.8k
void LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const {
49
31.8k
  AU.setPreservesAll();
50
31.8k
  AU.addRequiredTransitive<LiveIntervals>();
51
31.8k
  AU.addRequiredTransitive<VirtRegMap>();
52
31.8k
  MachineFunctionPass::getAnalysisUsage(AU);
53
31.8k
}
54
55
587k
bool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) {
56
587k
  TRI = MF.getSubtarget().getRegisterInfo();
57
587k
  LIS = &getAnalysis<LiveIntervals>();
58
587k
  VRM = &getAnalysis<VirtRegMap>();
59
587k
60
587k
  unsigned NumRegUnits = TRI->getNumRegUnits();
61
587k
  if (NumRegUnits != Matrix.size())
62
30.8k
    Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]);
63
587k
  Matrix.init(LIUAlloc, NumRegUnits);
64
587k
65
587k
  // Make sure no stale queries get reused.
66
587k
  invalidateVirtRegs();
67
587k
  return false;
68
587k
}
69
70
587k
void LiveRegMatrix::releaseMemory() {
71
76.1M
  for (unsigned i = 0, e = Matrix.size(); 
i != e76.1M
;
++i75.6M
) {
72
75.6M
    Matrix[i].clear();
73
75.6M
    // No need to clear Queries here, since LiveIntervalUnion::Query doesn't
74
75.6M
    // have anything important to clear and LiveRegMatrix's runOnFunction()
75
75.6M
    // does a std::unique_ptr::reset anyways.
76
75.6M
  }
77
587k
}
78
79
template <typename Callable>
80
static bool foreachUnit(const TargetRegisterInfo *TRI,
81
                        LiveInterval &VRegInterval, unsigned PhysReg,
82
146M
                        Callable Func) {
83
146M
  if (
VRegInterval.hasSubRanges()146M
) {
84
4.52M
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); 
Units.isValid()4.52M
;
++Units2.71M
) {
85
3.75M
      unsigned Unit = (*Units).first;
86
3.75M
      LaneBitmask Mask = (*Units).second;
87
7.04M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88
7.04M
        if (
(S.LaneMask & Mask).any()7.04M
) {
89
3.74M
          if (Func(Unit, S))
90
1.04M
            return true;
91
2.69M
          break;
92
2.69M
        }
93
7.04M
      }
94
3.75M
    }
95
146M
  } else {
96
233M
    for (MCRegUnitIterator Units(PhysReg, TRI); 
Units.isValid()233M
;
++Units88.2M
) {
97
146M
      if (Func(*Units, VRegInterval))
98
57.9M
        return true;
99
146M
    }
100
145M
  }
101
87.9M
  return false;
102
146M
}
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
82
10.4M
                        Callable Func) {
83
10.4M
  if (
VRegInterval.hasSubRanges()10.4M
) {
84
198k
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); 
Units.isValid()198k
;
++Units150k
) {
85
150k
      unsigned Unit = (*Units).first;
86
150k
      LaneBitmask Mask = (*Units).second;
87
343k
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88
343k
        if (
(S.LaneMask & Mask).any()343k
) {
89
147k
          if (Func(Unit, S))
90
0
            return true;
91
147k
          break;
92
147k
        }
93
343k
      }
94
150k
    }
95
10.4M
  } else {
96
21.0M
    for (MCRegUnitIterator Units(PhysReg, TRI); 
Units.isValid()21.0M
;
++Units10.6M
) {
97
10.6M
      if (Func(*Units, VRegInterval))
98
0
        return true;
99
10.6M
    }
100
10.4M
  }
101
10.4M
  return false;
102
10.4M
}
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
82
603k
                        Callable Func) {
83
603k
  if (
VRegInterval.hasSubRanges()603k
) {
84
3.93k
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); 
Units.isValid()3.93k
;
++Units2.87k
) {
85
2.87k
      unsigned Unit = (*Units).first;
86
2.87k
      LaneBitmask Mask = (*Units).second;
87
5.80k
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88
5.80k
        if (
(S.LaneMask & Mask).any()5.80k
) {
89
2.86k
          if (Func(Unit, S))
90
0
            return true;
91
2.86k
          break;
92
2.86k
        }
93
5.80k
      }
94
2.87k
    }
95
603k
  } else {
96
1.22M
    for (MCRegUnitIterator Units(PhysReg, TRI); 
Units.isValid()1.22M
;
++Units617k
) {
97
617k
      if (Func(*Units, VRegInterval))
98
0
        return true;
99
617k
    }
100
602k
  }
101
603k
  return false;
102
603k
}
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
82
68.9M
                        Callable Func) {
83
68.9M
  if (
VRegInterval.hasSubRanges()68.9M
) {
84
3.48M
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); 
Units.isValid()3.48M
;
++Units2.38M
) {
85
2.81M
      unsigned Unit = (*Units).first;
86
2.81M
      LaneBitmask Mask = (*Units).second;
87
5.57M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88
5.57M
        if (
(S.LaneMask & Mask).any()5.57M
) {
89
2.79M
          if (Func(Unit, S))
90
424k
            return true;
91
2.37M
          break;
92
2.37M
        }
93
5.57M
      }
94
2.81M
    }
95
68.9M
  } else {
96
134M
    for (MCRegUnitIterator Units(PhysReg, TRI); 
Units.isValid()134M
;
++Units66.8M
) {
97
68.5M
      if (Func(*Units, VRegInterval))
98
1.64M
        return true;
99
68.5M
    }
100
67.8M
  }
101
66.8M
  return false;
102
68.9M
}
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
82
66.8M
                        Callable Func) {
83
66.8M
  if (
VRegInterval.hasSubRanges()66.8M
) {
84
843k
    for (MCRegUnitMaskIterator Units(PhysReg, TRI); 
Units.isValid()843k
;
++Units171k
) {
85
796k
      unsigned Unit = (*Units).first;
86
796k
      LaneBitmask Mask = (*Units).second;
87
1.11M
      for (LiveInterval::SubRange &S : VRegInterval.subranges()) {
88
1.11M
        if (
(S.LaneMask & Mask).any()1.11M
) {
89
793k
          if (Func(Unit, S))
90
624k
            return true;
91
168k
          break;
92
168k
        }
93
1.11M
      }
94
796k
    }
95
66.8M
  } else {
96
76.3M
    for (MCRegUnitIterator Units(PhysReg, TRI); 
Units.isValid()76.3M
;
++Units10.0M
) {
97
66.4M
      if (Func(*Units, VRegInterval))
98
56.3M
        return true;
99
66.4M
    }
100
66.2M
  }
101
9.93M
  return false;
102
66.8M
}
103
104
10.4M
void LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) {
105
10.4M
  DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI)
106
10.4M
               << " to " << PrintReg(PhysReg, TRI) << ':');
107
10.4M
  assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment");
108
10.4M
  VRM->assignVirt2Phys(VirtReg.reg, PhysReg);
109
10.4M
110
10.4M
  foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
111
10.7M
                                         const LiveRange &Range) {
112
10.7M
    DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << ' ' << Range);
113
10.7M
    Matrix[Unit].unify(VirtReg, Range);
114
10.7M
    return false;
115
10.7M
  });
116
10.4M
117
10.4M
  ++NumAssigned;
118
10.4M
  DEBUG(dbgs() << '\n');
119
10.4M
}
120
121
603k
void LiveRegMatrix::unassign(LiveInterval &VirtReg) {
122
603k
  unsigned PhysReg = VRM->getPhys(VirtReg.reg);
123
603k
  DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI)
124
603k
               << " from " << PrintReg(PhysReg, TRI) << ':');
125
603k
  VRM->clearVirt(VirtReg.reg);
126
603k
127
603k
  foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
128
620k
                                         const LiveRange &Range) {
129
620k
    DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI));
130
620k
    Matrix[Unit].extract(VirtReg, Range);
131
620k
    return false;
132
620k
  });
133
603k
134
603k
  ++NumUnassigned;
135
603k
  DEBUG(dbgs() << '\n');
136
603k
}
137
138
1.84M
bool LiveRegMatrix::isPhysRegUsed(unsigned PhysReg) const {
139
2.92M
  for (MCRegUnitIterator Unit(PhysReg, TRI); 
Unit.isValid()2.92M
;
++Unit1.07M
) {
140
1.85M
    if (!Matrix[*Unit].empty())
141
781k
      return true;
142
1.85M
  }
143
1.06M
  return false;
144
1.84M
}
145
146
bool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg,
147
124M
                                             unsigned PhysReg) {
148
124M
  // Check if the cached information is valid.
149
124M
  // The same BitVector can be reused for all PhysRegs.
150
124M
  // We could cache multiple VirtRegs if it becomes necessary.
151
124M
  if (
RegMaskVirtReg != VirtReg.reg || 124M
RegMaskTag != UserTag113M
) {
152
11.2M
    RegMaskVirtReg = VirtReg.reg;
153
11.2M
    RegMaskTag = UserTag;
154
11.2M
    RegMaskUsable.clear();
155
11.2M
    LIS->checkRegMaskInterference(VirtReg, RegMaskUsable);
156
11.2M
  }
157
124M
158
124M
  // The BitVector is indexed by PhysReg, not register unit.
159
124M
  // Regmask interference is more fine grained than regunits.
160
124M
  // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8.
161
76.3M
  return !RegMaskUsable.empty() && 
(!PhysReg || 76.3M
!RegMaskUsable.test(PhysReg)76.3M
);
162
124M
}
163
164
bool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg,
165
68.9M
                                             unsigned PhysReg) {
166
68.9M
  if (VirtReg.empty())
167
0
    return false;
168
68.9M
  CoalescerPair CP(VirtReg.reg, PhysReg, *TRI);
169
68.9M
170
68.9M
  bool Result = foreachUnit(TRI, VirtReg, PhysReg, [&](unsigned Unit,
171
71.3M
                                                       const LiveRange &Range) {
172
71.3M
    const LiveRange &UnitRange = LIS->getRegUnit(Unit);
173
71.3M
    return Range.overlaps(UnitRange, CP, *LIS->getSlotIndexes());
174
71.3M
  });
175
68.9M
  return Result;
176
68.9M
}
177
178
LiveIntervalUnion::Query &LiveRegMatrix::query(const LiveRange &LR,
179
86.3M
                                               unsigned RegUnit) {
180
86.3M
  LiveIntervalUnion::Query &Q = Queries[RegUnit];
181
86.3M
  Q.init(UserTag, LR, Matrix[RegUnit]);
182
86.3M
  return Q;
183
86.3M
}
184
185
LiveRegMatrix::InterferenceKind
186
124M
LiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) {
187
124M
  if (VirtReg.empty())
188
6.09k
    return IK_Free;
189
124M
190
124M
  // Regmask interference is the fastest check.
191
124M
  
if (124M
checkRegMaskInterference(VirtReg, PhysReg)124M
)
192
55.2M
    return IK_RegMask;
193
68.9M
194
68.9M
  // Check for fixed interference.
195
68.9M
  
if (68.9M
checkRegUnitInterference(VirtReg, PhysReg)68.9M
)
196
2.06M
    return IK_RegUnit;
197
66.8M
198
66.8M
  // Check the matrix for virtual register interference.
199
66.8M
  bool Interference = foreachUnit(TRI, VirtReg, PhysReg,
200
67.2M
                                  [&](unsigned Unit, const LiveRange &LR) {
201
67.2M
    return query(LR, Unit).checkInterference();
202
67.2M
  });
203
66.8M
  if (Interference)
204
56.9M
    return IK_VirtReg;
205
9.93M
206
9.93M
  return IK_Free;
207
9.93M
}