1//===-- llvm/CodeGen/AllocationOrder.h - Allocation Order -*- C++ -*-------===//
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 and target hooks. The AllocationOrder class encapsulates all of that.
13//
14//===----------------------------------------------------------------------===//
15
16#ifndef LLVM_LIB_CODEGEN_ALLOCATIONORDER_H
17#define LLVM_LIB_CODEGEN_ALLOCATIONORDER_H
18
19#include "llvm/ADT/ArrayRef.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/CodeGen/Register.h"
23#include "llvm/CodeGen/TargetRegisterInfo.h"
24
25namespace llvm {
26
27class RegisterClassInfo;
28class VirtRegMap;
29class LiveRegMatrix;
30
31class LLVM_LIBRARY_VISIBILITY AllocationOrder {
32 // Used as storage for both Hints and CustomOrder if the Order received in the
33 // constructor needs to be altered. [0, NumHints) contains regular hints. If a
34 // custom order is present, [NumHints, end) contains the custom order.
35 const SmallVector<MCPhysReg, 16> HintsAndCustomOrder;
36 const int NumHints;
37 ArrayRef<MCPhysReg> Order;
38 // How far into the Order we can iterate. This is 0 if the AllocationOrder is
39 // constructed with HardHints = true, Order.size() otherwise. While
40 // technically a size_t, it will participate in comparisons with the
41 // Iterator's Pos, which must be signed, so it's typed here as signed, too, to
42 // avoid warnings and under the assumption that the size of Order is
43 // relatively small.
44 // IterationLimit defines an invalid iterator position.
45 const int IterationLimit;
46
47 ArrayRef<MCPhysReg> hints() const {
48 return ArrayRef<MCPhysReg>(HintsAndCustomOrder).take_front(N: NumHints);
49 }
50
51public:
52 /// Forward iterator for an AllocationOrder.
53 class Iterator final {
54 const AllocationOrder &AO;
55 int Pos = 0;
56
57 public:
58 Iterator(const AllocationOrder &AO, int Pos) : AO(AO), Pos(Pos) {}
59
60 /// Return true if the current position is that of a preferred register.
61 bool isHint() const { return Pos < 0; }
62
63 /// Return the next physical register in the allocation order.
64 MCRegister operator*() const {
65 if (Pos < 0)
66 return AO.HintsAndCustomOrder[AO.NumHints + Pos];
67 assert(Pos < AO.IterationLimit);
68 return AO.Order[Pos];
69 }
70
71 /// Advance the iterator to the next position. If that's past the Hints
72 /// list, advance to the first value that's not also in the Hints list.
73 Iterator &operator++() {
74 if (Pos < AO.IterationLimit)
75 ++Pos;
76 while (Pos >= 0 && Pos < AO.IterationLimit && AO.isHint(Reg: AO.Order[Pos]))
77 ++Pos;
78 return *this;
79 }
80
81 bool operator==(const Iterator &Other) const {
82 assert(&AO == &Other.AO);
83 return Pos == Other.Pos;
84 }
85
86 bool operator!=(const Iterator &Other) const { return !(*this == Other); }
87 };
88
89 /// Create a new AllocationOrder for VirtReg.
90 /// @param VirtReg Virtual register to allocate for.
91 /// @param VRM Virtual register map for function.
92 /// @param RegClassInfo Information about reserved and allocatable registers.
93 static AllocationOrder create(Register VirtReg, const VirtRegMap &VRM,
94 const RegisterClassInfo &RegClassInfo,
95 const LiveRegMatrix *Matrix);
96
97 /// Create an AllocationOrder from HintsAndCustomOrder that contains NumHints
98 /// Hints optionally followed by a custom order. When that custom order is
99 /// present it becomes the allocation order otherwise Order is used as-is.
100 AllocationOrder(SmallVector<MCPhysReg, 16> &&HintsAndCustomOrder,
101 int NumHints, ArrayRef<MCPhysReg> Order, bool HardHints)
102 : HintsAndCustomOrder(std::move(HintsAndCustomOrder)), NumHints(NumHints),
103 Order(static_cast<int>(this->HintsAndCustomOrder.size()) > NumHints
104 ? ArrayRef<MCPhysReg>(this->HintsAndCustomOrder)
105 .drop_front(N: NumHints)
106 : Order),
107 IterationLimit(HardHints ? 0 : static_cast<int>(this->Order.size())) {}
108
109 /// Create an AllocationOrder given the Hints, Order, and HardHints values.
110 /// Use the create method above - the ctor is for unittests.
111 AllocationOrder(SmallVector<MCPhysReg, 16> &&Hints, ArrayRef<MCPhysReg> Order,
112 bool HardHints)
113 : AllocationOrder(std::move(Hints), static_cast<int>(Hints.size()), Order,
114 HardHints) {}
115
116 Iterator begin() const { return Iterator(*this, -NumHints); }
117
118 Iterator end() const { return Iterator(*this, IterationLimit); }
119
120 Iterator getOrderLimitEnd(unsigned OrderLimit) const {
121 assert(OrderLimit <= Order.size());
122 if (OrderLimit == 0)
123 return end();
124 Iterator Ret(*this,
125 std::min(a: static_cast<int>(OrderLimit) - 1, b: IterationLimit));
126 return ++Ret;
127 }
128
129 /// Get the allocation order without reordered hints.
130 ArrayRef<MCPhysReg> getOrder() const { return Order; }
131
132 /// Return true if a custom order replaced the RegisterClassInfo order.
133 bool hasCustomOrder() const {
134 return static_cast<int>(HintsAndCustomOrder.size()) > NumHints;
135 }
136
137 /// Return true if Reg is a preferred physical register.
138 bool isHint(Register Reg) const {
139 assert(!Reg.isPhysical() ||
140 Reg.id() <
141 static_cast<uint32_t>(std::numeric_limits<MCPhysReg>::max()));
142 return Reg.isPhysical() && is_contained(Range: hints(), Element: Reg.id());
143 }
144};
145
146} // end namespace llvm
147
148#endif
149