1 //===- BitTracker.h ---------------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
11 #define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
13 #include "llvm/ADT/DenseSet.h"
14 #include "llvm/ADT/SetVector.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/CodeGen/MachineOperand.h"
28 class MachineRegisterInfo;
29 class MachineBasicBlock;
30 class MachineFunction;
33 class TargetRegisterClass;
34 class TargetRegisterInfo;
42 struct MachineEvaluator;
44 using BranchTargetList = SetVector<const MachineBasicBlock *>;
45 using CellMapType = std::map<unsigned, RegisterCell>;
47 BitTracker(const MachineEvaluator &E, MachineFunction &F);
51 void trace(bool On = false) { Trace = On; }
52 bool has(unsigned Reg) const;
53 const RegisterCell &lookup(unsigned Reg) const;
54 RegisterCell get(RegisterRef RR) const;
55 void put(RegisterRef RR, const RegisterCell &RC);
56 void subst(RegisterRef OldRR, RegisterRef NewRR);
57 bool reached(const MachineBasicBlock *B) const;
58 void visit(const MachineInstr &MI);
60 void print_cells(raw_ostream &OS) const;
63 void visitPHI(const MachineInstr &PI);
64 void visitNonBranch(const MachineInstr &MI);
65 void visitBranchesFrom(const MachineInstr &BI);
66 void visitUsesOf(unsigned Reg);
68 using CFGEdge = std::pair<int, int>;
69 using EdgeSetType = std::set<CFGEdge>;
70 using InstrSetType = std::set<const MachineInstr *>;
71 using EdgeQueueType = std::queue<CFGEdge>;
73 // Priority queue of instructions using modified registers, ordered by
74 // their relative position in a basic block.
76 unsigned size() const {
82 MachineInstr *front() const {
85 void push(MachineInstr *MI) {
86 if (Set.insert(MI).second)
95 bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
97 std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses;
98 DenseSet<MachineInstr*> Set; // Set to avoid adding duplicate entries.
102 void runEdgeQueue(BitVector &BlockScanned);
105 const MachineEvaluator &ME;
107 MachineRegisterInfo &MRI;
110 EdgeSetType EdgeExec; // Executable flow graph edges.
111 InstrSetType InstrExec; // Executable instructions.
112 UseQueueType UseQ; // Work queue of register uses.
113 EdgeQueueType FlowQ; // Work queue of CFG edges.
114 DenseSet<unsigned> ReachedBB; // Cache of reached blocks.
115 bool Trace; // Enable tracing for debugging.
118 // Abstraction of a reference to bit at position Pos from a register Reg.
119 struct BitTracker::BitRef {
120 BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {}
122 bool operator== (const BitRef &BR) const {
123 // If Reg is 0, disregard Pos.
124 return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos);
131 // Abstraction of a register reference in MachineOperand. It contains the
132 // register number and the subregister index.
133 struct BitTracker::RegisterRef {
134 RegisterRef(unsigned R = 0, unsigned S = 0)
136 RegisterRef(const MachineOperand &MO)
137 : Reg(MO.getReg()), Sub(MO.getSubReg()) {}
142 // Value that a single bit can take. This is outside of the context of
143 // any register, it is more of an abstraction of the two-element set of
144 // possible bit values. One extension here is the "Ref" type, which
145 // indicates that this bit takes the same value as the bit described by
147 struct BitTracker::BitValue {
149 Top, // Bit not yet defined.
152 Ref // Bit value same as the one described in RefI.
153 // Conceptually, there is no explicit "bottom" value: the lattice's
154 // bottom will be expressed as a "ref to itself", which, in the context
155 // of registers, could be read as "this value of this bit is defined by
159 // Self <= x, where "Self" is "ref to itself".
160 // This makes the value lattice different for each virtual register
161 // (even for each bit in the same virtual register), since the "bottom"
162 // for one register will be a simple "ref" for another register.
163 // Since we do not store the "Self" bit and register number, the meet
164 // operation will need to take it as a parameter.
166 // In practice there is a special case for values that are not associa-
167 // ted with any specific virtual register. An example would be a value
168 // corresponding to a bit of a physical register, or an intermediate
169 // value obtained in some computation (such as instruction evaluation).
170 // Such cases are identical to the usual Ref type, but the register
171 // number is 0. In such case the Pos field of the reference is ignored.
173 // What is worthy of notice is that in value V (that is a "ref"), as long
174 // as the RefI.Reg is not 0, it may actually be the same register as the
175 // one in which V will be contained. If the RefI.Pos refers to the posi-
176 // tion of V, then V is assumed to be "bottom" (as a "ref to itself"),
177 // otherwise V is taken to be identical to the referenced bit of the
179 // If RefI.Reg is 0, however, such a reference to the same register is
180 // not possible. Any value V that is a "ref", and whose RefI.Reg is 0
181 // is treated as "bottom".
186 BitValue(ValueType T = Top) : Type(T) {}
187 BitValue(bool B) : Type(B ? One : Zero) {}
188 BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {}
190 bool operator== (const BitValue &V) const {
193 if (Type == Ref && !(RefI == V.RefI))
197 bool operator!= (const BitValue &V) const {
198 return !operator==(V);
201 bool is(unsigned T) const {
202 assert(T == 0 || T == 1);
203 return T == 0 ? Type == Zero
204 : (T == 1 ? Type == One : false);
207 // The "meet" operation is the "." operation in a semilattice (L, ., T, B):
210 // (3) x.(y.z) = (x.y).z
211 // (4) x.T = x (i.e. T = "top")
212 // (5) x.B = B (i.e. B = "bottom")
214 // This "meet" function will update the value of the "*this" object with
215 // the newly calculated one, and return "true" if the value of *this has
216 // changed, and "false" otherwise.
217 // To prove that it satisfies the conditions (1)-(5), it is sufficient
218 // to show that a relation
219 // x <= y <=> x.y = x
220 // defines a partial order (i.e. that "meet" is same as "infimum").
221 bool meet(const BitValue &V, const BitRef &Self) {
222 // First, check the cases where there is nothing to be done.
223 if (Type == Ref && RefI == Self) // Bottom.meet(V) = Bottom (i.e. This)
225 if (V.Type == Top) // This.meet(Top) = This
227 if (*this == V) // This.meet(This) = This
230 // At this point, we know that the value of "this" will change.
231 // If it is Top, it will become the same as V, otherwise it will
232 // become "bottom" (i.e. Self).
235 RefI = V.RefI; // This may be irrelevant, but copy anyway.
244 // Create a reference to the bit value V.
245 static BitValue ref(const BitValue &V);
247 static BitValue self(const BitRef &Self = BitRef());
250 return Type == Zero || Type == One;
253 operator bool() const {
254 assert(Type == Zero || Type == One);
258 friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV);
261 // This operation must be idempotent, i.e. ref(ref(V)) == ref(V).
262 inline BitTracker::BitValue
263 BitTracker::BitValue::ref(const BitValue &V) {
265 return BitValue(V.Type);
267 return BitValue(V.RefI.Reg, V.RefI.Pos);
271 inline BitTracker::BitValue
272 BitTracker::BitValue::self(const BitRef &Self) {
273 return BitValue(Self.Reg, Self.Pos);
276 // A sequence of bits starting from index B up to and including index E.
277 // If E < B, the mask represents two sections: [0..E] and [B..W) where
278 // W is the width of the register.
279 struct BitTracker::BitMask {
281 BitMask(uint16_t b, uint16_t e) : B(b), E(e) {}
283 uint16_t first() const { return B; }
284 uint16_t last() const { return E; }
291 // Representation of a register: a list of BitValues.
292 struct BitTracker::RegisterCell {
293 RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {}
295 uint16_t width() const {
299 const BitValue &operator[](uint16_t BitN) const {
300 assert(BitN < Bits.size());
303 BitValue &operator[](uint16_t BitN) {
304 assert(BitN < Bits.size());
308 bool meet(const RegisterCell &RC, unsigned SelfR);
309 RegisterCell &insert(const RegisterCell &RC, const BitMask &M);
310 RegisterCell extract(const BitMask &M) const; // Returns a new cell.
311 RegisterCell &rol(uint16_t Sh); // Rotate left.
312 RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V);
313 RegisterCell &cat(const RegisterCell &RC); // Concatenate.
314 uint16_t cl(bool B) const;
315 uint16_t ct(bool B) const;
317 bool operator== (const RegisterCell &RC) const;
318 bool operator!= (const RegisterCell &RC) const {
319 return !operator==(RC);
322 // Replace the ref-to-reg-0 bit values with the given register.
323 RegisterCell ®ify(unsigned R);
325 // Generate a "ref" cell for the corresponding register. In the resulting
326 // cell each bit will be described as being the same as the corresponding
327 // bit in register Reg (i.e. the cell is "defined" by register Reg).
328 static RegisterCell self(unsigned Reg, uint16_t Width);
329 // Generate a "top" cell of given size.
330 static RegisterCell top(uint16_t Width);
331 // Generate a cell that is a "ref" to another cell.
332 static RegisterCell ref(const RegisterCell &C);
335 // The DefaultBitN is here only to avoid frequent reallocation of the
336 // memory in the vector.
337 static const unsigned DefaultBitN = 32;
338 using BitValueList = SmallVector<BitValue, DefaultBitN>;
341 friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC);
344 inline bool BitTracker::has(unsigned Reg) const {
345 return Map.find(Reg) != Map.end();
348 inline const BitTracker::RegisterCell&
349 BitTracker::lookup(unsigned Reg) const {
350 CellMapType::const_iterator F = Map.find(Reg);
351 assert(F != Map.end());
355 inline BitTracker::RegisterCell
356 BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) {
357 RegisterCell RC(Width);
358 for (uint16_t i = 0; i < Width; ++i)
359 RC.Bits[i] = BitValue::self(BitRef(Reg, i));
363 inline BitTracker::RegisterCell
364 BitTracker::RegisterCell::top(uint16_t Width) {
365 RegisterCell RC(Width);
366 for (uint16_t i = 0; i < Width; ++i)
367 RC.Bits[i] = BitValue(BitValue::Top);
371 inline BitTracker::RegisterCell
372 BitTracker::RegisterCell::ref(const RegisterCell &C) {
373 uint16_t W = C.width();
375 for (unsigned i = 0; i < W; ++i)
376 RC[i] = BitValue::ref(C[i]);
380 // A class to evaluate target's instructions and update the cell maps.
381 // This is used internally by the bit tracker. A target that wants to
382 // utilize this should implement the evaluation functions (noted below)
383 // in a subclass of this class.
384 struct BitTracker::MachineEvaluator {
385 MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M)
387 virtual ~MachineEvaluator() = default;
389 uint16_t getRegBitWidth(const RegisterRef &RR) const;
391 RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const;
392 void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const;
394 // A result of any operation should use refs to the source cells, not
395 // the cells directly. This function is a convenience wrapper to quickly
396 // generate a ref for a cell corresponding to a register reference.
397 RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const {
398 RegisterCell RC = getCell(RR, M);
399 return RegisterCell::ref(RC);
403 // Check if a cell is an immediate value (i.e. all bits are either 0 or 1).
404 bool isInt(const RegisterCell &A) const;
405 // Convert cell to an immediate value.
406 uint64_t toInt(const RegisterCell &A) const;
408 // Generate cell from an immediate value.
409 RegisterCell eIMM(int64_t V, uint16_t W) const;
410 RegisterCell eIMM(const ConstantInt *CI) const;
413 RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const;
414 RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const;
415 RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const;
416 RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const;
419 RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const;
420 RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const;
421 RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const;
424 RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const;
425 RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const;
426 RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const;
427 RegisterCell eNOT(const RegisterCell &A1) const;
429 // Set bit, clear bit.
430 RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const;
431 RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const;
433 // Count leading/trailing bits (zeros/ones).
434 RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const;
435 RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const;
437 // Sign/zero extension.
438 RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const;
439 RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const;
442 // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1.
443 // INS R,S,b: take R and replace bits starting from b with S.
444 RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const;
445 RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2,
448 // User-provided functions for individual targets:
450 // Return a sub-register mask that indicates which bits in Reg belong
451 // to the subregister Sub. These bits are assumed to be contiguous in
452 // the super-register, and have the same ordering in the sub-register
453 // as in the super-register. It is valid to call this function with
454 // Sub == 0, in this case, the function should return a mask that spans
455 // the entire register Reg (which is what the default implementation
457 virtual BitMask mask(unsigned Reg, unsigned Sub) const;
458 // Indicate whether a given register class should be tracked.
459 virtual bool track(const TargetRegisterClass *RC) const { return true; }
460 // Evaluate a non-branching machine instruction, given the cell map with
461 // the input values. Place the results in the Outputs map. Return "true"
462 // if evaluation succeeded, "false" otherwise.
463 virtual bool evaluate(const MachineInstr &MI, const CellMapType &Inputs,
464 CellMapType &Outputs) const;
465 // Evaluate a branch, given the cell map with the input values. Fill out
466 // a list of all possible branch targets and indicate (through a flag)
467 // whether the branch could fall-through. Return "true" if this information
468 // has been successfully computed, "false" otherwise.
469 virtual bool evaluate(const MachineInstr &BI, const CellMapType &Inputs,
470 BranchTargetList &Targets, bool &FallsThru) const = 0;
471 // Given a register class RC, return a register class that should be assumed
472 // when a register from class RC is used with a subregister of index Idx.
473 virtual const TargetRegisterClass&
474 composeWithSubRegIndex(const TargetRegisterClass &RC, unsigned Idx) const {
477 llvm_unreachable("Unimplemented composeWithSubRegIndex");
479 // Return the size in bits of the physical register Reg.
480 virtual uint16_t getPhysRegBitWidth(unsigned Reg) const;
482 const TargetRegisterInfo &TRI;
483 MachineRegisterInfo &MRI;
486 } // end namespace llvm
488 #endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H