/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/WebAssembly/WebAssemblyRegColoring.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | //===-- WebAssemblyRegColoring.cpp - Register coloring --------------------===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | /// |
9 | | /// \file |
10 | | /// This file implements a virtual register coloring pass. |
11 | | /// |
12 | | /// WebAssembly doesn't have a fixed number of registers, but it is still |
13 | | /// desirable to minimize the total number of registers used in each function. |
14 | | /// |
15 | | /// This code is modeled after lib/CodeGen/StackSlotColoring.cpp. |
16 | | /// |
17 | | //===----------------------------------------------------------------------===// |
18 | | |
19 | | #include "WebAssembly.h" |
20 | | #include "WebAssemblyMachineFunctionInfo.h" |
21 | | #include "llvm/CodeGen/LiveIntervals.h" |
22 | | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
23 | | #include "llvm/CodeGen/MachineRegisterInfo.h" |
24 | | #include "llvm/CodeGen/Passes.h" |
25 | | #include "llvm/Support/Debug.h" |
26 | | #include "llvm/Support/raw_ostream.h" |
27 | | using namespace llvm; |
28 | | |
29 | | #define DEBUG_TYPE "wasm-reg-coloring" |
30 | | |
31 | | namespace { |
32 | | class WebAssemblyRegColoring final : public MachineFunctionPass { |
33 | | public: |
34 | | static char ID; // Pass identification, replacement for typeid |
35 | 413 | WebAssemblyRegColoring() : MachineFunctionPass(ID) {} |
36 | | |
37 | 4.72k | StringRef getPassName() const override { |
38 | 4.72k | return "WebAssembly Register Coloring"; |
39 | 4.72k | } |
40 | | |
41 | 413 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
42 | 413 | AU.setPreservesCFG(); |
43 | 413 | AU.addRequired<LiveIntervals>(); |
44 | 413 | AU.addRequired<MachineBlockFrequencyInfo>(); |
45 | 413 | AU.addPreserved<MachineBlockFrequencyInfo>(); |
46 | 413 | AU.addPreservedID(MachineDominatorsID); |
47 | 413 | MachineFunctionPass::getAnalysisUsage(AU); |
48 | 413 | } |
49 | | |
50 | | bool runOnMachineFunction(MachineFunction &MF) override; |
51 | | |
52 | | private: |
53 | | }; |
54 | | } // end anonymous namespace |
55 | | |
56 | | char WebAssemblyRegColoring::ID = 0; |
57 | | INITIALIZE_PASS(WebAssemblyRegColoring, DEBUG_TYPE, |
58 | | "Minimize number of registers used", false, false) |
59 | | |
60 | 413 | FunctionPass *llvm::createWebAssemblyRegColoring() { |
61 | 413 | return new WebAssemblyRegColoring(); |
62 | 413 | } |
63 | | |
64 | | // Compute the total spill weight for VReg. |
65 | | static float computeWeight(const MachineRegisterInfo *MRI, |
66 | | const MachineBlockFrequencyInfo *MBFI, |
67 | 11.8k | unsigned VReg) { |
68 | 11.8k | float Weight = 0.0f; |
69 | 11.8k | for (MachineOperand &MO : MRI->reg_nodbg_operands(VReg)) |
70 | 29.9k | Weight += LiveIntervals::getSpillWeight(MO.isDef(), MO.isUse(), MBFI, |
71 | 29.9k | *MO.getParent()); |
72 | 11.8k | return Weight; |
73 | 11.8k | } |
74 | | |
75 | 4.31k | bool WebAssemblyRegColoring::runOnMachineFunction(MachineFunction &MF) { |
76 | 4.31k | LLVM_DEBUG({ |
77 | 4.31k | dbgs() << "********** Register Coloring **********\n" |
78 | 4.31k | << "********** Function: " << MF.getName() << '\n'; |
79 | 4.31k | }); |
80 | 4.31k | |
81 | 4.31k | // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual |
82 | 4.31k | // registers could be modified before the longjmp is executed, resulting in |
83 | 4.31k | // the wrong value being used afterwards. (See <rdar://problem/8007500>.) |
84 | 4.31k | // TODO: Does WebAssembly need to care about setjmp for register coloring? |
85 | 4.31k | if (MF.exposesReturnsTwice()) |
86 | 2 | return false; |
87 | 4.31k | |
88 | 4.31k | MachineRegisterInfo *MRI = &MF.getRegInfo(); |
89 | 4.31k | LiveIntervals *Liveness = &getAnalysis<LiveIntervals>(); |
90 | 4.31k | const MachineBlockFrequencyInfo *MBFI = |
91 | 4.31k | &getAnalysis<MachineBlockFrequencyInfo>(); |
92 | 4.31k | WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
93 | 4.31k | |
94 | 4.31k | // Gather all register intervals into a list and sort them. |
95 | 4.31k | unsigned NumVRegs = MRI->getNumVirtRegs(); |
96 | 4.31k | SmallVector<LiveInterval *, 0> SortedIntervals; |
97 | 4.31k | SortedIntervals.reserve(NumVRegs); |
98 | 4.31k | |
99 | 4.31k | LLVM_DEBUG(dbgs() << "Interesting register intervals:\n"); |
100 | 67.2k | for (unsigned I = 0; I < NumVRegs; ++I62.9k ) { |
101 | 62.9k | unsigned VReg = TargetRegisterInfo::index2VirtReg(I); |
102 | 62.9k | if (MFI.isVRegStackified(VReg)) |
103 | 27.1k | continue; |
104 | 35.8k | // Skip unused registers, which can use $drop. |
105 | 35.8k | if (MRI->use_empty(VReg)) |
106 | 24.0k | continue; |
107 | 11.8k | |
108 | 11.8k | LiveInterval *LI = &Liveness->getInterval(VReg); |
109 | 11.8k | assert(LI->weight == 0.0f); |
110 | 11.8k | LI->weight = computeWeight(MRI, MBFI, VReg); |
111 | 11.8k | LLVM_DEBUG(LI->dump()); |
112 | 11.8k | SortedIntervals.push_back(LI); |
113 | 11.8k | } |
114 | 4.31k | LLVM_DEBUG(dbgs() << '\n'); |
115 | 4.31k | |
116 | 4.31k | // Sort them to put arguments first (since we don't want to rename live-in |
117 | 4.31k | // registers), by weight next, and then by position. |
118 | 4.31k | // TODO: Investigate more intelligent sorting heuristics. For starters, we |
119 | 4.31k | // should try to coalesce adjacent live intervals before non-adjacent ones. |
120 | 26.1k | llvm::sort(SortedIntervals, [MRI](LiveInterval *LHS, LiveInterval *RHS) { |
121 | 26.1k | if (MRI->isLiveIn(LHS->reg) != MRI->isLiveIn(RHS->reg)) |
122 | 0 | return MRI->isLiveIn(LHS->reg); |
123 | 26.1k | if (LHS->weight != RHS->weight) |
124 | 5.19k | return LHS->weight > RHS->weight; |
125 | 20.9k | if (LHS->empty() || RHS->empty()20.9k ) |
126 | 21 | return !LHS->empty() && RHS->empty()5 ; |
127 | 20.9k | return *LHS < *RHS; |
128 | 20.9k | }); |
129 | 4.31k | |
130 | 4.31k | LLVM_DEBUG(dbgs() << "Coloring register intervals:\n"); |
131 | 4.31k | SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u); |
132 | 4.31k | SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments( |
133 | 4.31k | SortedIntervals.size()); |
134 | 4.31k | BitVector UsedColors(SortedIntervals.size()); |
135 | 4.31k | bool Changed = false; |
136 | 16.1k | for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I11.8k ) { |
137 | 11.8k | LiveInterval *LI = SortedIntervals[I]; |
138 | 11.8k | unsigned Old = LI->reg; |
139 | 11.8k | size_t Color = I; |
140 | 11.8k | const TargetRegisterClass *RC = MRI->getRegClass(Old); |
141 | 11.8k | |
142 | 11.8k | // Check if it's possible to reuse any of the used colors. |
143 | 11.8k | if (!MRI->isLiveIn(Old)) |
144 | 47.8k | for (unsigned C : UsedColors.set_bits())11.8k { |
145 | 47.8k | if (MRI->getRegClass(SortedIntervals[C]->reg) != RC) |
146 | 3.66k | continue; |
147 | 44.1k | for (LiveInterval *OtherLI : Assignments[C]) |
148 | 44.4k | if (!OtherLI->empty() && OtherLI->overlaps(*LI)44.3k ) |
149 | 43.8k | goto continue_outer; |
150 | 44.1k | Color = C; |
151 | 292 | break; |
152 | 43.8k | continue_outer:; |
153 | 43.8k | } |
154 | 11.8k | |
155 | 11.8k | unsigned New = SortedIntervals[Color]->reg; |
156 | 11.8k | SlotMapping[I] = New; |
157 | 11.8k | Changed |= Old != New; |
158 | 11.8k | UsedColors.set(Color); |
159 | 11.8k | Assignments[Color].push_back(LI); |
160 | 11.8k | LLVM_DEBUG( |
161 | 11.8k | dbgs() << "Assigning vreg" << TargetRegisterInfo::virtReg2Index(LI->reg) |
162 | 11.8k | << " to vreg" << TargetRegisterInfo::virtReg2Index(New) << "\n"); |
163 | 11.8k | } |
164 | 4.31k | if (!Changed) |
165 | 4.11k | return false; |
166 | 195 | |
167 | 195 | // Rewrite register operands. |
168 | 1.23k | for (size_t I = 0, E = SortedIntervals.size(); 195 I < E; ++I1.04k ) { |
169 | 1.04k | unsigned Old = SortedIntervals[I]->reg; |
170 | 1.04k | unsigned New = SlotMapping[I]; |
171 | 1.04k | if (Old != New) |
172 | 292 | MRI->replaceRegWith(Old, New); |
173 | 1.04k | } |
174 | 195 | return true; |
175 | 195 | } |