1286425Sdim//===--- BitTracker.h -----------------------------------------------------===// 2286425Sdim// 3286425Sdim// The LLVM Compiler Infrastructure 4286425Sdim// 5286425Sdim// This file is distributed under the University of Illinois Open Source 6286425Sdim// License. See LICENSE.TXT for details. 7286425Sdim// 8286425Sdim//===----------------------------------------------------------------------===// 9286425Sdim 10286425Sdim#ifndef BITTRACKER_H 11286425Sdim#define BITTRACKER_H 12286425Sdim 13286425Sdim#include "llvm/ADT/SetVector.h" 14286425Sdim#include "llvm/ADT/SmallVector.h" 15286425Sdim#include "llvm/CodeGen/MachineFunction.h" 16286425Sdim 17286425Sdim#include <map> 18286425Sdim#include <queue> 19286425Sdim#include <set> 20286425Sdim 21286425Sdimnamespace llvm { 22286425Sdim class ConstantInt; 23286425Sdim class MachineRegisterInfo; 24286425Sdim class MachineBasicBlock; 25286425Sdim class MachineInstr; 26286425Sdim class MachineOperand; 27286425Sdim class raw_ostream; 28286425Sdim 29286425Sdimstruct BitTracker { 30286425Sdim struct BitRef; 31286425Sdim struct RegisterRef; 32286425Sdim struct BitValue; 33286425Sdim struct BitMask; 34286425Sdim struct RegisterCell; 35286425Sdim struct MachineEvaluator; 36286425Sdim 37286425Sdim typedef SetVector<const MachineBasicBlock *> BranchTargetList; 38286425Sdim 39296417Sdim typedef std::map<unsigned, RegisterCell> CellMapType; 40286425Sdim 41286425Sdim BitTracker(const MachineEvaluator &E, MachineFunction &F); 42286425Sdim ~BitTracker(); 43286425Sdim 44286425Sdim void run(); 45286425Sdim void trace(bool On = false) { Trace = On; } 46286425Sdim bool has(unsigned Reg) const; 47286425Sdim const RegisterCell &lookup(unsigned Reg) const; 48286425Sdim RegisterCell get(RegisterRef RR) const; 49286425Sdim void put(RegisterRef RR, const RegisterCell &RC); 50286425Sdim void subst(RegisterRef OldRR, RegisterRef NewRR); 51286425Sdim bool reached(const MachineBasicBlock *B) const; 52286425Sdim 53286425Sdimprivate: 54286425Sdim void visitPHI(const MachineInstr *PI); 55286425Sdim void visitNonBranch(const MachineInstr *MI); 56286425Sdim void visitBranchesFrom(const MachineInstr *BI); 57286425Sdim void visitUsesOf(unsigned Reg); 58286425Sdim void reset(); 59286425Sdim 60286425Sdim typedef std::pair<int,int> CFGEdge; 61286425Sdim typedef std::set<CFGEdge> EdgeSetType; 62286425Sdim typedef std::set<const MachineInstr *> InstrSetType; 63286425Sdim typedef std::queue<CFGEdge> EdgeQueueType; 64286425Sdim 65286425Sdim EdgeSetType EdgeExec; // Executable flow graph edges. 66286425Sdim InstrSetType InstrExec; // Executable instructions. 67286425Sdim EdgeQueueType FlowQ; // Work queue of CFG edges. 68286425Sdim bool Trace; // Enable tracing for debugging. 69286425Sdim 70286425Sdim const MachineEvaluator &ME; 71286425Sdim MachineFunction &MF; 72286425Sdim MachineRegisterInfo &MRI; 73286425Sdim CellMapType ⤅ 74286425Sdim}; 75286425Sdim 76286425Sdim 77286425Sdim// Abstraction of a reference to bit at position Pos from a register Reg. 78286425Sdimstruct BitTracker::BitRef { 79286425Sdim BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {} 80286425Sdim bool operator== (const BitRef &BR) const { 81286425Sdim // If Reg is 0, disregard Pos. 82286425Sdim return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos); 83286425Sdim } 84286425Sdim unsigned Reg; 85286425Sdim uint16_t Pos; 86286425Sdim}; 87286425Sdim 88286425Sdim 89286425Sdim// Abstraction of a register reference in MachineOperand. It contains the 90286425Sdim// register number and the subregister index. 91286425Sdimstruct BitTracker::RegisterRef { 92286425Sdim RegisterRef(unsigned R = 0, unsigned S = 0) 93286425Sdim : Reg(R), Sub(S) {} 94286425Sdim RegisterRef(const MachineOperand &MO) 95286425Sdim : Reg(MO.getReg()), Sub(MO.getSubReg()) {} 96286425Sdim unsigned Reg, Sub; 97286425Sdim}; 98286425Sdim 99286425Sdim 100286425Sdim// Value that a single bit can take. This is outside of the context of 101286425Sdim// any register, it is more of an abstraction of the two-element set of 102286425Sdim// possible bit values. One extension here is the "Ref" type, which 103286425Sdim// indicates that this bit takes the same value as the bit described by 104286425Sdim// RefInfo. 105286425Sdimstruct BitTracker::BitValue { 106286425Sdim enum ValueType { 107286425Sdim Top, // Bit not yet defined. 108286425Sdim Zero, // Bit = 0. 109286425Sdim One, // Bit = 1. 110286425Sdim Ref // Bit value same as the one described in RefI. 111286425Sdim // Conceptually, there is no explicit "bottom" value: the lattice's 112286425Sdim // bottom will be expressed as a "ref to itself", which, in the context 113286425Sdim // of registers, could be read as "this value of this bit is defined by 114286425Sdim // this bit". 115286425Sdim // The ordering is: 116286425Sdim // x <= Top, 117286425Sdim // Self <= x, where "Self" is "ref to itself". 118286425Sdim // This makes the value lattice different for each virtual register 119286425Sdim // (even for each bit in the same virtual register), since the "bottom" 120286425Sdim // for one register will be a simple "ref" for another register. 121286425Sdim // Since we do not store the "Self" bit and register number, the meet 122286425Sdim // operation will need to take it as a parameter. 123286425Sdim // 124286425Sdim // In practice there is a special case for values that are not associa- 125286425Sdim // ted with any specific virtual register. An example would be a value 126286425Sdim // corresponding to a bit of a physical register, or an intermediate 127286425Sdim // value obtained in some computation (such as instruction evaluation). 128286425Sdim // Such cases are identical to the usual Ref type, but the register 129286425Sdim // number is 0. In such case the Pos field of the reference is ignored. 130286425Sdim // 131286425Sdim // What is worthy of notice is that in value V (that is a "ref"), as long 132286425Sdim // as the RefI.Reg is not 0, it may actually be the same register as the 133286425Sdim // one in which V will be contained. If the RefI.Pos refers to the posi- 134286425Sdim // tion of V, then V is assumed to be "bottom" (as a "ref to itself"), 135286425Sdim // otherwise V is taken to be identical to the referenced bit of the 136286425Sdim // same register. 137286425Sdim // If RefI.Reg is 0, however, such a reference to the same register is 138286425Sdim // not possible. Any value V that is a "ref", and whose RefI.Reg is 0 139286425Sdim // is treated as "bottom". 140286425Sdim }; 141286425Sdim ValueType Type; 142286425Sdim BitRef RefI; 143286425Sdim 144286425Sdim BitValue(ValueType T = Top) : Type(T) {} 145286425Sdim BitValue(bool B) : Type(B ? One : Zero) {} 146286425Sdim BitValue(unsigned Reg, uint16_t Pos) : Type(Ref), RefI(Reg, Pos) {} 147286425Sdim 148286425Sdim bool operator== (const BitValue &V) const { 149286425Sdim if (Type != V.Type) 150286425Sdim return false; 151286425Sdim if (Type == Ref && !(RefI == V.RefI)) 152286425Sdim return false; 153286425Sdim return true; 154286425Sdim } 155286425Sdim bool operator!= (const BitValue &V) const { 156286425Sdim return !operator==(V); 157286425Sdim } 158286425Sdim bool is(unsigned T) const { 159286425Sdim assert(T == 0 || T == 1); 160286425Sdim return T == 0 ? Type == Zero 161286425Sdim : (T == 1 ? Type == One : false); 162286425Sdim } 163286425Sdim 164286425Sdim // The "meet" operation is the "." operation in a semilattice (L, ., T, B): 165286425Sdim // (1) x.x = x 166286425Sdim // (2) x.y = y.x 167286425Sdim // (3) x.(y.z) = (x.y).z 168286425Sdim // (4) x.T = x (i.e. T = "top") 169286425Sdim // (5) x.B = B (i.e. B = "bottom") 170286425Sdim // 171286425Sdim // This "meet" function will update the value of the "*this" object with 172286425Sdim // the newly calculated one, and return "true" if the value of *this has 173286425Sdim // changed, and "false" otherwise. 174286425Sdim // To prove that it satisfies the conditions (1)-(5), it is sufficient 175286425Sdim // to show that a relation 176286425Sdim // x <= y <=> x.y = x 177286425Sdim // defines a partial order (i.e. that "meet" is same as "infimum"). 178286425Sdim bool meet(const BitValue &V, const BitRef &Self) { 179286425Sdim // First, check the cases where there is nothing to be done. 180286425Sdim if (Type == Ref && RefI == Self) // Bottom.meet(V) = Bottom (i.e. This) 181286425Sdim return false; 182286425Sdim if (V.Type == Top) // This.meet(Top) = This 183286425Sdim return false; 184286425Sdim if (*this == V) // This.meet(This) = This 185286425Sdim return false; 186286425Sdim 187286425Sdim // At this point, we know that the value of "this" will change. 188286425Sdim // If it is Top, it will become the same as V, otherwise it will 189286425Sdim // become "bottom" (i.e. Self). 190286425Sdim if (Type == Top) { 191286425Sdim Type = V.Type; 192286425Sdim RefI = V.RefI; // This may be irrelevant, but copy anyway. 193286425Sdim return true; 194286425Sdim } 195286425Sdim // Become "bottom". 196286425Sdim Type = Ref; 197286425Sdim RefI = Self; 198286425Sdim return true; 199286425Sdim } 200286425Sdim 201286425Sdim // Create a reference to the bit value V. 202286425Sdim static BitValue ref(const BitValue &V); 203286425Sdim // Create a "self". 204286425Sdim static BitValue self(const BitRef &Self = BitRef()); 205286425Sdim 206286425Sdim bool num() const { 207286425Sdim return Type == Zero || Type == One; 208286425Sdim } 209286425Sdim operator bool() const { 210286425Sdim assert(Type == Zero || Type == One); 211286425Sdim return Type == One; 212286425Sdim } 213286425Sdim 214286425Sdim friend raw_ostream &operator<<(raw_ostream &OS, const BitValue &BV); 215286425Sdim}; 216286425Sdim 217286425Sdim 218286425Sdim// This operation must be idempotent, i.e. ref(ref(V)) == ref(V). 219286425Sdiminline BitTracker::BitValue 220286425SdimBitTracker::BitValue::ref(const BitValue &V) { 221286425Sdim if (V.Type != Ref) 222286425Sdim return BitValue(V.Type); 223286425Sdim if (V.RefI.Reg != 0) 224286425Sdim return BitValue(V.RefI.Reg, V.RefI.Pos); 225286425Sdim return self(); 226286425Sdim} 227286425Sdim 228286425Sdim 229286425Sdiminline BitTracker::BitValue 230286425SdimBitTracker::BitValue::self(const BitRef &Self) { 231286425Sdim return BitValue(Self.Reg, Self.Pos); 232286425Sdim} 233286425Sdim 234286425Sdim 235286425Sdim// A sequence of bits starting from index B up to and including index E. 236286425Sdim// If E < B, the mask represents two sections: [0..E] and [B..W) where 237286425Sdim// W is the width of the register. 238286425Sdimstruct BitTracker::BitMask { 239286425Sdim BitMask() : B(0), E(0) {} 240286425Sdim BitMask(uint16_t b, uint16_t e) : B(b), E(e) {} 241286425Sdim uint16_t first() const { return B; } 242286425Sdim uint16_t last() const { return E; } 243286425Sdimprivate: 244286425Sdim uint16_t B, E; 245286425Sdim}; 246286425Sdim 247286425Sdim 248286425Sdim// Representation of a register: a list of BitValues. 249286425Sdimstruct BitTracker::RegisterCell { 250286425Sdim RegisterCell(uint16_t Width = DefaultBitN) : Bits(Width) {} 251286425Sdim 252286425Sdim uint16_t width() const { 253286425Sdim return Bits.size(); 254286425Sdim } 255286425Sdim const BitValue &operator[](uint16_t BitN) const { 256286425Sdim assert(BitN < Bits.size()); 257286425Sdim return Bits[BitN]; 258286425Sdim } 259286425Sdim BitValue &operator[](uint16_t BitN) { 260286425Sdim assert(BitN < Bits.size()); 261286425Sdim return Bits[BitN]; 262286425Sdim } 263286425Sdim 264286425Sdim bool meet(const RegisterCell &RC, unsigned SelfR); 265286425Sdim RegisterCell &insert(const RegisterCell &RC, const BitMask &M); 266286425Sdim RegisterCell extract(const BitMask &M) const; // Returns a new cell. 267286425Sdim RegisterCell &rol(uint16_t Sh); // Rotate left. 268286425Sdim RegisterCell &fill(uint16_t B, uint16_t E, const BitValue &V); 269286425Sdim RegisterCell &cat(const RegisterCell &RC); // Concatenate. 270286425Sdim uint16_t cl(bool B) const; 271286425Sdim uint16_t ct(bool B) const; 272286425Sdim 273286425Sdim bool operator== (const RegisterCell &RC) const; 274286425Sdim bool operator!= (const RegisterCell &RC) const { 275286425Sdim return !operator==(RC); 276286425Sdim } 277286425Sdim 278286425Sdim // Generate a "ref" cell for the corresponding register. In the resulting 279286425Sdim // cell each bit will be described as being the same as the corresponding 280286425Sdim // bit in register Reg (i.e. the cell is "defined" by register Reg). 281286425Sdim static RegisterCell self(unsigned Reg, uint16_t Width); 282286425Sdim // Generate a "top" cell of given size. 283286425Sdim static RegisterCell top(uint16_t Width); 284286425Sdim // Generate a cell that is a "ref" to another cell. 285286425Sdim static RegisterCell ref(const RegisterCell &C); 286286425Sdim 287286425Sdimprivate: 288286425Sdim // The DefaultBitN is here only to avoid frequent reallocation of the 289286425Sdim // memory in the vector. 290286425Sdim static const unsigned DefaultBitN = 32; 291286425Sdim typedef SmallVector<BitValue, DefaultBitN> BitValueList; 292286425Sdim BitValueList Bits; 293286425Sdim 294286425Sdim friend raw_ostream &operator<<(raw_ostream &OS, const RegisterCell &RC); 295286425Sdim}; 296286425Sdim 297286425Sdim 298286425Sdiminline bool BitTracker::has(unsigned Reg) const { 299286425Sdim return Map.find(Reg) != Map.end(); 300286425Sdim} 301286425Sdim 302286425Sdim 303286425Sdiminline const BitTracker::RegisterCell& 304286425SdimBitTracker::lookup(unsigned Reg) const { 305286425Sdim CellMapType::const_iterator F = Map.find(Reg); 306286425Sdim assert(F != Map.end()); 307286425Sdim return F->second; 308286425Sdim} 309286425Sdim 310286425Sdim 311286425Sdiminline BitTracker::RegisterCell 312286425SdimBitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) { 313286425Sdim RegisterCell RC(Width); 314286425Sdim for (uint16_t i = 0; i < Width; ++i) 315286425Sdim RC.Bits[i] = BitValue::self(BitRef(Reg, i)); 316286425Sdim return RC; 317286425Sdim} 318286425Sdim 319286425Sdim 320286425Sdiminline BitTracker::RegisterCell 321286425SdimBitTracker::RegisterCell::top(uint16_t Width) { 322286425Sdim RegisterCell RC(Width); 323286425Sdim for (uint16_t i = 0; i < Width; ++i) 324286425Sdim RC.Bits[i] = BitValue(BitValue::Top); 325286425Sdim return RC; 326286425Sdim} 327286425Sdim 328286425Sdim 329286425Sdiminline BitTracker::RegisterCell 330286425SdimBitTracker::RegisterCell::ref(const RegisterCell &C) { 331286425Sdim uint16_t W = C.width(); 332286425Sdim RegisterCell RC(W); 333286425Sdim for (unsigned i = 0; i < W; ++i) 334286425Sdim RC[i] = BitValue::ref(C[i]); 335286425Sdim return RC; 336286425Sdim} 337286425Sdim 338286425Sdim// A class to evaluate target's instructions and update the cell maps. 339286425Sdim// This is used internally by the bit tracker. A target that wants to 340286425Sdim// utilize this should implement the evaluation functions (noted below) 341286425Sdim// in a subclass of this class. 342286425Sdimstruct BitTracker::MachineEvaluator { 343286425Sdim MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M) 344286425Sdim : TRI(T), MRI(M) {} 345286425Sdim virtual ~MachineEvaluator() {} 346286425Sdim 347286425Sdim uint16_t getRegBitWidth(const RegisterRef &RR) const; 348286425Sdim 349286425Sdim RegisterCell getCell(const RegisterRef &RR, const CellMapType &M) const; 350286425Sdim void putCell(const RegisterRef &RR, RegisterCell RC, CellMapType &M) const; 351286425Sdim // A result of any operation should use refs to the source cells, not 352286425Sdim // the cells directly. This function is a convenience wrapper to quickly 353286425Sdim // generate a ref for a cell corresponding to a register reference. 354286425Sdim RegisterCell getRef(const RegisterRef &RR, const CellMapType &M) const { 355286425Sdim RegisterCell RC = getCell(RR, M); 356286425Sdim return RegisterCell::ref(RC); 357286425Sdim } 358286425Sdim 359286425Sdim // Helper functions. 360286425Sdim // Check if a cell is an immediate value (i.e. all bits are either 0 or 1). 361286425Sdim bool isInt(const RegisterCell &A) const; 362286425Sdim // Convert cell to an immediate value. 363286425Sdim uint64_t toInt(const RegisterCell &A) const; 364286425Sdim 365286425Sdim // Generate cell from an immediate value. 366286425Sdim RegisterCell eIMM(int64_t V, uint16_t W) const; 367286425Sdim RegisterCell eIMM(const ConstantInt *CI) const; 368286425Sdim 369286425Sdim // Arithmetic. 370286425Sdim RegisterCell eADD(const RegisterCell &A1, const RegisterCell &A2) const; 371286425Sdim RegisterCell eSUB(const RegisterCell &A1, const RegisterCell &A2) const; 372286425Sdim RegisterCell eMLS(const RegisterCell &A1, const RegisterCell &A2) const; 373286425Sdim RegisterCell eMLU(const RegisterCell &A1, const RegisterCell &A2) const; 374286425Sdim 375286425Sdim // Shifts. 376286425Sdim RegisterCell eASL(const RegisterCell &A1, uint16_t Sh) const; 377286425Sdim RegisterCell eLSR(const RegisterCell &A1, uint16_t Sh) const; 378286425Sdim RegisterCell eASR(const RegisterCell &A1, uint16_t Sh) const; 379286425Sdim 380286425Sdim // Logical. 381286425Sdim RegisterCell eAND(const RegisterCell &A1, const RegisterCell &A2) const; 382286425Sdim RegisterCell eORL(const RegisterCell &A1, const RegisterCell &A2) const; 383286425Sdim RegisterCell eXOR(const RegisterCell &A1, const RegisterCell &A2) const; 384286425Sdim RegisterCell eNOT(const RegisterCell &A1) const; 385286425Sdim 386286425Sdim // Set bit, clear bit. 387286425Sdim RegisterCell eSET(const RegisterCell &A1, uint16_t BitN) const; 388286425Sdim RegisterCell eCLR(const RegisterCell &A1, uint16_t BitN) const; 389286425Sdim 390286425Sdim // Count leading/trailing bits (zeros/ones). 391286425Sdim RegisterCell eCLB(const RegisterCell &A1, bool B, uint16_t W) const; 392286425Sdim RegisterCell eCTB(const RegisterCell &A1, bool B, uint16_t W) const; 393286425Sdim 394286425Sdim // Sign/zero extension. 395286425Sdim RegisterCell eSXT(const RegisterCell &A1, uint16_t FromN) const; 396286425Sdim RegisterCell eZXT(const RegisterCell &A1, uint16_t FromN) const; 397286425Sdim 398286425Sdim // Extract/insert 399286425Sdim // XTR R,b,e: extract bits from A1 starting at bit b, ending at e-1. 400286425Sdim // INS R,S,b: take R and replace bits starting from b with S. 401286425Sdim RegisterCell eXTR(const RegisterCell &A1, uint16_t B, uint16_t E) const; 402286425Sdim RegisterCell eINS(const RegisterCell &A1, const RegisterCell &A2, 403286425Sdim uint16_t AtN) const; 404286425Sdim 405286425Sdim // User-provided functions for individual targets: 406286425Sdim 407286425Sdim // Return a sub-register mask that indicates which bits in Reg belong 408286425Sdim // to the subregister Sub. These bits are assumed to be contiguous in 409286425Sdim // the super-register, and have the same ordering in the sub-register 410286425Sdim // as in the super-register. It is valid to call this function with 411286425Sdim // Sub == 0, in this case, the function should return a mask that spans 412286425Sdim // the entire register Reg (which is what the default implementation 413286425Sdim // does). 414286425Sdim virtual BitMask mask(unsigned Reg, unsigned Sub) const; 415286425Sdim // Indicate whether a given register class should be tracked. 416286425Sdim virtual bool track(const TargetRegisterClass *RC) const { return true; } 417286425Sdim // Evaluate a non-branching machine instruction, given the cell map with 418286425Sdim // the input values. Place the results in the Outputs map. Return "true" 419286425Sdim // if evaluation succeeded, "false" otherwise. 420286425Sdim virtual bool evaluate(const MachineInstr *MI, const CellMapType &Inputs, 421286425Sdim CellMapType &Outputs) const; 422286425Sdim // Evaluate a branch, given the cell map with the input values. Fill out 423286425Sdim // a list of all possible branch targets and indicate (through a flag) 424286425Sdim // whether the branch could fall-through. Return "true" if this information 425286425Sdim // has been successfully computed, "false" otherwise. 426286425Sdim virtual bool evaluate(const MachineInstr *BI, const CellMapType &Inputs, 427286425Sdim BranchTargetList &Targets, bool &FallsThru) const = 0; 428286425Sdim 429286425Sdim const TargetRegisterInfo &TRI; 430286425Sdim MachineRegisterInfo &MRI; 431286425Sdim}; 432286425Sdim 433286425Sdim} // end namespace llvm 434286425Sdim 435286425Sdim#endif 436