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