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 
24 namespace llvm {
25 
26 class RegisterClassInfo;
27 class VirtRegMap;
28 class LiveRegMatrix;
29 
30 class 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 
42 public:
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.
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(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.
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(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
125