LLVM 20.0.0git
AllocationOrder.h
Go to the documentation of this file.
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"
23
24namespace llvm {
25
26class RegisterClassInfo;
27class VirtRegMap;
28class LiveRegMatrix;
29
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 curent 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.
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.
65 if (Pos < AO.IterationLimit)
66 ++Pos;
67 while (Pos >= 0 && Pos < AO.IterationLimit && AO.isHint(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(unsigned VirtReg, const VirtRegMap &VRM,
85 const RegisterClassInfo &RegClassInfo,
86 const LiveRegMatrix *Matrix);
87
88 /// Create an AllocationOrder given the Hits, Order, and HardHits values.
89 /// Use the create method above - the ctor is for unittests.
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(static_cast<int>(OrderLimit) - 1, 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(Hints, Reg.id());
119 }
120};
121
122} // end namespace llvm
123
124#endif
#define LLVM_LIBRARY_VISIBILITY
Definition: Compiler.h:131
std::optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1295
Live Register Matrix
unsigned Reg
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Forward iterator for an AllocationOrder.
bool isHint() const
Return true if the curent position is that of a preferred register.
bool operator==(const Iterator &Other) const
Iterator(const AllocationOrder &AO, int Pos)
Iterator & operator++()
Advance the iterator to the next position.
bool operator!=(const Iterator &Other) const
MCRegister operator*() const
Return the next physical register in the allocation order.
bool isHint(Register Reg) const
Return true if Reg is a preferred physical register.
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
Iterator end() const
Iterator getOrderLimitEnd(unsigned OrderLimit) const
AllocationOrder(SmallVector< MCPhysReg, 16 > &&Hints, ArrayRef< MCPhysReg > Order, bool HardHints)
Create an AllocationOrder given the Hits, Order, and HardHits values.
Iterator begin() const
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:33
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1680
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858