Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/RenameIndependentSubregs.cpp
Line
Count
Source
1
//===-- RenameIndependentSubregs.cpp - Live Interval Analysis -------------===//
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
/// Rename independent subregisters looks for virtual registers with
10
/// independently used subregisters and renames them to new virtual registers.
11
/// Example: In the following:
12
///   %0:sub0<read-undef> = ...
13
///   %0:sub1 = ...
14
///   use %0:sub0
15
///   %0:sub0 = ...
16
///   use %0:sub0
17
///   use %0:sub1
18
/// sub0 and sub1 are never used together, and we have two independent sub0
19
/// definitions. This pass will rename to:
20
///   %0:sub0<read-undef> = ...
21
///   %1:sub1<read-undef> = ...
22
///   use %1:sub1
23
///   %2:sub1<read-undef> = ...
24
///   use %2:sub1
25
///   use %0:sub0
26
//
27
//===----------------------------------------------------------------------===//
28
29
#include "LiveRangeUtils.h"
30
#include "PHIEliminationUtils.h"
31
#include "llvm/CodeGen/LiveInterval.h"
32
#include "llvm/CodeGen/LiveIntervals.h"
33
#include "llvm/CodeGen/MachineFunctionPass.h"
34
#include "llvm/CodeGen/MachineInstrBuilder.h"
35
#include "llvm/CodeGen/MachineRegisterInfo.h"
36
#include "llvm/CodeGen/Passes.h"
37
#include "llvm/CodeGen/TargetInstrInfo.h"
38
39
using namespace llvm;
40
41
#define DEBUG_TYPE "rename-independent-subregs"
42
43
namespace {
44
45
class RenameIndependentSubregs : public MachineFunctionPass {
46
public:
47
  static char ID;
48
34.2k
  RenameIndependentSubregs() : MachineFunctionPass(ID) {}
49
50
522k
  StringRef getPassName() const override {
51
522k
    return "Rename Disconnected Subregister Components";
52
522k
  }
53
54
34.0k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
55
34.0k
    AU.setPreservesCFG();
56
34.0k
    AU.addRequired<LiveIntervals>();
57
34.0k
    AU.addPreserved<LiveIntervals>();
58
34.0k
    AU.addRequired<SlotIndexes>();
59
34.0k
    AU.addPreserved<SlotIndexes>();
60
34.0k
    MachineFunctionPass::getAnalysisUsage(AU);
61
34.0k
  }
62
63
  bool runOnMachineFunction(MachineFunction &MF) override;
64
65
private:
66
  struct SubRangeInfo {
67
    ConnectedVNInfoEqClasses ConEQ;
68
    LiveInterval::SubRange *SR;
69
    unsigned Index;
70
71
    SubRangeInfo(LiveIntervals &LIS, LiveInterval::SubRange &SR,
72
                 unsigned Index)
73
148k
      : ConEQ(LIS), SR(&SR), Index(Index) {}
74
  };
75
76
  /// Split unrelated subregister components and rename them to new vregs.
77
  bool renameComponents(LiveInterval &LI) const;
78
79
  /// Build a vector of SubRange infos and a union find set of
80
  /// equivalence classes.
81
  /// Returns true if more than 1 equivalence class was found.
82
  bool findComponents(IntEqClasses &Classes,
83
                      SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
84
                      LiveInterval &LI) const;
85
86
  /// Distribute the LiveInterval segments into the new LiveIntervals
87
  /// belonging to their class.
88
  void distribute(const IntEqClasses &Classes,
89
                  const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
90
                  const SmallVectorImpl<LiveInterval*> &Intervals) const;
91
92
  /// Constructs main liverange and add missing undef+dead flags.
93
  void computeMainRangesFixFlags(const IntEqClasses &Classes,
94
      const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
95
      const SmallVectorImpl<LiveInterval*> &Intervals) const;
96
97
  /// Rewrite Machine Operands to use the new vreg belonging to their class.
98
  void rewriteOperands(const IntEqClasses &Classes,
99
                       const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
100
                       const SmallVectorImpl<LiveInterval*> &Intervals) const;
101
102
103
  LiveIntervals *LIS;
104
  MachineRegisterInfo *MRI;
105
  const TargetInstrInfo *TII;
106
};
107
108
} // end anonymous namespace
109
110
char RenameIndependentSubregs::ID;
111
112
char &llvm::RenameIndependentSubregsID = RenameIndependentSubregs::ID;
113
114
42.3k
INITIALIZE_PASS_BEGIN(RenameIndependentSubregs, DEBUG_TYPE,
115
42.3k
                      "Rename Independent Subregisters", false, false)
