Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LiveInterval.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LiveInterval.cpp - Live Interval Representation --------------------===//
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 implements the LiveRange and LiveInterval classes.  Given some
10
// numbering of each the machine instructions an interval [i, j) is said to be a
11
// live range for register v if there is no instruction with number j' >= j
12
// such that v is live at j' and there is no instruction with number i' < i such
13
// that v is live at i'. In this implementation ranges can have holes,
14
// i.e. a range might look like [1,20), [50,65), [1000,1001).  Each
15
// individual segment is represented as an instance of LiveRange::Segment,
16
// and the whole range is represented as an instance of LiveRange.
17
//
18
//===----------------------------------------------------------------------===//
19
20
#include "llvm/CodeGen/LiveInterval.h"
21
#include "LiveRangeUtils.h"
22
#include "RegisterCoalescer.h"
23
#include "llvm/ADT/ArrayRef.h"
24
#include "llvm/ADT/STLExtras.h"
25
#include "llvm/ADT/SmallPtrSet.h"
26
#include "llvm/ADT/SmallVector.h"
27
#include "llvm/ADT/iterator_range.h"
28
#include "llvm/CodeGen/LiveIntervals.h"
29
#include "llvm/CodeGen/MachineBasicBlock.h"
30
#include "llvm/CodeGen/MachineInstr.h"
31
#include "llvm/CodeGen/MachineOperand.h"
32
#include "llvm/CodeGen/MachineRegisterInfo.h"
33
#include "llvm/CodeGen/SlotIndexes.h"
34
#include "llvm/CodeGen/TargetRegisterInfo.h"
35
#include "llvm/Config/llvm-config.h"
36
#include "llvm/MC/LaneBitmask.h"
37
#include "llvm/Support/Compiler.h"
38
#include "llvm/Support/Debug.h"
39
#include "llvm/Support/raw_ostream.h"
40
#include <algorithm>
41
#include <cassert>
42
#include <cstddef>
43
#include <iterator>
44
#include <utility>
45
46
using namespace llvm;
47
48
namespace {
49
50
//===----------------------------------------------------------------------===//
51
// Implementation of various methods necessary for calculation of live ranges.
52
// The implementation of the methods abstracts from the concrete type of the
53
// segment collection.
54
//
55
// Implementation of the class follows the Template design pattern. The base
56
// class contains generic algorithms that call collection-specific methods,
57
// which are provided in concrete subclasses. In order to avoid virtual calls
58
// these methods are provided by means of C++ template instantiation.
59
// The base class calls the methods of the subclass through method impl(),
60
// which casts 'this' pointer to the type of the subclass.
61
//
62
//===----------------------------------------------------------------------===//
63
64
template <typename ImplT, typename IteratorT, typename CollectionT>
65
class CalcLiveRangeUtilBase {
66
protected:
67
  LiveRange *LR;
68
69
protected:
70
112M
  CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::CalcLiveRangeUtilBase(llvm::LiveRange*)
Line
Count
Source
70
15.1M
  CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::CalcLiveRangeUtilBase(llvm::LiveRange*)
Line
Count
Source
70
97.6M
  CalcLiveRangeUtilBase(LiveRange *LR) : LR(LR) {}
71
72
public:
73
  using Segment = LiveRange::Segment;
74
  using iterator = IteratorT;
75
76
  /// A counterpart of LiveRange::createDeadDef: Make sure the range has a
77
  /// value defined at @p Def.
78
  /// If @p ForVNI is null, and there is no value defined at @p Def, a new
79
  /// value will be allocated using @p VNInfoAllocator.
80
  /// If @p ForVNI is null, the return value is the value defined at @p Def,
81
  /// either a pre-existing one, or the one newly created.
82
  /// If @p ForVNI is not null, then @p Def should be the location where
83
  /// @p ForVNI is defined. If the range does not have a value defined at
84
  /// @p Def, the value @p ForVNI will be used instead of allocating a new
85
  /// one. If the range already has a value defined at @p Def, it must be
86
  /// same as @p ForVNI. In either case, @p ForVNI will be the return value.
87
  VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator *VNInfoAllocator,
88
23.9M
                        VNInfo *ForVNI) {
89
23.9M
    assert(!Def.isDead() && "Cannot define a value at the dead slot");
90
23.9M
    assert((!ForVNI || ForVNI->def == Def) &&
91
23.9M
           "If ForVNI is specified, it must match Def");
92
23.9M
    iterator I = impl().find(Def);
93
23.9M
    if (I == segments().end()) {
94
17.7M
      VNInfo *VNI = ForVNI ? 
ForVNI292k
:
LR->getNextValue(Def, *VNInfoAllocator)17.4M
;
95
17.7M
      impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
96
17.7M
      return VNI;
97
17.7M
    }
98
6.18M
99
6.18M
    Segment *S = segmentAt(I);
100
6.18M
    if (SlotIndex::isSameInstr(Def, S->start)) {
101
260k
      assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
102
260k
      assert(S->valno->def == S->start && "Inconsistent existing value def");
103
260k
104
260k
      // It is possible to have both normal and early-clobber defs of the same
105
260k
      // register on an instruction. It doesn't make a lot of sense, but it is
106
260k
      // possible to specify in inline assembly.
107
260k
      //
108
260k
      // Just convert everything to early-clobber.
109
260k
      Def = std::min(Def, S->start);
110
260k
      if (Def != S->start)
111
45
        S->start = S->valno->def = Def;
112
260k
      return S->valno;
113
260k
    }
114
5.92M
    assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
115
5.92M
    VNInfo *VNI = ForVNI ? 
ForVNI202k
:
LR->getNextValue(Def, *VNInfoAllocator)5.71M
;
116
5.92M
    segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
117
5.92M
    return VNI;
118
5.92M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::createDeadDef(llvm::SlotIndex, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>*, llvm::VNInfo*)
Line
Count
Source
88
8.45M
                        VNInfo *ForVNI) {
89
8.45M
    assert(!Def.isDead() && "Cannot define a value at the dead slot");
90
8.45M
    assert((!ForVNI || ForVNI->def == Def) &&
91
8.45M
           "If ForVNI is specified, it must match Def");
92
8.45M
    iterator I = impl().find(Def);
93
8.45M
    if (I == segments().end()) {
94
3.12M
      VNInfo *VNI = ForVNI ? 
ForVNI0
: LR->getNextValue(Def, *VNInfoAllocator);
95
3.12M
      impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
96
3.12M
      return VNI;
97
3.12M
    }
98
5.33M
99
5.33M
    Segment *S = segmentAt(I);
100
5.33M
    if (SlotIndex::isSameInstr(Def, S->start)) {
101
42.1k
      assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
102
42.1k
      assert(S->valno->def == S->start && "Inconsistent existing value def");
103
42.1k
104
42.1k
      // It is possible to have both normal and early-clobber defs of the same
105
42.1k
      // register on an instruction. It doesn't make a lot of sense, but it is
106
42.1k
      // possible to specify in inline assembly.
107
42.1k
      //
108
42.1k
      // Just convert everything to early-clobber.
109
42.1k
      Def = std::min(Def, S->start);
110
42.1k
      if (Def != S->start)
111
0
        S->start = S->valno->def = Def;
112
42.1k
      return S->valno;
113
42.1k
    }
114
5.28M
    assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
115
5.28M
    VNInfo *VNI = ForVNI ? 
ForVNI0
: LR->getNextValue(Def, *VNInfoAllocator);
116
5.28M
    segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
117
5.28M
    return VNI;
118
5.28M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::createDeadDef(llvm::SlotIndex, llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096ul, 4096ul>*, llvm::VNInfo*)
Line
Count
Source
88
15.4M
                        VNInfo *ForVNI) {
89
15.4M
    assert(!Def.isDead() && "Cannot define a value at the dead slot");
90
15.4M
    assert((!ForVNI || ForVNI->def == Def) &&
91
15.4M
           "If ForVNI is specified, it must match Def");
92
15.4M
    iterator I = impl().find(Def);
93
15.4M
    if (I == segments().end()) {
94
14.6M
      VNInfo *VNI = ForVNI ? 
ForVNI292k
:
LR->getNextValue(Def, *VNInfoAllocator)14.3M
;
95
14.6M
      impl().insertAtEnd(Segment(Def, Def.getDeadSlot(), VNI));
96
14.6M
      return VNI;
97
14.6M
    }
98
851k
99
851k
    Segment *S = segmentAt(I);
100
851k
    if (SlotIndex::isSameInstr(Def, S->start)) {
101
218k
      assert((!ForVNI || ForVNI == S->valno) && "Value number mismatch");
102
218k
      assert(S->valno->def == S->start && "Inconsistent existing value def");
103
218k
104
218k
      // It is possible to have both normal and early-clobber defs of the same
105
218k
      // register on an instruction. It doesn't make a lot of sense, but it is
106
218k
      // possible to specify in inline assembly.
107
218k
      //
108
218k
      // Just convert everything to early-clobber.
109
218k
      Def = std::min(Def, S->start);
110
218k
      if (Def != S->start)
111
45
        S->start = S->valno->def = Def;
112
218k
      return S->valno;
113
218k
    }
114
633k
    assert(SlotIndex::isEarlierInstr(Def, S->start) && "Already live at def");
115
633k
    VNInfo *VNI = ForVNI ? 
ForVNI202k
:
LR->getNextValue(Def, *VNInfoAllocator)430k
;
116
633k
    segments().insert(I, Segment(Def, Def.getDeadSlot(), VNI));
117
633k
    return VNI;
118
633k
  }
119
120
15.3M
  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
121
15.3M
    if (segments().empty())
122
0
      return nullptr;
123
15.3M
    iterator I =
124
15.3M
      impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
125
15.3M
    if (I == segments().begin())
126
1.60k
      return nullptr;
127
15.3M
    --I;
128
15.3M
    if (I->end <= StartIdx)
129
12.9M
      return nullptr;
130
2.35M
    if (I->end < Use)
131
1.24M
      extendSegmentEndTo(I, Use);
132
2.35M
    return I->valno;
133
2.35M
  }
Unexecuted instantiation: LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::extendInBlock(llvm::SlotIndex, llvm::SlotIndex)
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::extendInBlock(llvm::SlotIndex, llvm::SlotIndex)
Line
Count
Source
120
15.3M
  VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use) {
121
15.3M
    if (segments().empty())
122
0
      return nullptr;
123
15.3M
    iterator I =
124
15.3M
      impl().findInsertPos(Segment(Use.getPrevSlot(), Use, nullptr));
125
15.3M
    if (I == segments().begin())
126
1.60k
      return nullptr;
127
15.3M
    --I;
128
15.3M
    if (I->end <= StartIdx)
129
12.9M
      return nullptr;
130
2.35M
    if (I->end < Use)
131
1.24M
      extendSegmentEndTo(I, Use);
132
2.35M
    return I->valno;
133
2.35M
  }
