text: /*===================== begin_copyright_notice ==================================
  
  Copyright (c) 2017 Intel Corporation
  
  Permission is hereby granted, free of charge, to any person obtaining a
  copy of this software and associated documentation files (the
  "Software"), to deal in the Software without restriction, including
  without limitation the rights to use, copy, modify, merge, publish,
  distribute, sublicense, and/or sell copies of the Software, and to
  permit persons to whom the Software is furnished to do so, subject to
  the following conditions:
  
  The above copyright notice and this permission notice shall be included
  in all copies or substantial portions of the Software.
  
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  
  
  ======================= end_copyright_notice ==================================*/
  #ifndef FLOWGRAPH_H
  #define FLOWGRAPH_H
  
  #include "VISADefines.h"
  #include "G4_BB.hpp"
  #include "Gen4_IR.hpp"
  #include "RelocationInfo.h"
  
  #include <list>
  #include <map>
  #include <ostream>
  #include <set>
  #include <string>
  #include <unordered_set>
  #include <unordered_map>
  #include <vector>
  
  namespace vISA
  {
  class FlowGraph;
  class G4_BB;
  class G4_Kernel;
  class IR_Builder;
  class PhyRegSummary;
  class VarSplitPass;
  
  //
  // FuncInfo - Function CFG information
  //    This class maintains a CFG summary of the function (its INIT block, EXIT block and
  //    number of call sites). The functions's INIT block will contain a pointer to its
  //    related FuncInfo object. The FuncInfo definition is used for inter-procedural liveness
  //    analysis (IPA).
  class FuncInfo
  {
  private:
      unsigned id;        // the function id
      G4_BB*   initBB;    // the init node
      G4_BB*   exitBB;    // the exit node
      unsigned callCount; // the number of call sites
  
      std::vector<G4_BB*>  BBList;      // the list of BBs
      std::list<FuncInfo *>  callees; // the list of callees
      unsigned scopeID;               // the function scope ID
  
      bool visited;
      unsigned preID;
      unsigned postID;
  
  public:
  
      FuncInfo(unsigned p_id, G4_BB* p_initBB, G4_BB* p_exitBB)
          : id(p_id), initBB(p_initBB), exitBB(p_exitBB), callCount(1)
          , scopeID(0), visited(false), preID(0), postID(0)
      {
      }
  
      ~FuncInfo()
      {
          BBList.clear();
          callees.clear();
      }
  
      void *operator new(size_t sz, Mem_Manager& m)    {return m.alloc(sz);}
  
      bool doIPA() const {return callCount > 1;}
  
      unsigned getId() const {return id;}
      void setId(unsigned val) {id = val;}
  
      G4_BB* getInitBB() const {return initBB;}
      G4_BB* getExitBB() const {return exitBB;}
  
      void incrementCallCount() {++callCount;}
  
      void updateInitBB(G4_BB* p_initBB) {initBB = p_initBB;}
      void updateExitBB(G4_BB* p_exitBB) {exitBB = p_exitBB;}
  
      void                    addCallee(FuncInfo *fn) {callees.push_back(fn);}
      std::list<FuncInfo *>&  getCallees() {return callees;}
  
      void                  addBB(G4_BB* bb) {BBList.push_back(bb);}
      std::vector<G4_BB*>&  getBBList() {return BBList;}
  
      unsigned getScopeID() const {return scopeID;}
      void     setScopeID(unsigned id) {scopeID = id;}
  
      bool     getVisited() const {return visited;}
      void     setVisited() {visited = true;}
  
      unsigned getPreID() const {return preID;}
      void     setPreID(unsigned id) {preID = id;}
  
      unsigned getPostID() const {return postID;}
      void     setPostID(unsigned id) {postID = id;}
  
      void dump() const;
  }; // FuncInfo
  
  
  
  ///
  /// A hashtable of <declare, node> where every node is a vector of
  /// {LB, RB} (left-bounds and right-bounds)
  /// A source operand (either SrcRegRegion or Predicate) is considered to be global
  /// if it is not fully defined in one BB
  ///
  class GlobalOpndHashTable
  {
      Mem_Manager& mem;
      std_arena_based_allocator<uint32_t> private_arena_allocator;
  
      static uint32_t packBound(uint16_t lb, uint16_t rb)
      {
          return (rb << 16) + lb;
      }
  
      static uint16_t getLB(uint32_t value)
      {
          return (uint16_t) (value & 0xFFFF);
      }
      static uint16_t getRB(uint32_t value)
      {
          return (uint16_t) (value >> 16);
      }
  
      struct HashNode
      {
          // each elements is {LB, RB} pair where [0:15] is LB and [16:31] is RB
          std::vector<uint32_t, std_arena_based_allocator<uint32_t>> bounds;
  
          HashNode(uint16_t lb, uint16_t rb, std_arena_based_allocator<uint32_t>& m)
              : bounds(m)
          {
              bounds.push_back(packBound(lb, rb));
          }
  
          void *operator new(size_t sz, Mem_Manager& m) {return m.alloc(sz);}
  
          void insert(uint16_t newLB, uint16_t newRB);
          bool isInNode(uint16_t lb, uint16_t rb) const;
      };
  
      // "global" refers to declares with elements that are used without a preceding define in the same BB
      std::map<G4_Declare*, HashNode*> globalVars;
      // for debugging it's often useful to dump out the global operands, not just declares.
      // Note that this may not be an exhaustive list, for example it does not cover dst global operands;
      // for accuracy one should use isOpndGlobal()
      std::vector<G4_Operand*> globalOpnds;
  
  public:
      GlobalOpndHashTable(Mem_Manager& m) : mem(m) { }
  
      void addGlobalOpnd(G4_Operand * opnd);
      // returns true if def may possibly define a global variable
      bool isOpndGlobal(G4_Operand * def) const;
      void clearHashTable();
  
      void dump(std::ostream &os = std::cerr) const;
  }; // GlobalOpndHashTable
  
  //
  // A table mapping the subroutine (INIT) block id's to their FuncInfo nodes.
  //
  typedef std::unordered_map<int, FuncInfo*> FuncInfoHashTable;
  typedef std::unordered_map<G4_Label*, G4_BB*> Label_BB_Map;
  
  class FlowGraph
  {
      // This list maintains the ordering of the basic blocks (i.e., asm and binary emission will output
      // the blocks in list oder.
      // Important: Due to the nature of SIMD CF, it is unsafe to change the order of basic blocks
      // Once the list is populated in constructFlowGraph(), the only changes allowed are
      // 1. insertion of new exit BBs due to handleExit/handleReturn/handleFRet.  The exit BB
      //    must be the last BB for the kernel/subroutine/function it belongs to
      // 2. deletion of unreachable blocks
      // 3. merging of blocks that only contain one label with its (single) successor
      // If you need to change the block ordering for any reason, create another data structure instead of
      // modifying this one
      BB_LIST BBs;
  
      unsigned traversalNum;                      // used for flow graph traversals
      unsigned numBBId;                            // number of basic blocks
      bool     reducible;                            // reducibility of the graph
      bool     doIPA;                             // requires inter-procedural liveness analysis
      bool     hasStackCalls;                     // indicates that the flowgraph contains STACK_CALL calls
      bool     isStackCallFunc;                    // indicates the function itself is a STACK_CALL function
      unsigned autoLabelId;
      G4_Kernel* pKernel;                         // back pointer to the kernel object
  
      // map each BB to its local RA GRF usage summary, populated in local RA
      std::map<G4_BB*, PhyRegSummary*> bbLocalRAMap;
      // vector of summaries created for each BB, needed for deallocation later
      std::vector<PhyRegSummary*> localRASummaries;
  
      // list of all BBs ever created
      // This list only grows and is freed when the FlowGraph is destroyed
      std::vector<G4_BB*> BBAllocList;
  
      // stores all INST that may be target of indirect jump. Currently these inst must be jmpi themselves
      std::unordered_set<G4_INST*> indirectJmpTarget;
  
      // stores all endift inst that have labels associated with it
      std::unordered_map<G4_INST*, G4_Label*> endifWithLabels;
  
      // label to subroutine BB's map. This is used to add edges between subroutine caller/callee
      // ToDo: We should use FuncInfo instead, but at the time it was needed FuncInfo was not constructed yet..
      std::unordered_map<G4_Label*, std::vector<G4_BB*>> subroutines;
  
  public:
      typedef std::pair<G4_BB*, G4_BB*> Edge;
      typedef std::set<G4_BB*> Blocks;
      typedef std::map<Edge, Blocks> Loop;
  
      Mem_Manager& mem;                            // mem mananger for creating BBs & starting IP table
      INST_LIST_NODE_ALLOCATOR& instListAlloc;     // a reference to dedicated mem allocator for holding instruction list nodes
  
      std::list<Edge> backEdges;                  // list of all backedges (tail->head)
      Loop naturalLoops;
  
      // function info nodes. entry function is not included.
      std::vector<FuncInfo*> funcInfoTable;
  
      std::vector<FuncInfo*> sortedFuncTable;     // subroutines in reverse topographical order (leaf at top)
                                                  // kernelInfo is the last element with invalid func id
  
      FuncInfo* kernelInfo;                       // the call info for the kernel function
  
      IR_Builder *builder;                        // needed to create new instructions (mainly labels)
      GlobalOpndHashTable globalOpndHT;
  
      G4_Declare *            framePtrDcl;
      G4_Declare *            stackPtrDcl;
      G4_Declare *            scratchRegDcl;
      G4_Declare *            pseudoVCEDcl;
  
      // pseudo declares used by RA to model the save/restore variables at each call site
      struct PseudoDcls
      {
          G4_Declare* VCA;
          G4_Declare* A0;
          G4_Declare* Flag;
      };
  
      std::unordered_map<G4_InstCF*, struct PseudoDcls> fcallToPseudoDclMap;
  
      // offset in unit of OW
      unsigned                    callerSaveAreaOffset = 0;
      unsigned                    calleeSaveAreaOffset = 0;
      unsigned                    frameSizeInOWord = 0;
  
      // Bank conflict statistics.
      struct BankConflictStatistics
      {
          unsigned NumOfGoodInsts = 0;
          unsigned NumOfBadInsts = 0;
          unsigned NumOfOKInsts = 0;
  
          void addGood() { ++NumOfGoodInsts; }
          void addBad() { ++NumOfBadInsts; }
          void addOK() { ++NumOfOKInsts; }
          void clear()
          {
              NumOfGoodInsts = 0;
              NumOfBadInsts = 0;
              NumOfOKInsts = 0;
          }
      } BCStats;
  
      struct XeBankConflictStatistics
      {
          unsigned simd8 = 0;    //The number of simd8 instructions, one simd16 is treated as two simd8 if it's not HF
          unsigned BCNum = 0;  //The number of band conflict.
          int sameBankConflicts = 0;
          int simd16ReadSuppression = 0;
          int twoSrcBC = 0;
  
          void clear()
          {
              simd8 = 0;
              BCNum = 0;
              sameBankConflicts = 0;
              simd16ReadSuppression = 0;
              twoSrcBC = 0;
          }
          void addBC(unsigned num) { BCNum += num; }
          void addSameBankBC(unsigned num) { sameBankConflicts += num; }
          void addSimd16RSBC(unsigned num) { simd16ReadSuppression += num; }
          void add2SrcBC(unsigned num) { twoSrcBC += num; }
          void addSIMD8() { ++simd8; }
  
      } XeBCStats;
      unsigned numRMWs = 0;    // counting the number of read-modify-write
  public:
      // forwarding functions to the BBs list
      BB_LIST_ITER begin() { return BBs.begin(); }
      BB_LIST_ITER end() { return BBs.end(); }
      BB_LIST::reverse_iterator rbegin() { return BBs.rbegin(); }
      BB_LIST::reverse_iterator rend() { return BBs.rend(); }
      BB_LIST::const_iterator cbegin() const { return BBs.cbegin(); }
      BB_LIST::const_iterator cend() const { return BBs.cend(); }
      BB_LIST::const_reverse_iterator crbegin() const { return BBs.crbegin(); }
      BB_LIST::const_reverse_iterator crend() const { return BBs.crend(); }
  
      size_t size() { return BBs.size(); }
      bool empty() const { return BBs.empty(); }
      G4_BB* back() const {return BBs.back(); }
  
      static void setPhysicalLink(G4_BB* pred, G4_BB* succ);
  
      BB_LIST_ITER insert(BB_LIST_ITER iter, G4_BB* bb);
  
  
      void push_back(G4_BB* bb) {insert(BBs.end(), bb);}
  
      void erase(BB_LIST_ITER iter);
  
      BB_LIST& getBBList() { return BBs; }
  
      // add BB to be the first BB
      void addPrologBB(G4_BB* BB);
  
  
      // append another CFG's BBs to this CFG.
      // note that we don't add additional CFG edges as its purpose is just to
      // stitch the two binaries togather
      void append(const FlowGraph& otherFG);
  
      G4_BB* getLabelBB(Label_BB_Map& map, G4_Label* label);
      G4_BB* beginBB(Label_BB_Map& map, G4_INST* first);
  
      bool performIPA() const {return doIPA;}
  
      bool getHasStackCalls() const { return hasStackCalls; }
      void setHasStackCalls() { hasStackCalls = true; }
  
      bool getIsStackCallFunc() const {return isStackCallFunc;}
      void setIsStackCallFunc() {isStackCallFunc = true;}
  
      G4_Kernel* getKernel() {return pKernel;}
  
      void mergeFReturns();
  
      G4_Declare*& getFramePtrDcl()                   {return framePtrDcl;}
      G4_Declare*& getStackPtrDcl()                   {return stackPtrDcl;}
      G4_Declare*& getScratchRegDcl()                 {return scratchRegDcl;}
  
      bool isPseudoVCEDcl(const G4_Declare* dcl) const { return dcl == pseudoVCEDcl; }
      bool isPseudoVCADcl(const G4_Declare* dcl) const
      {
          for (auto iter : fcallToPseudoDclMap)
          {
              if (iter.second.VCA == dcl)
              {
                  return true;
              }
          }
          return false;
      }
      bool isPseudoA0Dcl(const G4_Declare* dcl) const
      {
          for (auto iter : fcallToPseudoDclMap)
          {
              if (iter.second.A0 == dcl)
              {
                  return true;
              }
          }
          return false;
      }
      bool isPseudoFlagDcl(const G4_Declare* dcl) const
      {
          for (auto iter : fcallToPseudoDclMap)
          {
              if (iter.second.Flag == dcl)
              {
                  return true;
              }
          }
          return false;
      }
      bool isPseudoDcl(const G4_Declare* dcl) const
      {
          if (!getHasStackCalls() && !getIsStackCallFunc())
          {
              return false;
          }
          if (isPseudoVCEDcl(dcl))
          {
              return true;
          }
          for (auto iter : fcallToPseudoDclMap)
          {
              if (iter.second.A0 == dcl || iter.second.Flag == dcl || iter.second.VCA == dcl)
              {
                  return true;
              }
          }
          return false;
      }
  
      //
      // Merge multiple returns into one, prepare for spill code insertion
      //
      void mergeReturn(FuncInfoHashTable& funcInfoTable);
      G4_BB* mergeSubRoutineReturn(G4_Label* subroutine);
      void normalizeSubRoutineBB(FuncInfoHashTable& funcInfoTable);
      void processGoto(bool HasSIMDCF);
      void processSCF(FuncInfoHashTable& FuncInfoMap);
      void insertJoinToBB(G4_BB* bb, G4_ExecSize execSize, G4_Label* jip);
  
      // functions for structure analysis
      G4_Kernel *getKernel() const { return pKernel; }
      G4_Label* insertEndif(G4_BB* bb, G4_ExecSize execSize, bool createLabel);
      void setJIPForEndif(G4_INST* endif, G4_INST* target, G4_BB* targetBB);
      void convertGotoToJmpi(G4_INST *gotoInst);
      bool convertJmpiToGoto();
  
      unsigned getNumFuncs() const {return unsigned(funcInfoTable.size());}
  
      void handleReturn(Label_BB_Map& map, FuncInfoHashTable& funcInfoTable);
      void linkReturnAddr(G4_BB* bb, G4_BB* returnAddr);
  
      void handleExit(G4_BB* lastKernelBB);
      void handleWait();
  
      void preprocess(INST_LIST& instlist);
  
      FlowGraph() = delete;
      FlowGraph(const FlowGraph&) = delete;
      FlowGraph& operator=(const FlowGraph&) = delete;
  
      FlowGraph(INST_LIST_NODE_ALLOCATOR& alloc, G4_Kernel* kernel, Mem_Manager& m) :
        traversalNum(0), numBBId(0), reducible(true),
        doIPA(false), hasStackCalls(false), isStackCallFunc(false), autoLabelId(0),
        pKernel(kernel), mem(m), instListAlloc(alloc),
        kernelInfo(NULL), builder(NULL), globalOpndHT(m), framePtrDcl(NULL),
        stackPtrDcl(NULL), scratchRegDcl(NULL), pseudoVCEDcl(NULL) {}
  
      ~FlowGraph();
  
      void setBuilder(IR_Builder *pBuilder) {builder = pBuilder;}
  
      void addPredSuccEdges(G4_BB* pred, G4_BB* succ, bool tofront=true)
      {
          if (tofront)
              pred->Succs.push_front(succ);
          else
              pred->Succs.push_back(succ);
  
          succ->Preds.push_front(pred);
      }
  
      void addUniquePredSuccEdges(G4_BB* pred, G4_BB* succ, bool tofront=true)
      {
          // like above, but check for duplicate edges
          auto iter = std::find_if(pred->Succs.begin(), pred->Succs.end(), [succ](G4_BB* bb) { return bb == succ; });
          if (iter == pred->Succs.end())
          {
              addPredSuccEdges(pred, succ, tofront);
          }
      }
  
      void removePredSuccEdges(G4_BB* pred, G4_BB* succ);
  
      G4_INST* createNewLabelInst(G4_Label* label, int lineNo = 0, int CISAOff = -1);
  
      G4_BB* createNewBB(bool insertInFG = true);
      G4_BB* createNewBBWithLabel(const char* LabelPrefix, int Lineno = 0, int CISAoff = -1);
      int64_t insertDummyUUIDMov();
      //
      // Increase by one so that all BBs' traversal are less than traversalNum
      //
      void prepareTraversal()    {traversalNum++;}
      unsigned getTraversalNum() {return traversalNum;}
  
      //
      // Check if the graph is reducible
      //
      bool isReducible() { return reducible; }
  
      //
      // Remove any placeholder empty blocks that could have been inserted to aid analysis
      //
      void removeRedundantLabels();
      //
      // remove any mov with the same src and dst opnds
      //
      void removeRedundMov();
      //
      // Remove any placeholder empty blocks that could have been inserted to aid analysis.
      //
      void removeEmptyBlocks();
      //
      // Add a dummy BB for multiple-exit flow graph
      //
      void linkDummyBB();
      //
      // Re-assign block ID so that we can use id to determine the ordering of two blocks in
      // the code layout
      //
      void reassignBlockIDs();
  
      //
      // Remove blocks that are unreachable via control flow of program
      //
      void removeUnreachableBlocks(FuncInfoHashTable& funcInfoHT);
  
      void constructFlowGraph(INST_LIST& instlist);
      bool matchBranch(int &sn, INST_LIST& instlist, INST_LIST_ITER &it);
  
      void localDataFlowAnalysis();
      void resetLocalDataFlowData();
  
      unsigned getNumBB() const {return numBBId;}
      G4_BB* getEntryBB()       {return BBs.front();}
  
      void addFrameSetupDeclares(IR_Builder& builder, PhyRegPool& regPool);
      void addSaveRestorePseudoDeclares(IR_Builder& builder);
      void markDivergentBBs();
  
      // Used for CISA 3.0
      void incrementNumBBs() { numBBId++ ; }
      G4_BB* getUniqueReturnBlock();
  
      void normalizeFlowGraph();
  
      // This is mainly used to link subroutine call-return BBs
      // ToDo: maintain this during BB add/delete instead of having to call it explicitly
      void setPhysicalPredSucc();
  
      void markRPOTraversal();
  
      void findBackEdges();
      void findNaturalLoops();
  
      void traverseFunc(FuncInfo* func, unsigned *ptr);
      void topologicalSortCallGraph();
      void findDominators(std::map<FuncInfo*, std::set<FuncInfo*>>& domMap);
      unsigned resolveVarScope(G4_Declare* dcl, FuncInfo* func);
      void markVarScope(std::vector<G4_BB*>& BBList, FuncInfo* func);
      void markScope();
  
      void addSIMDEdges();
  
      void addBBLRASummary(G4_BB* bb, PhyRegSummary* summary)
      {
          bbLocalRAMap.insert(std::make_pair(bb, summary));
          localRASummaries.push_back(summary);
      }
  
      void clearBBLRASummaries()
      {
          bbLocalRAMap.clear();
      }
  
      PhyRegSummary* getBBLRASummary(G4_BB* bb) const
      {
          auto&& iter = bbLocalRAMap.find(bb);
          return iter != bbLocalRAMap.end() ? iter->second : nullptr;
      }
  
      uint32_t getNumCalls() const
      {
          uint32_t numCalls = 0;
          for (auto bb : BBs)
          {
              if (bb->isEndWithCall())
              {
                  ++numCalls;
              }
          }
          return numCalls;
      }
  
      bool isIndirectJmpTarget(G4_INST* inst) const
      {
          return indirectJmpTarget.count(inst) > 0;
      }
  
      G4_Label* getLabelForEndif(G4_INST* inst) const
      {
          auto iter = endifWithLabels.find(inst);
          if (iter != endifWithLabels.end())
          {
              return iter->second;
          }
          else
          {
              return nullptr;
          }
      }
  
      bool endWithGotoInLastBB() const
      {
          if (BBs.empty())
          {
              return false;
          }
          G4_BB* lastBB = back();
          return lastBB->isEndWithGoto();
      }
  
      /// Return true if PredBB->SuccBB is a backward branch goto/jmpi/while.
      bool isBackwardBranch(G4_BB* PredBB, G4_BB* SuccBB) const
      {
          if (PredBB->size() == 0) return false;
          G4_INST* bInst = PredBB->back();
          G4_BB* targetBB = PredBB->Succs.size() > 0 ? PredBB->Succs.back() : nullptr;
          bool isBr = (bInst->opcode() == G4_goto || bInst->opcode() == G4_jmpi);
          // Note that isBackward() should return true for while as well.
          return targetBB == SuccBB &&
              ((isBr && bInst->asCFInst()->isBackward()) || bInst->opcode() == G4_while);
      }
  
      void setABIForStackCallFunctionCalls();
  
      // This is for TGL WA
      void findNestedDivergentBBs(std::unordered_map<G4_BB*, int>& nestedDivergentBBs);
  
      void print(std::ostream& OS) const;
      void dump() const;
  private:
      // Use normalized region descriptors for each source operand if possible.
      void normalizeRegionDescriptors();
  
      // Find the BB that has the given label from the range [StartIter, EndIter).
      G4_BB* findLabelBB(
          BB_LIST_ITER StartIter,
          BB_LIST_ITER EndIter,
          const char* Label);
  
      void decoupleReturnBlock(G4_BB*);
      void decoupleInitBlock(G4_BB*, FuncInfoHashTable& funcInfoTable);
      void DFSTraverse(G4_BB* bb, unsigned& preId, unsigned& postId, FuncInfo* fn);
  }; // FlowGraph
  
  
  class PostDom
  {
  public:
      PostDom(G4_Kernel&);
      std::unordered_set<G4_BB*>& getPostDom(G4_BB*);
      std::vector<G4_BB*>& getImmPostDom(G4_BB*);
      void run();
      void dumpImmDom();
      G4_BB* getCommonImmDom(std::unordered_set<G4_BB*>&);
  
  private:
      G4_Kernel& kernel;
      G4_BB* exitBB = nullptr;
      std::vector<std::unordered_set<G4_BB*>> postDoms;
      std::vector<std::vector<G4_BB*>> immPostDoms;
  
      void updateImmPostDom();
  };
  } // vISA::
  #endif // FLOWGRAPH_H
  