1 //===- llvm/CodeGen/DbgEntityHistoryCalculator.h ----------------*- 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 #ifndef LLVM_CODEGEN_DBGENTITYHISTORYCALCULATOR_H
10 #define LLVM_CODEGEN_DBGENTITYHISTORYCALCULATOR_H
11 
12 #include "llvm/ADT/MapVector.h"
13 #include "llvm/ADT/PointerIntPair.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include <utility>
16 
17 namespace llvm {
18 
19 class DILocation;
20 class LexicalScopes;
21 class DINode;
22 class MachineFunction;
23 class MachineInstr;
24 class TargetRegisterInfo;
25 
26 /// Record instruction ordering so we can query their relative positions within
27 /// a function. Meta instructions are given the same ordinal as the preceding
28 /// non-meta instruction. Class state is invalid if MF is modified after
29 /// calling initialize.
30 class InstructionOrdering {
31 public:
32   void initialize(const MachineFunction &MF);
33   void clear() { InstNumberMap.clear(); }
34 
35   /// Check if instruction \p A comes before \p B, where \p A and \p B both
36   /// belong to the MachineFunction passed to initialize().
37   bool isBefore(const MachineInstr *A, const MachineInstr *B) const;
38 
39 private:
40   /// Each instruction is assigned an order number.
41   DenseMap<const MachineInstr *, unsigned> InstNumberMap;
42 };
43 
44 /// For each user variable, keep a list of instruction ranges where this
45 /// variable is accessible. The variables are listed in order of appearance.
46 class DbgValueHistoryMap {
47 public:
48   /// Index in the entry vector.
49   typedef size_t EntryIndex;
50 
51   /// Special value to indicate that an entry is valid until the end of the
52   /// function.
53   static const EntryIndex NoEntry = std::numeric_limits<EntryIndex>::max();
54 
55   /// Specifies a change in a variable's debug value history.
56   ///
57   /// There exist two types of entries:
58   ///
59   /// * Debug value entry:
60   ///
61   ///   A new debug value becomes live. If the entry's \p EndIndex is \p NoEntry,
62   ///   the value is valid until the end of the function. For other values, the
63   ///   index points to the entry in the entry vector that ends this debug
64   ///   value. The ending entry can either be an overlapping debug value, or
65   ///   an instruction that clobbers the value.
66   ///
67   /// * Clobbering entry:
68   ///
69   ///   This entry's instruction clobbers one or more preceding
70   ///   register-described debug values that have their end index
71   ///   set to this entry's position in the entry vector.
72   class Entry {
73     friend DbgValueHistoryMap;
74 
75   public:
76     enum EntryKind { DbgValue, Clobber };
77 
78     Entry(const MachineInstr *Instr, EntryKind Kind)
79         : Instr(Instr, Kind), EndIndex(NoEntry) {}
80 
81     const MachineInstr *getInstr() const { return Instr.getPointer(); }
82     EntryIndex getEndIndex() const { return EndIndex; }
83     EntryKind getEntryKind() const { return Instr.getInt(); }
84 
85     bool isClobber() const { return getEntryKind() == Clobber; }
86     bool isDbgValue() const { return getEntryKind() == DbgValue; }
87     bool isClosed() const { return EndIndex != NoEntry; }
88 
89     void endEntry(EntryIndex EndIndex);
90 
91   private:
92     PointerIntPair<const MachineInstr *, 1, EntryKind> Instr;
93     EntryIndex EndIndex;
94   };
95   using Entries = SmallVector<Entry, 4>;
96   using InlinedEntity = std::pair<const DINode *, const DILocation *>;
97   using EntriesMap = MapVector<InlinedEntity, Entries>;
98 
99 private:
100   EntriesMap VarEntries;
101 
102 public:
103   bool startDbgValue(InlinedEntity Var, const MachineInstr &MI,
104                      EntryIndex &NewIndex);
105   EntryIndex startClobber(InlinedEntity Var, const MachineInstr &MI);
106 
107   Entry &getEntry(InlinedEntity Var, EntryIndex Index) {
108     auto &Entries = VarEntries[Var];
109     return Entries[Index];
110   }
111 
112   /// Test whether a vector of entries features any non-empty locations. It
113   /// could have no entries, or only DBG_VALUE $noreg entries.
114   bool hasNonEmptyLocation(const Entries &Entries) const;
115 
116   /// Drop location ranges which exist entirely outside each variable's scope.
117   void trimLocationRanges(const MachineFunction &MF, LexicalScopes &LScopes,
118                           const InstructionOrdering &Ordering);
119   bool empty() const { return VarEntries.empty(); }
120   void clear() { VarEntries.clear(); }
121   EntriesMap::const_iterator begin() const { return VarEntries.begin(); }
122   EntriesMap::const_iterator end() const { return VarEntries.end(); }
123 
124 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
125   LLVM_DUMP_METHOD void dump() const;
126 #endif
127 };
128 
129 /// For each inlined instance of a source-level label, keep the corresponding
130 /// DBG_LABEL instruction. The DBG_LABEL instruction could be used to generate
131 /// a temporary (assembler) label before it.
132 class DbgLabelInstrMap {
133 public:
134   using InlinedEntity = std::pair<const DINode *, const DILocation *>;
135   using InstrMap = MapVector<InlinedEntity, const MachineInstr *>;
136 
137 private:
138   InstrMap LabelInstr;
139 
140 public:
141   void  addInstr(InlinedEntity Label, const MachineInstr &MI);
142 
143   bool empty() const { return LabelInstr.empty(); }
144   void clear() { LabelInstr.clear(); }
145   InstrMap::const_iterator begin() const { return LabelInstr.begin(); }
146   InstrMap::const_iterator end() const { return LabelInstr.end(); }
147 };
148 
149 void calculateDbgEntityHistory(const MachineFunction *MF,
150                                const TargetRegisterInfo *TRI,
151                                DbgValueHistoryMap &DbgValues,
152                                DbgLabelInstrMap &DbgLabels);
153 
154 } // end namespace llvm
155 
156 #endif // LLVM_CODEGEN_DBGENTITYHISTORYCALCULATOR_H
157