134
135
  std::pair<VNInfo*,bool> extendInBlock(ArrayRef<SlotIndex> Undefs,
136
57.5M
      SlotIndex StartIdx, SlotIndex Use) {
137
57.5M
    if (segments().empty())
138
0
      return std::make_pair(nullptr, false);
139
57.5M
    SlotIndex BeforeUse = Use.getPrevSlot();
140
57.5M
    iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
141
57.5M
    if (I == segments().begin())
142
47.6k
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
143
57.5M
    --I;
144
57.5M
    if (I->end <= StartIdx)
145
28.5M
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
146
28.9M
    if (I->end < Use) {
147
25.6M
      if (LR->isUndefIn(Undefs, I->end, BeforeUse))
148
2
        return std::make_pair(nullptr, true);
149
25.6M
      extendSegmentEndTo(I, Use);
150
25.6M
    }
151
28.9M
    
return std::make_pair(I->valno, false)28.9M
;
152
28.9M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::extendInBlock(llvm::ArrayRef<llvm::SlotIndex>, llvm::SlotIndex, llvm::SlotIndex)
Line
Count
Source
136
6.70M
      SlotIndex StartIdx, SlotIndex Use) {
137
6.70M
    if (segments().empty())
138
0
      return std::make_pair(nullptr, false);
139
6.70M
    SlotIndex BeforeUse = Use.getPrevSlot();
140
6.70M
    iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
141
6.70M
    if (I == segments().begin())
142
0
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
143
6.70M
    --I;
144
6.70M
    if (I->end <= StartIdx)
145
949
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
146
6.70M
    if (I->end < Use) {
147
6.69M
      if (LR->isUndefIn(Undefs, I->end, BeforeUse))
148
0
        return std::make_pair(nullptr, true);
149
6.69M
      extendSegmentEndTo(I, Use);
150
6.69M
    }
151
6.70M
    return std::make_pair(I->valno, false);
152
6.70M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::extendInBlock(llvm::ArrayRef<llvm::SlotIndex>, llvm::SlotIndex, llvm::SlotIndex)
Line
Count
Source
136
50.8M
      SlotIndex StartIdx, SlotIndex Use) {
137
50.8M
    if (segments().empty())
138
0
      return std::make_pair(nullptr, false);
139
50.8M
    SlotIndex BeforeUse = Use.getPrevSlot();
140
50.8M
    iterator I = impl().findInsertPos(Segment(BeforeUse, Use, nullptr));
141
50.8M
    if (I == segments().begin())
142
47.6k
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
143
50.8M
    --I;
144
50.8M
    if (I->end <= StartIdx)
145
28.5M
      return std::make_pair(nullptr, LR->isUndefIn(Undefs, StartIdx, BeforeUse));
146
22.2M
    if (I->end < Use) {
147
18.9M
      if (LR->isUndefIn(Undefs, I->end, BeforeUse))
148
2
        return std::make_pair(nullptr, true);
149
18.9M
      extendSegmentEndTo(I, Use);
150
18.9M
    }
151
22.2M
    
return std::make_pair(I->valno, false)22.2M
;
152
22.2M
  }
153
154
  /// This method is used when we want to extend the segment specified
155
  /// by I to end at the specified endpoint. To do this, we should
156
  /// merge and eliminate all segments that this will overlap
157
  /// with. The iterator is not invalidated.
158
29.9M
  void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
159
29.9M
    assert(I != segments().end() && "Not a valid segment!");
160
29.9M
    Segment *S = segmentAt(I);
161
29.9M
    VNInfo *ValNo = I->valno;
162
29.9M
163
29.9M
    // Search for the first segment that we can't merge with.
164
29.9M
    iterator MergeTo = std::next(I);
165
29.9M
    for (; MergeTo != segments().end() && 
NewEnd >= MergeTo->end10.2M
;
++MergeTo0
)
166
29.9M
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
167
29.9M
168
29.9M
    // If NewEnd was in the middle of a segment, make sure to get its endpoint.
169
29.9M
    S->end = std::max(NewEnd, std::prev(MergeTo)->end);
170
29.9M
171
29.9M
    // If the newly formed segment now touches the segment after it and if they
172
29.9M
    // have the same value number, merge the two segments into one segment.
173
29.9M
    if (MergeTo != segments().end() && 
MergeTo->start <= I->end10.2M
&&
174
29.9M
        
MergeTo->valno == ValNo3.93M
) {
175
2.33M
      S->end = MergeTo->end;
176
2.33M
      ++MergeTo;
177
2.33M
    }
178
29.9M
179
29.9M
    // Erase any dead segments.
180
29.9M
    segments().erase(std::next(I), MergeTo);
181
29.9M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::extendSegmentEndTo(std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, llvm::SlotIndex)
Line
Count
Source
158
6.69M
  void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
159
6.69M
    assert(I != segments().end() && "Not a valid segment!");
160
6.69M
    Segment *S = segmentAt(I);
161
6.69M
    VNInfo *ValNo = I->valno;
162
6.69M
163
6.69M
    // Search for the first segment that we can't merge with.
164
6.69M
    iterator MergeTo = std::next(I);
165
6.69M
    for (; MergeTo != segments().end() && 
NewEnd >= MergeTo->end5.03M
;
++MergeTo0
)
166
6.69M
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
167
6.69M
168
6.69M
    // If NewEnd was in the middle of a segment, make sure to get its endpoint.
169
6.69M
    S->end = std::max(NewEnd, std::prev(MergeTo)->end);
170
6.69M
171
6.69M
    // If the newly formed segment now touches the segment after it and if they
172
6.69M
    // have the same value number, merge the two segments into one segment.
173
6.69M
    if (MergeTo != segments().end() && 
MergeTo->start <= I->end5.03M
&&
174
6.69M
        
MergeTo->valno == ValNo838k
) {
175
114
      S->end = MergeTo->end;
176
114
      ++MergeTo;
177
114
    }
178
6.69M
179
6.69M
    // Erase any dead segments.
180
6.69M
    segments().erase(std::next(I), MergeTo);
181
6.69M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::extendSegmentEndTo(llvm::LiveRange::Segment*, llvm::SlotIndex)
Line
Count
Source
158
23.2M
  void extendSegmentEndTo(iterator I, SlotIndex NewEnd) {
159
23.2M
    assert(I != segments().end() && "Not a valid segment!");
160
23.2M
    Segment *S = segmentAt(I);
161
23.2M
    VNInfo *ValNo = I->valno;
162
23.2M
163
23.2M
    // Search for the first segment that we can't merge with.
164
23.2M
    iterator MergeTo = std::next(I);
165
23.2M
    for (; MergeTo != segments().end() && 
NewEnd >= MergeTo->end5.24M
;
++MergeTo0
)
166
23.2M
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
167
23.2M
168
23.2M
    // If NewEnd was in the middle of a segment, make sure to get its endpoint.
169
23.2M
    S->end = std::max(NewEnd, std::prev(MergeTo)->end);
170
23.2M
171
23.2M
    // If the newly formed segment now touches the segment after it and if they
172
23.2M
    // have the same value number, merge the two segments into one segment.
173
23.2M
    if (MergeTo != segments().end() && 
MergeTo->start <= I->end5.24M
&&
174
23.2M
        
MergeTo->valno == ValNo3.09M
) {
175
2.33M
      S->end = MergeTo->end;
176
2.33M
      ++MergeTo;
177
2.33M
    }
178
23.2M
179
23.2M
    // Erase any dead segments.
180
23.2M
    segments().erase(std::next(I), MergeTo);
181
23.2M
  }
182
183
  /// This method is used when we want to extend the segment specified
184
  /// by I to start at the specified endpoint.  To do this, we should
185
  /// merge and eliminate all segments that this will overlap with.
186
6.56M
  iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
187
6.56M
    assert(I != segments().end() && "Not a valid segment!");
188
6.56M
    Segment *S = segmentAt(I);
189
6.56M
    VNInfo *ValNo = I->valno;
190
6.56M
191
6.56M
    // Search for the first segment that we can't merge with.
192
6.56M
    iterator MergeTo = I;
193
6.56M
    do {
194
6.56M
      if (MergeTo == segments().begin()) {
195
897
        S->start = NewStart;
196
897
        segments().erase(MergeTo, I);
197
897
        return I;
198
897
      }
199
6.56M
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
200
6.56M
      --MergeTo;
201
6.56M
    } while (NewStart <= MergeTo->start);
202
6.56M
203
6.56M
    // If we start in the middle of another segment, just delete a range and
204
6.56M
    // extend that segment.
205
6.56M
    
if (6.56M
MergeTo->end >= NewStart6.56M
&&
MergeTo->valno == ValNo4.45k
) {
206
0
      segmentAt(MergeTo)->end = S->end;
207
6.56M
    } else {
208
6.56M
      // Otherwise, extend the segment right after.
209
6.56M
      ++MergeTo;
210
6.56M
      Segment *MergeToSeg = segmentAt(MergeTo);
211
6.56M
      MergeToSeg->start = NewStart;
212
6.56M
      MergeToSeg->end = S->end;
213
6.56M
    }
214
6.56M
215
6.56M
    segments().erase(std::next(MergeTo), std::next(I));
216
6.56M
    return MergeTo;
217
6.56M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::extendSegmentStartTo(std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, llvm::SlotIndex)
Line
Count
Source
186
24
  iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
187
24
    assert(I != segments().end() && "Not a valid segment!");
188
24
    Segment *S = segmentAt(I);
189
24
    VNInfo *ValNo = I->valno;
190
24
191
24
    // Search for the first segment that we can't merge with.
192
24
    iterator MergeTo = I;
193
24
    do {
194
24
      if (MergeTo == segments().begin()) {
195
0
        S->start = NewStart;
196
0
        segments().erase(MergeTo, I);
197
0
        return I;
198
0
      }
199
24
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
200
24
      --MergeTo;
201
24
    } while (NewStart <= MergeTo->start);
202
24
203
24
    // If we start in the middle of another segment, just delete a range and
204
24
    // extend that segment.
205
24
    if (MergeTo->end >= NewStart && 
MergeTo->valno == ValNo0
) {
206
0
      segmentAt(MergeTo)->end = S->end;
207
24
    } else {
208
24
      // Otherwise, extend the segment right after.
209
24
      ++MergeTo;
210
24
      Segment *MergeToSeg = segmentAt(MergeTo);
211
24
      MergeToSeg->start = NewStart;
212
24
      MergeToSeg->end = S->end;
213
24
    }
214
24
215
24
    segments().erase(std::next(MergeTo), std::next(I));
216
24
    return MergeTo;
