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: Iterator(const AllocationOrder & AO,int Pos)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. isHint()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. AllocationOrder(SmallVector<MCPhysReg,16> && Hints,ArrayRef<MCPhysReg> Order,bool HardHints)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 begin()95 Iterator begin() const { 96 return Iterator(*this, -(static_cast<int>(Hints.size()))); 97 } 98 end()99 Iterator end() const { return Iterator(*this, IterationLimit); } 100 getOrderLimitEnd(unsigned OrderLimit)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. getOrder()111 ArrayRef<MCPhysReg> getOrder() const { return Order; } 112 113 /// Return true if Reg is a preferred physical register. isHint(Register Reg)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