116
42.3k
INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
117
42.3k
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
118
42.3k
INITIALIZE_PASS_END(RenameIndependentSubregs, DEBUG_TYPE,
119
                    "Rename Independent Subregisters", false, false)
120
121
73.2k
bool RenameIndependentSubregs::renameComponents(LiveInterval &LI) const {
122
73.2k
  // Shortcut: We cannot have split components with a single definition.
123
73.2k
  if (LI.valnos.size() < 2)
124
26.1k
    return false;
125
47.0k
126
47.0k
  SmallVector<SubRangeInfo, 4> SubRangeInfos;
127
47.0k
  IntEqClasses Classes;
128
47.0k
  if (!findComponents(Classes, SubRangeInfos, LI))
129
46.9k
    return false;
130
89
131
89
  // Create a new VReg for each class.
132
89
  unsigned Reg = LI.reg;
133
89
  const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
134
89
  SmallVector<LiveInterval*, 4> Intervals;
135
89
  Intervals.push_back(&LI);
136
89
  LLVM_DEBUG(dbgs() << printReg(Reg) << ": Found " << Classes.getNumClasses()
137
89
                    << " equivalence classes.\n");
138
89
  LLVM_DEBUG(dbgs() << printReg(Reg) << ": Splitting into newly created:");
139
298
  for (unsigned I = 1, NumClasses = Classes.getNumClasses(); I < NumClasses;
140
209
       ++I) {
141
209
    unsigned NewVReg = MRI->createVirtualRegister(RegClass);
142
209
    LiveInterval &NewLI = LIS->createEmptyInterval(NewVReg);
143
209
    Intervals.push_back(&NewLI);
144
209
    LLVM_DEBUG(dbgs() << ' ' << printReg(NewVReg));
145
209
  }
146
89
  LLVM_DEBUG(dbgs() << '\n');
147
89
148
89
  rewriteOperands(Classes, SubRangeInfos, Intervals);
149
89
  distribute(Classes, SubRangeInfos, Intervals);
150
89
  computeMainRangesFixFlags(Classes, SubRangeInfos, Intervals);
151
89
  return true;
152
89
}
153
154
bool RenameIndependentSubregs::findComponents(IntEqClasses &Classes,
155
    SmallVectorImpl<RenameIndependentSubregs::SubRangeInfo> &SubRangeInfos,
156
47.0k
    LiveInterval &LI) const {
157
47.0k
  // First step: Create connected components for the VNInfos inside the
158
47.0k
  // subranges and count the global number of such components.
159
47.0k
  unsigned NumComponents = 0;
160
148k
  for (LiveInterval::SubRange &SR : LI.subranges()) {
161
148k
    SubRangeInfos.push_back(SubRangeInfo(*LIS, SR, NumComponents));
162
148k
    ConnectedVNInfoEqClasses &ConEQ = SubRangeInfos.back().ConEQ;
163
148k
164
148k
    unsigned NumSubComponents = ConEQ.Classify(SR);
165
148k
    NumComponents += NumSubComponents;
166
148k
  }
167
47.0k
  // Shortcut: With only 1 subrange, the normal separate component tests are
168
47.0k
  // enough and we do not need to perform the union-find on the subregister
169
47.0k
  // segments.
170
47.0k
  if (SubRangeInfos.size() < 2)
171
9
    return false;
172
47.0k
173
47.0k
  // Next step: Build union-find structure over all subranges and merge classes
174
47.0k
  // across subranges when they are affected by the same MachineOperand.
175
47.0k
  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
176
47.0k
  Classes.grow(NumComponents);
177
47.0k
  unsigned Reg = LI.reg;
178
225k
  for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
179
225k
    if (!MO.isDef() && 
!MO.readsReg()82.9k
)
180
63
      continue;
181
225k
    unsigned SubRegIdx = MO.getSubReg();
182
225k
    LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
183
225k
    unsigned MergedID = ~0u;
184
822k
    for (RenameIndependentSubregs::SubRangeInfo &SRInfo : SubRangeInfos) {
185
822k
      const LiveInterval::SubRange &SR = *SRInfo.SR;
186
822k
      if ((SR.LaneMask & LaneMask).none())
187
453k
        continue;
188
369k
      SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
189
369k
      Pos = MO.isDef() ? 
Pos.getRegSlot(MO.isEarlyClobber())155k
190
369k
                       : 
Pos.getBaseIndex()213k
;
191
369k
      const VNInfo *VNI = SR.getVNInfoAt(Pos);
192
369k
      if (VNI == nullptr)
193
304
        continue;
194
369k
195
369k
      // Map to local representant ID.
196
369k
      unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
197
369k
      // Global ID
198
369k
      unsigned ID = LocalID + SRInfo.Index;
199
369k
      // Merge other sets
200
369k
      MergedID = MergedID == ~0u ? 
ID225k
:
Classes.join(MergedID, ID)143k
;
201
369k
    }
202
225k
  }