217
24
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::extendSegmentStartTo(llvm::LiveRange::Segment*, llvm::SlotIndex)
Line
Count
Source
186
6.56M
  iterator extendSegmentStartTo(iterator I, SlotIndex NewStart) {
187
6.56M
    assert(I != segments().end() && "Not a valid segment!");
188
6.56M
    Segment *S = segmentAt(I);
189
6.56M
    VNInfo *ValNo = I->valno;
190
6.56M
191
6.56M
    // Search for the first segment that we can't merge with.
192
6.56M
    iterator MergeTo = I;
193
6.56M
    do {
194
6.56M
      if (MergeTo == segments().begin()) {
195
897
        S->start = NewStart;
196
897
        segments().erase(MergeTo, I);
197
897
        return I;
198
897
      }
199
6.56M
      assert(MergeTo->valno == ValNo && "Cannot merge with differing values!");
200
6.56M
      --MergeTo;
201
6.56M
    } while (NewStart <= MergeTo->start);
202
6.56M
203
6.56M
    // If we start in the middle of another segment, just delete a range and
204
6.56M
    // extend that segment.
205
6.56M
    
if (6.56M
MergeTo->end >= NewStart6.56M
&&
MergeTo->valno == ValNo4.45k
) {
206
0
      segmentAt(MergeTo)->end = S->end;
207
6.56M
    } else {
208
6.56M
      // Otherwise, extend the segment right after.
209
6.56M
      ++MergeTo;
210
6.56M
      Segment *MergeToSeg = segmentAt(MergeTo);
211
6.56M
      MergeToSeg->start = NewStart;
212
6.56M
      MergeToSeg->end = S->end;
213
6.56M
    }
214
6.56M
215
6.56M
    segments().erase(std::next(MergeTo), std::next(I));
216
6.56M
    return MergeTo;
217
6.56M
  }
