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/SmallVector.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/MC/MCRegister.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   int Pos = 0;
34 
35   // If HardHints is true, *only* Hints will be returned.
36   const bool HardHints;
37 
38 public:
39 
40   /// Create a new AllocationOrder for VirtReg.
41   /// @param VirtReg      Virtual register to allocate for.
42   /// @param VRM          Virtual register map for function.
43   /// @param RegClassInfo Information about reserved and allocatable registers.
44   static AllocationOrder create(unsigned VirtReg, const VirtRegMap &VRM,
45                                 const RegisterClassInfo &RegClassInfo,
46                                 const LiveRegMatrix *Matrix);
47 
48   /// Create an AllocationOrder given the Hits, Order, and HardHits values.
49   /// Use the create method above - the ctor is for unittests.
50   AllocationOrder(SmallVector<MCPhysReg, 16> &&Hints, ArrayRef<MCPhysReg> Order,
51                   bool HardHints)
52       : Hints(std::move(Hints)), Order(Order),
53         Pos(-static_cast<int>(this->Hints.size())), HardHints(HardHints) {}
54 
55   /// Get the allocation order without reordered hints.
56   ArrayRef<MCPhysReg> getOrder() const { return Order; }
57 
58   /// Return the next physical register in the allocation order, or 0.
59   /// It is safe to call next() again after it returned 0, it will keep
60   /// returning 0 until rewind() is called.
61   MCPhysReg next(unsigned Limit = 0) {
62     if (Pos < 0)
63       return Hints.end()[Pos++];
64     if (HardHints)
65       return 0;
66     if (!Limit)
67       Limit = Order.size();
68     while (Pos < int(Limit)) {
69       unsigned Reg = Order[Pos++];
70       if (!isHint(Reg))
71         return Reg;
72     }
73     return 0;
74   }
75 
76   /// Start over from the beginning.
77   void rewind() { Pos = -int(Hints.size()); }
78 
79   /// Return true if the last register returned from next() was a preferred register.
80   bool isHint() const { return Pos <= 0; }
81 
82   /// Return true if PhysReg is a preferred register.
83   bool isHint(unsigned PhysReg) const { return is_contained(Hints, PhysReg); }
84 };
85 
86 } // end namespace llvm
87 
88 #endif
89