| 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 "WebAssemblyUtilities.h" |
| 22 | #include "llvm/CodeGen/LiveIntervals.h" |
| 23 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
| 24 | #include "llvm/CodeGen/MachineFunctionAnalysisManager.h" |
| 25 | #include "llvm/CodeGen/MachinePassManager.h" |
| 26 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
| 27 | #include "llvm/CodeGen/Passes.h" |
| 28 | #include "llvm/CodeGen/SlotIndexes.h" |
| 29 | #include "llvm/IR/Analysis.h" |
| 30 | #include "llvm/Support/Debug.h" |
| 31 | #include "llvm/Support/raw_ostream.h" |
| 32 | using namespace llvm; |
| 33 | |
| 34 | #define DEBUG_TYPE "wasm-reg-coloring" |
| 35 | |
| 36 | namespace { |
| 37 | class WebAssemblyRegColoringLegacy final : public MachineFunctionPass { |
| 38 | public: |
| 39 | static char ID; // Pass identification, replacement for typeid |
| 40 | WebAssemblyRegColoringLegacy() : MachineFunctionPass(ID) {} |
| 41 | |
| 42 | StringRef getPassName() const override { |
| 43 | return "WebAssembly Register Coloring" ; |
| 44 | } |
| 45 | |
| 46 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
| 47 | AU.setPreservesCFG(); |
| 48 | AU.addRequired<LiveIntervalsWrapperPass>(); |
| 49 | AU.addRequired<MachineBlockFrequencyInfoWrapperPass>(); |
| 50 | MachineFunctionPass::getAnalysisUsage(AU); |
| 51 | } |
| 52 | |
| 53 | bool runOnMachineFunction(MachineFunction &MF) override; |
| 54 | }; |
| 55 | } // end anonymous namespace |
| 56 | |
| 57 | char WebAssemblyRegColoringLegacy::ID = 0; |
| 58 | INITIALIZE_PASS(WebAssemblyRegColoringLegacy, DEBUG_TYPE, |
| 59 | "Minimize number of registers used" , false, false) |
| 60 | |
| 61 | FunctionPass *llvm::createWebAssemblyRegColoringLegacyPass() { |
| 62 | return new WebAssemblyRegColoringLegacy(); |
| 63 | } |
| 64 | |
| 65 | // Compute the total spill weight for VReg. |
| 66 | static float computeWeight(const MachineRegisterInfo *MRI, |
| 67 | const MachineBlockFrequencyInfo *MBFI, |
| 68 | unsigned VReg) { |
| 69 | float Weight = 0.0f; |
| 70 | for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg: VReg)) |
| 71 | Weight += LiveIntervals::getSpillWeight(isDef: MO.isDef(), isUse: MO.isUse(), MBFI, |
| 72 | MI: *MO.getParent()); |
| 73 | return Weight; |
| 74 | } |
| 75 | |
| 76 | // Create a map of "Register -> vector of <SlotIndex, DBG_VALUE>". |
| 77 | // The SlotIndex is the slot index of the next non-debug instruction or the end |
| 78 | // of a BB, because DBG_VALUE's don't have slot index themselves. |
| 79 | // Adapted from RegisterCoalescer::buildVRegToDbgValueMap. |
| 80 | static DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>> |
| 81 | buildVRegToDbgValueMap(MachineFunction &MF, const LiveIntervals *Liveness) { |
| 82 | DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>> |
| 83 | DbgVRegToValues; |
| 84 | const SlotIndexes *Slots = Liveness->getSlotIndexes(); |
| 85 | SmallVector<MachineInstr *, 8> ToInsert; |
| 86 | |
| 87 | // After collecting a block of DBG_VALUEs into ToInsert, enter them into the |
| 88 | // map. |
| 89 | auto CloseNewDVRange = [&DbgVRegToValues, &ToInsert](SlotIndex Slot) { |
| 90 | for (auto *X : ToInsert) { |
| 91 | for (const auto &Op : X->debug_operands()) { |
| 92 | if (Op.isReg() && Op.getReg().isVirtual()) |
| 93 | DbgVRegToValues[Op.getReg()].push_back(x: {Slot, X}); |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | ToInsert.clear(); |
| 98 | }; |
| 99 | |
| 100 | // Iterate over all instructions, collecting them into the ToInsert vector. |
| 101 | // Once a non-debug instruction is found, record the slot index of the |
| 102 | // collected DBG_VALUEs. |
| 103 | for (auto &MBB : MF) { |
| 104 | SlotIndex CurrentSlot = Slots->getMBBStartIdx(mbb: &MBB); |
| 105 | |
| 106 | for (auto &MI : MBB) { |
| 107 | if (MI.isDebugValue()) { |
| 108 | if (any_of(Range: MI.debug_operands(), P: [](const MachineOperand &MO) { |
| 109 | return MO.isReg() && MO.getReg().isVirtual(); |
| 110 | })) |
| 111 | ToInsert.push_back(Elt: &MI); |
| 112 | } else if (!MI.isDebugOrPseudoInstr()) { |
| 113 | CurrentSlot = Slots->getInstructionIndex(MI); |
| 114 | CloseNewDVRange(CurrentSlot); |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | // Close range of DBG_VALUEs at the end of blocks. |
| 119 | CloseNewDVRange(Slots->getMBBEndIdx(mbb: &MBB)); |
| 120 | } |
| 121 | |
| 122 | // Sort all DBG_VALUEs we've seen by slot number. |
| 123 | for (auto &Pair : DbgVRegToValues) |
| 124 | llvm::sort(C&: Pair.second); |
| 125 | return DbgVRegToValues; |
| 126 | } |
| 127 | |
| 128 | // After register coalescing, some DBG_VALUEs will be invalid. Set them undef. |
| 129 | // This function has to run before the actual coalescing, i.e., the register |
| 130 | // changes. |
| 131 | static void undefInvalidDbgValues( |
| 132 | const LiveIntervals *Liveness, |
| 133 | ArrayRef<SmallVector<LiveInterval *, 4>> Assignments, |
| 134 | DenseMap<Register, std::vector<std::pair<SlotIndex, MachineInstr *>>> |
| 135 | &DbgVRegToValues) { |
| 136 | #ifndef NDEBUG |
| 137 | DenseSet<Register> SeenRegs; |
| 138 | #endif |
| 139 | for (const auto &CoalescedIntervals : Assignments) { |
| 140 | if (CoalescedIntervals.empty()) |
| 141 | continue; |
| 142 | for (LiveInterval *LI : CoalescedIntervals) { |
| 143 | Register Reg = LI->reg(); |
| 144 | #ifndef NDEBUG |
| 145 | // Ensure we don't process the same register twice |
| 146 | assert(SeenRegs.insert(Reg).second); |
| 147 | #endif |
| 148 | auto RegMapIt = DbgVRegToValues.find(Val: Reg); |
| 149 | if (RegMapIt == DbgVRegToValues.end()) |
| 150 | continue; |
| 151 | SlotIndex LastSlot; |
| 152 | bool LastUndefResult = false; |
| 153 | for (auto [Slot, DbgValue] : RegMapIt->second) { |
| 154 | // All consecutive DBG_VALUEs have the same slot because the slot |
| 155 | // indices they have is the one for the first non-debug instruction |
| 156 | // after it, because DBG_VALUEs don't have slot index themselves. Before |
| 157 | // doing live range queries, quickly check if the current DBG_VALUE has |
| 158 | // the same slot index as the previous one, in which case we should do |
| 159 | // the same. Note that RegMapIt->second, the vector of {SlotIndex, |
| 160 | // DBG_VALUE}, is sorted by SlotIndex, which is necessary for this |
| 161 | // check. |
| 162 | if (Slot == LastSlot) { |
| 163 | if (LastUndefResult) { |
| 164 | LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n" ); |
| 165 | DbgValue->setDebugValueUndef(); |
| 166 | } |
| 167 | continue; |
| 168 | } |
| 169 | LastSlot = Slot; |
| 170 | LastUndefResult = false; |
| 171 | for (LiveInterval *OtherLI : CoalescedIntervals) { |
| 172 | if (LI == OtherLI) |
| 173 | continue; |
| 174 | |
| 175 | // This DBG_VALUE has 'Reg' (the current LiveInterval's register) as |
| 176 | // its operand. If this DBG_VALUE's slot index is within other |
| 177 | // registers' live ranges, this DBG_VALUE should be undefed. For |
| 178 | // example, suppose %0 and %1 are to be coalesced into %0. |
| 179 | // ; %0's live range starts |
| 180 | // %0 = value_0 |
| 181 | // DBG_VALUE %0, !"a", ... (a) |
| 182 | // DBG_VALUE %1, !"b", ... (b) |
| 183 | // use %0 |
| 184 | // ; %0's live range ends |
| 185 | // ... |
| 186 | // ; %1's live range starts |
| 187 | // %1 = value_1 |
| 188 | // DBG_VALUE %0, !"c", ... (c) |
| 189 | // DBG_VALUE %1, !"d", ... (d) |
| 190 | // use %1 |
| 191 | // ; %1's live range ends |
| 192 | // |
| 193 | // In this code, (b) and (c) should be set to undef. After the two |
| 194 | // registers are coalesced, (b) will incorrectly say the variable |
| 195 | // "b"'s value is 'value_0', and (c) will also incorrectly say the |
| 196 | // variable "c"'s value is value_1. Note it doesn't actually matter |
| 197 | // which register they are coalesced into (%0 or %1); (b) and (c) |
| 198 | // should be set to undef as well if they are coalesced into %1. |
| 199 | // |
| 200 | // This happens DBG_VALUEs are not included when computing live |
| 201 | // ranges. |
| 202 | // |
| 203 | // Note that it is not possible for this DBG_VALUE to be |
| 204 | // simultaneously within 'Reg''s live range and one of other coalesced |
| 205 | // registers' live ranges because if their live ranges overlapped they |
| 206 | // would have not been selected as a coalescing candidate in the first |
| 207 | // place. |
| 208 | auto *SegmentIt = OtherLI->find(Pos: Slot); |
| 209 | if (SegmentIt != OtherLI->end() && SegmentIt->contains(I: Slot)) { |
| 210 | LLVM_DEBUG(dbgs() << "Undefed: " << *DbgValue << "\n" ); |
| 211 | DbgValue->setDebugValueUndef(); |
| 212 | LastUndefResult = true; |
| 213 | break; |
| 214 | } |
| 215 | } |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | static bool regColoring(MachineFunction &MF, LiveIntervals *Liveness, |
| 222 | const MachineBlockFrequencyInfo *MBFI) { |
| 223 | LLVM_DEBUG({ |
| 224 | dbgs() << "********** Register Coloring **********\n" |
| 225 | << "********** Function: " << MF.getName() << '\n'; |
| 226 | }); |
| 227 | |
| 228 | MachineRegisterInfo *MRI = &MF.getRegInfo(); |
| 229 | WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); |
| 230 | |
| 231 | // We don't preserve SSA form. |
| 232 | MRI->leaveSSA(); |
| 233 | |
| 234 | // Gather all register intervals into a list and sort them. |
| 235 | unsigned NumVRegs = MRI->getNumVirtRegs(); |
| 236 | SmallVector<LiveInterval *, 0> SortedIntervals; |
| 237 | SortedIntervals.reserve(N: NumVRegs); |
| 238 | |
| 239 | // Record DBG_VALUEs and their SlotIndexes. |
| 240 | auto DbgVRegToValues = buildVRegToDbgValueMap(MF, Liveness); |
| 241 | |
| 242 | LLVM_DEBUG(dbgs() << "Interesting register intervals:\n" ); |
| 243 | for (unsigned I = 0; I < NumVRegs; ++I) { |
| 244 | Register VReg = Register::index2VirtReg(Index: I); |
| 245 | if (MFI.isVRegStackified(VReg)) |
| 246 | continue; |
| 247 | // Skip unused registers, which can use $drop. |
| 248 | if (MRI->use_empty(RegNo: VReg)) |
| 249 | continue; |
| 250 | |
| 251 | LiveInterval *LI = &Liveness->getInterval(Reg: VReg); |
| 252 | assert(LI->weight() == 0.0f); |
| 253 | LI->setWeight(computeWeight(MRI, MBFI, VReg)); |
| 254 | LLVM_DEBUG(LI->dump()); |
| 255 | SortedIntervals.push_back(Elt: LI); |
| 256 | } |
| 257 | LLVM_DEBUG(dbgs() << '\n'); |
| 258 | |
| 259 | // Sort them to put arguments first (since we don't want to rename live-in |
| 260 | // registers), by weight next, and then by position. |
| 261 | // TODO: Investigate more intelligent sorting heuristics. For starters, we |
| 262 | // should try to coalesce adjacent live intervals before non-adjacent ones. |
| 263 | llvm::sort(C&: SortedIntervals, Comp: [MRI](LiveInterval *LHS, LiveInterval *RHS) { |
| 264 | if (MRI->isLiveIn(Reg: LHS->reg()) != MRI->isLiveIn(Reg: RHS->reg())) |
| 265 | return MRI->isLiveIn(Reg: LHS->reg()); |
| 266 | if (LHS->weight() != RHS->weight()) |
| 267 | return LHS->weight() > RHS->weight(); |
| 268 | if (LHS->empty() || RHS->empty()) |
| 269 | return !LHS->empty() && RHS->empty(); |
| 270 | return *LHS < *RHS; |
| 271 | }); |
| 272 | |
| 273 | // ABI contract: the async context must always be available in local 0. |
| 274 | // Another value in the same register would make WebAssemblyExplicitLocals |
| 275 | // copy the argument to another local. |
| 276 | Register SwiftAsyncReg = WebAssembly::getSwiftAsyncArgReg(MF); |
| 277 | |
| 278 | LLVM_DEBUG(dbgs() << "Coloring register intervals:\n" ); |
| 279 | SmallVector<unsigned, 16> SlotMapping(SortedIntervals.size(), -1u); |
| 280 | SmallVector<SmallVector<LiveInterval *, 4>, 16> Assignments( |
| 281 | SortedIntervals.size()); |
| 282 | BitVector UsedColors(SortedIntervals.size()); |
| 283 | bool Changed = false; |
| 284 | for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) { |
| 285 | LiveInterval *LI = SortedIntervals[I]; |
| 286 | Register Old = LI->reg(); |
| 287 | size_t Color = I; |
| 288 | const TargetRegisterClass *RC = MRI->getRegClass(Reg: Old); |
| 289 | |
| 290 | // Check if it's possible to reuse any of the used colors. |
| 291 | if (!MRI->isLiveIn(Reg: Old) && Old != SwiftAsyncReg) |
| 292 | for (unsigned C : UsedColors.set_bits()) { |
| 293 | if (MRI->getRegClass(Reg: SortedIntervals[C]->reg()) != RC || |
| 294 | SortedIntervals[C]->reg() == SwiftAsyncReg) |
| 295 | continue; |
| 296 | for (LiveInterval *OtherLI : Assignments[C]) |
| 297 | if (!OtherLI->empty() && OtherLI->overlaps(other: *LI)) |
| 298 | goto continue_outer; |
| 299 | Color = C; |
| 300 | break; |
| 301 | continue_outer:; |
| 302 | } |
| 303 | |
| 304 | Register New = SortedIntervals[Color]->reg(); |
| 305 | SlotMapping[I] = New; |
| 306 | Changed |= Old != New; |
| 307 | UsedColors.set(Color); |
| 308 | Assignments[Color].push_back(Elt: LI); |
| 309 | // If we reassigned the stack pointer, update the debug frame base info. |
| 310 | if (Old != New && MFI.isFrameBaseVirtual() && MFI.getFrameBaseVreg() == Old) |
| 311 | MFI.setFrameBaseVreg(New); |
| 312 | LLVM_DEBUG(dbgs() << "Assigning vreg " << printReg(LI->reg()) << " to vreg " |
| 313 | << printReg(New) << "\n" ); |
| 314 | } |
| 315 | if (!Changed) |
| 316 | return false; |
| 317 | |
| 318 | // Set DBG_VALUEs that will be invalid after coalescing to undef. |
| 319 | undefInvalidDbgValues(Liveness, Assignments, DbgVRegToValues); |
| 320 | |
| 321 | // Rewrite register operands. |
| 322 | for (size_t I = 0, E = SortedIntervals.size(); I < E; ++I) { |
| 323 | Register Old = SortedIntervals[I]->reg(); |
| 324 | unsigned New = SlotMapping[I]; |
| 325 | if (Old != New) |
| 326 | MRI->replaceRegWith(FromReg: Old, ToReg: New); |
| 327 | } |
| 328 | return true; |
| 329 | } |
| 330 | |
| 331 | bool WebAssemblyRegColoringLegacy::runOnMachineFunction(MachineFunction &MF) { |
| 332 | // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual |
| 333 | // registers could be modified before the longjmp is executed, resulting in |
| 334 | // the wrong value being used afterwards. |
| 335 | // TODO: Does WebAssembly need to care about setjmp for register coloring? |
| 336 | if (MF.exposesReturnsTwice()) |
| 337 | return false; |
| 338 | |
| 339 | LiveIntervals *Liveness = &getAnalysis<LiveIntervalsWrapperPass>().getLIS(); |
| 340 | const MachineBlockFrequencyInfo *MBFI = |
| 341 | &getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI(); |
| 342 | return regColoring(MF, Liveness, MBFI); |
| 343 | } |
| 344 | |
| 345 | PreservedAnalyses |
| 346 | WebAssemblyRegColoringPass::run(MachineFunction &MF, |
| 347 | MachineFunctionAnalysisManager &MFAM) { |
| 348 | // If there are calls to setjmp or sigsetjmp, don't perform coloring. Virtual |
| 349 | // registers could be modified before the longjmp is executed, resulting in |
| 350 | // the wrong value being used afterwards. |
| 351 | // TODO: Does WebAssembly need to care about setjmp for register coloring? |
| 352 | if (MF.exposesReturnsTwice()) |
| 353 | return PreservedAnalyses::all(); |
| 354 | |
| 355 | LiveIntervals *Liveness = &MFAM.getResult<LiveIntervalsAnalysis>(IR&: MF); |
| 356 | const MachineBlockFrequencyInfo *MBFI = |
| 357 | &MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF); |
| 358 | return regColoring(MF, Liveness, MBFI) |
| 359 | ? getMachineFunctionPassPreservedAnalyses() |
| 360 | .preserveSet<CFGAnalyses>() |
| 361 | : PreservedAnalyses::all(); |
| 362 | } |
| 363 | |