203
47.0k
204
47.0k
  // Early exit if we ended up with a single equivalence class.
205
47.0k
  Classes.compress();
206
47.0k
  unsigned NumClasses = Classes.getNumClasses();
207
47.0k
  return NumClasses > 1;
208
47.0k
}
209
210
void RenameIndependentSubregs::rewriteOperands(const IntEqClasses &Classes,
211
    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
212
89
    const SmallVectorImpl<LiveInterval*> &Intervals) const {
213
89
  const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
214
89
  unsigned Reg = Intervals[0]->reg;
215
89
  for (MachineRegisterInfo::reg_nodbg_iterator I = MRI->reg_nodbg_begin(Reg),
216
1.02k
       E = MRI->reg_nodbg_end(); I != E; ) {
217
939
    MachineOperand &MO = *I++;
218
939
    if (!MO.isDef() && 
!MO.readsReg()505
)
219
2
      continue;
220
937
221
937
    auto *MI = MO.getParent();
222
937
    SlotIndex Pos = LIS->getInstructionIndex(*MI);
223
937
    Pos = MO.isDef() ? 
Pos.getRegSlot(MO.isEarlyClobber())434
224
937
                     : 
Pos.getBaseIndex()503
;
225
937
    unsigned SubRegIdx = MO.getSubReg();
226
937
    LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubRegIdx);
227
937
228
937
    unsigned ID = ~0u;
229
5.93k
    for (const SubRangeInfo &SRInfo : SubRangeInfos) {
230
5.93k
      const LiveInterval::SubRange &SR = *SRInfo.SR;
231
5.93k
      if ((SR.LaneMask & LaneMask).none())
232
4.99k
        continue;
233
940
      const VNInfo *VNI = SR.getVNInfoAt(Pos);
234
940
      if (VNI == nullptr)
235
3
        continue;
236
937
237
937
      // Map to local representant ID.
238
937
      unsigned LocalID = SRInfo.ConEQ.getEqClass(VNI);
239
937
      // Global ID
240
937
      ID = Classes[LocalID + SRInfo.Index];
241
937
      break;
242
937
    }
243
937
244
937
    unsigned VReg = Intervals[ID]->reg;
245
937
    MO.setReg(VReg);
246
937
247
937
    if (MO.isTied() && 
Reg != VReg5
) {
248
3
      /// Undef use operands are not tracked in the equivalence class,
249
3
      /// but need to be updated if they are tied; take care to only
250
3
      /// update the tied operand.
251
3
      unsigned OperandNo = MI->getOperandNo(&MO);
252
3
      unsigned TiedIdx = MI->findTiedOperandIdx(OperandNo);
253
3
      MI->getOperand(TiedIdx).setReg(VReg);
254
3
255
3
      // above substitution breaks the iterator, so restart.
256
3
      I = MRI->reg_nodbg_begin(Reg);
257
3
    }
258
937
  }
