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
24namespace llvm {
25
26class RegisterClassInfo;
27class VirtRegMap;
28class LiveRegMatrix;
29
30class LLVM_LIBRARY_VISIBILITY AllocationOrder {
31 const SmallVector<MCPhysReg, 16> Hints;
32 ArrayRef<MCPhysReg> Order;
33 // How far into the Order we can iterate. This is 0 if the AllocationOrder is
34 // constructed with HardHints = true, Order.size() otherwise. While
35 // technically a size_t, it will participate in comparisons with the
36 // Iterator's Pos, which must be signed, so it's typed here as signed, too, to
37 // avoid warnings and under the assumption that the size of Order is
38 // relatively small.
39 // IterationLimit defines an invalid iterator position.
40 const int IterationLimit;
41
42public:
43 /// Forward iterator for an AllocationOrder.
44 class Iterator final {
45 const AllocationOrder &AO;
46 int Pos = 0;
47
48 public:
49 Iterator(const AllocationOrder &AO, int Pos) : AO(AO), Pos(Pos) {}
50
51 /// Return true if the current position is that of a preferred register.
52 bool isHint() const { return Pos < 0; }
53
54 /// Return the next physical register in the allocation order.
55 MCRegister operator*() const {
56 if (Pos < 0)
57 return AO.Hints.end()[Pos];
58 assert(Pos < AO.IterationLimit);
59 return AO.Order[Pos];
60 }
61
62 /// Advance the iterator to the next position. If that's past the Hints
63 /// list, advance to the first value that's not also in the Hints list.
64 Iterator &operator++() {
65 if (Pos < AO.IterationLimit)
66 ++Pos;
67 while (Pos >= 0 && Pos < AO.IterationLimit && AO.isHint(Reg: AO.Order[Pos]))
68 ++Pos;
69 return *this;
70 }
71
72 bool operator==(const Iterator &Other) const {
73 assert(&AO == &Other.AO);
74 return Pos == Other.Pos;
75 }
76
77 bool operator!=(const Iterator &Other) const { return !(*this == Other); }
78 };
79
80 /// Create a new AllocationOrder for VirtReg.
81 /// @param VirtReg Virtual register to allocate for.
82 /// @param VRM Virtual register map for function.
83 /// @param RegClassInfo Information about reserved and allocatable registers.
84 static AllocationOrder create(Register VirtReg, const VirtRegMap &VRM,
85 const RegisterClassInfo &RegClassInfo,
86 const LiveRegMatrix *Matrix);
87
88 /// Create an AllocationOrder given the Hints, Order, and HardHints values.
89 /// Use the create method above - the ctor is for unittests.
90 AllocationOrder(SmallVector<MCPhysReg, 16> &&Hints, ArrayRef<MCPhysReg> Order,
91 bool HardHints)
92 : Hints(std::move(Hints)), Order(Order),
93 IterationLimit(HardHints ? 0 : static_cast<int>(Order.size())) {}
94
95 Iterator begin() const {
96 return Iterator(*this, -(static_cast<int>(Hints.size())));
97 }
98
99 Iterator end() const { return Iterator(*this, IterationLimit); }
100
101 Iterator getOrderLimitEnd(unsigned OrderLimit) const {
102 assert(OrderLimit <= Order.size());
103 if (OrderLimit == 0)
104 return end();
105 Iterator Ret(*this,
106 std::min(a: static_cast<int>(OrderLimit) - 1, b: IterationLimit));
107 return ++Ret;
108 }
109
110 /// Get the allocation order without reordered hints.
111 ArrayRef<MCPhysReg> getOrder() const { return Order; }
112
113 /// Return true if Reg is a preferred physical register.
114 bool isHint(Register Reg) const {
115 assert(!Reg.isPhysical() ||
116 Reg.id() <
117 static_cast<uint32_t>(std::numeric_limits<MCPhysReg>::max()));
118 return Reg.isPhysical() && is_contained(Range: Hints, Element: Reg.id());
119 }
120};
121
122} // end namespace llvm
123
124#endif
125