1 //===-- llvm/CodeGen/AllocationOrder.h - Allocation Order -*- C++ -*-------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements an allocation order for virtual registers.
11 //
12 // The preferred allocation order for a virtual register depends on allocation
13 // hints and target hooks. The AllocationOrder class encapsulates all of that.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_LIB_CODEGEN_ALLOCATIONORDER_H
18 #define LLVM_LIB_CODEGEN_ALLOCATIONORDER_H
19 
20 #include "llvm/ADT/ArrayRef.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/MC/MCRegisterInfo.h"
23 
24 namespace llvm {
25 
26 class RegisterClassInfo;
27 class VirtRegMap;
28 class LiveRegMatrix;
29 
30 class LLVM_LIBRARY_VISIBILITY AllocationOrder {
31   SmallVector<MCPhysReg, 16> Hints;
32   ArrayRef<MCPhysReg> Order;
33   int Pos;
34 
35   // If HardHints is true, *only* Hints will be returned.
36   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   AllocationOrder(unsigned VirtReg,
45                   const VirtRegMap &VRM,
46                   const RegisterClassInfo &RegClassInfo,
47                   const LiveRegMatrix *Matrix);
48 
49   /// Get the allocation order without reordered hints.
getOrder()50   ArrayRef<MCPhysReg> getOrder() const { return Order; }
51 
52   /// Return the next physical register in the allocation order, or 0.
53   /// It is safe to call next() again after it returned 0, it will keep
54   /// returning 0 until rewind() is called.
55   unsigned next(unsigned Limit = 0) {
56     if (Pos < 0)
57       return Hints.end()[Pos++];
58     if (HardHints)
59       return 0;
60     if (!Limit)
61       Limit = Order.size();
62     while (Pos < int(Limit)) {
63       unsigned Reg = Order[Pos++];
64       if (!isHint(Reg))
65         return Reg;
66     }
67     return 0;
68   }
69 
70   /// As next(), but allow duplicates to be returned, and stop before the
71   /// Limit'th register in the RegisterClassInfo allocation order.
72   ///
73   /// This can produce more than Limit registers if there are hints.
nextWithDups(unsigned Limit)74   unsigned nextWithDups(unsigned Limit) {
75     if (Pos < 0)
76       return Hints.end()[Pos++];
77     if (HardHints)
78       return 0;
79     if (Pos < int(Limit))
80       return Order[Pos++];
81     return 0;
82   }
83 
84   /// Start over from the beginning.
rewind()85   void rewind() { Pos = -int(Hints.size()); }
86 
87   /// Return true if the last register returned from next() was a preferred register.
isHint()88   bool isHint() const { return Pos <= 0; }
89 
90   /// Return true if PhysReg is a preferred register.
isHint(unsigned PhysReg)91   bool isHint(unsigned PhysReg) const { return is_contained(Hints, PhysReg); }
92 };
93 
94 } // end namespace llvm
95 
96 #endif
97