259
89
  // TODO: We could attempt to recompute new register classes while visiting
260
89
  // the operands: Some of the split register may be fine with less constraint
261
89
  // classes than the original vreg.
262
89
}
263
264
void RenameIndependentSubregs::distribute(const IntEqClasses &Classes,
265
    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
266
89
    const SmallVectorImpl<LiveInterval*> &Intervals) const {
267
89
  unsigned NumClasses = Classes.getNumClasses();
268
89
  SmallVector<unsigned, 8> VNIMapping;
269
89
  SmallVector<LiveInterval::SubRange*, 8> SubRanges;
270
89
  BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
271
818
  for (const SubRangeInfo &SRInfo : SubRangeInfos) {
272
818
    LiveInterval::SubRange &SR = *SRInfo.SR;
273
818
    unsigned NumValNos = SR.valnos.size();
274
818
    VNIMapping.clear();
275
818
    VNIMapping.reserve(NumValNos);
276
818
    SubRanges.clear();
277
818
    SubRanges.resize(NumClasses-1, nullptr);
278
1.82k
    for (unsigned I = 0; I < NumValNos; 
++I1.00k
) {
279
1.00k
      const VNInfo &VNI = *SR.valnos[I];
280
1.00k
      unsigned LocalID = SRInfo.ConEQ.getEqClass(&VNI);
281
1.00k
      unsigned ID = Classes[LocalID + SRInfo.Index];
282
1.00k
      VNIMapping.push_back(ID);
283
1.00k
      if (ID > 0 && 
SubRanges[ID-1] == nullptr760
)
284
621
        SubRanges[ID-1] = Intervals[ID]->createSubRange(Allocator, SR.LaneMask);
285
1.00k
    }
286
818
    DistributeRange(SR, SubRanges.data(), VNIMapping);
287
818
  }
288
89
}
289
290
938
static bool subRangeLiveAt(const LiveInterval &LI, SlotIndex Pos) {
291
1.57k
  for (const LiveInterval::SubRange &SR : LI.subranges()) {
292
1.57k
    if (SR.liveAt(Pos))
293
698
      return true;
294
1.57k
  }
295
938
  
return false240
;
296
938
}
297
298
void RenameIndependentSubregs::computeMainRangesFixFlags(
299
    const IntEqClasses &Classes,
300
    const SmallVectorImpl<SubRangeInfo> &SubRangeInfos,
301
89
    const SmallVectorImpl<LiveInterval*> &Intervals) const {
302
89
  BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator();
303
89
  const SlotIndexes &Indexes = *LIS->getSlotIndexes();
304
387
  for (size_t I = 0, E = Intervals.size(); I < E; 
++I298
) {
305
298
    LiveInterval &LI = *Intervals[I];
306
298
    unsigned Reg = LI.reg;
307
298
308
298
    LI.removeEmptySubRanges();
309
298
310
298
    // There must be a def (or live-in) before every use. Splitting vregs may
311
298
    // violate this principle as the splitted vreg may not have a definition on
312
298
    // every path. Fix this by creating IMPLICIT_DEF instruction as necessary.
313
823
    for (const LiveInterval::SubRange &SR : LI.subranges()) {
314
823
      // Search for "PHI" value numbers in the subranges. We must find a live
315
823
      // value in each predecessor block, add an IMPLICIT_DEF where it is
316
823
      // missing.
317
1.84k
      for (unsigned I = 0; I < SR.valnos.size(); 
++I1.01k
) {
318
1.01k
        const VNInfo &VNI = *SR.valnos[I];
319
1.01k
        if (VNI.isUnused() || 
!VNI.isPHIDef()996
)
320
930
          continue;
321
87
322
87
        SlotIndex Def = VNI.def;
323
87
        MachineBasicBlock &MBB = *Indexes.getMBBFromIndex(Def);
324
174
        for (MachineBasicBlock *PredMBB : MBB.predecessors()) {
325
174
          SlotIndex PredEnd = Indexes.getMBBEndIdx(PredMBB);
326
174
          if (subRangeLiveAt(LI, PredEnd.getPrevSlot()))
327
162
            continue;
328
12
329
12
          MachineBasicBlock::iterator InsertPos =
330
12
            llvm::findPHICopyInsertPoint(PredMBB, &MBB, Reg);
331
12
          const MCInstrDesc &MCDesc = TII->get(TargetOpcode::IMPLICIT_DEF);
332
12
          MachineInstrBuilder ImpDef = BuildMI(*PredMBB, InsertPos,
333
12
                                               DebugLoc(), MCDesc, Reg);
334
12
          SlotIndex DefIdx = LIS->InsertMachineInstrInMaps(*ImpDef);
335
12
          SlotIndex RegDefIdx = DefIdx.getRegSlot();
336
14
          for (LiveInterval::SubRange &SR : LI.subranges()) {
337
14
            VNInfo *SRVNI = SR.getNextValue(RegDefIdx, Allocator);
338
14
            SR.addSegment(LiveRange::Segment(RegDefIdx, PredEnd, SRVNI));
339
14
          }
340
12
        }
341
87
      }
342
823
    }
343
298
344
952
    for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
345
952
      if (!MO.isDef())
346
508
        continue;
347
444
      unsigned SubRegIdx = MO.getSubReg();
348
444
      if (SubRegIdx == 0)
349
13
        continue;
350
431
      // After assigning the new vreg we may not have any other sublanes living
351
431
      // in and out of the instruction anymore. We need to add new dead and
352
431
      // undef flags in these cases.
353
431
      if (!MO.isUndef()) {
354
334
        SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent());
355
334
        if (!subRangeLiveAt(LI, Pos))
356
223
          MO.setIsUndef();
357
334
      }
358
431
      if (!MO.isDead()) {
359
430
        SlotIndex Pos = LIS->getInstructionIndex(*MO.getParent()).getDeadSlot();
360
430
        if (!subRangeLiveAt(LI, Pos))
361
5
          MO.setIsDead();
362
430
      }
363
431
    }
