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

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