218
219
15.9M
  iterator addSegment(Segment S) {
220
15.9M
    SlotIndex Start = S.start, End = S.end;
221
15.9M
    iterator I = impl().findInsertPos(S);
222
15.9M
223
15.9M
    // If the inserted segment starts in the middle or right at the end of
224
15.9M
    // another segment, just extend that segment to contain the segment of S.
225
15.9M
    if (I != segments().begin()) {
226
14.7M
      iterator B = std::prev(I);
227
14.7M
      if (S.valno == B->valno) {
228
13.4M
        if (B->start <= Start && B->end >= Start) {
229
3.04M
          extendSegmentEndTo(B, End);
230
3.04M
          return B;
231
3.04M
        }
232
1.37M
      } else {
233
1.37M
        // Check to make sure that we are not overlapping two live segments with
234
1.37M
        // different valno's.
235
1.37M
        assert(B->end <= Start &&
236
1.37M
               "Cannot overlap two segments with differing ValID's"
237
1.37M
               " (did you def the same reg twice in a MachineInstr?)");
238
1.37M
      }
239
14.7M
    }
240
15.9M
241
15.9M
    // Otherwise, if this segment ends in the middle of, or right next
242
15.9M
    // to, another segment, merge it into that segment.
243
15.9M
    
if (12.9M
I != segments().end()12.9M
) {
244
10.2M
      if (S.valno == I->valno) {
245
9.58M
        if (I->start <= End) {
246
6.56M
          I = extendSegmentStartTo(I, Start);
247
6.56M
248
6.56M
          // If S is a complete superset of a segment, we may need to grow its
249
6.56M
          // endpoint as well.
250
6.56M
          if (End > I->end)
251
0
            extendSegmentEndTo(I, End);
252
6.56M
          return I;
253
6.56M
        }
254
696k
      } else {
255
696k
        // Check to make sure that we are not overlapping two live segments with
256
696k
        // different valno's.
257
696k
        assert(I->start >= End &&
258
696k
               "Cannot overlap two segments with differing ValID's");
259
696k
      }
260
10.2M
    }
261
12.9M
262
12.9M
    // Otherwise, this is just a new segment that doesn't interact with
263
12.9M
    // anything.
264
12.9M
    // Insert it.
265
12.9M
    
return segments().insert(I, S)6.36M
;
266
12.9M
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::addSegment(llvm::LiveRange::Segment)
Line
Count
Source
219
948
  iterator addSegment(Segment S) {
220
948
    SlotIndex Start = S.start, End = S.end;
221
948
    iterator I = impl().findInsertPos(S);
222
948
223
948
    // If the inserted segment starts in the middle or right at the end of
224
948
    // another segment, just extend that segment to contain the segment of S.
225
948
    if (I != segments().begin()) {
226
948
      iterator B = std::prev(I);
227
948
      if (S.valno == B->valno) {
228
718
        if (B->start <= Start && B->end >= Start) {
229
444
          extendSegmentEndTo(B, End);
230
444
          return B;
231
444
        }
232
230
      } else {
233
230
        // Check to make sure that we are not overlapping two live segments with
234
230
        // different valno's.
235
230
        assert(B->end <= Start &&
236
230
               "Cannot overlap two segments with differing ValID's"
237
230
               " (did you def the same reg twice in a MachineInstr?)");
238
230
      }
239
948
    }
240
948
241
948
    // Otherwise, if this segment ends in the middle of, or right next
242
948
    // to, another segment, merge it into that segment.
243
948
    
if (504
I != segments().end()504
) {
244
490
      if (S.valno == I->valno) {
245
24
        if (I->start <= End) {
246
24
          I = extendSegmentStartTo(I, Start);
247
24
248
24
          // If S is a complete superset of a segment, we may need to grow its
249
24
          // endpoint as well.
250
24
          if (End > I->end)
251
0
            extendSegmentEndTo(I, End);
252
24
          return I;
253
24
        }
254
466
      } else {
255
466
        // Check to make sure that we are not overlapping two live segments with
256
466
        // different valno's.
257
466
        assert(I->start >= End &&
258
466
               "Cannot overlap two segments with differing ValID's");
259
466
      }
260
490
    }
261
504
262
504
    // Otherwise, this is just a new segment that doesn't interact with
263
504
    // anything.
264
504
    // Insert it.
265
504
    
return segments().insert(I, S)480
;
266
504
  }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::addSegment(llvm::LiveRange::Segment)
Line
Count
Source
219
15.9M
  iterator addSegment(Segment S) {
220
15.9M
    SlotIndex Start = S.start, End = S.end;
221
15.9M
    iterator I = impl().findInsertPos(S);
222
15.9M
223
15.9M
    // If the inserted segment starts in the middle or right at the end of
224
15.9M
    // another segment, just extend that segment to contain the segment of S.
225
15.9M
    if (I != segments().begin()) {
226
14.7M
      iterator B = std::prev(I);
227
14.7M
      if (S.valno == B->valno) {
228
13.4M
        if (B->start <= Start && B->end >= Start) {
229
3.04M
          extendSegmentEndTo(B, End);
230
3.04M
          return B;
231
3.04M
        }
232
1.37M
      } else {
233
1.37M
        // Check to make sure that we are not overlapping two live segments with
234
1.37M
        // different valno's.
235
1.37M
        assert(B->end <= Start &&
236
1.37M
               "Cannot overlap two segments with differing ValID's"
237
1.37M
               " (did you def the same reg twice in a MachineInstr?)");
238
1.37M
      }
239
14.7M
    }
240
15.9M
241
15.9M
    // Otherwise, if this segment ends in the middle of, or right next
242
15.9M
    // to, another segment, merge it into that segment.
243
15.9M
    
if (12.9M
I != segments().end()12.9M
) {
244
10.2M
      if (S.valno == I->valno) {
245
9.58M
        if (I->start <= End) {
246
6.56M
          I = extendSegmentStartTo(I, Start);
247
6.56M
248
6.56M
          // If S is a complete superset of a segment, we may need to grow its
249
6.56M
          // endpoint as well.
250
6.56M
          if (End > I->end)
251
0
            extendSegmentEndTo(I, End);
252
6.56M
          return I;
253
6.56M
        }
254
696k
      } else {
255
696k
        // Check to make sure that we are not overlapping two live segments with
256
696k
        // different valno's.
257
696k
        assert(I->start >= End &&
258
696k
               "Cannot overlap two segments with differing ValID's");
259
696k
      }
260
10.2M
    }
261
12.9M
262
12.9M
    // Otherwise, this is just a new segment that doesn't interact with
263
12.9M
    // anything.
264
12.9M
    // Insert it.
265
12.9M
    
return segments().insert(I, S)6.36M
;
266
12.9M
  }
267
268
private:
269
444M
  ImplT &impl() { return *static_cast<ImplT *>(this); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::impl()
Line
Count
Source
269
65.5M
  ImplT &impl() { return *static_cast<ImplT *>(this); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::impl()
Line
Count
Source
269
378M
  ImplT &impl() { return *static_cast<ImplT *>(this); }
270
271
313M
  CollectionT &segments() { return impl().segmentsColl(); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::segments()
Line
Count
Source
271
47.2M
  CollectionT &segments() { return impl().segmentsColl(); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::segments()
Line
Count
Source
271
266M
  CollectionT &segments() { return impl().segmentsColl(); }
272
273
49.2M
  Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilSet, std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>, std::__1::set<llvm::LiveRange::Segment, std::__1::less<llvm::LiveRange::Segment>, std::__1::allocator<llvm::LiveRange::Segment> > >::segmentAt(std::__1::__tree_const_iterator<llvm::LiveRange::Segment, std::__1::__tree_node<llvm::LiveRange::Segment, void*>*, long>)
Line
Count
Source
273
12.0M
  Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
LiveInterval.cpp:(anonymous namespace)::CalcLiveRangeUtilBase<(anonymous namespace)::CalcLiveRangeUtilVector, llvm::LiveRange::Segment*, llvm::SmallVector<llvm::LiveRange::Segment, 2u> >::segmentAt(llvm::LiveRange::Segment*)
Line
Count
Source
273
37.1M
  Segment *segmentAt(iterator I) { return const_cast<Segment *>(&(*I)); }
274
};
275
276
//===----------------------------------------------------------------------===//
277
//   Instantiation of the methods for calculation of live ranges
278
//   based on a segment vector.
279
//===----------------------------------------------------------------------===//
280
281
class CalcLiveRangeUtilVector;
282
using CalcLiveRangeUtilVectorBase =
283
    CalcLiveRangeUtilBase<CalcLiveRangeUtilVector, LiveRange::iterator,
284
                          LiveRange::Segments>;
285
286
class CalcLiveRangeUtilVector : public CalcLiveRangeUtilVectorBase {
287
public:
288
97.6M
  CalcLiveRangeUtilVector(LiveRange *LR) : CalcLiveRangeUtilVectorBase(LR) {}
289
290
private:
291
  friend CalcLiveRangeUtilVectorBase;
292
293
266M
  LiveRange::Segments &segmentsColl() { return LR->segments; }
294
295
14.6M
  void insertAtEnd(const Segment &S) { LR->segments.push_back(S); }
296
297
15.4M
  iterator find(SlotIndex Pos) { return LR->find(Pos); }
298
299
82.2M
  iterator findInsertPos(Segment S) { return llvm::upper_bound(*LR, S.start); }
300
};
301
302
//===----------------------------------------------------------------------===//
303
//   Instantiation of the methods for calculation of live ranges
304
//   based on a segment set.
305
//===----------------------------------------------------------------------===//
306
307
class CalcLiveRangeUtilSet;
308
using CalcLiveRangeUtilSetBase =
309
    CalcLiveRangeUtilBase<CalcLiveRangeUtilSet, LiveRange::SegmentSet::iterator,
310
                          LiveRange::SegmentSet>;
311
312
class CalcLiveRangeUtilSet : public CalcLiveRangeUtilSetBase {
313
public:
314
15.1M
  CalcLiveRangeUtilSet(LiveRange *LR) : CalcLiveRangeUtilSetBase(LR) {}
315
316
private:
317
  friend CalcLiveRangeUtilSetBase;
318
319
47.2M
  LiveRange::SegmentSet &segmentsColl() { return *LR->segmentSet; }
320
321
3.12M
  void insertAtEnd(const Segment &S) {
322
3.12M
    LR->segmentSet->insert(LR->segmentSet->end(), S);
323
3.12M
  }
324
325
8.45M
  iterator find(SlotIndex Pos) {
326
8.45M
    iterator I =
327
8.45M
        LR->segmentSet->upper_bound(Segment(Pos, Pos.getNextSlot(), nullptr));
328
8.45M
    if (I == LR->segmentSet->begin())
329
2.92M
      return I;
330
5.53M
    iterator PrevI = std::prev(I);
331
5.53M
    if (Pos < (*PrevI).end)
332
41.9k
      return PrevI;
333
5.48M
    return I;
334
5.48M
  }
335
336
6.70M
  iterator findInsertPos(Segment S) {
337
6.70M
    iterator I = LR->segmentSet->upper_bound(S);
338
6.70M
    if (I != LR->segmentSet->end() && 
!(S.start < *I)5.04M
)
339
0
      ++I;
340
6.70M
    return I;
341
6.70M
  }
342
};
343
344
} // end anonymous namespace
345
346
//===----------------------------------------------------------------------===//
347
//   LiveRange methods
348
//===----------------------------------------------------------------------===//
349
350
225M
LiveRange::iterator LiveRange::find(SlotIndex Pos) {
351
225M
  // This algorithm is basically std::upper_bound.
352
225M
  // Unfortunately, std::upper_bound cannot be used with mixed types until we
353
225M
  // adopt C++0x. Many libraries can do it, but not all.
354
225M
  if (empty() || 
Pos >= endIndex()202M
)
355
46.7M
    return end();
356
178M
  iterator I = begin();
357
178M
  size_t Len = size();
358
327M
  do {
359
327M
    size_t Mid = Len >> 1;
360
327M
    if (Pos < I[Mid].end) {
361
247M
      Len = Mid;
362
247M
    } else {
363
79.4M
      I += Mid + 1;
364
79.4M
      Len -= Mid + 1;
365
79.4M
    }
366
327M
  } while (Len);
367
178M
  return I;
368
178M
}
369
370
23.4M
VNInfo *LiveRange::createDeadDef(SlotIndex Def, VNInfo::Allocator &VNIAlloc) {
371
23.4M
  // Use the segment set, if it is available.
372
23.4M
  if (segmentSet != nullptr)
373
8.45M
    return CalcLiveRangeUtilSet(this).createDeadDef(Def, &VNIAlloc, nullptr);
374
14.9M
  // Otherwise use the segment vector.
375
14.9M
  return CalcLiveRangeUtilVector(this).createDeadDef(Def, &VNIAlloc, nullptr);
376
14.9M
}
377
378
495k
VNInfo *LiveRange::createDeadDef(VNInfo *VNI) {
379
495k
  // Use the segment set, if it is available.
380
495k
  if (segmentSet != nullptr)
381
0
    return CalcLiveRangeUtilSet(this).createDeadDef(VNI->def, nullptr, VNI);
382
495k
  // Otherwise use the segment vector.
383
495k
  return CalcLiveRangeUtilVector(this).createDeadDef(VNI->def, nullptr, VNI);
384
495k
}
385
386
// overlaps - Return true if the intersection of the two live ranges is
387
// not empty.
388
//
389
// An example for overlaps():
390
//
391
// 0: A = ...
392
// 4: B = ...
393
// 8: C = A + B ;; last use of A
394
//
395
// The live ranges should look like:
396
//
397
// A = [3, 11)
398
// B = [7, x)
399
// C = [11, y)
400
//
401
// A->overlaps(C) should return false since we want to be able to join
402
// A and C.
403
//
404
bool LiveRange::overlapsFrom(const LiveRange& other,
405
7.42M
                             const_iterator StartPos) const {
406
7.42M
  assert(!empty() && "empty range");
407
7.42M
  const_iterator i = begin();
408
7.42M
  const_iterator ie = end();
409
7.42M
  const_iterator j = StartPos;
410
7.42M
  const_iterator je = other.end();
411
7.42M
412
7.42M
  assert((StartPos->start <= i->start || StartPos == other.begin()) &&
413
7.42M
         StartPos != other.end() && "Bogus start position hint!");
414
7.42M
415
7.42M
  if (i->start < j->start) {
416
5.00M
    i = std::upper_bound(i, ie, j->start);
417
5.00M
    if (i != begin()) --i;
418
5.00M
  } else 
if (2.41M
j->start < i->start2.41M
) {
419
2.41M
    ++StartPos;
420
2.41M
    if (StartPos != other.end() && 
StartPos->start <= i->start237k
) {
421
123k
      assert(StartPos < other.end() && i < end());
422
123k
      j = std::upper_bound(j, je, i->start);
423
123k
      if (j != other.begin()) --j;
424
123k
    }
425
2.41M
  } else {
426
1.74k
    return true;
427
1.74k
  }
428
7.42M
429
7.42M
  if (j == je) 
return false0
;
430
7.42M
431
8.98M
  
while (7.42M
i != ie) {
432
7.58M
    if (i->start > j->start) {
433
2.50M
      std::swap(i, j);
434
2.50M
      std::swap(ie, je);
435
2.50M
    }
436
7.58M
437
7.58M
    if (i->end > j->start)
438
6.03M
      return true;
439
1.55M
    ++i;
440
1.55M
  }
441
7.42M
442
7.42M
  
return false1.39M
;
443
7.42M
}
444
445
bool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP,
446
65.6M
                         const SlotIndexes &Indexes) const {
447
65.6M
  assert(!empty() && "empty range");
448
65.6M
  if (Other.empty())
449
55.1M
    return false;
450
10.4M
451
10.4M
  // Use binary searches to find initial positions.
452
10.4M
  const_iterator I = find(Other.beginIndex());
453
10.4M
  const_iterator IE = end();
454
10.4M
  if (I == IE)
455
811k
    return false;
456
9.67M
  const_iterator J = Other.find(I->start);
457
9.67M
  const_iterator JE = Other.end();
458
9.67M
  if (J == JE)
459
3.77M
    return false;
460
5.89M
461
8.56M
  
while (5.89M
true8.56M
) {
462
8.56M
    // J has just been advanced to satisfy:
463
8.56M
    assert(J->end >= I->start);
464
8.56M
    // Check for an overlap.
465
8.56M
    if (J->start < I->end) {
466
2.36M
      // I and J are overlapping. Find the later start.
467
2.36M
      SlotIndex Def = std::max(I->start, J->start);
468
2.36M
      // Allow the overlap if Def is a coalescable copy.
469
2.36M
      if (Def.isBlock() ||
470
2.36M
          
!CP.isCoalescable(Indexes.getInstructionFromIndex(Def))2.36M
)
471
2.13M
        return true;
472
6.42M
    }
473
6.42M
    // Advance the iterator that ends first to check for more overlaps.
474
6.42M
    if (J->end > I->end) {
475
6.20M
      std::swap(I, J);
476
6.20M
      std::swap(IE, JE);
477
6.20M
    }
478
6.42M
    // Advance J until J->end >= I->start.
479
6.42M
    do
480
10.3M
      if (++J == JE)
481
3.75M
        return false;
482
6.58M
    while (J->end < I->start);
483
6.42M
  }
484
5.89M
}
485
486
/// overlaps - Return true if the live range overlaps an interval specified
487
/// by [Start, End).
488
319k
bool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const {
489
319k
  assert(Start < End && "Invalid range");
490
319k
  const_iterator I = std::lower_bound(begin(), end(), End);
491
319k
  return I != begin() && 
(--I)->end > Start268k
;
492
319k
}
493
494
1.31M
bool LiveRange::covers(const LiveRange &Other) const {
495
1.31M
  if (empty())
496
0
    return Other.empty();
497
1.31M
498
1.31M
  const_iterator I = begin();
499
1.36M
  for (const Segment &O : Other.segments) {
500
1.36M
    I = advanceTo(I, O.start);
501
1.36M
    if (I == end() || I->start > O.start)
502
0
      return false;
503
1.36M
504
1.36M
    // Check adjacent live segments and see if we can get behind O.end.
505
2.54M
    
while (1.36M
I->end < O.end) {
506
1.17M
      const_iterator Last = I;
507
1.17M
      // Get next segment and abort if it was not adjacent.
508
1.17M
      ++I;
509
1.17M
      if (I == end() || Last->end != I->start)
510
0
        return false;
511
1.17M
    }
512
1.36M
  }
513
1.31M
  return true;
514
1.31M
}
515
516
/// ValNo is dead, remove it.  If it is the largest value number, just nuke it
517
/// (and any other deleted values neighboring it), otherwise mark it as ~1U so
518
/// it can be nuked later.
519
691k
void LiveRange::markValNoForDeletion(VNInfo *ValNo) {
520
691k
  if (ValNo->id == getNumValNums()-1) {
521
631k
    do {
522
631k
      valnos.pop_back();
523
631k
    } while (!valnos.empty() && 
valnos.back()->isUnused()47.1k
);
524
603k
  } else {
525
87.5k
    ValNo->markUnused();
526
87.5k
  }
527
691k
}
528
529
/// RenumberValues - Renumber all values in order of appearance and delete the
530
/// remaining unused values.
531
410k
void LiveRange::RenumberValues() {
532
410k
  SmallPtrSet<VNInfo*, 8> Seen;
533
410k
  valnos.clear();
534
1.30M
  for (const Segment &S : segments) {
535
1.30M
    VNInfo *VNI = S.valno;
536
1.30M
    if (!Seen.insert(VNI).second)
537
386k
      continue;
538
914k
    assert(!VNI->isUnused() && "Unused valno used by live segment");
539
914k
    VNI->id = (unsigned)valnos.size();
540
914k
    valnos.push_back(VNI);
541
914k
  }
542
410k
}
543
544
948
void LiveRange::addSegmentToSet(Segment S) {
545
948
  CalcLiveRangeUtilSet(this).addSegment(S);
546
948
}
547
548
15.9M
LiveRange::iterator LiveRange::addSegment(Segment S) {
549
15.9M
  // Use the segment set, if it is available.
550
15.9M
  if (segmentSet != nullptr) {
551
12
    addSegmentToSet(S);
552
12
    return end();
553
12
  }
554
15.9M
  // Otherwise use the segment vector.
555
15.9M
  return CalcLiveRangeUtilVector(this).addSegment(S);
556
15.9M
}
557
558
0
void LiveRange::append(const Segment S) {
559
0
  // Check that the segment belongs to the back of the list.
560
0
  assert(segments.empty() || segments.back().end <= S.start);
561
0
  segments.push_back(S);
562
0
}
563
564
std::pair<VNInfo*,bool> LiveRange::extendInBlock(ArrayRef<SlotIndex> Undefs,
565
57.5M
    SlotIndex StartIdx, SlotIndex Kill) {
566
57.5M
  // Use the segment set, if it is available.
567
57.5M
  if (segmentSet != nullptr)
568
6.70M
    return CalcLiveRangeUtilSet(this).extendInBlock(Undefs, StartIdx, Kill);
569
50.8M
  // Otherwise use the segment vector.
570
50.8M
  return CalcLiveRangeUtilVector(this).extendInBlock(Undefs, StartIdx, Kill);
571
50.8M
}
572
573
15.3M
VNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) {
574
15.3M
  // Use the segment set, if it is available.
575
15.3M
  if (segmentSet != nullptr)
576
0
    return CalcLiveRangeUtilSet(this).extendInBlock(StartIdx, Kill);
577
15.3M
  // Otherwise use the segment vector.
578
15.3M
  return CalcLiveRangeUtilVector(this).extendInBlock(StartIdx, Kill);
579
15.3M
}
580
581
/// Remove the specified segment from this range.  Note that the segment must
582
/// be in a single Segment in its entirety.
583
void LiveRange::removeSegment(SlotIndex Start, SlotIndex End,
584
149k
                              bool RemoveDeadValNo) {
585
149k
  // Find the Segment containing this span.
586
149k
  iterator I = find(Start);
587
149k
  assert(I != end() && "Segment is not in range!");
588
149k
  assert(I->containsInterval(Start, End)
589
149k
         && "Segment is not entirely in range!");
590
149k
591
149k
  // If the span we are removing is at the start of the Segment, adjust it.
592
149k
  VNInfo *ValNo = I->valno;
593
149k
  if (I->start == Start) {
594
56.4k
    if (I->end == End) {
595
55.1k
      if (RemoveDeadValNo) {
596
957
        // Check if val# is dead.
597
957
        bool isDead = true;
598
64.8k
        for (const_iterator II = begin(), EE = end(); II != EE; 
++II63.8k
)
599
63.8k
          if (II != I && 
II->valno == ValNo62.9k
) {
600
0
            isDead = false;
601
0
            break;
602
0
          }
603
957
        if (isDead) {
604
957
          // Now that ValNo is dead, remove it.
605
957
          markValNoForDeletion(ValNo);
606
957
        }
607
957
      }
608
55.1k
609
55.1k
      segments.erase(I);  // Removed the whole Segment.
610
55.1k
    } else
611
1.31k
      I->start = End;
612
56.4k
    return;
613
56.4k
  }
614
92.6k
615
92.6k
  // Otherwise if the span we are removing is at the end of the Segment,
616
92.6k
  // adjust the other way.
617
92.6k
  if (I->end == End) {
618
91.8k
    I->end = Start;
619
91.8k
    return;
620
91.8k
  }
621
851
622
851
  // Otherwise, we are splitting the Segment into two pieces.
623
851
  SlotIndex OldEnd = I->end;
624
851
  I->end = Start;   // Trim the old segment.
625
851
626
851
  // Insert the new one.
627
851
  segments.insert(std::next(I), Segment(End, OldEnd, ValNo));
628
851
}
629
630
/// removeValNo - Remove all the segments defined by the specified value#.
631
/// Also remove the value# from value# list.
632
689k
void LiveRange::removeValNo(VNInfo *ValNo) {
633
689k
  if (empty()) 
return0
;
634
2.20M
  
segments.erase(remove_if(*this, [ValNo](const Segment &S) 689k
{
635
2.20M
    return S.valno == ValNo;
636
2.20M
  }), end());
637
689k
  // Now that ValNo is dead, remove it.
638
689k
  markValNoForDeletion(ValNo);
639
689k
}
640
641
void LiveRange::join(LiveRange &Other,
642
                     const int *LHSValNoAssignments,
643
                     const int *RHSValNoAssignments,
644
3.64M
                     SmallVectorImpl<VNInfo *> &NewVNInfo) {
645
3.64M
  verify();
646
3.64M
647
3.64M
  // Determine if any of our values are mapped.  This is uncommon, so we want
648
3.64M
  // to avoid the range scan if not.
649
3.64M
  bool MustMapCurValNos = false;
650
3.64M
  unsigned NumVals = getNumValNums();
651
3.64M
  unsigned NumNewVals = NewVNInfo.size();
652
10.4M
  for (unsigned i = 0; i != NumVals; 
++i6.79M
) {
653
9.19M
    unsigned LHSValID = LHSValNoAssignments[i];
654
9.19M
    if (i != LHSValID ||
655
9.19M
        
(8.90M
NewVNInfo[LHSValID]8.90M
&&
NewVNInfo[LHSValID] != getValNumInfo(i)8.90M
)) {
656
2.40M
      MustMapCurValNos = true;
657
2.40M
      break;
658
2.40M
    }
659
9.19M
  }
660
3.64M
661
3.64M
  // If we have to apply a mapping to our base range assignment, rewrite it now.
662
3.64M
  if (MustMapCurValNos && 
!empty()2.40M
) {
663
2.40M
    // Map the first live range.
664
2.40M
665
2.40M
    iterator OutIt = begin();
666
2.40M
    OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]];
667
10.3M
    for (iterator I = std::next(OutIt), E = end(); I != E; 
++I7.94M
) {
668
7.94M
      VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]];
