Skip to content

Commit e53b31a

Browse files
author
Krzysztof Parzyszek
committedJul 7, 2015
[Hexagon] Implement bit-tracking facility with specifics for Hexagon
This includes code that is intended to be target-independent as well as the Hexagon-specific details. This is just the framework without any users. llvm-svn: 241595
·
llvmorg-22-initllvmorg-3.7.0-rc1
1 parent bfc481b commit e53b31a

File tree

5 files changed

+2832
-0
lines changed

5 files changed

+2832
-0
lines changed
 

‎llvm/lib/Target/Hexagon/BitTracker.cpp‎

Lines changed: 1133 additions & 0 deletions
Large diffs are not rendered by default.

‎llvm/lib/Target/Hexagon/BitTracker.h‎

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

‎llvm/lib/Target/Hexagon/CMakeLists.txt‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,9 @@ tablegen(LLVM HexagonGenSubtargetInfo.inc -gen-subtarget)
1212
add_public_tablegen_target(HexagonCommonTableGen)
1313

1414
add_llvm_target(HexagonCodeGen
15+
BitTracker.cpp
1516
HexagonAsmPrinter.cpp
17+
HexagonBitTracker.cpp
1618
HexagonCFGOptimizer.cpp
1719
HexagonCopyToCombine.cpp
1820
HexagonExpandCondsets.cpp

‎llvm/lib/Target/Hexagon/HexagonBitTracker.cpp‎

Lines changed: 1176 additions & 0 deletions
Large diffs are not rendered by default.

‎llvm/lib/Target/Hexagon/HexagonBitTracker.h‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
//===--- HexagonBitTracker.h ----------------------------------------------===//
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+
#ifndef HEXAGONBITTRACKER_H
11+
#define HEXAGONBITTRACKER_H
12+
13+
#include "BitTracker.h"
14+
#include "llvm/ADT/DenseMap.h"
15+
16+
namespace llvm {
17+
class HexagonInstrInfo;
18+
class HexagonRegisterInfo;
19+
}
20+
21+
struct HexagonEvaluator : public BitTracker::MachineEvaluator {
22+
typedef BitTracker::CellMapType CellMapType;
23+
typedef BitTracker::RegisterRef RegisterRef;
24+
typedef BitTracker::RegisterCell RegisterCell;
25+
typedef BitTracker::BranchTargetList BranchTargetList;
26+
27+
HexagonEvaluator(const llvm::HexagonRegisterInfo &tri,
28+
llvm::MachineRegisterInfo &mri, const llvm::HexagonInstrInfo &tii,
29+
llvm::MachineFunction &mf);
30+
31+
virtual bool evaluate(const llvm::MachineInstr *MI,
32+
const CellMapType &Inputs, CellMapType &Outputs) const;
33+
virtual bool evaluate(const llvm::MachineInstr *BI,
34+
const CellMapType &Inputs, BranchTargetList &Targets,
35+
bool &FallsThru) const;
36+
37+
virtual BitTracker::BitMask mask(unsigned Reg, unsigned Sub) const;
38+
39+
llvm::MachineFunction &MF;
40+
llvm::MachineFrameInfo &MFI;
41+
const llvm::HexagonInstrInfo &TII;
42+
43+
private:
44+
bool evaluateLoad(const llvm::MachineInstr *MI, const CellMapType &Inputs,
45+
CellMapType &Outputs) const;
46+
bool evaluateFormalCopy(const llvm::MachineInstr *MI,
47+
const CellMapType &Inputs, CellMapType &Outputs) const;
48+
49+
unsigned getNextPhysReg(unsigned PReg, unsigned Width) const;
50+
unsigned getVirtRegFor(unsigned PReg) const;
51+
52+
// Type of formal parameter extension.
53+
struct ExtType {
54+
enum { SExt, ZExt };
55+
char Type;
56+
uint16_t Width;
57+
ExtType() : Type(0), Width(0) {}
58+
ExtType(char t, uint16_t w) : Type(t), Width(w) {}
59+
};
60+
// Map VR -> extension type.
61+
typedef llvm::DenseMap<unsigned,ExtType> RegExtMap;
62+
RegExtMap VRX;
63+
};
64+
65+
#endif
66+

0 commit comments

Comments
 (0)
Please sign in to comment.