1//===-- llvm/CodeGen/AllocationOrder.cpp - Allocation Order ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements an allocation order for virtual registers.
10//
11// The preferred allocation order for a virtual register depends on allocation
12// hints, anti-hints, and target hooks. The AllocationOrder class encapsulates
13// all of that.
14//
15//===----------------------------------------------------------------------===//
16
17#include "AllocationOrder.h"
18#include "llvm/ADT/BitVector.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/CodeGen/RegisterClassInfo.h"
22#include "llvm/CodeGen/VirtRegMap.h"
23#include "llvm/Support/Debug.h"
24#include "llvm/Support/raw_ostream.h"
25
26using namespace llvm;
27
28#define DEBUG_TYPE "regalloc"
29
30static void getBitVecRegAntiHints(Register VReg, BitVector &AntiHintedRegUnits,
31 const VirtRegMap &VRM,
32 const MachineRegisterInfo &MRI,
33 const TargetRegisterInfo &TRI) {
34 assert(VReg.isVirtual() && "Anti-hints are only for virtual registers");
35 for (Register AntiHintVReg : MRI.getRegAllocationAntiHints(VReg)) {
36 // Check if the anti-hinted register has been allocated.
37 if (!VRM.hasPhys(virtReg: AntiHintVReg))
38 continue;
39 // Delay until first allocated anti-hinted register so unused cases keep
40 // default empty BitVector.
41 if (AntiHintedRegUnits.empty())
42 AntiHintedRegUnits.resize(N: TRI.getNumRegUnits());
43 for (MCRegUnit Unit : TRI.regunits(Reg: VRM.getPhys(virtReg: AntiHintVReg)))
44 AntiHintedRegUnits.set(static_cast<unsigned>(Unit));
45 }
46}
47
48// Compare VirtRegMap::getRegAllocPref().
49AllocationOrder AllocationOrder::create(Register VirtReg, const VirtRegMap &VRM,
50 const RegisterClassInfo &RegClassInfo,
51 const LiveRegMatrix *Matrix) {
52 const MachineFunction &MF = VRM.getMachineFunction();
53 const TargetRegisterInfo *TRI = &VRM.getTargetRegInfo();
54 const MachineRegisterInfo &MRI = MF.getRegInfo();
55 auto Order = RegClassInfo.getOrder(RC: MF.getRegInfo().getRegClass(Reg: VirtReg));
56 // Get Hints.
57 SmallSetVector<MCPhysReg, 16> Hints;
58 bool HardHints =
59 TRI->getRegAllocationHints(VirtReg, Order, Hints, MF, VRM: &VRM, Matrix);
60
61 // HintsAndCustomOrder holds Hints first followed by the custom order if the
62 // anti-hints reorders it.
63 SmallVector<MCPhysReg, 16> HintsAndCustomOrder = Hints.takeVector();
64 const int NumHints = static_cast<int>(HintsAndCustomOrder.size());
65
66 // HintsAndCustomOrder only holds Hints (custom order is not added yet).
67 LLVM_DEBUG({
68 if (NumHints) {
69 dbgs() << "hints:";
70 for (MCPhysReg Hint : HintsAndCustomOrder)
71 dbgs() << ' ' << printReg(Hint, TRI);
72 dbgs() << '\n';
73 }
74 });
75
76 // Get anti-hints.
77 BitVector AntiHintedRegUnits;
78 getBitVecRegAntiHints(VReg: VirtReg, AntiHintedRegUnits, VRM, MRI, TRI: *TRI);
79
80 LLVM_DEBUG({
81 if (AntiHintedRegUnits.any()) {
82 dbgs() << "anti-hints:";
83 for (Register AntiHintVReg : MRI.getRegAllocationAntiHints(VirtReg)) {
84 if (!VRM.hasPhys(AntiHintVReg))
85 continue;
86 dbgs() << ' ' << printReg(VRM.getPhys(AntiHintVReg), TRI);
87 }
88 dbgs() << '\n';
89 }
90 });
91
92 if (AntiHintedRegUnits.any())
93 TRI->applyRegAllocationAntiHints(VirtReg, Order, HintsAndCustomOrder,
94 NumHints, AntiHintedRegUnits, MF, Matrix,
95 RegClassInfo: &RegClassInfo);
96
97 // Create allocation order object.
98 AllocationOrder AO(std::move(HintsAndCustomOrder), NumHints, Order,
99 HardHints);
100
101 assert(all_of(AO.hints(),
102 [&](MCPhysReg Hint) { return is_contained(AO.Order, Hint); }) &&
103 "Target hint is outside allocation order.");
104 return AO;
105}
106