669
7.94M
      assert(nextValNo && "Huh?");
670
7.94M
671
7.94M
      // If this live range has the same value # as its immediate predecessor,
672
7.94M
      // and if they are neighbors, remove one Segment.  This happens when we
673
7.94M
      // have [0,4:0)[4,7:1) and map 0/1 onto the same value #.
674
7.94M
      if (OutIt->valno == nextValNo && 
OutIt->end == I->start773k
) {
675
9.59k
        OutIt->end = I->end;
676
7.94M
      } else {
677
7.94M
        // Didn't merge. Move OutIt to the next segment,
678
7.94M
        ++OutIt;
679
7.94M
        OutIt->valno = nextValNo;
680
7.94M
        if (OutIt != I) {
681
22.1k
          OutIt->start = I->start;
682
22.1k
          OutIt->end = I->end;
683
22.1k
        }
684
7.94M
      }
685
7.94M
    }
686
2.40M
    // If we merge some segments, chop off the end.
687
2.40M
    ++OutIt;
688
2.40M
    segments.erase(OutIt, end());
689
2.40M
  }
690
3.64M
691
3.64M
  // Rewrite Other values before changing the VNInfo ids.
692
3.64M
  // This can leave Other in an invalid state because we're not coalescing
693
3.64M
  // touching segments that now have identical values. That's OK since Other is
694
3.64M
  // not supposed to be valid after calling join();
695
3.64M
  for (Segment &S : Other.segments)
696
5.12M
    S.valno = NewVNInfo[RHSValNoAssignments[S.valno->id]];
697
3.64M
698
3.64M
  // Update val# info. Renumber them and make sure they all belong to this
699
3.64M
  // LiveRange now. Also remove dead val#'s.
700
3.64M
  unsigned NumValNos = 0;
701
17.5M
  for (unsigned i = 0; i < NumNewVals; 
++i13.8M
) {
702
13.8M
    VNInfo *VNI = NewVNInfo[i];
703
13.8M
    if (VNI) {
704
13.8M
      if (NumValNos >= NumVals)
705
765k
        valnos.push_back(VNI);
706
13.0M
      else
707
13.0M
        valnos[NumValNos] = VNI;
708
13.8M
      VNI->id = NumValNos++;  // Renumber val#.
709
13.8M
    }
710
13.8M
  }
711
3.64M
  if (NumNewVals < NumVals)
712
85.5k
    valnos.resize(NumNewVals);  // shrinkify
713
3.64M
714
3.64M
  // Okay, now insert the RHS live segments into the LHS.
715
3.64M
  LiveRangeUpdater Updater(this);
716
3.64M
  for (Segment &S : Other.segments)
717
5.12M
    Updater.add(S);
