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/MC/MCRegisterInfo.h"
22
23namespace llvm {
24
25class RegisterClassInfo;
26class VirtRegMap;
27class LiveRegMatrix;
28
29class LLVM_LIBRARY_VISIBILITY AllocationOrder {
30  SmallVector<MCPhysReg, 16> Hints;
31  ArrayRef<MCPhysReg> Order;
32  int Pos;
33
34  // If HardHints is true, *only* Hints will be returned.
35  bool HardHints;
36
37public:
38
39  /// Create a new AllocationOrder for VirtReg.
40  /// @param VirtReg      Virtual register to allocate for.
41  /// @param VRM          Virtual register map for function.
42  /// @param RegClassInfo Information about reserved and allocatable registers.
43  AllocationOrder(unsigned VirtReg,
44                  const VirtRegMap &VRM,
45                  const RegisterClassInfo &RegClassInfo,
46                  const LiveRegMatrix *Matrix);
47
48  /// Get the allocation order without reordered hints.
49  ArrayRef<MCPhysReg> getOrder() const { return Order; }
50
51  /// Return the next physical register in the allocation order, or 0.
52  /// It is safe to call next() again after it returned 0, it will keep
53  /// returning 0 until rewind() is called.
54  unsigned next(unsigned Limit = 0) {
55    if (Pos < 0)
56      return Hints.end()[Pos++];
57    if (HardHints)
58      return 0;
59    if (!Limit)
60      Limit = Order.size();
61    while (Pos < int(Limit)) {
62      unsigned Reg = Order[Pos++];
63      if (!isHint(Reg))
64        return Reg;
65    }
66    return 0;
67  }
68
69  /// As next(), but allow duplicates to be returned, and stop before the
70  /// Limit'th register in the RegisterClassInfo allocation order.
71  ///
72  /// This can produce more than Limit registers if there are hints.
73  unsigned nextWithDups(unsigned Limit) {
74    if (Pos < 0)
75      return Hints.end()[Pos++];
76    if (HardHints)
77      return 0;
78    if (Pos < int(Limit))
79      return Order[Pos++];
80    return 0;
81  }
82
83  /// Start over from the beginning.
84  void rewind() { Pos = -int(Hints.size()); }
85
86  /// Return true if the last register returned from next() was a preferred register.
87  bool isHint() const { return Pos <= 0; }
88
89  /// Return true if PhysReg is a preferred register.
90  bool isHint(unsigned PhysReg) const { return is_contained(Hints, PhysReg); }
91};
92
93} // end namespace llvm
94
95#endif
96