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

   1 //===- BitTracker.h ---------------------------------------------*- C++ -*-===//
   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 LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
  11 #define LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H
  12
  13 #include "llvm/ADT/DenseSet.h"
  14 #include "llvm/ADT/SetVector.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineOperand.h"
  18 #include <cassert>
  19 #include <cstdint>
  20 #include <map>
  21 #include <queue>
  22 #include <set>
  23 #include <utility>
  24
  25 namespace llvm {
  26
  27 class BitVector;
  28 class ConstantInt;
  29 class MachineRegisterInfo;
  30 class MachineBasicBlock;
  31 class MachineFunction;
  32 class raw_ostream;
  33 class TargetRegisterClass;
  34 class TargetRegisterInfo;
  35
  36 struct BitTracker {
  37   struct BitRef;
  38   struct RegisterRef;
  39   struct BitValue;
  40   struct BitMask;
  41   struct RegisterCell;
  42   struct MachineEvaluator;
  43
  44   using BranchTargetList = SetVector<const MachineBasicBlock *>;
  45   using CellMapType = std::map<unsigned, RegisterCell>;
  46
  47   BitTracker(const MachineEvaluator &E, MachineFunction &F);
  48   ~BitTracker();
  49
  50   void run();
  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);
  59
  60   void print_cells(raw_ostream &OS) const;
  61
  62 private:
  63   void visitPHI(const MachineInstr &PI);
  64   void visitNonBranch(const MachineInstr &MI);
  65   void visitBranchesFrom(const MachineInstr &BI);
  66   void visitUsesOf(unsigned Reg);
  67
  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>;
  72
  73   // Priority queue of instructions using modified registers, ordered by
  74   // their relative position in a basic block.
  75   struct UseQueueType {
  76     UseQueueType() : Uses(Dist) {}
  77
  78     unsigned size() const {
  79       return Uses.size();
  80     }
  81     bool empty() const {
  82       return size() == 0;
  83     }
  84     MachineInstr *front() const {
  85       return Uses.top();
  86     }
  87     void push(MachineInstr *MI) {
  88       if (Set.insert(MI).second)
  89         Uses.push(MI);
  90     }
  91     void pop() {
  92       Set.erase(front());
  93       Uses.pop();
  94     }
  95     void reset() {
  96       Dist.clear();
  97     }
  98   private:
  99     struct Cmp {
 100       Cmp(DenseMap<const MachineInstr*,unsigned> &Map) : Dist(Map) {}
 101       bool operator()(const MachineInstr *MI, const MachineInstr *MJ) const;
 102       DenseMap<const MachineInstr*,unsigned> &Dist;
 103     };
 104     std::priority_queue<MachineInstr*, std::vector<MachineInstr*>, Cmp> Uses;
 105     DenseSet<const MachineInstr*> Set; // Set to avoid adding duplicate entries.
 106     DenseMap<const MachineInstr*,unsigned> Dist;
 107   };
 108
 109   void reset();
 110   void runEdgeQueue(BitVector &BlockScanned);
 111   void runUseQueue();
 112
 113   const MachineEvaluator &ME;
 114   MachineFunction &MF;
 115   MachineRegisterInfo &MRI;
 116   CellMapType &Map;
 117
 118   EdgeSetType EdgeExec;         // Executable flow graph edges.
 119   InstrSetType InstrExec;       // Executable instructions.
 120   UseQueueType UseQ;            // Work queue of register uses.
 121   EdgeQueueType FlowQ;          // Work queue of CFG edges.
 122   DenseSet<unsigned> ReachedBB; // Cache of reached blocks.
 123   bool Trace;                   // Enable tracing for debugging.
 124 };
 125
 126 // Abstraction of a reference to bit at position Pos from a register Reg.
 127 struct BitTracker::BitRef {
 128   BitRef(unsigned R = 0, uint16_t P = 0) : Reg(R), Pos(P) {}
 129
 130   bool operator== (const BitRef &BR) const {
 131     // If Reg is 0, disregard Pos.
 132     return Reg == BR.Reg && (Reg == 0 || Pos == BR.Pos);
 133   }
 134
 135   unsigned Reg;
 136   uint16_t Pos;
 137 };
 138
 139 // Abstraction of a register reference in MachineOperand.  It contains the
 140 // register number and the subregister index.
 141 struct BitTracker::RegisterRef {
 142   RegisterRef(unsigned R = 0, unsigned S = 0)
 143     : Reg(R), Sub(S) {}
 144   RegisterRef(const MachineOperand &MO)
 145       : Reg(MO.getReg()), Sub(MO.getSubReg()) {}
 146
 147   unsigned Reg, 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.
 155 struct BitTracker::BitValue {
 156   enum ValueType {
 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   };
 191   ValueType Type;
 192   BitRef RefI;
 193
 194   BitValue(ValueType T = Top) : Type(T) {}
 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).
 270 inline BitTracker::BitValue
 271 BitTracker::BitValue::ref(const BitValue &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
 279 inline BitTracker::BitValue
 280 BitTracker::BitValue::self(const BitRef &Self) {
 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.
 287 struct BitTracker::BitMask {
 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
 294 private:
 295   uint16_t B = 0;
 296   uint16_t E = 0;
 297 };
 298
 299 // Representation of a register: a list of BitValues.
 300 struct BitTracker::RegisterCell {
 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   }
 311   BitValue &operator[](uint16_t BitN) {
 312     assert(BitN < Bits.size());
 313     return Bits[BitN];
 314   }
 315
 316   bool meet(const RegisterCell &RC, unsigned 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
 342 private:
 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
 352 inline bool BitTracker::has(unsigned Reg) const {
 353   return Map.find(Reg) != Map.end();
 354 }
 355
 356 inline const BitTracker::RegisterCell&
 357 BitTracker::lookup(unsigned Reg) const {
 358   CellMapType::const_iterator F = Map.find(Reg);
 359   assert(F != Map.end());
 360   return F->second;
 361 }
 362
 363 inline BitTracker::RegisterCell
 364 BitTracker::RegisterCell::self(unsigned Reg, uint16_t Width) {
 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
 371 inline BitTracker::RegisterCell
 372 BitTracker::RegisterCell::top(uint16_t Width) {
 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
 379 inline BitTracker::RegisterCell
 380 BitTracker::RegisterCell::ref(const RegisterCell &C) {
 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.
 392 struct BitTracker::MachineEvaluator {
 393   MachineEvaluator(const TargetRegisterInfo &T, MachineRegisterInfo &M)
 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(unsigned 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(unsigned Reg) const;
 489
 490   const TargetRegisterInfo &TRI;
 491   MachineRegisterInfo &MRI;
 492 };
 493
 494 } // end namespace llvm
 495
 496 #endif // LLVM_LIB_TARGET_HEXAGON_BITTRACKER_H