718
3.64M
}
719
720
/// Merge all of the segments in RHS into this live range as the specified
721
/// value number.  The segments in RHS are allowed to overlap with segments in
722
/// the current range, but only if the overlapping segments have the
723
/// specified value number.
724
void LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS,
725
146k
                                       VNInfo *LHSValNo) {
726
146k
  LiveRangeUpdater Updater(this);
727
146k
  for (const Segment &S : RHS.segments)
728
350k
    Updater.add(S.start, S.end, LHSValNo);
729
146k
}
730
731
/// MergeValueInAsValue - Merge all of the live segments of a specific val#
732
/// in RHS into this live range as the specified value number.
733
/// The segments in RHS are allowed to overlap with segments in the
734
/// current range, it will replace the value numbers of the overlaped
735
/// segments with the specified value number.
736
void LiveRange::MergeValueInAsValue(const LiveRange &RHS,
737
                                    const VNInfo *RHSValNo,
738
136k
                                    VNInfo *LHSValNo) {
739
136k
  LiveRangeUpdater Updater(this);
740
136k
  for (const Segment &S : RHS.segments)
741
1.33M
    if (S.valno == RHSValNo)
742
199k
      Updater.add(S.start, S.end, LHSValNo);
743
136k
}
744
745
/// MergeValueNumberInto - This method is called when two value nubmers
746
/// are found to be equivalent.  This eliminates V1, replacing all
747
/// segments with the V1 value number with the V2 value number.  This can
748
/// cause merging of V1/V2 values numbers and compaction of the value space.
749
102
VNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) {
750
102
  assert(V1 != V2 && "Identical value#'s are always equivalent!");
751
102
752
102
  // This code actually merges the (numerically) larger value number into the
753
102
  // smaller value number, which is likely to allow us to compactify the value
754
102
  // space.  The only thing we have to be careful of is to preserve the
755
102
  // instruction that defines the result value.
756
102
757
102
  // Make sure V2 is smaller than V1.
758
102
  if (V1->id < V2->id) {
759
12
    V1->copyFrom(*V2);
760
12
    std::swap(V1, V2);
761
12
  }
762
102
763
102
  // Merge V1 segments into V2.
764
936
  for (iterator I = begin(); I != end(); ) {
765
834
    iterator S = I++;
766
834
    if (S->valno != V1) 
continue730
; // Not a V1 Segment.
767
104
768
104
    // Okay, we found a V1 live range.  If it had a previous, touching, V2 live
769
104
    // range, extend it.
770
104
    if (S != begin()) {
771
103
      iterator Prev = S-1;
772
103
      if (Prev->valno == V2 && 
Prev->end == S->start92
) {
773
90
        Prev->end = S->end;
774
90
775
90
        // Erase this live-range.
776
90
        segments.erase(S);
777
90
        I = Prev+1;
778
90
        S = Prev;
779
90
      }
780
103
    }
781
104
782
104
    // Okay, now we have a V1 or V2 live range that is maximally merged forward.
783
104
    // Ensure that it is a V2 live-range.
784
104
    S->valno = V2;
785
104
786
104
    // If we can merge it into later V2 segments, do so now.  We ignore any
787
104
    // following V1 segments, as they will be merged in subsequent iterations
788
104
    // of the loop.
789
104
    if (I != end()) {
790
103
      if (I->start == S->end && 
I->valno == V294
) {
791
12
        S->end = I->end;
792
12
        segments.erase(I);
793
12
        I = S+1;
794
12
      }
795
103
    }
796
104
  }
797
102
798
102
  // Now that V1 is dead, remove it.
799
102
  markValNoForDeletion(V1);
800
102
801
102
  return V2;
802
102
}
803
804
4.28M
void LiveRange::flushSegmentSet() {
805
4.28M
  assert(segmentSet != nullptr && "segment set must have been created");
806
4.28M
  assert(
807
4.28M
      segments.empty() &&
808
4.28M
      "segment set can be used only initially before switching to the array");
809
4.28M
  segments.append(segmentSet->begin(), segmentSet->end());
810
4.28M
  segmentSet = nullptr;
811
4.28M
  verify();
812
4.28M
}
813
814
2.82M
bool LiveRange::isLiveAtIndexes(ArrayRef<SlotIndex> Slots) const {
815
2.82M
  ArrayRef<SlotIndex>::iterator SlotI = Slots.begin();
816
2.82M
  ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
817
2.82M
818
2.82M
  // If there are no regmask slots, we have nothing to search.
819
2.82M
  if (SlotI == SlotE)
820
745k
    return false;
821
2.07M
822
2.07M
  // Start our search at the first segment that ends after the first slot.
823
2.07M
  const_iterator SegmentI = find(*SlotI);
824
2.07M
  const_iterator SegmentE = end();
825
2.07M
826
2.07M
  // If there are no segments that end after the first slot, we're done.
827
2.07M
  if (SegmentI == SegmentE)
828
305k
    return false;
829
1.77M
830
1.77M
  // Look for each slot in the live range.
831
167M
  
for ( ; 1.77M
SlotI != SlotE;
++SlotI165M
) {
832
167M
    // Go to the next segment that ends after the current slot.
833
167M
    // The slot may be within a hole in the range.
834
167M
    SegmentI = advanceTo(SegmentI, *SlotI);
835
167M
    if (SegmentI == SegmentE)
836
1.46M
      return false;
837
165M
838
165M
    // If this segment contains the slot, we're done.
839
165M
    if (SegmentI->contains(*SlotI))
840
24.4k
      return true;
841
165M
    // Otherwise, look for the next slot.
842
165M
  }
843
1.77M
844
1.77M
  // We didn't find a segment containing any of the slots.
845
1.77M
  
return false283k
;
846
1.77M
}
847
848
597k
void LiveInterval::freeSubRange(SubRange *S) {
849
597k
  S->~SubRange();
850
597k
  // Memory was allocated with BumpPtr allocator and is not freed here.
851
597k
}
852
853
13.9M
void LiveInterval::removeEmptySubRanges() {
854
13.9M
  SubRange **NextPtr = &SubRanges;
855
13.9M
  SubRange *I = *NextPtr;
856
14.5M
  while (I != nullptr) {
857
595k
    if (!I->empty()) {
858
590k
      NextPtr = &I->Next;
859
590k
      I = *NextPtr;
860
590k
      continue;
861
590k
    }
862
4.30k
    // Skip empty subranges until we find the first nonempty one.
863
4.86k
    
do 4.30k
{
864
4.86k
      SubRange *Next = I->Next;
865
4.86k
      freeSubRange(I);
866
4.86k
      I = Next;
867
4.86k
    } while (I != nullptr && 
I->empty()4.57k
);
868
4.30k
    *NextPtr = I;
869
4.30k
  }
870
13.9M
}
871
872
13.7M
void LiveInterval::clearSubRanges() {
873
14.3M
  for (SubRange *I = SubRanges, *Next; I != nullptr; 
I = Next592k
) {
874
592k
    Next = I->Next;
875
592k
    freeSubRange(I);
876
592k
  }
877
13.7M
  SubRanges = nullptr;
878
13.7M
}
879
880
/// For each VNI in \p SR, check whether or not that value defines part
881
/// of the mask describe by \p LaneMask and if not, remove that value
882
/// from \p SR.
883
static void stripValuesNotDefiningMask(unsigned Reg, LiveInterval::SubRange &SR,
884
                                       LaneBitmask LaneMask,
885
                                       const SlotIndexes &Indexes,
886
386k
                                       const TargetRegisterInfo &TRI) {
887
386k
  // Phys reg should not be tracked at subreg level.
888
386k
  // Same for noreg (Reg == 0).
889
386k
  if (!TargetRegisterInfo::isVirtualRegister(Reg) || !Reg)
890
0
    return;
891
386k
  // Remove the values that don't define those lanes.
892
386k
  SmallVector<VNInfo *, 8> ToBeRemoved;
893
391k
  for (VNInfo *VNI : SR.valnos) {
894
391k
    if (VNI->isUnused())
895
24
      continue;
896
391k
    // PHI definitions don't have MI attached, so there is nothing
897
391k
    // we can use to strip the VNI.
898
391k
    if (VNI->isPHIDef())
899
990
      continue;
900
390k
    const MachineInstr *MI = Indexes.getInstructionFromIndex(VNI->def);
901
390k
    assert(MI && "Cannot find the definition of a value");
902
390k
    bool hasDef = false;
903
403k
    for (ConstMIBundleOperands MOI(*MI); MOI.isValid(); 
++MOI12.7k
) {
904
403k
      if (!MOI->isReg() || 
!MOI->isDef()401k
)
905
5.38k
        continue;
906
398k
      if (MOI->getReg() != Reg)
907
7.41k
        continue;
908
390k
      if ((TRI.getSubRegIndexLaneMask(MOI->getSubReg()) & LaneMask).none())
909
1
        continue;
910
390k
      hasDef = true;
911
390k
      break;
912
390k
    }
913
390k
914
390k
    if (!hasDef)
915
1
      ToBeRemoved.push_back(VNI);
916
390k
  }
917
386k
  for (VNInfo *VNI : ToBeRemoved)
918
1
    SR.removeValNo(VNI);
919
386k
920
386k
  assert(!SR.empty() && "At least one value should be defined by this mask");
921
386k
}
922
923
void LiveInterval::refineSubRanges(
924
    BumpPtrAllocator &Allocator, LaneBitmask LaneMask,
925
    std::function<void(LiveInterval::SubRange &)> Apply,
926
1.01M
    const SlotIndexes &Indexes, const TargetRegisterInfo &TRI) {
927
1.01M
  LaneBitmask ToApply = LaneMask;
928
2.72M
  for (SubRange &SR : subranges()) {
929
2.72M
    LaneBitmask SRMask = SR.LaneMask;
930
2.72M
    LaneBitmask Matching = SRMask & LaneMask;
931
2.72M
    if (Matching.none())
932
1.75M
      continue;
933
971k
934
971k
    SubRange *MatchingRange;
935
971k
    if (SRMask == Matching) {
936
778k
      // The subrange fits (it does not cover bits outside \p LaneMask).
937
778k
      MatchingRange = &SR;
938
778k
    } else {
939
193k
      // We have to split the subrange into a matching and non-matching part.
940
193k
      // Reduce lanemask of existing lane to non-matching part.
941
193k
      SR.LaneMask = SRMask & ~Matching;
942
193k
      // Create a new subrange for the matching part
943
193k
      MatchingRange = createSubRangeFrom(Allocator, Matching, SR);
944
193k
      // Now that the subrange is split in half, make sure we
945
193k
      // only keep in the subranges the VNIs that touch the related half.
946
193k
      stripValuesNotDefiningMask(reg, *MatchingRange, Matching, Indexes, TRI);
947
193k
      stripValuesNotDefiningMask(reg, SR, SR.LaneMask, Indexes, TRI);
948
193k
    }
949
971k
    Apply(*MatchingRange);
950
971k
    ToApply &= ~Matching;
951
971k
  }
952
1.01M
  // Create a new subrange if there are uncovered bits left.
953
1.01M
  if (ToApply.any()) {
954
308k
    SubRange *NewRange = createSubRange(Allocator, ToApply);
955
308k
    Apply(*NewRange);
956
308k
  }
957
1.01M
}
958
959
14.7M
unsigned LiveInterval::getSize() const {
960
14.7M
  unsigned Sum = 0;
961
14.7M
  for (const Segment &S : segments)
962
26.3M
    Sum += S.start.distance(S.end);
963
14.7M
  return Sum;
964
14.7M
}
965
966
void LiveInterval::computeSubRangeUndefs(SmallVectorImpl<SlotIndex> &Undefs,
967
                                         LaneBitmask LaneMask,
968
                                         const MachineRegisterInfo &MRI,
969
809k
                                         const SlotIndexes &Indexes) const {
970
809k
  assert(TargetRegisterInfo::isVirtualRegister(reg));
971
809k
  LaneBitmask VRegMask = MRI.getMaxLaneMaskForVReg(reg);
972
809k
  assert((VRegMask & LaneMask).any());
973
809k
  const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();
974
1.90M
  for (const MachineOperand &MO : MRI.def_operands(reg)) {
975
1.90M
    if (!MO.isUndef())
976
1.47M
      continue;
977
430k
    unsigned SubReg = MO.getSubReg();
978
430k
    assert(SubReg != 0 && "Undef should only be set on subreg defs");
979
430k
    LaneBitmask DefMask = TRI.getSubRegIndexLaneMask(SubReg);
980
430k
    LaneBitmask UndefMask = VRegMask & ~DefMask;
981
430k
    if ((UndefMask & LaneMask).any()) {
982
315k
      const MachineInstr &MI = *MO.getParent();
983
315k
      bool EarlyClobber = MO.isEarlyClobber();
984
315k
      SlotIndex Pos = Indexes.getInstructionIndex(MI).getRegSlot(EarlyClobber);
985
315k
      Undefs.push_back(Pos);
986
315k
    }
987
430k
  }
988
809k
}
989
990
26
raw_ostream& llvm::operator<<(raw_ostream& OS, const LiveRange::Segment &S) {
991
26
  return OS << '[' << S.start << ',' << S.end << ':' << S.valno->id << ')';
992
26
}
993
994
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
995
LLVM_DUMP_METHOD void LiveRange::Segment::dump() const {
996
  dbgs() << *this << '\n';
997
}
998
#endif
999
1000
15
void LiveRange::print(raw_ostream &OS) const {
1001
15
  if (empty())
1002
0
    OS << "EMPTY";
1003
15
  else {
1004
26
    for (const Segment &S : segments) {
1005
26
      OS << S;
1006
26
      assert(S.valno == getValNumInfo(S.valno->id) && "Bad VNInfo");
1007
26
    }
1008
15
  }
1009
15
1010
15
  // Print value number info.
1011
15
  if (getNumValNums()) {
1012
15
    OS << "  ";
1013
15
    unsigned vnum = 0;
1014
41
    for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e;
1015
26
         ++i, ++vnum) {
1016
26
      const VNInfo *vni = *i;
1017
26
      if (vnum) 
OS << ' '11
;
1018
26
      OS << vnum << '@';
1019
26
      if (vni->isUnused()) {
1020
0
        OS << 'x';
1021
26
      } else {
1022
26
        OS << vni->def;
1023
26
        if (vni->isPHIDef())
1024
0
          OS << "-phi";
1025
26
      }
1026
26
    }
1027
15
  }
