1//===- BitTracker.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_LIB_TARGET_HEXAGON_BITTRACKER_H
10#define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
11
12#include "llvm/ADT/DenseSet.h"
13#include "llvm/ADT/SetVector.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/CodeGen/MachineInstr.h"
16#include "llvm/CodeGen/MachineOperand.h"
17#include <map>
18#include <queue>
19#include <set>
20
21namespace llvm {
22
23class BitVector;
24class ConstantInt;
25class MachineRegisterInfo;
26class MachineBasicBlock;
27class MachineFunction;
28class raw_ostream;
29class MCRegisterClass;
30using TargetRegisterClass = MCRegisterClass;
31class TargetRegisterInfo;
32
33struct BitTracker {
34 struct BitRef;
35 struct RegisterRef;
36 struct BitValue;
37 struct BitMask;
38 struct RegisterCell;
39 struct MachineEvaluator;
40
41 using BranchTargetList = SetVector<const MachineBasicBlock *>;
42 using CellMapType = std::map<unsigned, RegisterCell>;
43
44 BitTracker(const MachineEvaluator &E, MachineFunction &F);
45 ~BitTracker();
46
47 void run();
48 void trace(bool On = false) { Trace = On; }
49 bool has(unsigned Reg) const;
50 const RegisterCell &lookup(unsigned Reg) const;
51 RegisterCell get(RegisterRef RR) const;
52 void put(RegisterRef RR, const RegisterCell &RC);
53 void subst(RegisterRef OldRR, RegisterRef NewRR);
54 bool reached(const MachineBasicBlock *B) const;
55 void visit(const MachineInstr &MI);
56
57 void print_cells(raw_ostream &OS) const;
58
59private:
60 void visitPHI(const MachineInstr &PI);
61 void visitNonBranch(const MachineInstr &MI);
62 void visitBranchesFrom(const MachineInstr &BI);
63 void visitUsesOf(Register Reg);
64
65 using CFGEdge = std::pair<int, int>;
66 using EdgeSetType = std::set<CFGEdge>;
67 using InstrSetType = std::set<const MachineInstr *>;
68 using EdgeQueueType = std::queue<CFGEdge>;
69
70 // Priority queue of instructions using modified registers, ordered by
71 // their relative position in a basic block.
72 struct UseQueueType {
73 UseQueueType() : Uses(Dist) {}
74
75 unsigned size() const {
76 return Uses.size();
77 }
78 bool empty() const {
79 return size() == 0;
80 }
81 MachineInstr *front() const {
82 return Uses.top();
83 }
84 void push(MachineInstr *MI) {
85 if (Set.insert(V: MI).second)
86 Uses.push(x: MI);
87 }
88 void pop() {
89 Set.erase(V: front());
90 Uses.pop();
91 }
92 void reset() {
93 Dist.clear();
94 }
95 private:
96 struct Cmp {
97 Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {}
98 bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
99 DenseMap<const MachineInstr*,unsigned> &Dist;
100 };
101 DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries.
102 DenseMap<const MachineInstr*,unsigned> Dist;
103 std::priority_queue<MachineInstr *, std::vector<MachineInstr *>, Cmp> Uses;
104 };
105
106 void reset();
107 void runEdgeQueue(BitVector &BlockScanned);
108 void runUseQueue();
109
110 const MachineEvaluator &ME;
111 MachineFunction &MF;
112 MachineRegisterInfo &MRI;
113 CellMapType &Map;
114
115 EdgeSetType EdgeExec; // Executable flow graph edges.
116 InstrSetType InstrExec; // Executable instructions.
117 UseQueueType UseQ; // Work queue of register uses.
118 EdgeQueueType FlowQ; // Work queue of CFG edges.
119 DenseSet<unsigned> ReachedBB; // Cache of reached blocks.
120 bool Trace; // Enable tracing for debugging.
121};
122
123// Abstraction of a reference to bit at position Pos from a register Reg.
124struct BitTracker::BitRef {
125 BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {}
126
127 bool operator== (const BitRef &BR) const {
128 // If Reg is 0, disregard Pos.
129 return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos);
130 }
131
132 Register Reg;
133 uint16_t Pos;
134};
135
136// Abstraction of a register reference in MachineOperand. It contains the
137// register number and the subregister index.
138// FIXME: Consolidate duplicate definitions of RegisterRef
139struct BitTracker::RegisterRef {
140 RegisterRef(Register R = 0, unsigned S = 0) : Reg(R), Sub(S) {}
141 RegisterRef(const MachineOperand &MO)
142 : Reg(MO.getReg()), Sub(MO.getSubReg()) {}
143
144 Register Reg;
145 unsigned Sub;
146};
147
148// Value that a single bit can take. This is outside of the context of
149// any register, it is more of an abstraction of the two-element set of
150// possible bit values. One extension here is the "Ref" type, which
151// indicates that this bit takes the same value as the bit described by
152// RefInfo.
153struct BitTracker::BitValue {
154 enum ValueType {
155 Top, // Bit not yet defined.
156 Zero, // Bit = 0.
157 One, // Bit = 1.
158 Ref // Bit value same as the one described in RefI.
159 // Conceptually, there is no explicit "bottom" value: the lattice's
160 // bottom will be expressed as a "ref to itself", which, in the context
161 // of registers, could be read as "this value of this bit is defined by
162 // this bit".
163 // The ordering is:
164 // x <= Top,
165 // Self <= x, where "Self" is "ref to itself".
166 // This makes the value lattice different for each virtual register
167 // (even for each bit in the same virtual register), since the "bottom"
168 // for one register will be a simple "ref" for another register.
169 // Since we do not store the "Self" bit and register number, the meet
170 // operation will need to take it as a parameter.
171 //
172 // In practice there is a special case for values that are not associa-
173 // ted with any specific virtual register. An example would be a value
174 // corresponding to a bit of a physical register, or an intermediate
175 // value obtained in some computation (such as instruction evaluation).
176 // Such cases are identical to the usual Ref type, but the register
177 // number is 0. In such case the Pos field of the reference is ignored.
178 //
179 // What is worthy of notice is that in value V (that is a "ref"), as long
180 // as the RefI.Reg is not 0, it may actually be the same register as the
181 // one in which V will be contained. If the RefI.Pos refers to the posi-
182 // tion of V, then V is assumed to be "bottom" (as a "ref to itself"),
183 // otherwise V is taken to be identical to the referenced bit of the
184 // same register.
185 // If RefI.Reg is 0, however, such a reference to the same register is
186 // not possible. Any value V that is a "ref", and whose RefI.Reg is 0
187 // is treated as "bottom".
188 };
189 ValueType Type;
190 BitRef RefI;
191
192 BitValue(ValueType T = Top) : Type(T) {}
193 BitValue(bool B) : Type(B ? One : Zero) {}
194 BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {}
195
196 bool operator== (const BitValue &V) const {
197 if (Type != V.Type)
198 return false;
199 if (Type == Ref && !(RefI == V.RefI))
200 return false;
201 return true;
202 }
203 bool operator!= (const BitValue &V) const {
204 return !operator==(V);
205 }
206
207 bool is(unsigned T) const {
208 assert(T == 0 || T == 1);
209 return T == 0 ? Type == Zero
210 : (T == 1 ? Type == One : false);
211 }
212
213 // The "meet" operation is the "." operation in a semilattice (L, ., T, B):
214 // (1) x.x = x
215 // (2) x.y = y.x
216 // (3) x.(y.z) = (x.y).z
217 // (4) x.T = x (i.e. T = "top")
218 // (5) x.B = B (i.e. B = "bottom")
219 //
220 // This "meet" function will update the value of the "*this" object with
221 // the newly calculated one, and return "true" if the value of *this has
222 // changed, and "false" otherwise.
223 // To prove that it satisfies the conditions (1)-(5), it is sufficient
224 // to show that a relation
225 // x <= y <=> x.y = x
226 // defines a partial order (i.e. that "meet" is same as "infimum").
227 bool meet(const BitValue &V, const BitRef &Self) {
228 // First, check the cases where there is nothing to be done.
229 if (Type == Ref && RefI == Self) // Bottom.meet(V) = Bottom (i.e. This)
230 return false;
231 if (V.Type == Top) // This.meet(Top) = This
232 return false;
233 if (*this == V) // This.meet(This) = This
234 return false;
235
236 // At this point, we know that the value of "this" will change.
237 // If it is Top, it will become the same as V, otherwise it will
238 // become "bottom" (i.e. Self).
239 if (Type == Top) {
240 Type = V.Type;
241 RefI = V.RefI; // This may be irrelevant, but copy anyway.
242 return true;
243 }
244 // Become "bottom".
245 Type = Ref;
246 RefI = Self;
247 return true;
248 }
249
250 // Create a reference to the bit value V.
251 static BitValue ref(const BitValue &V);
252 // Create a "self".
253 static BitValue self(const BitRef &Self = BitRef());
254
255 bool num() const {
256 return Type == Zero || Type == One;
257 }
258
259 operator bool() const {
260 assert(Type == Zero || Type == One);
261 return Type == One;
262 }
263
264 friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV);
265};
266
267// This operation must be idempotent, i.e. ref(ref(V)) == ref(V).
268inline BitTracker::BitValue
269BitTracker::BitValue::ref(const BitValue &V) {
270 if (V.Type != Ref)
271 return BitValue(V.Type);
272 if (V.RefI.Reg != 0)
273 return BitValue(V.RefI.Reg, V.RefI.Pos);
274 return self();
275}
276
277inline BitTracker::BitValue
278BitTracker::BitValue::self(const BitRef &Self) {
279 return BitValue(Self.Reg, Self.Pos);
280}
281
282// A sequence of bits starting from index B up to and including index E.
283// If E < B, the mask represents two sections: [0..E] and [B..W) where
284// W is the width of the register.
285struct BitTracker::BitMask {
286 BitMask() = default;
287 BitMask(uint16_t b, uint16_t e) : B(b), E(e) {}
288
289 uint16_t first() const { return B; }
290 uint16_t last() const { return E; }
291
292private:
293 uint16_t B = 0;
294 uint16_t E = 0;
295};
296
297// Representation of a register: a list of BitValues.
298struct BitTracker::RegisterCell {
299 RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {}
300
301 uint16_t width() const {
302 return Bits.size();
303 }
304
305 const BitValue &operator[](uint16_t BitN) const {
306 assert(BitN < Bits.size());
307 return Bits[BitN];
308 }
309 BitValue &operator[](uint16_t BitN) {
310 assert(BitN < Bits.size());
311 return Bits[BitN];
312 }
313
314 bool meet(const RegisterCell &RC, Register SelfR);
315 RegisterCell &insert(const RegisterCell &RC, const BitMask &M);
316 RegisterCell extract(const BitMask &M) const; // Returns a new cell.
317 RegisterCell &rol(uint16_t Sh); // Rotate left.
318 RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V);
319 RegisterCell &cat(const RegisterCell &RC); // Concatenate.
320 uint16_t cl(bool B) const;
321 uint16_t ct(bool B) const;
322
323 bool operator== (const RegisterCell &RC) const;
324 bool operator!= (const RegisterCell &RC) const {
325 return !operator==(RC);
326 }
327
328 // Replace the ref-to-reg-0 bit values with the given register.
329 RegisterCell &regify(unsigned R);
330
331 // Generate a "ref" cell for the corresponding register. In the resulting
332 // cell each bit will be described as being the same as the corresponding
333 // bit in register Reg (i.e. the cell is "defined" by register Reg).
334 static RegisterCell self(unsigned Reg, uint16_t Width);
335 // Generate a "top" cell of given size.
336 static RegisterCell top(uint16_t Width);
337 // Generate a cell that is a "ref" to another cell.
338 static RegisterCell ref(const RegisterCell &C);
339
340private:
341 // The DefaultBitN is here only to avoid frequent reallocation of the
342 // memory in the vector.
343 static const unsigned DefaultBitN = 32;
344 using BitValueList = SmallVector<BitValue, DefaultBitN>;
345 BitValueList Bits;
346
347 friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC);
348};
349
350inline bool BitTracker::has(unsigned Reg) const {
351 return Map.find(x: Reg) != Map.end();
352}
353
354inline const BitTracker::RegisterCell&
355BitTracker::lookup(unsigned Reg) const {
356 CellMapType::const_iterator F = Map.find(x: Reg);
357 assert(F != Map.end());
358 return F->second;
359}
360
361inline BitTracker::RegisterCell
362BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) {
363 RegisterCell RC(Width);
364 for (uint16_t i = 0; i < Width; ++i)
365 RC.Bits[i] = BitValue::self(Self: BitRef(Reg, i));
366 return RC;
367}
368
369inline BitTracker::RegisterCell
370BitTracker::RegisterCell::top(uint16_t Width) {
371 RegisterCell RC(Width);
372 for (uint16_t i = 0; i < Width; ++i)
373 RC.Bits[i] = BitValue(BitValue::Top);
374 return RC;
375}
376
377inline BitTracker::RegisterCell
378BitTracker::RegisterCell::ref(const RegisterCell &C) {
379 uint16_t W = C.width();
380 RegisterCell RC(W);
381 for (unsigned i = 0; i < W; ++i)
382 RC[i] = BitValue::ref(V: C[i]);
383 return RC;
384}
385
386// A class to evaluate target's instructions and update the cell maps.
387// This is used internally by the bit tracker. A target that wants to
388// utilize this should implement the evaluation functions (noted below)
389// in a subclass of this class.
390struct BitTracker::MachineEvaluator {
391 MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M)
392 : TRI(T), MRI(M) {}
393 virtual ~MachineEvaluator() = default;
394
395 uint16_t getRegBitWidth(const RegisterRef &RR) const;
396
397 RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const;
398 void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const;
399
400 // A result of any operation should use refs to the source cells, not
401 // the cells directly. This function is a convenience wrapper to quickly
402 // generate a ref for a cell corresponding to a register reference.
403 RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const {
404 RegisterCell RC = getCell(RR, M);
405 return RegisterCell::ref(C: RC);
406 }
407
408 // Helper functions.
409 // Check if a cell is an immediate value (i.e. all bits are either 0 or 1).
410 bool isInt(const RegisterCell &A) const;
411 // Convert cell to an immediate value.
412 uint64_t toInt(const RegisterCell &A) const;
413
414 // Generate cell from an immediate value.
415 RegisterCell eIMM(int64_t V, uint16_t W) const;
416 RegisterCell eIMM(const ConstantInt *CI) const;
417
418 // Arithmetic.
419 RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const;
420 RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const;
421 RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const;
422 RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const;
423
424 // Shifts.
425 RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const;
426 RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const;
427 RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const;
428
429 // Logical.
430 RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const;
431 RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const;
432 RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const;
433 RegisterCell eNOT(const RegisterCell &A1) const;
434
435 // Set bit, clear bit.
436 RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const;
437 RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const;
438
439 // Count leading/trailing bits (zeros/ones).
440 RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const;
441 RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const;
442
443 // Sign/zero extension.
444 RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const;
445 RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const;
446
447 // Extract/insert
448 // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1.
449 // INS R,S,b: take R and replace bits starting from b with S.
450 RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const;
451 RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2,
452 uint16_t AtN) const;
453
454 // User-provided functions for individual targets:
455
456 // Return a sub-register mask that indicates which bits in Reg belong
457 // to the subregister Sub. These bits are assumed to be contiguous in
458 // the super-register, and have the same ordering in the sub-register
459 // as in the super-register. It is valid to call this function with
460 // Sub == 0, in this case, the function should return a mask that spans
461 // the entire register Reg (which is what the default implementation
462 // does).
463 virtual BitMask mask(Register Reg, unsigned Sub) const;
464 // Indicate whether a given register class should be tracked.
465 virtual bool track(const TargetRegisterClass *RC) const { return true; }
466 // Evaluate a non-branching machine instruction, given the cell map with
467 // the input values. Place the results in the Outputs map. Return "true"
468 // if evaluation succeeded, "false" otherwise.
469 virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs,
470 CellMapType &Outputs) const;
471 // Evaluate a branch, given the cell map with the input values. Fill out
472 // a list of all possible branch targets and indicate (through a flag)
473 // whether the branch could fall-through. Return "true" if this information
474 // has been successfully computed, "false" otherwise.
475 virtual bool evaluate(const MachineInstr &BI, const CellMapType &Inputs,
476 BranchTargetList &Targets, bool &FallsThru) const = 0;
477 // Given a register class RC, return a register class that should be assumed
478 // when a register from class RC is used with a subregister of index Idx.
479 virtual const TargetRegisterClass&
480 composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const {
481 if (Idx == 0)
482 return RC;
483 llvm_unreachable("Unimplemented composeWithSubRegIndex");
484 }
485 // Return the size in bits of the physical register Reg.
486 virtual uint16_t getPhysRegBitWidth(MCRegister Reg) const;
487
488 const TargetRegisterInfo &TRI;
489 MachineRegisterInfo &MRI;
490};
491
492} // end namespace llvm
493
494#endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
495