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