1028
15
}
1029
1030
4
void LiveInterval::SubRange::print(raw_ostream &OS) const {
1031
4
  OS << " L" << PrintLaneMask(LaneMask) << ' '
1032
4
     << static_cast<const LiveRange&>(*this);
1033
4
}
1034
1035
6
void LiveInterval::print(raw_ostream &OS) const {
1036
6
  OS << printReg(reg) << ' ';
1037
6
  super::print(OS);
1038
6
  // Print subranges
1039
6
  for (const SubRange &SR : subranges())
1040
4
    OS << SR;
1041
6
  OS << " weight:" << weight;
1042
6
}
1043
1044
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1045
LLVM_DUMP_METHOD void LiveRange::dump() const {
1046
  dbgs() << *this << '\n';
1047
}
1048
1049
LLVM_DUMP_METHOD void LiveInterval::SubRange::dump() const {
1050
  dbgs() << *this << '\n';
1051
}
1052
1053
LLVM_DUMP_METHOD void LiveInterval::dump() const {
1054
  dbgs() << *this << '\n';
1055
}
1056
#endif
1057
1058
#ifndef NDEBUG
1059
void LiveRange::verify() const {
1060
  for (const_iterator I = begin(), E = end(); I != E; ++I) {
1061
    assert(I->start.isValid());
1062
    assert(I->end.isValid());
1063
    assert(I->start < I->end);
1064
    assert(I->valno != nullptr);
1065
    assert(I->valno->id < valnos.size());
1066
    assert(I->valno == valnos[I->valno->id]);
1067
    if (std::next(I) != E) {
1068
      assert(I->end <= std::next(I)->start);
1069
      if (I->end == std::next(I)->start)
1070
        assert(I->valno != std::next(I)->valno);
1071
    }
1072
  }
1073
}
1074
1075
void LiveInterval::verify(const MachineRegisterInfo *MRI) const {
1076
  super::verify();
1077
1078
  // Make sure SubRanges are fine and LaneMasks are disjunct.
1079
  LaneBitmask Mask;
1080
  LaneBitmask MaxMask = MRI != nullptr ? MRI->getMaxLaneMaskForVReg(reg)
1081
                                       : LaneBitmask::getAll();
1082
  for (const SubRange &SR : subranges()) {
1083
    // Subrange lanemask should be disjunct to any previous subrange masks.
1084
    assert((Mask & SR.LaneMask).none());
1085
    Mask |= SR.LaneMask;
1086
1087
    // subrange mask should not contained in maximum lane mask for the vreg.
1088
    assert((Mask & ~MaxMask).none());
1089
    // empty subranges must be removed.
1090
    assert(!SR.empty());
1091
1092
    SR.verify();
1093
    // Main liverange should cover subrange.
1094
    assert(covers(SR));
1095
  }
1096
}
1097
#endif
1098
1099
//===----------------------------------------------------------------------===//
1100
//                           LiveRangeUpdater class
1101
//===----------------------------------------------------------------------===//
1102
//
1103
// The LiveRangeUpdater class always maintains these invariants:
1104
//
1105
// - When LastStart is invalid, Spills is empty and the iterators are invalid.
1106
//   This is the initial state, and the state created by flush().
1107
//   In this state, isDirty() returns false.
1108
//
1109
// Otherwise, segments are kept in three separate areas:
1110
//
1111
// 1. [begin; WriteI) at the front of LR.
1112
// 2. [ReadI; end) at the back of LR.
1113
// 3. Spills.
1114
//
1115
// - LR.begin() <= WriteI <= ReadI <= LR.end().
1116
// - Segments in all three areas are fully ordered and coalesced.
1117
// - Segments in area 1 precede and can't coalesce with segments in area 2.
1118
// - Segments in Spills precede and can't coalesce with segments in area 2.
1119
// - No coalescing is possible between segments in Spills and segments in area
1120
//   1, and there are no overlapping segments.
1121
//
1122
// The segments in Spills are not ordered with respect to the segments in area
1123
// 1. They need to be merged.
1124
//
1125
// When they exist, Spills.back().start <= LastStart,
1126
//                 and WriteI[-1].start <= LastStart.
1127
1128
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1129
void LiveRangeUpdater::print(raw_ostream &OS) const {
1130
  if (!isDirty()) {
1131
    if (LR)
1132
      OS << "Clean updater: " << *LR << '\n';
1133
    else
1134
      OS << "Null updater.\n";
1135
    return;
1136
  }
1137
  assert(LR && "Can't have null LR in dirty updater.");
1138
  OS << " updater with gap = " << (ReadI - WriteI)
1139
     << ", last start = " << LastStart
1140
     << ":\n  Area 1:";
1141
  for (const auto &S : make_range(LR->begin(), WriteI))
1142
    OS << ' ' << S;
1143
  OS << "\n  Spills:";
1144
  for (unsigned I = 0, E = Spills.size(); I != E; ++I)
1145
    OS << ' ' << Spills[I];
1146
  OS << "\n  Area 2:";
1147
  for (const auto &S : make_range(ReadI, LR->end()))
1148
    OS << ' ' << S;
1149
  OS << '\n';
1150
}
1151
1152
LLVM_DUMP_METHOD void LiveRangeUpdater::dump() const {
1153
  print(errs());
1154
}
1155
#endif
1156
1157
// Determine if A and B should be coalesced.
1158
static inline bool coalescable(const LiveRange::Segment &A,
1159
46.3M
                               const LiveRange::Segment &B) {
1160
46.3M
  assert(A.start <= B.start && "Unordered live segments.");
1161
46.3M
  if (A.end == B.start)
1162
30.3M
    return A.valno == B.valno;
1163
15.9M
  if (A.end < B.start)
1164
15.6M
    return false;
1165
338k
  assert(A.valno == B.valno && "Cannot overlap different values");
1166
338k
  return true;
1167
338k
}
1168
1169
33.8M
void LiveRangeUpdater::add(LiveRange::Segment Seg) {
1170
33.8M
  assert(LR && "Cannot add to a null destination");
1171
33.8M
1172
33.8M
  // Fall back to the regular add method if the live range
1173
33.8M
  // is using the segment set instead of the segment vector.
1174
33.8M
  if (LR->segmentSet != nullptr) {
1175
936
    LR->addSegmentToSet(Seg);
1176
936
    return;
1177
936
  }
1178
33.8M
1179
33.8M
  // Flush the state if Start moves backwards.
1180
33.8M
  if (!LastStart.isValid() || 
LastStart > Seg.start26.4M
) {
1181
9.46M
    if (isDirty())
1182
2.01M
      flush();
1183
9.46M
    // This brings us to an uninitialized state. Reinitialize.
1184
9.46M
    assert(Spills.empty() && "Leftover spilled segments");
1185
9.46M
    WriteI = ReadI = LR->begin();
1186
9.46M
  }
1187
33.8M
1188
33.8M
  // Remember start for next time.
1189
33.8M
  LastStart = Seg.start;
1190
33.8M
1191
33.8M
  // Advance ReadI until it ends after Seg.start.
1192
33.8M
  LiveRange::iterator E = LR->end();
1193
33.8M
  if (ReadI != E && 
ReadI->end <= Seg.start13.8M
) {
1194
8.13M
    // First try to close the gap between WriteI and ReadI with spills.
1195
8.13M
    if (ReadI != WriteI)
1196
339k
      mergeSpills();
1197
8.13M
    // Then advance ReadI.
1198
8.13M
    if (ReadI == WriteI)
1199
7.80M
      ReadI = WriteI = LR->find(Seg.start);
1200
333k
    else
1201
1.25M
      
while (333k
ReadI != E &&
ReadI->end <= Seg.start1.23M
)
1202
921k
        *WriteI++ = *ReadI++;
1203
8.13M
  }
1204
33.8M
1205
33.8M
  assert(ReadI == E || ReadI->end > Seg.start);
1206
33.8M
1207
33.8M
  // Check if the ReadI segment begins early.
1208
33.8M
  if (ReadI != E && 
ReadI->start <= Seg.start10.3M
) {
1209
412k
    assert(ReadI->valno == Seg.valno && "Cannot overlap different values");
1210
412k
    // Bail if Seg is completely contained in ReadI.
1211
412k
    if (ReadI->end >= Seg.end)
1212
336k
      return;
1213
75.0k
    // Coalesce into Seg.
1214
75.0k
    Seg.start = ReadI->start;
1215
75.0k
    ++ReadI;
1216
75.0k
  }
1217
33.8M
1218
33.8M
  // Coalesce as much as possible from ReadI into Seg.
1219
38.9M
  
while (33.5M
ReadI != E &&
coalescable(Seg, *ReadI)12.9M
) {
1220
5.40M
    Seg.end = std::max(Seg.end, ReadI->end);
1221
5.40M
    ++ReadI;
1222
5.40M
  }
1223
33.5M
1224
33.5M
  // Try coalescing Spills.back() into Seg.
1225
33.5M
  if (!Spills.empty() && 
coalescable(Spills.back(), Seg)2.26M
) {
1226
805k
    Seg.start = Spills.back().start;
1227
805k
    Seg.end = std::max(Spills.back().end, Seg.end);
1228
805k
    Spills.pop_back();
1229
805k
  }
1230
33.5M
1231
33.5M
  // Try coalescing Seg into WriteI[-1].
1232
33.5M
  if (WriteI != LR->begin() && 
coalescable(WriteI[-1], Seg)31.1M
) {
1233
22.6M
    WriteI[-1].end = std::max(WriteI[-1].end, Seg.end);
1234
22.6M
    return;
1235
22.6M
  }
1236
10.8M
1237
10.8M
  // Seg doesn't coalesce with anything, and needs to be inserted somewhere.
1238
10.8M
  if (WriteI != ReadI) {
1239
2.92M
    *WriteI++ = Seg;
1240
2.92M
    return;
1241
2.92M
  }
1242
7.93M
1243
7.93M
  // Finally, append to LR or Spills.
1244
7.93M
  if (WriteI == E) {
1245
5.63M
    LR->segments.push_back(Seg);
1246
5.63M
    WriteI = ReadI = LR->end();
1247
5.63M
  } else
1248
2.30M
    Spills.push_back(Seg);
1249
7.93M
}
1250
1251
// Merge as many spilled segments as possible into the gap between WriteI
1252
// and ReadI. Advance WriteI to reflect the inserted instructions.
1253
1.30M
void LiveRangeUpdater::mergeSpills() {
1254
1.30M
  // Perform a backwards merge of Spills and [SpillI;WriteI).
1255
1.30M
  size_t GapSize = ReadI - WriteI;
1256
1.30M
  size_t NumMoved = std::min(Spills.size(), GapSize);
1257
1.30M
  LiveRange::iterator Src = WriteI;
1258
1.30M
  LiveRange::iterator Dst = Src + NumMoved;
1259
1.30M
  LiveRange::iterator SpillSrc = Spills.end();
1260
1.30M
  LiveRange::iterator B = LR->begin();
1261
1.30M
1262
1.30M
  // This is the new WriteI position after merging spills.
1263
1.30M
  WriteI = Dst;
1264
1.30M
1265
1.30M
  // Now merge Src and Spills backwards.
1266
3.87M
  while (Src != Dst) {
1267
2.57M
    if (Src != B && 
Src[-1].start > SpillSrc[-1].start1.99M
)
1268
1.07M
      *--Dst = *--Src;
1269
1.49M
    else
1270
1.49M
      *--Dst = *--SpillSrc;
1271
2.57M
  }
1272
1.30M
  assert(NumMoved == size_t(Spills.end() - SpillSrc));
1273
1.30M
  Spills.erase(SpillSrc, Spills.end());
1274
1.30M
}
1275
1276
10.3M
void LiveRangeUpdater::flush() {
1277
10.3M
  if (!isDirty())
1278
901k
    return;
1279
9.46M
  // Clear the dirty state.
1280
9.46M
  LastStart = SlotIndex();
1281
9.46M
1282
9.46M
  assert(LR && "Cannot add to a null destination");
1283
9.46M
1284
9.46M
  // Nothing to merge?
1285
9.46M
  if (Spills.empty()) {
1286
8.50M
    LR->segments.erase(WriteI, ReadI);
1287
8.50M
    LR->verify();
1288
8.50M
    return;
1289
8.50M
  }
1290
963k
1291
963k
  // Resize the WriteI - ReadI gap to match Spills.
1292
963k
  size_t GapSize = ReadI - WriteI;
1293
963k
  if (GapSize < Spills.size()) {
1294
959k
    // The gap is too small. Make some room.
1295
959k
    size_t WritePos = WriteI - LR->begin();
1296
959k
    LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment());
1297
959k
    // This also invalidated ReadI, but it is recomputed below.
1298
959k
    WriteI = LR->begin() + WritePos;
1299
959k
  } else {
1300
4.49k
    // Shrink the gap if necessary.
1301
4.49k
    LR->segments.erase(WriteI + Spills.size(), ReadI);
1302
4.49k
  }
