src/jitcs_int_dfg_analysis.h

   1 //===-- evm/bblock.h - a single basic block --*- C++ -*-===//
   2 //
   3 // A basic block contains a list of instructions.
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #ifndef _JITCS_INT_DFGANALYSIS_H_
   8 #define _JITCS_INT_DFGANALYSIS_H_
   9
  10 #include "jitcs_base.h"
  11 #include "jitcs_ids.h"
  12 #include "jitcs_adt_ref.h"
  13 #include "jitcs_adt_slice.h"
  14 #include "jitcs_int_adt_bitmap.h"
  15 #include "jitcs_int_virtualregister.h"
  16 #include "jitcs_int_function_impl.h"
  17
  18 namespace jitcs {
  19 class IDumper;
  20 class BasicBlockImpl;
  21 class FunctionImpl;
  22 class TempAllocator;
  23
  24 class DFGAnalysis {
  25 public:
  26   enum AMode {
  27     M_Local,
  28     M_Global
  29   };
  30   struct ResourceData {
  31     enum { E_UseDefBits = 2, E_UseDefMask = (1 << E_UseDefBits) - 1,
  32            E_UseDefShift = 0, E_Use = 1, E_Def = 2, E_UseDef = E_Use | E_Def,
  33            //E_SizeBits = 3, E_SizeMask = (1 << E_SizeBits) - 1,
  34            //E_SizeShift = E_UseDefShift + E_UseDefBits,
  35            //E_ResClassBits = 3, E_ResClassMask = (1 << E_ResClassBits) - 1,
  36            //E_ResClassShift = E_SizeShift + E_SizeBits,
  37            //E_ResClassShift = E_UseDefShift + E_UseDefBits,
  38            E_ResShift = E_UseDefShift + E_UseDefBits };
  39     u32 resInfo;
  40     u32 allowedMask;
  41     u32 nextUse;
  42     u32 hintMask;
  43
  44     ResId getResId() { return static_cast<ResId>(resInfo >> E_ResShift); }
  45     //ResClassId getResClassId() {
  46     //  return static_cast<ResClassId>
  47     //    ((resInfo >> E_ResClassShift) & E_ResClassMask);
  48     //}
  49     //u32 getResLogSize() { return ((resInfo >> E_SizeShift) & E_SizeMask); }
  50     u32 getNext(BitSlice liveOut) {
  51       return nextUse == ~1 ? (~0 ^ liveOut.test(getResId())) : nextUse;
  52     }
  53     u32 getUseDef() { return ((resInfo >> E_UseDefShift) & E_UseDefMask); }
  54     bool isUse() { return (resInfo & E_Use) != 0; }
  55     bool isDef() { return (resInfo & E_Def) != 0; }
  56     bool isUseOnly() { return (resInfo & E_UseDefMask) == E_Use; }
  57     bool isDefOnly() { return (resInfo & E_UseDefMask) == E_Def; }
  58     bool isUseDef() { return (resInfo & E_UseDefMask) == E_UseDef; }
  59   };
  60   struct InstructionData {
  61     ResourceData* ptr;
  62     u8 resClassEnd[8];
  63
  64     // for each resource class, the range of relevant resources can be
  65     // extracted as ptr[RCL == 0 ? 0 : resClassEnd[RCL-1] .. resClassEnd[RCL]]
  66     // - each range of resources starts with fixed register resources
  67     // - the non-fixed register resources are ordered by increasing number of
  68     // bits in the mask field
  69     // - the bit of fixed resources is removed from non-fixed resources
  70     // with overlapping life-range (concerning the instruction)
  71     void check();
  72   };
  73   struct NextData {
  74     u32 next, last;
  75   };
  76   struct BlockData {
  77     BasicBlockImpl* bb;
  78     Slice<InstructionData> instructions;
  79     Slice<NextData> useRangeData;
  80     BitSlice useRangeIsValid;
  81     BitSlice liveIn;
  82     BitSlice liveOut;
  83     BitSlice used;
  84     BitSlice defined;
  85   };
  86
  87 public:
  88   DFGAnalysis();
  89   void init(FunctionImpl& f, AMode m, Slice<u32> touchedFixed);
  90   void dump(IDumper& o) const;
  91
  92   bool isUsed(Ref<BasicBlock> bb, Ref<const VirtualRegister> v) const;
  93   bool isDefined(Ref<BasicBlock> bb, Ref<const VirtualRegister> v) const;
  94   bool isLiveIn(Ref<BasicBlock> bb, Ref<const VirtualRegister> v) const;
  95   bool isLiveOut(Ref<BasicBlock> bb, Ref<const VirtualRegister> v) const;
  96
  97   bool isUsed(Ref<BasicBlockImpl> bb, Ref<const VirtualRegister> v) const;
  98   bool isDefined(Ref<BasicBlockImpl> bb, Ref<const VirtualRegister> v) const;
  99   bool isLiveIn(Ref<BasicBlockImpl> bb, Ref<const VirtualRegister> v) const;
 100   bool isLiveOut(Ref<BasicBlockImpl> bb, Ref<const VirtualRegister> v) const;
 101
 102   void extractUseDef(Ref<BasicBlockImpl> bb, size_t ins,
 103                      BitSlice used, BitSlice defined) const;
 104
 105 private:
 106
 107 private:
 108   Slice<BlockData> _blocks;
 109 };
 110
 111 struct GatherResourceList {
 112   enum { NUM = 15 };
 113   struct Entry {
 114     u32 resInfo;
 115     u32 mask;
 116   };
 117
 118   struct ClassWise {
 119     Entry touchedResources[NUM];
 120     u32 numFixed, numNonFixed;
 121   };
 122   ClassWise byClass[8];
 123   u8 classInit;
 124   // --------------------
 125   void init() {
 126     classInit = 0;
 127   }
 128   // --------------------
 129   void addNonFixedDef(Ref<const VirtualRegister> r, u32 mask) {
 130     _addNonFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_Def);
 131   }
 132   void addNonFixedUseDef(Ref<const VirtualRegister> r, u32 mask) {
 133     _addNonFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_UseDef);
 134   }
 135   void addNonFixedUse(Ref<const VirtualRegister> r, u32 mask) {
 136     _addNonFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_Use);
 137   }
 138   // --------------------
 139   void addFixedDef(Ref<const VirtualRegister> r, u32 mask) {
 140     _addFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_Def);
 141   }
 142   void addFixedUseDef(Ref<const VirtualRegister> r, u32 mask) {
 143     _addFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_UseDef);
 144   }
 145   void addFixedUse(Ref<const VirtualRegister> r, u32 mask) {
 146     _addFixed(r->resclass, _combine(r), mask, DFGAnalysis::ResourceData::E_Use);
 147   }
 148   // --------------------
 149   void addFixedDef(ResId res, ResClassId rescl, u32 mask) {
 150     _addFixed(rescl, _combine(res), mask, DFGAnalysis::ResourceData::E_Def);
 151   }
 152   void addFixedUseDef(ResId res, ResClassId rescl, u32 mask) {
 153     _addFixed(rescl, _combine(res), mask, DFGAnalysis::ResourceData::E_UseDef);
 154   }
 155   void addFixedUse(ResId res, ResClassId rescl, u32 mask) {
 156     _addFixed(rescl, _combine(res), mask, DFGAnalysis::ResourceData::E_Use);
 157   }
 158
 159 private:
 160   u32 _combine(ResId res) const {
 161     return (res << DFGAnalysis::ResourceData::E_ResShift);
 162   }
 163   u32 _combine(Ref<const VirtualRegister> r) const {
 164     return _combine(r->res);
 165   }
 166   void _addNonFixed(ResClassId, u32 id, u32 mask, u32 usedef);
 167   void _addFixed(ResClassId, u32 id, u32 mask, u32 usedef);
 168 };
 169
 170 class SetupBlockResourceInfo {
 171 public:
 172   SetupBlockResourceInfo(FunctionImpl& f);
 173   SetupBlockResourceInfo() = delete;
 174   SetupBlockResourceInfo(const SetupBlockResourceInfo&) = delete;
 175   SetupBlockResourceInfo& operator =(const SetupBlockResourceInfo&) = delete;
 176
 177   void init(Slice<DFGAnalysis::InstructionData> ins,
 178             BitSlice def, BitSlice use,
 179             BitSlice nextValid, Slice<DFGAnalysis::NextData> next,
 180             Slice<u32> touchedFixed);
 181   void push_front(GatherResourceList&);
 182
 183   RefOrNull<const VirtualRegister> getFrameRegister(size_t fr) {
 184     return _f.getFrameRegisterInfo(fr).reg;
 185   }
 186
 187 private:
 188   Slice<DFGAnalysis::InstructionData> _ins;
 189   BitSlice _def, _use, _nextValid;
 190   Slice<u32> _touchedFixed;
 191   Slice<DFGAnalysis::NextData> _next;
 192   size_t _idx;
 193   FunctionImpl& _f;
 194   TempAllocator &_alloc;
 195   Slice<DFGAnalysis::ResourceData> _remaining;
 196   u32 _rclCnt;
 197 };
 198
 199 } // end of namespace jitcs
 200
 201 #endif
 202 // _JITCS_INT_DFGANALYSIS_H_