364
298
365
298
    if (I == 0)
366
89
      LI.clear();
367
298
    LIS->constructMainRangeFromSubranges(LI);
368
298
    // A def of a subregister may be a use of other register lanes. Replacing
369
298
    // such a def with a def of a different register will eliminate the use,
370
298
    // and may cause the recorded live range to be larger than the actual
371
298
    // liveness in the program IR.
372
298
    LIS->shrinkToUses(&LI);
373
298
  }
374
89
}
375
376
488k
bool RenameIndependentSubregs::runOnMachineFunction(MachineFunction &MF) {
377
488k
  // Skip renaming if liveness of subregister is not tracked.
378
488k
  MRI = &MF.getRegInfo();
379
488k
  if (!MRI->subRegLivenessEnabled())
380
457k
    return false;
381
30.9k
382
30.9k
  LLVM_DEBUG(dbgs() << "Renaming independent subregister live ranges in "
383
30.9k
                    << MF.getName() << '\n');
384
30.9k
385
30.9k
  LIS = &getAnalysis<LiveIntervals>();
386
30.9k
  TII = MF.getSubtarget().getInstrInfo();
387
30.9k
388
30.9k
  // Iterate over all vregs. Note that we query getNumVirtRegs() the newly
389
30.9k
  // created vregs end up with higher numbers but do not need to be visited as
390
30.9k
  // there can't be any further splitting.
391
30.9k
  bool Changed = false;
392
987k
  for (size_t I = 0, E = MRI->getNumVirtRegs(); I < E; 
++I956k
) {
393
956k
    unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
394
956k
    if (!LIS->hasInterval(Reg))
395
646k
      continue;
396
310k
    LiveInterval &LI = LIS->getInterval(Reg);
397
310k
    if (!LI.hasSubRanges())
398
236k
      continue;
399
73.2k
400
73.2k
    Changed |= renameComponents(LI);
401
73.2k
  }
402
30.9k
403
30.9k
  return Changed;
404
30.9k
}