1303
963k
  ReadI = WriteI + Spills.size();
1304
963k
  mergeSpills();
1305
963k
  LR->verify();
1306
963k
}
1307
1308
3.00M
unsigned ConnectedVNInfoEqClasses::Classify(const LiveRange &LR) {
1309
3.00M
  // Create initial equivalence classes.
1310
3.00M
  EqClass.clear();
1311
3.00M
  EqClass.grow(LR.getNumValNums());
1312
3.00M
1313
3.00M
  const VNInfo *used = nullptr, *unused = nullptr;
1314
3.00M
1315
3.00M
  // Determine connections.
1316
4.24M
  for (const VNInfo *VNI : LR.valnos) {
1317
4.24M
    // Group all unused values into one class.
1318
4.24M
    if (VNI->isUnused()) {
1319
722
      if (unused)
1320
17
        EqClass.join(unused->id, VNI->id);
1321
722
      unused = VNI;
1322
722
      continue;
1323
722
    }
1324
4.24M
    used = VNI;
1325
4.24M
    if (VNI->isPHIDef()) {
1326
268k
      const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def);
1327
268k
      assert(MBB && "Phi-def has no defining MBB");
1328
268k
      // Connect to values live out of predecessors.
1329
268k
      for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
1330
1.03M
           PE = MBB->pred_end(); PI != PE; 
++PI762k
)
1331
762k
        if (const VNInfo *PVNI = LR.getVNInfoBefore(LIS.getMBBEndIdx(*PI)))
1332
762k
          EqClass.join(VNI->id, PVNI->id);
1333
3.97M
    } else {
1334
3.97M
      // Normal value defined by an instruction. Check for two-addr redef.
1335
3.97M
      // FIXME: This could be coincidental. Should we really check for a tied
1336
3.97M
      // operand constraint?
1337
3.97M
      // Note that VNI->def may be a use slot for an early clobber def.
1338
3.97M
      if (const VNInfo *UVNI = LR.getVNInfoBefore(VNI->def))
1339
697k
        EqClass.join(VNI->id, UVNI->id);
1340
3.97M
    }
1341
4.24M
  }
1342
3.00M
1343
3.00M
  // Lump all the unused values in with the last used value.
1344
3.00M
  if (used && 
unused2.95M
)
1345
705
    EqClass.join(used->id, unused->id);
1346
3.00M
1347
3.00M
  EqClass.compress();
1348
3.00M
  return EqClass.getNumClasses();
1349
3.00M
}
1350
1351
void ConnectedVNInfoEqClasses::Distribute(LiveInterval &LI, LiveInterval *LIV[],
1352
64.5k
                                          MachineRegisterInfo &MRI) {
1353
64.5k
  // Rewrite instructions.
1354
64.5k
  for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg),
1355
518k
       RE = MRI.reg_end(); RI != RE;) {
1356
454k
    MachineOperand &MO = *RI;
1357
454k
    MachineInstr *MI = RI->getParent();
1358
454k
    ++RI;
1359
454k
    const VNInfo *VNI;
1360
454k
    if (MI->isDebugValue()) {
1361
15
      // DBG_VALUE instructions don't have slot indexes, so get the index of
1362
15
      // the instruction before them. The value is defined there too.
1363
15
      SlotIndex Idx = LIS.getSlotIndexes()->getIndexBefore(*MI);
1364
15
      VNI = LI.Query(Idx).valueOut();
1365
454k
    } else {
1366
454k
      SlotIndex Idx = LIS.getInstructionIndex(*MI);
1367
454k
      LiveQueryResult LRQ = LI.Query(Idx);
1368
454k
      VNI = MO.readsReg() ? 
LRQ.valueIn()264k
:
LRQ.valueDefined()189k
;
1369
454k
    }
1370
454k
    // In the case of an <undef> use that isn't tied to any def, VNI will be
1371
454k
    // NULL. If the use is tied to a def, VNI will be the defined value.
1372
454k
    if (!VNI)
1373
0
      continue;
1374
454k
    if (unsigned EqClass = getEqClass(VNI))
1375
251k
      MO.setReg(LIV[EqClass-1]->reg);
1376
454k
  }
1377
64.5k
1378
64.5k
  // Distribute subregister liveranges.
1379
64.5k
  if (LI.hasSubRanges()) {
1380
32
    unsigned NumComponents = EqClass.getNumClasses();
1381
32
    SmallVector<unsigned, 8> VNIMapping;
1382
32
    SmallVector<LiveInterval::SubRange*, 8> SubRanges;
1383
32
    BumpPtrAllocator &Allocator = LIS.getVNInfoAllocator();
1384
122
    for (LiveInterval::SubRange &SR : LI.subranges()) {
1385
122
      // Create new subranges in the split intervals and construct a mapping
1386
122
      // for the VNInfos in the subrange.
1387
122
      unsigned NumValNos = SR.valnos.size();
1388
122
      VNIMapping.clear();
1389
122
      VNIMapping.reserve(NumValNos);
1390
122
      SubRanges.clear();
1391
122
      SubRanges.resize(NumComponents-1, nullptr);
1392
364
      for (unsigned I = 0; I < NumValNos; 
++I242
) {
1393
242
        const VNInfo &VNI = *SR.valnos[I];
1394
242
        unsigned ComponentNum;
1395
242
        if (VNI.isUnused()) {
1396
2
          ComponentNum = 0;
1397
240
        } else {
1398
240
          const VNInfo *MainRangeVNI = LI.getVNInfoAt(VNI.def);
1399
240
          assert(MainRangeVNI != nullptr
1400
240
                 && "SubRange def must have corresponding main range def");
1401
240
          ComponentNum = getEqClass(MainRangeVNI);
1402
240
          if (ComponentNum > 0 && 
SubRanges[ComponentNum-1] == nullptr122
) {
1403
122
            SubRanges[ComponentNum-1]
1404
122
              = LIV[ComponentNum-1]->createSubRange(Allocator, SR.LaneMask);
1405
122
          }
1406
240
        }
1407
242
        VNIMapping.push_back(ComponentNum);
1408
242
      }
1409
122
      DistributeRange(SR, SubRanges.data(), VNIMapping);
1410
122
    }
1411
32
    LI.removeEmptySubRanges();
1412
32
  }
1413
64.5k
1414
64.5k
  // Distribute main liverange.
1415
64.5k
  DistributeRange(LI, LIV, EqClass);
1416
64.5k
}