|
121
|
1 //===- LiveIntervalAnalysis.cpp - Live Interval Analysis ------------------===//
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 // The LLVM Compiler Infrastructure
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 // This file is distributed under the University of Illinois Open Source
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 // License. See LICENSE.TXT for details.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 //
|
|
121
|
10 /// \file This file implements the LiveInterval analysis pass which is used
|
|
|
11 /// by the Linear Scan Register allocator. This pass linearizes the
|
|
|
12 /// basic blocks of the function in DFS order and computes live intervals for
|
|
|
13 /// each virtual and physical register.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 #include "LiveRangeCalc.h"
|
|
121
|
19 #include "llvm/ADT/ArrayRef.h"
|
|
|
20 #include "llvm/ADT/DepthFirstIterator.h"
|
|
|
21 #include "llvm/ADT/SmallPtrSet.h"
|
|
|
22 #include "llvm/ADT/SmallVector.h"
|
|
|
23 #include "llvm/ADT/iterator_range.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 #include "llvm/Analysis/AliasAnalysis.h"
|
|
121
|
25 #include "llvm/CodeGen/LiveInterval.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 #include "llvm/CodeGen/LiveVariables.h"
|
|
121
|
27 #include "llvm/CodeGen/MachineBasicBlock.h"
|
|
77
|
28 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 #include "llvm/CodeGen/MachineDominators.h"
|
|
121
|
30 #include "llvm/CodeGen/MachineFunction.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 #include "llvm/CodeGen/MachineInstr.h"
|
|
121
|
32 #include "llvm/CodeGen/MachineInstrBundle.h"
|
|
|
33 #include "llvm/CodeGen/MachineOperand.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 #include "llvm/CodeGen/Passes.h"
|
|
121
|
36 #include "llvm/CodeGen/SlotIndexes.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 #include "llvm/CodeGen/VirtRegMap.h"
|
|
121
|
38 #include "llvm/MC/LaneBitmask.h"
|
|
|
39 #include "llvm/MC/MCRegisterInfo.h"
|
|
|
40 #include "llvm/Pass.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 #include "llvm/Support/BlockFrequency.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 #include "llvm/Support/CommandLine.h"
|
|
121
|
43 #include "llvm/Support/Compiler.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 #include "llvm/Support/Debug.h"
|
|
121
|
45 #include "llvm/Support/MathExtras.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 #include "llvm/Support/raw_ostream.h"
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 #include "llvm/Target/TargetRegisterInfo.h"
|
|
77
|
48 #include "llvm/Target/TargetSubtargetInfo.h"
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 #include <algorithm>
|
|
121
|
50 #include <cassert>
|
|
|
51 #include <cstdint>
|
|
|
52 #include <iterator>
|
|
|
53 #include <tuple>
|
|
|
54 #include <utility>
|
|
|
55
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
56 using namespace llvm;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
57
|
|
77
|
58 #define DEBUG_TYPE "regalloc"
|
|
|
59
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
60 char LiveIntervals::ID = 0;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 char &llvm::LiveIntervalsID = LiveIntervals::ID;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
62 INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
63 "Live Interval Analysis", false, false)
|
|
95
|
64 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 "Live Interval Analysis", false, false)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
69
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 #ifndef NDEBUG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 static cl::opt<bool> EnablePrecomputePhysRegs(
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 "precompute-phys-liveness", cl::Hidden,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 cl::desc("Eagerly compute live intervals for all physreg units."));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74 #else
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
75 static bool EnablePrecomputePhysRegs = false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 #endif // NDEBUG
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77
|
|
83
|
78 namespace llvm {
|
|
121
|
79
|
|
83
|
80 cl::opt<bool> UseSegmentSetForPhysRegs(
|
|
|
81 "use-segment-set-for-physregs", cl::Hidden, cl::init(true),
|
|
|
82 cl::desc(
|
|
|
83 "Use segment set for the computation of the live ranges of physregs."));
|
|
121
|
84
|
|
|
85 } // end namespace llvm
|
|
83
|
86
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
87 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
88 AU.setPreservesCFG();
|
|
95
|
89 AU.addRequired<AAResultsWrapperPass>();
|
|
|
90 AU.addPreserved<AAResultsWrapperPass>();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
91 AU.addPreserved<LiveVariables>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
92 AU.addPreservedID(MachineLoopInfoID);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93 AU.addRequiredTransitiveID(MachineDominatorsID);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 AU.addPreservedID(MachineDominatorsID);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
95 AU.addPreserved<SlotIndexes>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
96 AU.addRequiredTransitive<SlotIndexes>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
97 MachineFunctionPass::getAnalysisUsage(AU);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
98 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99
|
|
121
|
100 LiveIntervals::LiveIntervals() : MachineFunctionPass(ID) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
101 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
102 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
103
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104 LiveIntervals::~LiveIntervals() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
105 delete LRCalc;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
106 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
107
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
108 void LiveIntervals::releaseMemory() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
109 // Free the live intervals themselves.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
110 for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
111 delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 VirtRegIntervals.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
113 RegMaskSlots.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
114 RegMaskBits.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
115 RegMaskBlocks.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116
|
|
121
|
117 for (LiveRange *LR : RegUnitRanges)
|
|
|
118 delete LR;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
119 RegUnitRanges.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
120
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
121 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
122 VNInfoAllocator.Reset();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
123 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
124
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
125 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
126 MF = &fn;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
127 MRI = &MF->getRegInfo();
|
|
83
|
128 TRI = MF->getSubtarget().getRegisterInfo();
|
|
|
129 TII = MF->getSubtarget().getInstrInfo();
|
|
95
|
130 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
131 Indexes = &getAnalysis<SlotIndexes>();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
132 DomTree = &getAnalysis<MachineDominatorTree>();
|
|
83
|
133
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
134 if (!LRCalc)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
135 LRCalc = new LiveRangeCalc();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
136
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
137 // Allocate space for all virtual registers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
138 VirtRegIntervals.resize(MRI->getNumVirtRegs());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
139
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
140 computeVirtRegs();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
141 computeRegMasks();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
142 computeLiveInRegUnits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
143
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
144 if (EnablePrecomputePhysRegs) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
145 // For stress testing, precompute live ranges of all physical register
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 // units, including reserved registers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
147 for (unsigned i = 0, e = TRI->getNumRegUnits(); i != e; ++i)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
148 getRegUnit(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
149 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
150 DEBUG(dump());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
151 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
153
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
154 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
155 OS << "********** INTERVALS **********\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
156
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
157 // Dump the regunits.
|
|
121
|
158 for (unsigned Unit = 0, UnitE = RegUnitRanges.size(); Unit != UnitE; ++Unit)
|
|
|
159 if (LiveRange *LR = RegUnitRanges[Unit])
|
|
|
160 OS << PrintRegUnit(Unit, TRI) << ' ' << *LR << '\n';
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
161
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
162 // Dump the virtregs.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
163 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
164 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
165 if (hasInterval(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
166 OS << getInterval(Reg) << '\n';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
167 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
168
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
169 OS << "RegMasks:";
|
|
121
|
170 for (SlotIndex Idx : RegMaskSlots)
|
|
|
171 OS << ' ' << Idx;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
172 OS << '\n';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
173
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
174 printInstrs(OS);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
175 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
176
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
177 void LiveIntervals::printInstrs(raw_ostream &OS) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
178 OS << "********** MACHINEINSTRS **********\n";
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
179 MF->print(OS, Indexes);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
180 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
181
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
182 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
|
|
121
|
183 LLVM_DUMP_METHOD void LiveIntervals::dumpInstrs() const {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
184 printInstrs(dbgs());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
185 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
186 #endif
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
187
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
188 LiveInterval* LiveIntervals::createInterval(unsigned reg) {
|
|
121
|
189 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? huge_valf : 0.0F;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
190 return new LiveInterval(reg, Weight);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
191 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
192
|
|
121
|
193 /// Compute the live interval of a virtual register, based on defs and uses.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
194 void LiveIntervals::computeVirtRegInterval(LiveInterval &LI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
195 assert(LRCalc && "LRCalc not initialized.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
196 assert(LI.empty() && "Should only compute empty intervals.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
197 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
|
|
120
|
198 LRCalc->calculate(LI, MRI->shouldTrackSubRegLiveness(LI.reg));
|
|
|
199 computeDeadValues(LI, nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
200 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
201
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
202 void LiveIntervals::computeVirtRegs() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
204 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
205 if (MRI->reg_nodbg_empty(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
206 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
207 createAndComputeVirtRegInterval(Reg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
208 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
209 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
210
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
211 void LiveIntervals::computeRegMasks() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
212 RegMaskBlocks.resize(MF->getNumBlockIDs());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
213
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
214 // Find all instructions with regmask operands.
|
|
121
|
215 for (const MachineBasicBlock &MBB : *MF) {
|
|
100
|
216 std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB.getNumber()];
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
217 RMB.first = RegMaskSlots.size();
|
|
100
|
218
|
|
|
219 // Some block starts, such as EH funclets, create masks.
|
|
|
220 if (const uint32_t *Mask = MBB.getBeginClobberMask(TRI)) {
|
|
|
221 RegMaskSlots.push_back(Indexes->getMBBStartIdx(&MBB));
|
|
|
222 RegMaskBits.push_back(Mask);
|
|
|
223 }
|
|
|
224
|
|
121
|
225 for (const MachineInstr &MI : MBB) {
|
|
100
|
226 for (const MachineOperand &MO : MI.operands()) {
|
|
95
|
227 if (!MO.isRegMask())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
228 continue;
|
|
120
|
229 RegMaskSlots.push_back(Indexes->getInstructionIndex(MI).getRegSlot());
|
|
100
|
230 RegMaskBits.push_back(MO.getRegMask());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
231 }
|
|
100
|
232 }
|
|
|
233
|
|
120
|
234 // Some block ends, such as funclet returns, create masks. Put the mask on
|
|
|
235 // the last instruction of the block, because MBB slot index intervals are
|
|
|
236 // half-open.
|
|
100
|
237 if (const uint32_t *Mask = MBB.getEndClobberMask(TRI)) {
|
|
120
|
238 assert(!MBB.empty() && "empty return block?");
|
|
|
239 RegMaskSlots.push_back(
|
|
|
240 Indexes->getInstructionIndex(MBB.back()).getRegSlot());
|
|
100
|
241 RegMaskBits.push_back(Mask);
|
|
|
242 }
|
|
|
243
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
244 // Compute the number of register mask instructions in this block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
245 RMB.second = RegMaskSlots.size() - RMB.first;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
247 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
248
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
249 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
250 // Register Unit Liveness
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
251 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
252 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
253 // Fixed interference typically comes from ABI boundaries: Function arguments
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
254 // and return values are passed in fixed registers, and so are exception
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
255 // pointers entering landing pads. Certain instructions require values to be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
256 // present in specific registers. That is also represented through fixed
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
257 // interference.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
258 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
259
|
|
121
|
260 /// Compute the live range of a register unit, based on the uses and defs of
|
|
|
261 /// aliasing registers. The range should be empty, or contain only dead
|
|
|
262 /// phi-defs from ABI blocks.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
263 void LiveIntervals::computeRegUnitRange(LiveRange &LR, unsigned Unit) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
264 assert(LRCalc && "LRCalc not initialized.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
265 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
266
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
267 // The physregs aliasing Unit are the roots and their super-registers.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
268 // Create all values as dead defs before extending to uses. Note that roots
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
269 // may share super-registers. That's OK because createDeadDefs() is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
270 // idempotent. It is very rare for a register unit to have multiple roots, so
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
271 // uniquing super-registers is probably not worthwhile.
|
|
121
|
272 bool IsReserved = false;
|
|
|
273 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
|
|
|
274 bool IsRootReserved = true;
|
|
|
275 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
|
|
|
276 Super.isValid(); ++Super) {
|
|
|
277 unsigned Reg = *Super;
|
|
|
278 if (!MRI->reg_empty(Reg))
|
|
|
279 LRCalc->createDeadDefs(LR, Reg);
|
|
|
280 // A register unit is considered reserved if all its roots and all their
|
|
|
281 // super registers are reserved.
|
|
|
282 if (!MRI->isReserved(Reg))
|
|
|
283 IsRootReserved = false;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
284 }
|
|
121
|
285 IsReserved |= IsRootReserved;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
286 }
|
|
121
|
287 assert(IsReserved == MRI->isReservedRegUnit(Unit) &&
|
|
|
288 "reserved computation mismatch");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
289
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
290 // Now extend LR to reach all uses.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
291 // Ignore uses of reserved registers. We only track defs of those.
|
|
121
|
292 if (!IsReserved) {
|
|
|
293 for (MCRegUnitRootIterator Root(Unit, TRI); Root.isValid(); ++Root) {
|
|
|
294 for (MCSuperRegIterator Super(*Root, TRI, /*IncludeSelf=*/true);
|
|
|
295 Super.isValid(); ++Super) {
|
|
|
296 unsigned Reg = *Super;
|
|
|
297 if (!MRI->reg_empty(Reg))
|
|
|
298 LRCalc->extendToUses(LR, Reg);
|
|
|
299 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
300 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
301 }
|
|
83
|
302
|
|
|
303 // Flush the segment set to the segment vector.
|
|
|
304 if (UseSegmentSetForPhysRegs)
|
|
|
305 LR.flushSegmentSet();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
306 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
307
|
|
121
|
308 /// Precompute the live ranges of any register units that are live-in to an ABI
|
|
|
309 /// block somewhere. Register values can appear without a corresponding def when
|
|
|
310 /// entering the entry block or a landing pad.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
311 void LiveIntervals::computeLiveInRegUnits() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
312 RegUnitRanges.resize(TRI->getNumRegUnits());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
313 DEBUG(dbgs() << "Computing live-in reg-units in ABI blocks.\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
314
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
315 // Keep track of the live range sets allocated.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
316 SmallVector<unsigned, 8> NewRanges;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
317
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
318 // Check all basic blocks for live-ins.
|
|
121
|
319 for (const MachineBasicBlock &MBB : *MF) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
320 // We only care about ABI blocks: Entry + landing pads.
|
|
121
|
321 if ((&MBB != &MF->front() && !MBB.isEHPad()) || MBB.livein_empty())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
322 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
323
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
324 // Create phi-defs at Begin for all live-in registers.
|
|
121
|
325 SlotIndex Begin = Indexes->getMBBStartIdx(&MBB);
|
|
|
326 DEBUG(dbgs() << Begin << "\tBB#" << MBB.getNumber());
|
|
|
327 for (const auto &LI : MBB.liveins()) {
|
|
95
|
328 for (MCRegUnitIterator Units(LI.PhysReg, TRI); Units.isValid(); ++Units) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
329 unsigned Unit = *Units;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
330 LiveRange *LR = RegUnitRanges[Unit];
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
331 if (!LR) {
|
|
83
|
332 // Use segment set to speed-up initial computation of the live range.
|
|
|
333 LR = RegUnitRanges[Unit] = new LiveRange(UseSegmentSetForPhysRegs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
334 NewRanges.push_back(Unit);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
335 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
336 VNInfo *VNI = LR->createDeadDef(Begin, getVNInfoAllocator());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
337 (void)VNI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
338 DEBUG(dbgs() << ' ' << PrintRegUnit(Unit, TRI) << '#' << VNI->id);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
339 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
340 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
341 DEBUG(dbgs() << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
342 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
343 DEBUG(dbgs() << "Created " << NewRanges.size() << " new intervals.\n");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
344
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
345 // Compute the 'normal' part of the ranges.
|
|
121
|
346 for (unsigned Unit : NewRanges)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
347 computeRegUnitRange(*RegUnitRanges[Unit], Unit);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
348 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
349
|
|
83
|
350 static void createSegmentsForValues(LiveRange &LR,
|
|
121
|
351 iterator_range<LiveInterval::vni_iterator> VNIs) {
|
|
|
352 for (VNInfo *VNI : VNIs) {
|
|
83
|
353 if (VNI->isUnused())
|
|
|
354 continue;
|
|
|
355 SlotIndex Def = VNI->def;
|
|
|
356 LR.addSegment(LiveRange::Segment(Def, Def.getDeadSlot(), VNI));
|
|
|
357 }
|
|
|
358 }
|
|
|
359
|
|
121
|
360 using ShrinkToUsesWorkList = SmallVector<std::pair<SlotIndex, VNInfo*>, 16>;
|
|
83
|
361
|
|
|
362 static void extendSegmentsToUses(LiveRange &LR, const SlotIndexes &Indexes,
|
|
|
363 ShrinkToUsesWorkList &WorkList,
|
|
|
364 const LiveRange &OldRange) {
|
|
|
365 // Keep track of the PHIs that are in use.
|
|
|
366 SmallPtrSet<VNInfo*, 8> UsedPHIs;
|
|
|
367 // Blocks that have already been added to WorkList as live-out.
|
|
121
|
368 SmallPtrSet<const MachineBasicBlock*, 16> LiveOut;
|
|
83
|
369
|
|
|
370 // Extend intervals to reach all uses in WorkList.
|
|
|
371 while (!WorkList.empty()) {
|
|
|
372 SlotIndex Idx = WorkList.back().first;
|
|
|
373 VNInfo *VNI = WorkList.back().second;
|
|
|
374 WorkList.pop_back();
|
|
|
375 const MachineBasicBlock *MBB = Indexes.getMBBFromIndex(Idx.getPrevSlot());
|
|
|
376 SlotIndex BlockStart = Indexes.getMBBStartIdx(MBB);
|
|
|
377
|
|
|
378 // Extend the live range for VNI to be live at Idx.
|
|
|
379 if (VNInfo *ExtVNI = LR.extendInBlock(BlockStart, Idx)) {
|
|
|
380 assert(ExtVNI == VNI && "Unexpected existing value number");
|
|
|
381 (void)ExtVNI;
|
|
|
382 // Is this a PHIDef we haven't seen before?
|
|
|
383 if (!VNI->isPHIDef() || VNI->def != BlockStart ||
|
|
|
384 !UsedPHIs.insert(VNI).second)
|
|
|
385 continue;
|
|
|
386 // The PHI is live, make sure the predecessors are live-out.
|
|
121
|
387 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
|
|
83
|
388 if (!LiveOut.insert(Pred).second)
|
|
|
389 continue;
|
|
|
390 SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
|
|
|
391 // A predecessor is not required to have a live-out value for a PHI.
|
|
|
392 if (VNInfo *PVNI = OldRange.getVNInfoBefore(Stop))
|
|
|
393 WorkList.push_back(std::make_pair(Stop, PVNI));
|
|
|
394 }
|
|
|
395 continue;
|
|
|
396 }
|
|
|
397
|
|
|
398 // VNI is live-in to MBB.
|
|
|
399 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
|
|
|
400 LR.addSegment(LiveRange::Segment(BlockStart, Idx, VNI));
|
|
|
401
|
|
|
402 // Make sure VNI is live-out from the predecessors.
|
|
121
|
403 for (const MachineBasicBlock *Pred : MBB->predecessors()) {
|
|
83
|
404 if (!LiveOut.insert(Pred).second)
|
|
|
405 continue;
|
|
|
406 SlotIndex Stop = Indexes.getMBBEndIdx(Pred);
|
|
|
407 assert(OldRange.getVNInfoBefore(Stop) == VNI &&
|
|
|
408 "Wrong value out of predecessor");
|
|
|
409 WorkList.push_back(std::make_pair(Stop, VNI));
|
|
|
410 }
|
|
|
411 }
|
|
|
412 }
|
|
|
413
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
414 bool LiveIntervals::shrinkToUses(LiveInterval *li,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
415 SmallVectorImpl<MachineInstr*> *dead) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
416 DEBUG(dbgs() << "Shrink: " << *li << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
417 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
418 && "Can only shrink virtual registers");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
419
|
|
83
|
420 // Shrink subregister live ranges.
|
|
95
|
421 bool NeedsCleanup = false;
|
|
83
|
422 for (LiveInterval::SubRange &S : li->subranges()) {
|
|
|
423 shrinkToUses(S, li->reg);
|
|
95
|
424 if (S.empty())
|
|
|
425 NeedsCleanup = true;
|
|
83
|
426 }
|
|
95
|
427 if (NeedsCleanup)
|
|
|
428 li->removeEmptySubRanges();
|
|
83
|
429
|
|
|
430 // Find all the values used, including PHI kills.
|
|
|
431 ShrinkToUsesWorkList WorkList;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
432
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
433 // Visit all instructions reading li->reg.
|
|
121
|
434 unsigned Reg = li->reg;
|
|
|
435 for (MachineInstr &UseMI : MRI->reg_instructions(Reg)) {
|
|
|
436 if (UseMI.isDebugValue() || !UseMI.readsVirtualRegister(Reg))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
437 continue;
|
|
121
|
438 SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
439 LiveQueryResult LRQ = li->Query(Idx);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
440 VNInfo *VNI = LRQ.valueIn();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
441 if (!VNI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
442 // This shouldn't happen: readsVirtualRegister returns true, but there is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
443 // no live value. It is likely caused by a target getting <undef> flags
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
444 // wrong.
|
|
121
|
445 DEBUG(dbgs() << Idx << '\t' << UseMI
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
446 << "Warning: Instr claims to read non-existent value in "
|
|
121
|
447 << *li << '\n');
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
448 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
449 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
450 // Special case: An early-clobber tied operand reads and writes the
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
451 // register one slot early.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
452 if (VNInfo *DefVNI = LRQ.valueDefined())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
453 Idx = DefVNI->def;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
454
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
455 WorkList.push_back(std::make_pair(Idx, VNI));
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
456 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
457
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
458 // Create new live ranges with only minimal live segments per def.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
459 LiveRange NewLR;
|
|
83
|
460 createSegmentsForValues(NewLR, make_range(li->vni_begin(), li->vni_end()));
|
|
|
461 extendSegmentsToUses(NewLR, *Indexes, WorkList, *li);
|
|
77
|
462
|
|
|
463 // Move the trimmed segments back.
|
|
|
464 li->segments.swap(NewLR.segments);
|
|
83
|
465
|
|
|
466 // Handle dead values.
|
|
|
467 bool CanSeparate = computeDeadValues(*li, dead);
|
|
77
|
468 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
|
|
|
469 return CanSeparate;
|
|
|
470 }
|
|
|
471
|
|
83
|
472 bool LiveIntervals::computeDeadValues(LiveInterval &LI,
|
|
77
|
473 SmallVectorImpl<MachineInstr*> *dead) {
|
|
95
|
474 bool MayHaveSplitComponents = false;
|
|
121
|
475 for (VNInfo *VNI : LI.valnos) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
476 if (VNI->isUnused())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
477 continue;
|
|
83
|
478 SlotIndex Def = VNI->def;
|
|
|
479 LiveRange::iterator I = LI.FindSegmentContaining(Def);
|
|
|
480 assert(I != LI.end() && "Missing segment for VNI");
|
|
|
481
|
|
|
482 // Is the register live before? Otherwise we may have to add a read-undef
|
|
|
483 // flag for subregister defs.
|
|
95
|
484 unsigned VReg = LI.reg;
|
|
|
485 if (MRI->shouldTrackSubRegLiveness(VReg)) {
|
|
83
|
486 if ((I == LI.begin() || std::prev(I)->end < Def) && !VNI->isPHIDef()) {
|
|
|
487 MachineInstr *MI = getInstructionFromIndex(Def);
|
|
100
|
488 MI->setRegisterDefReadUndef(VReg);
|
|
83
|
489 }
|
|
|
490 }
|
|
|
491
|
|
|
492 if (I->end != Def.getDeadSlot())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
493 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
494 if (VNI->isPHIDef()) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
495 // This is a dead PHI. Remove it.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
496 VNI->markUnused();
|
|
83
|
497 LI.removeSegment(I);
|
|
|
498 DEBUG(dbgs() << "Dead PHI at " << Def << " may separate interval\n");
|
|
95
|
499 MayHaveSplitComponents = true;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
500 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
501 // This is a dead def. Make sure the instruction knows.
|
|
83
|
502 MachineInstr *MI = getInstructionFromIndex(Def);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
503 assert(MI && "No instruction defining live value");
|
|
120
|
504 MI->addRegisterDead(LI.reg, TRI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
505 if (dead && MI->allDefsAreDead()) {
|
|
83
|
506 DEBUG(dbgs() << "All defs dead: " << Def << '\t' << *MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
507 dead->push_back(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
508 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
509 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
510 }
|
|
95
|
511 return MayHaveSplitComponents;
|
|
83
|
512 }
|
|
|
513
|
|
120
|
514 void LiveIntervals::shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg) {
|
|
83
|
515 DEBUG(dbgs() << "Shrink: " << SR << '\n');
|
|
|
516 assert(TargetRegisterInfo::isVirtualRegister(Reg)
|
|
|
517 && "Can only shrink virtual registers");
|
|
|
518 // Find all the values used, including PHI kills.
|
|
|
519 ShrinkToUsesWorkList WorkList;
|
|
|
520
|
|
|
521 // Visit all instructions reading Reg.
|
|
|
522 SlotIndex LastIdx;
|
|
120
|
523 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) {
|
|
|
524 // Skip "undef" uses.
|
|
|
525 if (!MO.readsReg())
|
|
83
|
526 continue;
|
|
|
527 // Maybe the operand is for a subregister we don't care about.
|
|
|
528 unsigned SubReg = MO.getSubReg();
|
|
|
529 if (SubReg != 0) {
|
|
95
|
530 LaneBitmask LaneMask = TRI->getSubRegIndexLaneMask(SubReg);
|
|
121
|
531 if ((LaneMask & SR.LaneMask).none())
|
|
83
|
532 continue;
|
|
|
533 }
|
|
|
534 // We only need to visit each instruction once.
|
|
120
|
535 MachineInstr *UseMI = MO.getParent();
|
|
|
536 SlotIndex Idx = getInstructionIndex(*UseMI).getRegSlot();
|
|
83
|
537 if (Idx == LastIdx)
|
|
|
538 continue;
|
|
|
539 LastIdx = Idx;
|
|
|
540
|
|
|
541 LiveQueryResult LRQ = SR.Query(Idx);
|
|
|
542 VNInfo *VNI = LRQ.valueIn();
|
|
|
543 // For Subranges it is possible that only undef values are left in that
|
|
|
544 // part of the subregister, so there is no real liverange at the use
|
|
|
545 if (!VNI)
|
|
|
546 continue;
|
|
|
547
|
|
|
548 // Special case: An early-clobber tied operand reads and writes the
|
|
|
549 // register one slot early.
|
|
|
550 if (VNInfo *DefVNI = LRQ.valueDefined())
|
|
|
551 Idx = DefVNI->def;
|
|
|
552
|
|
|
553 WorkList.push_back(std::make_pair(Idx, VNI));
|
|
|
554 }
|
|
|
555
|
|
|
556 // Create a new live ranges with only minimal live segments per def.
|
|
|
557 LiveRange NewLR;
|
|
|
558 createSegmentsForValues(NewLR, make_range(SR.vni_begin(), SR.vni_end()));
|
|
|
559 extendSegmentsToUses(NewLR, *Indexes, WorkList, SR);
|
|
|
560
|
|
|
561 // Move the trimmed ranges back.
|
|
|
562 SR.segments.swap(NewLR.segments);
|
|
|
563
|
|
|
564 // Remove dead PHI value numbers
|
|
121
|
565 for (VNInfo *VNI : SR.valnos) {
|
|
83
|
566 if (VNI->isUnused())
|
|
|
567 continue;
|
|
|
568 const LiveRange::Segment *Segment = SR.getSegmentContaining(VNI->def);
|
|
|
569 assert(Segment != nullptr && "Missing segment for VNI");
|
|
|
570 if (Segment->end != VNI->def.getDeadSlot())
|
|
|
571 continue;
|
|
|
572 if (VNI->isPHIDef()) {
|
|
|
573 // This is a dead PHI. Remove it.
|
|
120
|
574 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
|
|
83
|
575 VNI->markUnused();
|
|
|
576 SR.removeSegment(*Segment);
|
|
|
577 }
|
|
|
578 }
|
|
|
579
|
|
|
580 DEBUG(dbgs() << "Shrunk: " << SR << '\n');
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
581 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
582
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
583 void LiveIntervals::extendToIndices(LiveRange &LR,
|
|
120
|
584 ArrayRef<SlotIndex> Indices,
|
|
|
585 ArrayRef<SlotIndex> Undefs) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
586 assert(LRCalc && "LRCalc not initialized.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
587 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
|
|
121
|
588 for (SlotIndex Idx : Indices)
|
|
|
589 LRCalc->extend(LR, Idx, /*PhysReg=*/0, Undefs);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
590 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
591
|
|
83
|
592 void LiveIntervals::pruneValue(LiveRange &LR, SlotIndex Kill,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
593 SmallVectorImpl<SlotIndex> *EndPoints) {
|
|
83
|
594 LiveQueryResult LRQ = LR.Query(Kill);
|
|
|
595 VNInfo *VNI = LRQ.valueOutOrDead();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
596 if (!VNI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
597 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
598
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
599 MachineBasicBlock *KillMBB = Indexes->getMBBFromIndex(Kill);
|
|
83
|
600 SlotIndex MBBEnd = Indexes->getMBBEndIdx(KillMBB);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
601
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
602 // If VNI isn't live out from KillMBB, the value is trivially pruned.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
603 if (LRQ.endPoint() < MBBEnd) {
|
|
83
|
604 LR.removeSegment(Kill, LRQ.endPoint());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
605 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
606 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
607 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
608
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
609 // VNI is live out of KillMBB.
|
|
83
|
610 LR.removeSegment(Kill, MBBEnd);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
611 if (EndPoints) EndPoints->push_back(MBBEnd);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
612
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
613 // Find all blocks that are reachable from KillMBB without leaving VNI's live
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
614 // range. It is possible that KillMBB itself is reachable, so start a DFS
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
615 // from each successor.
|
|
121
|
616 using VisitedTy = df_iterator_default_set<MachineBasicBlock*,9>;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
617 VisitedTy Visited;
|
|
121
|
618 for (MachineBasicBlock *Succ : KillMBB->successors()) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
619 for (df_ext_iterator<MachineBasicBlock*, VisitedTy>
|
|
121
|
620 I = df_ext_begin(Succ, Visited), E = df_ext_end(Succ, Visited);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
621 I != E;) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
622 MachineBasicBlock *MBB = *I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
623
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
624 // Check if VNI is live in to MBB.
|
|
83
|
625 SlotIndex MBBStart, MBBEnd;
|
|
77
|
626 std::tie(MBBStart, MBBEnd) = Indexes->getMBBRange(MBB);
|
|
83
|
627 LiveQueryResult LRQ = LR.Query(MBBStart);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
628 if (LRQ.valueIn() != VNI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
629 // This block isn't part of the VNI segment. Prune the search.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
630 I.skipChildren();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
631 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
632 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
633
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
634 // Prune the search if VNI is killed in MBB.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
635 if (LRQ.endPoint() < MBBEnd) {
|
|
83
|
636 LR.removeSegment(MBBStart, LRQ.endPoint());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
637 if (EndPoints) EndPoints->push_back(LRQ.endPoint());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
638 I.skipChildren();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
639 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
640 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
641
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
642 // VNI is live through MBB.
|
|
83
|
643 LR.removeSegment(MBBStart, MBBEnd);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
644 if (EndPoints) EndPoints->push_back(MBBEnd);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
645 ++I;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
646 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
647 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
648 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
649
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
650 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
651 // Register allocator hooks.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
652 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
653
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
654 void LiveIntervals::addKillFlags(const VirtRegMap *VRM) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
655 // Keep track of regunit ranges.
|
|
83
|
656 SmallVector<std::pair<const LiveRange*, LiveRange::const_iterator>, 8> RU;
|
|
|
657 // Keep track of subregister ranges.
|
|
|
658 SmallVector<std::pair<const LiveInterval::SubRange*,
|
|
|
659 LiveRange::const_iterator>, 4> SRs;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
660
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
661 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
662 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
663 if (MRI->reg_nodbg_empty(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
664 continue;
|
|
83
|
665 const LiveInterval &LI = getInterval(Reg);
|
|
|
666 if (LI.empty())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
667 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
668
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
669 // Find the regunit intervals for the assigned register. They may overlap
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
670 // the virtual register live range, cancelling any kills.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
671 RU.clear();
|
|
121
|
672 for (MCRegUnitIterator Unit(VRM->getPhys(Reg), TRI); Unit.isValid();
|
|
|
673 ++Unit) {
|
|
|
674 const LiveRange &RURange = getRegUnit(*Unit);
|
|
83
|
675 if (RURange.empty())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
676 continue;
|
|
83
|
677 RU.push_back(std::make_pair(&RURange, RURange.find(LI.begin()->end)));
|
|
|
678 }
|
|
|
679
|
|
95
|
680 if (MRI->subRegLivenessEnabled()) {
|
|
83
|
681 SRs.clear();
|
|
|
682 for (const LiveInterval::SubRange &SR : LI.subranges()) {
|
|
|
683 SRs.push_back(std::make_pair(&SR, SR.find(LI.begin()->end)));
|
|
|
684 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
685 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
686
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
687 // Every instruction that kills Reg corresponds to a segment range end
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
688 // point.
|
|
83
|
689 for (LiveInterval::const_iterator RI = LI.begin(), RE = LI.end(); RI != RE;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
690 ++RI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
691 // A block index indicates an MBB edge.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
692 if (RI->end.isBlock())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
693 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
694 MachineInstr *MI = getInstructionFromIndex(RI->end);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
695 if (!MI)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
696 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
697
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
698 // Check if any of the regunits are live beyond the end of RI. That could
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
699 // happen when a physreg is defined as a copy of a virtreg:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
700 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
701 // %EAX = COPY %vreg5
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
702 // FOO %vreg5 <--- MI, cancel kill because %EAX is live.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
703 // BAR %EAX<kill>
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
704 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
705 // There should be no kill flag on FOO when %vreg5 is rewritten as %EAX.
|
|
83
|
706 for (auto &RUP : RU) {
|
|
|
707 const LiveRange &RURange = *RUP.first;
|
|
|
708 LiveRange::const_iterator &I = RUP.second;
|
|
|
709 if (I == RURange.end())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
710 continue;
|
|
83
|
711 I = RURange.advanceTo(I, RI->end);
|
|
|
712 if (I == RURange.end() || I->start >= RI->end)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
713 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
714 // I is overlapping RI.
|
|
83
|
715 goto CancelKill;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
716 }
|
|
83
|
717
|
|
95
|
718 if (MRI->subRegLivenessEnabled()) {
|
|
83
|
719 // When reading a partial undefined value we must not add a kill flag.
|
|
|
720 // The regalloc might have used the undef lane for something else.
|
|
|
721 // Example:
|
|
|
722 // %vreg1 = ... ; R32: %vreg1
|
|
|
723 // %vreg2:high16 = ... ; R64: %vreg2
|
|
|
724 // = read %vreg2<kill> ; R64: %vreg2
|
|
|
725 // = read %vreg1 ; R32: %vreg1
|
|
|
726 // The <kill> flag is correct for %vreg2, but the register allocator may
|
|
|
727 // assign R0L to %vreg1, and R0 to %vreg2 because the low 32bits of R0
|
|
|
728 // are actually never written by %vreg2. After assignment the <kill>
|
|
|
729 // flag at the read instruction is invalid.
|
|
95
|
730 LaneBitmask DefinedLanesMask;
|
|
83
|
731 if (!SRs.empty()) {
|
|
|
732 // Compute a mask of lanes that are defined.
|
|
121
|
733 DefinedLanesMask = LaneBitmask::getNone();
|
|
83
|
734 for (auto &SRP : SRs) {
|
|
|
735 const LiveInterval::SubRange &SR = *SRP.first;
|
|
|
736 LiveRange::const_iterator &I = SRP.second;
|
|
|
737 if (I == SR.end())
|
|
|
738 continue;
|
|
|
739 I = SR.advanceTo(I, RI->end);
|
|
|
740 if (I == SR.end() || I->start >= RI->end)
|
|
|
741 continue;
|
|
|
742 // I is overlapping RI
|
|
|
743 DefinedLanesMask |= SR.LaneMask;
|
|
|
744 }
|
|
|
745 } else
|
|
121
|
746 DefinedLanesMask = LaneBitmask::getAll();
|
|
83
|
747
|
|
|
748 bool IsFullWrite = false;
|
|
|
749 for (const MachineOperand &MO : MI->operands()) {
|
|
|
750 if (!MO.isReg() || MO.getReg() != Reg)
|
|
|
751 continue;
|
|
|
752 if (MO.isUse()) {
|
|
|
753 // Reading any undefined lanes?
|
|
95
|
754 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg());
|
|
121
|
755 if ((UseMask & ~DefinedLanesMask).any())
|
|
83
|
756 goto CancelKill;
|
|
|
757 } else if (MO.getSubReg() == 0) {
|
|
|
758 // Writing to the full register?
|
|
|
759 assert(MO.isDef());
|
|
|
760 IsFullWrite = true;
|
|
|
761 }
|
|
|
762 }
|
|
|
763
|
|
|
764 // If an instruction writes to a subregister, a new segment starts in
|
|
|
765 // the LiveInterval. But as this is only overriding part of the register
|
|
|
766 // adding kill-flags is not correct here after registers have been
|
|
|
767 // assigned.
|
|
|
768 if (!IsFullWrite) {
|
|
|
769 // Next segment has to be adjacent in the subregister write case.
|
|
|
770 LiveRange::const_iterator N = std::next(RI);
|
|
|
771 if (N != LI.end() && N->start == RI->end)
|
|
|
772 goto CancelKill;
|
|
|
773 }
|
|
|
774 }
|
|
|
775
|
|
|
776 MI->addRegisterKilled(Reg, nullptr);
|
|
|
777 continue;
|
|
|
778 CancelKill:
|
|
|
779 MI->clearRegisterKills(Reg, nullptr);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
780 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
781 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
782 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
783
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
784 MachineBasicBlock*
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
785 LiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
786 // A local live range must be fully contained inside the block, meaning it is
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
787 // defined and killed at instructions, not at block boundaries. It is not
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
788 // live in or or out of any block.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
789 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
790 // It is technically possible to have a PHI-defined live range identical to a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
791 // single block, but we are going to return false in that case.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
792
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
793 SlotIndex Start = LI.beginIndex();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
794 if (Start.isBlock())
|
|
77
|
795 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
796
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
797 SlotIndex Stop = LI.endIndex();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
798 if (Stop.isBlock())
|
|
77
|
799 return nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
800
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
801 // getMBBFromIndex doesn't need to search the MBB table when both indexes
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
802 // belong to proper instructions.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
803 MachineBasicBlock *MBB1 = Indexes->getMBBFromIndex(Start);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
804 MachineBasicBlock *MBB2 = Indexes->getMBBFromIndex(Stop);
|
|
77
|
805 return MBB1 == MBB2 ? MBB1 : nullptr;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
806 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
807
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
808 bool
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
809 LiveIntervals::hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const {
|
|
83
|
810 for (const VNInfo *PHI : LI.valnos) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
811 if (PHI->isUnused() || !PHI->isPHIDef())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
812 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
813 const MachineBasicBlock *PHIMBB = getMBBFromIndex(PHI->def);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
814 // Conservatively return true instead of scanning huge predecessor lists.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
815 if (PHIMBB->pred_size() > 100)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
816 return true;
|
|
121
|
817 for (const MachineBasicBlock *Pred : PHIMBB->predecessors())
|
|
|
818 if (VNI == LI.getVNInfoBefore(Indexes->getMBBEndIdx(Pred)))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
819 return true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
820 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
821 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
822 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
823
|
|
120
|
824 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
|
|
|
825 const MachineBlockFrequencyInfo *MBFI,
|
|
|
826 const MachineInstr &MI) {
|
|
121
|
827 return getSpillWeight(isDef, isUse, MBFI, MI.getParent());
|
|
|
828 }
|
|
|
829
|
|
|
830 float LiveIntervals::getSpillWeight(bool isDef, bool isUse,
|
|
|
831 const MachineBlockFrequencyInfo *MBFI,
|
|
|
832 const MachineBasicBlock *MBB) {
|
|
|
833 BlockFrequency Freq = MBFI->getBlockFreq(MBB);
|
|
77
|
834 const float Scale = 1.0f / MBFI->getEntryFreq();
|
|
|
835 return (isDef + isUse) * (Freq.getFrequency() * Scale);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
836 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
837
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
838 LiveRange::Segment
|
|
120
|
839 LiveIntervals::addSegmentToEndOfBlock(unsigned reg, MachineInstr &startInst) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
840 LiveInterval& Interval = createEmptyInterval(reg);
|
|
120
|
841 VNInfo *VN = Interval.getNextValue(
|
|
|
842 SlotIndex(getInstructionIndex(startInst).getRegSlot()),
|
|
|
843 getVNInfoAllocator());
|
|
|
844 LiveRange::Segment S(SlotIndex(getInstructionIndex(startInst).getRegSlot()),
|
|
|
845 getMBBEndIdx(startInst.getParent()), VN);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
846 Interval.addSegment(S);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
847
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
848 return S;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
849 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
850
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
851 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
852 // Register mask functions
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
853 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
854
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
855 bool LiveIntervals::checkRegMaskInterference(LiveInterval &LI,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
856 BitVector &UsableRegs) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
857 if (LI.empty())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
858 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
859 LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
860
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
861 // Use a smaller arrays for local live ranges.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
862 ArrayRef<SlotIndex> Slots;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
863 ArrayRef<const uint32_t*> Bits;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
864 if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
865 Slots = getRegMaskSlotsInBlock(MBB->getNumber());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
866 Bits = getRegMaskBitsInBlock(MBB->getNumber());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
867 } else {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
868 Slots = getRegMaskSlots();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
869 Bits = getRegMaskBits();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
870 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
871
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
872 // We are going to enumerate all the register mask slots contained in LI.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
873 // Start with a binary search of RegMaskSlots to find a starting point.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
874 ArrayRef<SlotIndex>::iterator SlotI =
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
875 std::lower_bound(Slots.begin(), Slots.end(), LiveI->start);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
876 ArrayRef<SlotIndex>::iterator SlotE = Slots.end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
877
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
878 // No slots in range, LI begins after the last call.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
879 if (SlotI == SlotE)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
880 return false;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
881
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
882 bool Found = false;
|
|
121
|
883 while (true) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
884 assert(*SlotI >= LiveI->start);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
885 // Loop over all slots overlapping this segment.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
886 while (*SlotI < LiveI->end) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
887 // *SlotI overlaps LI. Collect mask bits.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
888 if (!Found) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
889 // This is the first overlap. Initialize UsableRegs to all ones.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
890 UsableRegs.clear();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
891 UsableRegs.resize(TRI->getNumRegs(), true);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
892 Found = true;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
893 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
894 // Remove usable registers clobbered by this mask.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
895 UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
896 if (++SlotI == SlotE)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
897 return Found;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
898 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
899 // *SlotI is beyond the current LI segment.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
900 LiveI = LI.advanceTo(LiveI, *SlotI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
901 if (LiveI == LiveE)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
902 return Found;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
903 // Advance SlotI until it overlaps.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
904 while (*SlotI < LiveI->start)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
905 if (++SlotI == SlotE)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
906 return Found;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
907 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
908 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
909
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
910 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
911 // IntervalUpdate class.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
912 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
913
|
|
121
|
914 /// Toolkit used by handleMove to trim or extend live intervals.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
915 class LiveIntervals::HMEditor {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
916 private:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
917 LiveIntervals& LIS;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
918 const MachineRegisterInfo& MRI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
919 const TargetRegisterInfo& TRI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
920 SlotIndex OldIdx;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
921 SlotIndex NewIdx;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
922 SmallPtrSet<LiveRange*, 8> Updated;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
923 bool UpdateFlags;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
924
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
925 public:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
926 HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
927 const TargetRegisterInfo& TRI,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
928 SlotIndex OldIdx, SlotIndex NewIdx, bool UpdateFlags)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
929 : LIS(LIS), MRI(MRI), TRI(TRI), OldIdx(OldIdx), NewIdx(NewIdx),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
930 UpdateFlags(UpdateFlags) {}
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
931
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
932 // FIXME: UpdateFlags is a workaround that creates live intervals for all
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
933 // physregs, even those that aren't needed for regalloc, in order to update
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
934 // kill flags. This is wasteful. Eventually, LiveVariables will strip all kill
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
935 // flags, and postRA passes will use a live register utility instead.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
936 LiveRange *getRegUnitLI(unsigned Unit) {
|
|
121
|
937 if (UpdateFlags && !MRI.isReservedRegUnit(Unit))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
938 return &LIS.getRegUnit(Unit);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
939 return LIS.getCachedRegUnit(Unit);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
940 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
941
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
942 /// Update all live ranges touched by MI, assuming a move from OldIdx to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
943 /// NewIdx.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
944 void updateAllRanges(MachineInstr *MI) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
945 DEBUG(dbgs() << "handleMove " << OldIdx << " -> " << NewIdx << ": " << *MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
946 bool hasRegMask = false;
|
|
95
|
947 for (MachineOperand &MO : MI->operands()) {
|
|
|
948 if (MO.isRegMask())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
949 hasRegMask = true;
|
|
95
|
950 if (!MO.isReg())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
951 continue;
|
|
120
|
952 if (MO.isUse()) {
|
|
|
953 if (!MO.readsReg())
|
|
|
954 continue;
|
|
|
955 // Aggressively clear all kill flags.
|
|
|
956 // They are reinserted by VirtRegRewriter.
|
|
95
|
957 MO.setIsKill(false);
|
|
120
|
958 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
959
|
|
95
|
960 unsigned Reg = MO.getReg();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
961 if (!Reg)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
962 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
963 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
964 LiveInterval &LI = LIS.getInterval(Reg);
|
|
83
|
965 if (LI.hasSubRanges()) {
|
|
95
|
966 unsigned SubReg = MO.getSubReg();
|
|
120
|
967 LaneBitmask LaneMask = SubReg ? TRI.getSubRegIndexLaneMask(SubReg)
|
|
|
968 : MRI.getMaxLaneMaskForVReg(Reg);
|
|
83
|
969 for (LiveInterval::SubRange &S : LI.subranges()) {
|
|
121
|
970 if ((S.LaneMask & LaneMask).none())
|
|
83
|
971 continue;
|
|
|
972 updateRange(S, Reg, S.LaneMask);
|
|
|
973 }
|
|
|
974 }
|
|
121
|
975 updateRange(LI, Reg, LaneBitmask::getNone());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
976 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
977 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
978
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
979 // For physregs, only update the regunits that actually have a
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
980 // precomputed live range.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
981 for (MCRegUnitIterator Units(Reg, &TRI); Units.isValid(); ++Units)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
982 if (LiveRange *LR = getRegUnitLI(*Units))
|
|
121
|
983 updateRange(*LR, *Units, LaneBitmask::getNone());
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
984 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
985 if (hasRegMask)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
986 updateRegMaskSlots();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
987 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
988
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
989 private:
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
990 /// Update a single live range, assuming an instruction has been moved from
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
991 /// OldIdx to NewIdx.
|
|
95
|
992 void updateRange(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
|
|
83
|
993 if (!Updated.insert(&LR).second)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
994 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
995 DEBUG({
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
996 dbgs() << " ";
|
|
83
|
997 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
998 dbgs() << PrintReg(Reg);
|
|
121
|
999 if (LaneMask.any())
|
|
95
|
1000 dbgs() << " L" << PrintLaneMask(LaneMask);
|
|
83
|
1001 } else {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1002 dbgs() << PrintRegUnit(Reg, &TRI);
|
|
83
|
1003 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1004 dbgs() << ":\t" << LR << '\n';
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1005 });
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1006 if (SlotIndex::isEarlierInstr(OldIdx, NewIdx))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1007 handleMoveDown(LR);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1008 else
|
|
83
|
1009 handleMoveUp(LR, Reg, LaneMask);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1010 DEBUG(dbgs() << " -->\t" << LR << '\n');
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1011 LR.verify();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1012 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1013
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1014 /// Update LR to reflect an instruction has been moved downwards from OldIdx
|
|
100
|
1015 /// to NewIdx (OldIdx < NewIdx).
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1016 void handleMoveDown(LiveRange &LR) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1017 LiveRange::iterator E = LR.end();
|
|
100
|
1018 // Segment going into OldIdx.
|
|
|
1019 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
|
|
|
1020
|
|
|
1021 // No value live before or after OldIdx? Nothing to do.
|
|
|
1022 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1023 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1024
|
|
100
|
1025 LiveRange::iterator OldIdxOut;
|
|
|
1026 // Do we have a value live-in to OldIdx?
|
|
|
1027 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1028 // If the live-in value already extends to NewIdx, there is nothing to do.
|
|
100
|
1029 if (SlotIndex::isEarlierEqualInstr(NewIdx, OldIdxIn->end))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1030 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1031 // Aggressively remove all kill flags from the old kill point.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1032 // Kill flags shouldn't be used while live intervals exist, they will be
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1033 // reinserted by VirtRegRewriter.
|
|
100
|
1034 if (MachineInstr *KillMI = LIS.getInstructionFromIndex(OldIdxIn->end))
|
|
120
|
1035 for (MIBundleOperands MO(*KillMI); MO.isValid(); ++MO)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1036 if (MO->isReg() && MO->isUse())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1037 MO->setIsKill(false);
|
|
120
|
1038
|
|
|
1039 // Is there a def before NewIdx which is not OldIdx?
|
|
|
1040 LiveRange::iterator Next = std::next(OldIdxIn);
|
|
|
1041 if (Next != E && !SlotIndex::isSameInstr(OldIdx, Next->start) &&
|
|
|
1042 SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
|
|
|
1043 // If we are here then OldIdx was just a use but not a def. We only have
|
|
|
1044 // to ensure liveness extends to NewIdx.
|
|
|
1045 LiveRange::iterator NewIdxIn =
|
|
|
1046 LR.advanceTo(Next, NewIdx.getBaseIndex());
|
|
|
1047 // Extend the segment before NewIdx if necessary.
|
|
|
1048 if (NewIdxIn == E ||
|
|
|
1049 !SlotIndex::isEarlierInstr(NewIdxIn->start, NewIdx)) {
|
|
|
1050 LiveRange::iterator Prev = std::prev(NewIdxIn);
|
|
|
1051 Prev->end = NewIdx.getRegSlot();
|
|
|
1052 }
|
|
|
1053 // Extend OldIdxIn.
|
|
|
1054 OldIdxIn->end = Next->start;
|
|
|
1055 return;
|
|
|
1056 }
|
|
|
1057
|
|
100
|
1058 // Adjust OldIdxIn->end to reach NewIdx. This may temporarily make LR
|
|
|
1059 // invalid by overlapping ranges.
|
|
|
1060 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
|
|
|
1061 OldIdxIn->end = NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber());
|
|
|
1062 // If this was not a kill, then there was no def and we're done.
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1063 if (!isKill)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1064 return;
|
|
100
|
1065
|
|
|
1066 // Did we have a Def at OldIdx?
|
|
120
|
1067 OldIdxOut = Next;
|
|
100
|
1068 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
|
|
|
1069 return;
|
|
|
1070 } else {
|
|
|
1071 OldIdxOut = OldIdxIn;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1072 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1073
|
|
100
|
1074 // If we are here then there is a Definition at OldIdx. OldIdxOut points
|
|
|
1075 // to the segment starting there.
|
|
|
1076 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
|
|
|
1077 "No def?");
|
|
|
1078 VNInfo *OldIdxVNI = OldIdxOut->valno;
|
|
|
1079 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
|
|
|
1080
|
|
|
1081 // If the defined value extends beyond NewIdx, just move the beginning
|
|
|
1082 // of the segment to NewIdx.
|
|
|
1083 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
|
|
|
1084 if (SlotIndex::isEarlierInstr(NewIdxDef, OldIdxOut->end)) {
|
|
|
1085 OldIdxVNI->def = NewIdxDef;
|
|
|
1086 OldIdxOut->start = OldIdxVNI->def;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1087 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1088 }
|
|
100
|
1089
|
|
|
1090 // If we are here then we have a Definition at OldIdx which ends before
|
|
120
|
1091 // NewIdx.
|
|
|
1092
|
|
100
|
1093 // Is there an existing Def at NewIdx?
|
|
|
1094 LiveRange::iterator AfterNewIdx
|
|
|
1095 = LR.advanceTo(OldIdxOut, NewIdx.getRegSlot());
|
|
120
|
1096 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
|
|
|
1097 if (!OldIdxDefIsDead &&
|
|
|
1098 SlotIndex::isEarlierInstr(OldIdxOut->end, NewIdxDef)) {
|
|
|
1099 // OldIdx is not a dead def, and NewIdxDef is inside a new interval.
|
|
|
1100 VNInfo *DefVNI;
|
|
|
1101 if (OldIdxOut != LR.begin() &&
|
|
|
1102 !SlotIndex::isEarlierInstr(std::prev(OldIdxOut)->end,
|
|
|
1103 OldIdxOut->start)) {
|
|
|
1104 // There is no gap between OldIdxOut and its predecessor anymore,
|
|
|
1105 // merge them.
|
|
|
1106 LiveRange::iterator IPrev = std::prev(OldIdxOut);
|
|
|
1107 DefVNI = OldIdxVNI;
|
|
|
1108 IPrev->end = OldIdxOut->end;
|
|
|
1109 } else {
|
|
|
1110 // The value is live in to OldIdx
|
|
|
1111 LiveRange::iterator INext = std::next(OldIdxOut);
|
|
|
1112 assert(INext != E && "Must have following segment");
|
|
|
1113 // We merge OldIdxOut and its successor. As we're dealing with subreg
|
|
|
1114 // reordering, there is always a successor to OldIdxOut in the same BB
|
|
|
1115 // We don't need INext->valno anymore and will reuse for the new segment
|
|
|
1116 // we create later.
|
|
|
1117 DefVNI = OldIdxVNI;
|
|
|
1118 INext->start = OldIdxOut->end;
|
|
|
1119 INext->valno->def = INext->start;
|
|
|
1120 }
|
|
|
1121 // If NewIdx is behind the last segment, extend that and append a new one.
|
|
|
1122 if (AfterNewIdx == E) {
|
|
|
1123 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
|
|
|
1124 // one position.
|
|
|
1125 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn -| end
|
|
|
1126 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS -| end
|
|
|
1127 std::copy(std::next(OldIdxOut), E, OldIdxOut);
|
|
|
1128 // The last segment is undefined now, reuse it for a dead def.
|
|
|
1129 LiveRange::iterator NewSegment = std::prev(E);
|
|
|
1130 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
|
|
|
1131 DefVNI);
|
|
|
1132 DefVNI->def = NewIdxDef;
|
|
|
1133
|
|
|
1134 LiveRange::iterator Prev = std::prev(NewSegment);
|
|
|
1135 Prev->end = NewIdxDef;
|
|
|
1136 } else {
|
|
|
1137 // OldIdxOut is undef at this point, Slide (OldIdxOut;AfterNewIdx] up
|
|
|
1138 // one position.
|
|
|
1139 // |- ?/OldIdxOut -| |- X0 -| ... |- Xn/AfterNewIdx -| |- Next -|
|
|
|
1140 // => |- X0/OldIdxOut -| ... |- Xn -| |- Xn/AfterNewIdx -| |- Next -|
|
|
|
1141 std::copy(std::next(OldIdxOut), std::next(AfterNewIdx), OldIdxOut);
|
|
|
1142 LiveRange::iterator Prev = std::prev(AfterNewIdx);
|
|
|
1143 // We have two cases:
|
|
|
1144 if (SlotIndex::isEarlierInstr(Prev->start, NewIdxDef)) {
|
|
|
1145 // Case 1: NewIdx is inside a liverange. Split this liverange at
|
|
|
1146 // NewIdxDef into the segment "Prev" followed by "NewSegment".
|
|
|
1147 LiveRange::iterator NewSegment = AfterNewIdx;
|
|
|
1148 *NewSegment = LiveRange::Segment(NewIdxDef, Prev->end, Prev->valno);
|
|
|
1149 Prev->valno->def = NewIdxDef;
|
|
|
1150
|
|
|
1151 *Prev = LiveRange::Segment(Prev->start, NewIdxDef, DefVNI);
|
|
|
1152 DefVNI->def = Prev->start;
|
|
|
1153 } else {
|
|
|
1154 // Case 2: NewIdx is in a lifetime hole. Keep AfterNewIdx as is and
|
|
|
1155 // turn Prev into a segment from NewIdx to AfterNewIdx->start.
|
|
|
1156 *Prev = LiveRange::Segment(NewIdxDef, AfterNewIdx->start, DefVNI);
|
|
|
1157 DefVNI->def = NewIdxDef;
|
|
|
1158 assert(DefVNI != AfterNewIdx->valno);
|
|
|
1159 }
|
|
|
1160 }
|
|
|
1161 return;
|
|
|
1162 }
|
|
|
1163
|
|
100
|
1164 if (AfterNewIdx != E &&
|
|
|
1165 SlotIndex::isSameInstr(AfterNewIdx->start, NewIdxDef)) {
|
|
|
1166 // There is an existing def at NewIdx. The def at OldIdx is coalesced into
|
|
|
1167 // that value.
|
|
|
1168 assert(AfterNewIdx->valno != OldIdxVNI && "Multiple defs of value?");
|
|
|
1169 LR.removeValNo(OldIdxVNI);
|
|
|
1170 } else {
|
|
|
1171 // There was no existing def at NewIdx. We need to create a dead def
|
|
|
1172 // at NewIdx. Shift segments over the old OldIdxOut segment, this frees
|
|
|
1173 // a new segment at the place where we want to construct the dead def.
|
|
|
1174 // |- OldIdxOut -| |- X0 -| ... |- Xn -| |- AfterNewIdx -|
|
|
|
1175 // => |- X0/OldIdxOut -| ... |- Xn -| |- undef/NewS. -| |- AfterNewIdx -|
|
|
|
1176 assert(AfterNewIdx != OldIdxOut && "Inconsistent iterators");
|
|
|
1177 std::copy(std::next(OldIdxOut), AfterNewIdx, OldIdxOut);
|
|
|
1178 // We can reuse OldIdxVNI now.
|
|
|
1179 LiveRange::iterator NewSegment = std::prev(AfterNewIdx);
|
|
|
1180 VNInfo *NewSegmentVNI = OldIdxVNI;
|
|
|
1181 NewSegmentVNI->def = NewIdxDef;
|
|
|
1182 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
|
|
|
1183 NewSegmentVNI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1184 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1185 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1186
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1187 /// Update LR to reflect an instruction has been moved upwards from OldIdx
|
|
100
|
1188 /// to NewIdx (NewIdx < OldIdx).
|
|
95
|
1189 void handleMoveUp(LiveRange &LR, unsigned Reg, LaneBitmask LaneMask) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1190 LiveRange::iterator E = LR.end();
|
|
100
|
1191 // Segment going into OldIdx.
|
|
|
1192 LiveRange::iterator OldIdxIn = LR.find(OldIdx.getBaseIndex());
|
|
|
1193
|
|
|
1194 // No value live before or after OldIdx? Nothing to do.
|
|
|
1195 if (OldIdxIn == E || SlotIndex::isEarlierInstr(OldIdx, OldIdxIn->start))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1196 return;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1197
|
|
100
|
1198 LiveRange::iterator OldIdxOut;
|
|
|
1199 // Do we have a value live-in to OldIdx?
|
|
|
1200 if (SlotIndex::isEarlierInstr(OldIdxIn->start, OldIdx)) {
|
|
|
1201 // If the live-in value isn't killed here, then we have no Def at
|
|
|
1202 // OldIdx, moreover the value must be live at NewIdx so there is nothing
|
|
|
1203 // to do.
|
|
|
1204 bool isKill = SlotIndex::isSameInstr(OldIdx, OldIdxIn->end);
|
|
|
1205 if (!isKill)
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1206 return;
|
|
100
|
1207
|
|
|
1208 // At this point we have to move OldIdxIn->end back to the nearest
|
|
120
|
1209 // previous use or (dead-)def but no further than NewIdx.
|
|
|
1210 SlotIndex DefBeforeOldIdx
|
|
|
1211 = std::max(OldIdxIn->start.getDeadSlot(),
|
|
|
1212 NewIdx.getRegSlot(OldIdxIn->end.isEarlyClobber()));
|
|
|
1213 OldIdxIn->end = findLastUseBefore(DefBeforeOldIdx, Reg, LaneMask);
|
|
100
|
1214
|
|
120
|
1215 // Did we have a Def at OldIdx? If not we are done now.
|
|
100
|
1216 OldIdxOut = std::next(OldIdxIn);
|
|
120
|
1217 if (OldIdxOut == E || !SlotIndex::isSameInstr(OldIdx, OldIdxOut->start))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1218 return;
|
|
100
|
1219 } else {
|
|
|
1220 OldIdxOut = OldIdxIn;
|
|
120
|
1221 OldIdxIn = OldIdxOut != LR.begin() ? std::prev(OldIdxOut) : E;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1222 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1223
|
|
100
|
1224 // If we are here then there is a Definition at OldIdx. OldIdxOut points
|
|
|
1225 // to the segment starting there.
|
|
|
1226 assert(OldIdxOut != E && SlotIndex::isSameInstr(OldIdx, OldIdxOut->start) &&
|
|
|
1227 "No def?");
|
|
|
1228 VNInfo *OldIdxVNI = OldIdxOut->valno;
|
|
|
1229 assert(OldIdxVNI->def == OldIdxOut->start && "Inconsistent def");
|
|
|
1230 bool OldIdxDefIsDead = OldIdxOut->end.isDead();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1231
|
|
100
|
1232 // Is there an existing def at NewIdx?
|
|
|
1233 SlotIndex NewIdxDef = NewIdx.getRegSlot(OldIdxOut->start.isEarlyClobber());
|
|
|
1234 LiveRange::iterator NewIdxOut = LR.find(NewIdx.getRegSlot());
|
|
|
1235 if (SlotIndex::isSameInstr(NewIdxOut->start, NewIdx)) {
|
|
|
1236 assert(NewIdxOut->valno != OldIdxVNI &&
|
|
|
1237 "Same value defined more than once?");
|
|
|
1238 // If OldIdx was a dead def remove it.
|
|
|
1239 if (!OldIdxDefIsDead) {
|
|
|
1240 // Remove segment starting at NewIdx and move begin of OldIdxOut to
|
|
|
1241 // NewIdx so it can take its place.
|
|
|
1242 OldIdxVNI->def = NewIdxDef;
|
|
|
1243 OldIdxOut->start = NewIdxDef;
|
|
|
1244 LR.removeValNo(NewIdxOut->valno);
|
|
|
1245 } else {
|
|
|
1246 // Simply remove the dead def at OldIdx.
|
|
|
1247 LR.removeValNo(OldIdxVNI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1248 }
|
|
100
|
1249 } else {
|
|
|
1250 // Previously nothing was live after NewIdx, so all we have to do now is
|
|
|
1251 // move the begin of OldIdxOut to NewIdx.
|
|
|
1252 if (!OldIdxDefIsDead) {
|
|
120
|
1253 // Do we have any intermediate Defs between OldIdx and NewIdx?
|
|
|
1254 if (OldIdxIn != E &&
|
|
|
1255 SlotIndex::isEarlierInstr(NewIdxDef, OldIdxIn->start)) {
|
|
|
1256 // OldIdx is not a dead def and NewIdx is before predecessor start.
|
|
|
1257 LiveRange::iterator NewIdxIn = NewIdxOut;
|
|
|
1258 assert(NewIdxIn == LR.find(NewIdx.getBaseIndex()));
|
|
|
1259 const SlotIndex SplitPos = NewIdxDef;
|
|
121
|
1260 OldIdxVNI = OldIdxIn->valno;
|
|
120
|
1261
|
|
|
1262 // Merge the OldIdxIn and OldIdxOut segments into OldIdxOut.
|
|
121
|
1263 OldIdxOut->valno->def = OldIdxIn->start;
|
|
120
|
1264 *OldIdxOut = LiveRange::Segment(OldIdxIn->start, OldIdxOut->end,
|
|
121
|
1265 OldIdxOut->valno);
|
|
120
|
1266 // OldIdxIn and OldIdxVNI are now undef and can be overridden.
|
|
|
1267 // We Slide [NewIdxIn, OldIdxIn) down one position.
|
|
|
1268 // |- X0/NewIdxIn -| ... |- Xn-1 -||- Xn/OldIdxIn -||- OldIdxOut -|
|
|
|
1269 // => |- undef/NexIdxIn -| |- X0 -| ... |- Xn-1 -| |- Xn/OldIdxOut -|
|
|
|
1270 std::copy_backward(NewIdxIn, OldIdxIn, OldIdxOut);
|
|
|
1271 // NewIdxIn is now considered undef so we can reuse it for the moved
|
|
|
1272 // value.
|
|
|
1273 LiveRange::iterator NewSegment = NewIdxIn;
|
|
|
1274 LiveRange::iterator Next = std::next(NewSegment);
|
|
|
1275 if (SlotIndex::isEarlierInstr(Next->start, NewIdx)) {
|
|
|
1276 // There is no gap between NewSegment and its predecessor.
|
|
|
1277 *NewSegment = LiveRange::Segment(Next->start, SplitPos,
|
|
|
1278 Next->valno);
|
|
|
1279 *Next = LiveRange::Segment(SplitPos, Next->end, OldIdxVNI);
|
|
|
1280 Next->valno->def = SplitPos;
|
|
|
1281 } else {
|
|
|
1282 // There is a gap between NewSegment and its predecessor
|
|
|
1283 // Value becomes live in.
|
|
|
1284 *NewSegment = LiveRange::Segment(SplitPos, Next->start, OldIdxVNI);
|
|
|
1285 NewSegment->valno->def = SplitPos;
|
|
|
1286 }
|
|
|
1287 } else {
|
|
|
1288 // Leave the end point of a live def.
|
|
|
1289 OldIdxOut->start = NewIdxDef;
|
|
|
1290 OldIdxVNI->def = NewIdxDef;
|
|
|
1291 if (OldIdxIn != E && SlotIndex::isEarlierInstr(NewIdx, OldIdxIn->end))
|
|
|
1292 OldIdxIn->end = NewIdx.getRegSlot();
|
|
|
1293 }
|
|
100
|
1294 } else {
|
|
|
1295 // OldIdxVNI is a dead def. It may have been moved across other values
|
|
|
1296 // in LR, so move OldIdxOut up to NewIdxOut. Slide [NewIdxOut;OldIdxOut)
|
|
|
1297 // down one position.
|
|
|
1298 // |- X0/NewIdxOut -| ... |- Xn-1 -| |- Xn/OldIdxOut -| |- next - |
|
|
|
1299 // => |- undef/NewIdxOut -| |- X0 -| ... |- Xn-1 -| |- next -|
|
|
|
1300 std::copy_backward(NewIdxOut, OldIdxOut, std::next(OldIdxOut));
|
|
|
1301 // OldIdxVNI can be reused now to build a new dead def segment.
|
|
|
1302 LiveRange::iterator NewSegment = NewIdxOut;
|
|
|
1303 VNInfo *NewSegmentVNI = OldIdxVNI;
|
|
|
1304 *NewSegment = LiveRange::Segment(NewIdxDef, NewIdxDef.getDeadSlot(),
|
|
|
1305 NewSegmentVNI);
|
|
|
1306 NewSegmentVNI->def = NewIdxDef;
|
|
|
1307 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1308 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1309 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1310
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1311 void updateRegMaskSlots() {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1312 SmallVectorImpl<SlotIndex>::iterator RI =
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1313 std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(),
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1314 OldIdx);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1315 assert(RI != LIS.RegMaskSlots.end() && *RI == OldIdx.getRegSlot() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1316 "No RegMask at OldIdx.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1317 *RI = NewIdx.getRegSlot();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1318 assert((RI == LIS.RegMaskSlots.begin() ||
|
|
77
|
1319 SlotIndex::isEarlierInstr(*std::prev(RI), *RI)) &&
|
|
|
1320 "Cannot move regmask instruction above another call");
|
|
|
1321 assert((std::next(RI) == LIS.RegMaskSlots.end() ||
|
|
|
1322 SlotIndex::isEarlierInstr(*RI, *std::next(RI))) &&
|
|
|
1323 "Cannot move regmask instruction below another call");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1324 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1325
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1326 // Return the last use of reg between NewIdx and OldIdx.
|
|
120
|
1327 SlotIndex findLastUseBefore(SlotIndex Before, unsigned Reg,
|
|
|
1328 LaneBitmask LaneMask) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1329 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
|
|
120
|
1330 SlotIndex LastUse = Before;
|
|
83
|
1331 for (MachineOperand &MO : MRI.use_nodbg_operands(Reg)) {
|
|
120
|
1332 if (MO.isUndef())
|
|
|
1333 continue;
|
|
83
|
1334 unsigned SubReg = MO.getSubReg();
|
|
121
|
1335 if (SubReg != 0 && LaneMask.any()
|
|
|
1336 && (TRI.getSubRegIndexLaneMask(SubReg) & LaneMask).none())
|
|
83
|
1337 continue;
|
|
|
1338
|
|
120
|
1339 const MachineInstr &MI = *MO.getParent();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1340 SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1341 if (InstSlot > LastUse && InstSlot < OldIdx)
|
|
120
|
1342 LastUse = InstSlot.getRegSlot();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1343 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1344 return LastUse;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1345 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1346
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1347 // This is a regunit interval, so scanning the use list could be very
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1348 // expensive. Scan upwards from OldIdx instead.
|
|
120
|
1349 assert(Before < OldIdx && "Expected upwards move");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1350 SlotIndexes *Indexes = LIS.getSlotIndexes();
|
|
120
|
1351 MachineBasicBlock *MBB = Indexes->getMBBFromIndex(Before);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1352
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1353 // OldIdx may not correspond to an instruction any longer, so set MII to
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1354 // point to the next instruction after OldIdx, or MBB->end().
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1355 MachineBasicBlock::iterator MII = MBB->end();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1356 if (MachineInstr *MI = Indexes->getInstructionFromIndex(
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1357 Indexes->getNextNonNullIndex(OldIdx)))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1358 if (MI->getParent() == MBB)
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1359 MII = MI;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1360
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1361 MachineBasicBlock::iterator Begin = MBB->begin();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1362 while (MII != Begin) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1363 if ((--MII)->isDebugValue())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1364 continue;
|
|
120
|
1365 SlotIndex Idx = Indexes->getInstructionIndex(*MII);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1366
|
|
120
|
1367 // Stop searching when Before is reached.
|
|
|
1368 if (!SlotIndex::isEarlierInstr(Before, Idx))
|
|
|
1369 return Before;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1370
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1371 // Check if MII uses Reg.
|
|
120
|
1372 for (MIBundleOperands MO(*MII); MO.isValid(); ++MO)
|
|
|
1373 if (MO->isReg() && !MO->isUndef() &&
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1374 TargetRegisterInfo::isPhysicalRegister(MO->getReg()) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1375 TRI.hasRegUnit(MO->getReg(), Reg))
|
|
120
|
1376 return Idx.getRegSlot();
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1377 }
|
|
120
|
1378 // Didn't reach Before. It must be the first instruction in the block.
|
|
|
1379 return Before;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1380 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1381 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1382
|
|
120
|
1383 void LiveIntervals::handleMove(MachineInstr &MI, bool UpdateFlags) {
|
|
|
1384 assert(!MI.isBundled() && "Can't handle bundled instructions yet.");
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1385 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1386 Indexes->removeMachineInstrFromMaps(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1387 SlotIndex NewIndex = Indexes->insertMachineInstrInMaps(MI);
|
|
120
|
1388 assert(getMBBStartIdx(MI.getParent()) <= OldIndex &&
|
|
|
1389 OldIndex < getMBBEndIdx(MI.getParent()) &&
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1390 "Cannot handle moves across basic block boundaries.");
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1391
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1392 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
|
|
120
|
1393 HME.updateAllRanges(&MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1394 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1395
|
|
120
|
1396 void LiveIntervals::handleMoveIntoBundle(MachineInstr &MI,
|
|
|
1397 MachineInstr &BundleStart,
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1398 bool UpdateFlags) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1399 SlotIndex OldIndex = Indexes->getInstructionIndex(MI);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1400 SlotIndex NewIndex = Indexes->getInstructionIndex(BundleStart);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1401 HMEditor HME(*this, *MRI, *TRI, OldIndex, NewIndex, UpdateFlags);
|
|
120
|
1402 HME.updateAllRanges(&MI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1403 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1404
|
|
83
|
1405 void LiveIntervals::repairOldRegInRange(const MachineBasicBlock::iterator Begin,
|
|
|
1406 const MachineBasicBlock::iterator End,
|
|
|
1407 const SlotIndex endIdx,
|
|
|
1408 LiveRange &LR, const unsigned Reg,
|
|
95
|
1409 LaneBitmask LaneMask) {
|
|
83
|
1410 LiveInterval::iterator LII = LR.find(endIdx);
|
|
|
1411 SlotIndex lastUseIdx;
|
|
120
|
1412 if (LII == LR.begin()) {
|
|
|
1413 // This happens when the function is called for a subregister that only
|
|
|
1414 // occurs _after_ the range that is to be repaired.
|
|
|
1415 return;
|
|
|
1416 }
|
|
83
|
1417 if (LII != LR.end() && LII->start < endIdx)
|
|
|
1418 lastUseIdx = LII->end;
|
|
|
1419 else
|
|
|
1420 --LII;
|
|
|
1421
|
|
|
1422 for (MachineBasicBlock::iterator I = End; I != Begin;) {
|
|
|
1423 --I;
|
|
120
|
1424 MachineInstr &MI = *I;
|
|
|
1425 if (MI.isDebugValue())
|
|
83
|
1426 continue;
|
|
|
1427
|
|
|
1428 SlotIndex instrIdx = getInstructionIndex(MI);
|
|
|
1429 bool isStartValid = getInstructionFromIndex(LII->start);
|
|
|
1430 bool isEndValid = getInstructionFromIndex(LII->end);
|
|
|
1431
|
|
|
1432 // FIXME: This doesn't currently handle early-clobber or multiple removed
|
|
|
1433 // defs inside of the region to repair.
|
|
120
|
1434 for (MachineInstr::mop_iterator OI = MI.operands_begin(),
|
|
|
1435 OE = MI.operands_end();
|
|
|
1436 OI != OE; ++OI) {
|
|
83
|
1437 const MachineOperand &MO = *OI;
|
|
|
1438 if (!MO.isReg() || MO.getReg() != Reg)
|
|
|
1439 continue;
|
|
|
1440
|
|
|
1441 unsigned SubReg = MO.getSubReg();
|
|
95
|
1442 LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubReg);
|
|
121
|
1443 if ((Mask & LaneMask).none())
|
|
83
|
1444 continue;
|
|
|
1445
|
|
|
1446 if (MO.isDef()) {
|
|
|
1447 if (!isStartValid) {
|
|
|
1448 if (LII->end.isDead()) {
|
|
|
1449 SlotIndex prevStart;
|
|
|
1450 if (LII != LR.begin())
|
|
|
1451 prevStart = std::prev(LII)->start;
|
|
|
1452
|
|
|
1453 // FIXME: This could be more efficient if there was a
|
|
|
1454 // removeSegment method that returned an iterator.
|
|
|
1455 LR.removeSegment(*LII, true);
|
|
|
1456 if (prevStart.isValid())
|
|
|
1457 LII = LR.find(prevStart);
|
|
|
1458 else
|
|
|
1459 LII = LR.begin();
|
|
|
1460 } else {
|
|
|
1461 LII->start = instrIdx.getRegSlot();
|
|
|
1462 LII->valno->def = instrIdx.getRegSlot();
|
|
|
1463 if (MO.getSubReg() && !MO.isUndef())
|
|
|
1464 lastUseIdx = instrIdx.getRegSlot();
|
|
|
1465 else
|
|
|
1466 lastUseIdx = SlotIndex();
|
|
|
1467 continue;
|
|
|
1468 }
|
|
|
1469 }
|
|
|
1470
|
|
|
1471 if (!lastUseIdx.isValid()) {
|
|
|
1472 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
|
|
|
1473 LiveRange::Segment S(instrIdx.getRegSlot(),
|
|
|
1474 instrIdx.getDeadSlot(), VNI);
|
|
|
1475 LII = LR.addSegment(S);
|
|
|
1476 } else if (LII->start != instrIdx.getRegSlot()) {
|
|
|
1477 VNInfo *VNI = LR.getNextValue(instrIdx.getRegSlot(), VNInfoAllocator);
|
|
|
1478 LiveRange::Segment S(instrIdx.getRegSlot(), lastUseIdx, VNI);
|
|
|
1479 LII = LR.addSegment(S);
|
|
|
1480 }
|
|
|
1481
|
|
|
1482 if (MO.getSubReg() && !MO.isUndef())
|
|
|
1483 lastUseIdx = instrIdx.getRegSlot();
|
|
|
1484 else
|
|
|
1485 lastUseIdx = SlotIndex();
|
|
|
1486 } else if (MO.isUse()) {
|
|
|
1487 // FIXME: This should probably be handled outside of this branch,
|
|
|
1488 // either as part of the def case (for defs inside of the region) or
|
|
|
1489 // after the loop over the region.
|
|
|
1490 if (!isEndValid && !LII->end.isBlock())
|
|
|
1491 LII->end = instrIdx.getRegSlot();
|
|
|
1492 if (!lastUseIdx.isValid())
|
|
|
1493 lastUseIdx = instrIdx.getRegSlot();
|
|
|
1494 }
|
|
|
1495 }
|
|
|
1496 }
|
|
|
1497 }
|
|
|
1498
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1499 void
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1500 LiveIntervals::repairIntervalsInRange(MachineBasicBlock *MBB,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1501 MachineBasicBlock::iterator Begin,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1502 MachineBasicBlock::iterator End,
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1503 ArrayRef<unsigned> OrigRegs) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1504 // Find anchor points, which are at the beginning/end of blocks or at
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1505 // instructions that already have indexes.
|
|
120
|
1506 while (Begin != MBB->begin() && !Indexes->hasIndex(*Begin))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1507 --Begin;
|
|
120
|
1508 while (End != MBB->end() && !Indexes->hasIndex(*End))
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1509 ++End;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1510
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1511 SlotIndex endIdx;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1512 if (End == MBB->end())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1513 endIdx = getMBBEndIdx(MBB).getPrevSlot();
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1514 else
|
|
120
|
1515 endIdx = getInstructionIndex(*End);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1516
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1517 Indexes->repairIndexesInRange(MBB, Begin, End);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1518
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1519 for (MachineBasicBlock::iterator I = End; I != Begin;) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1520 --I;
|
|
120
|
1521 MachineInstr &MI = *I;
|
|
|
1522 if (MI.isDebugValue())
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1523 continue;
|
|
120
|
1524 for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(),
|
|
|
1525 MOE = MI.operands_end();
|
|
|
1526 MOI != MOE; ++MOI) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1527 if (MOI->isReg() &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1528 TargetRegisterInfo::isVirtualRegister(MOI->getReg()) &&
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1529 !hasInterval(MOI->getReg())) {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1530 createAndComputeVirtRegInterval(MOI->getReg());
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1531 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1532 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1533 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1534
|
|
121
|
1535 for (unsigned Reg : OrigRegs) {
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1536 if (!TargetRegisterInfo::isVirtualRegister(Reg))
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1537 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1538
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1539 LiveInterval &LI = getInterval(Reg);
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1540 // FIXME: Should we support undefs that gain defs?
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1541 if (!LI.hasAtLeastOneValue())
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1542 continue;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1543
|
|
121
|
1544 for (LiveInterval::SubRange &S : LI.subranges())
|
|
83
|
1545 repairOldRegInRange(Begin, End, endIdx, S, Reg, S.LaneMask);
|
|
121
|
1546
|
|
83
|
1547 repairOldRegInRange(Begin, End, endIdx, LI, Reg);
|
|
|
1548 }
|
|
|
1549 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1550
|
|
83
|
1551 void LiveIntervals::removePhysRegDefAt(unsigned Reg, SlotIndex Pos) {
|
|
121
|
1552 for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
|
|
|
1553 if (LiveRange *LR = getCachedRegUnit(*Unit))
|
|
83
|
1554 if (VNInfo *VNI = LR->getVNInfoAt(Pos))
|
|
|
1555 LR->removeValNo(VNI);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1556 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1557 }
|
|
83
|
1558
|
|
|
1559 void LiveIntervals::removeVRegDefAt(LiveInterval &LI, SlotIndex Pos) {
|
|
120
|
1560 // LI may not have the main range computed yet, but its subranges may
|
|
|
1561 // be present.
|
|
83
|
1562 VNInfo *VNI = LI.getVNInfoAt(Pos);
|
|
120
|
1563 if (VNI != nullptr) {
|
|
|
1564 assert(VNI->def.getBaseIndex() == Pos.getBaseIndex());
|
|
|
1565 LI.removeValNo(VNI);
|
|
|
1566 }
|
|
83
|
1567
|
|
120
|
1568 // Also remove the value defined in subranges.
|
|
83
|
1569 for (LiveInterval::SubRange &S : LI.subranges()) {
|
|
|
1570 if (VNInfo *SVNI = S.getVNInfoAt(Pos))
|
|
120
|
1571 if (SVNI->def.getBaseIndex() == Pos.getBaseIndex())
|
|
|
1572 S.removeValNo(SVNI);
|
|
83
|
1573 }
|
|
|
1574 LI.removeEmptySubRanges();
|
|
|
1575 }
|
|
95
|
1576
|
|
|
1577 void LiveIntervals::splitSeparateComponents(LiveInterval &LI,
|
|
|
1578 SmallVectorImpl<LiveInterval*> &SplitLIs) {
|
|
|
1579 ConnectedVNInfoEqClasses ConEQ(*this);
|
|
100
|
1580 unsigned NumComp = ConEQ.Classify(LI);
|
|
95
|
1581 if (NumComp <= 1)
|
|
|
1582 return;
|
|
|
1583 DEBUG(dbgs() << " Split " << NumComp << " components: " << LI << '\n');
|
|
|
1584 unsigned Reg = LI.reg;
|
|
|
1585 const TargetRegisterClass *RegClass = MRI->getRegClass(Reg);
|
|
|
1586 for (unsigned I = 1; I < NumComp; ++I) {
|
|
|
1587 unsigned NewVReg = MRI->createVirtualRegister(RegClass);
|
|
|
1588 LiveInterval &NewLI = createEmptyInterval(NewVReg);
|
|
|
1589 SplitLIs.push_back(&NewLI);
|
|
|
1590 }
|
|
|
1591 ConEQ.Distribute(LI, SplitLIs.data(), *MRI);
|
|
|
1592 }
|
|
100
|
1593
|
|
120
|
1594 void LiveIntervals::constructMainRangeFromSubranges(LiveInterval &LI) {
|
|
|
1595 assert(LRCalc && "LRCalc not initialized.");
|
|
|
1596 LRCalc->reset(MF, getSlotIndexes(), DomTree, &getVNInfoAllocator());
|
|
|
1597 LRCalc->constructMainRangeFromSubranges(LI);
|
|
100
|
1598 }
|
