LLVM  14.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"
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 
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.
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() <
118  return Reg.isPhysical() && is_contained(Hints, Reg.id());
119  }
120 };
121 
122 } // end namespace llvm
123 
124 #endif
llvm::AllocationOrder::end
Iterator end() const
Definition: AllocationOrder.h:99
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
Reg
unsigned Reg
Definition: MachineSink.cpp:1566
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::AllocationOrder::AllocationOrder
AllocationOrder(SmallVector< MCPhysReg, 16 > &&Hints, ArrayRef< MCPhysReg > Order, bool HardHints)
Create an AllocationOrder given the Hits, Order, and HardHits values.
Definition: AllocationOrder.h:90
llvm::VirtRegMap
Definition: VirtRegMap.h:33
llvm::AllocationOrder::Iterator::operator==
bool operator==(const Iterator &Other) const
Definition: AllocationOrder.h:72
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
llvm::AllocationOrder::begin
Iterator begin() const
Definition: AllocationOrder.h:95
llvm::MipsISD::Ret
@ Ret
Definition: MipsISelLowering.h:116
STLExtras.h
llvm::AllocationOrder::Iterator
Forward iterator for an AllocationOrder.
Definition: AllocationOrder.h:44
llvm::AllocationOrder::Iterator::Iterator
Iterator(const AllocationOrder &AO, int Pos)
Definition: AllocationOrder.h:49
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::AllocationOrder::Iterator::operator++
Iterator & operator++()
Advance the iterator to the next position.
Definition: AllocationOrder.h:64
llvm::AllocationOrder
Definition: AllocationOrder.h:30
llvm::AllocationOrder::Iterator::isHint
bool isHint() const
Return true if the curent position is that of a preferred register.
Definition: AllocationOrder.h:52
llvm::AllocationOrder::Iterator::operator*
MCRegister operator*() const
Return the next physical register in the allocation order.
Definition: AllocationOrder.h:55
llvm::AllocationOrder::getOrderLimitEnd
Iterator getOrderLimitEnd(unsigned OrderLimit) const
Definition: AllocationOrder.h:101
llvm::is_contained
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
Definition: STLExtras.h:1616
ArrayRef.h
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
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:1609
llvm::RegisterClassInfo
Definition: RegisterClassInfo.h:30
llvm::AllocationOrder::getOrder
ArrayRef< MCPhysReg > getOrder() const
Get the allocation order without reordered hints.
Definition: AllocationOrder.h:111
llvm::size
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:1532
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
uint32_t
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:131
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
std
Definition: BitVector.h:838
llvm::AllocationOrder::isHint
bool isHint(Register Reg) const
Return true if Reg is a preferred physical register.
Definition: AllocationOrder.h:114
SmallVector.h
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
Register.h
llvm::AllocationOrder::Iterator::operator!=
bool operator!=(const Iterator &Other) const
Definition: AllocationOrder.h:77
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1175
llvm::MCRegister
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:23
llvm::LiveRegMatrix
Definition: LiveRegMatrix.h:40