text: // Licensed to the .NET Foundation under one or more agreements.
  // The .NET Foundation licenses this file to you under the MIT license.
  // See the LICENSE file in the project root for more information.
  
  /*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  XX                                                                           XX
  XX                            LoopCloning                                    XX
  XX                                                                           XX
  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
  
      Loop cloning optimizations comprise of the following steps:
          - Loop detection logic which is existing logic in the JIT that records
          loop information with loop flags.
          - The next step is to identify loop optimization candidates. This is done
          by optObtainLoopCloningOpts. The loop context variable is updated with
          all the necessary information (for ex: block, stmt, tree information)
          to do the optimization later.
              a) This involves checking if the loop is well-formed with respect to
              the optimization being performed.
              b) In array bounds check case, reconstructing the morphed GT_INDEX
              nodes back to their array representation.
                  i) The array index is stored in the "context" variable with
                  additional block, tree, stmt info.
          - Once the optimization candidates are identified, we derive cloning conditions
            For ex: to clone a simple "for (i=0; i<n; ++i) { a[i] }" loop, we need the
            following conditions:
                (a != null) && ((n >= 0) & (n <= a.length) & (stride > 0))
                a) Note the short circuit AND for (a != null). These are called block
                conditions or deref-conditions since these conditions need to be in their
                own blocks to be able to short-circuit.
                   i) For a doubly nested loop on i, j, we would then have
                   conditions like
                   (a != null) && (i < a.len) && (a[i] != null) && (j < a[i].len)
                   all short-circuiting creating blocks.
  
                   Advantage:
                      All conditions are checked before we enter the fast path. So fast
                      path gets as fast as it can be.
  
                   Disadvantage:
                      Creation of blocks.
  
                   Heuristic:
                      Therefore we will not clone if we exceed creating 4 blocks.
  
                b) The other conditions called cloning conditions are transformed into LC_Condition
                structs which are then optimized.
                   i) Optimization of conditions involves removing redundant condition checks.
                   ii) If some conditions evaluate to true statically, then they are removed.
                   iii) If any condition evaluates to false statically, then loop cloning is
                   aborted for that loop.
          - Then the block splitting occurs and loop cloning conditions is transformed into
          GenTree and added to the loop cloning choice block.
  
      Preconditions
          - Loop detection should have completed and the loop table should be
          populated with the loop dscs.
          - The loops that will be considered are the ones with the LPFLG_ITER
          marked on them.
  
      Limitations
          - For array based optimizations the loop choice condition is checked
          before the loop body. This implies that the loop initializer statement
          has not executed at the time of the check. So any loop cloning condition
          involving the initial value of the loop counter cannot be condition checked
          as it hasn't been assigned yet at the time of condition checking. Therefore
          the initial value has to be statically known. This can be fixed with further
          effort.
  
      Assumption
          - The assumption is that the optimization candidates collected during the
          identification phase will be the ones that will be optimized. In other words,
          the loop that is present originally will be the fast path. Explicitly, the cloned
          path will be the slow path and will be unoptimized. This allows us to
          collect additional information at the same time of identifying the optimization
          candidates. This later helps us to perform the optimizations during actual cloning.
          - All loop cloning choice conditions will automatically be "AND"-ed. These are
          bitwise AND operations.
          - Perform short circuit AND for (array != null) side effect check
          before hoisting (limit <= a.length) check.
            For ex: to clone a simple "for (i=0; i<n; ++i) { a[i] }" loop, we need the
            following conditions:
                (a != null) && ((n >= 0) & (n <= a.length) & (stride > 0))
  
  */
  #pragma once
  
  class Compiler;
  
  /**
   *
   *  Represents an array access and associated bounds checks.
   *  Array access is required have the array and indices in local variables.
   *  This struct is constructed using a GT_INDEX node that is broken into
   *  its sub trees.
   *
   */
  struct ArrIndex
  {
      unsigned                      arrLcl;   // The array base local num
      JitExpandArrayStack<unsigned> indLcls;  // The indices local nums
      JitExpandArrayStack<GenTree*> bndsChks; // The bounds checks nodes along each dimension.
      unsigned                      rank;     // Rank of the array
      BasicBlock*                   useBlock; // Block where the [] occurs
  
      ArrIndex(CompAllocator alloc) : arrLcl(BAD_VAR_NUM), indLcls(alloc), bndsChks(alloc), rank(0), useBlock(nullptr)
      {
      }
  
  #ifdef DEBUG
      void Print(unsigned dim = -1)
      {
          printf("V%02d", arrLcl);
          for (unsigned i = 0; i < ((dim == -1) ? rank : dim); ++i)
          {
              printf("[V%02d]", indLcls.GetRef(i));
          }
      }
  #endif
  };
  
  // Forward declarations
  #define LC_OPT(en) struct en##OptInfo;
  #include "loopcloningopts.h"
  
  /**
   *
   *  LcOptInfo represents the optimization information for loop cloning,
   *  other classes are supposed to derive from this base class.
   *
   *  Example usage:
   *  LcMdArrayOptInfo is multi-dimensional array optimization for which the
   *  loop can be cloned.
   *  LcArrIndexOptInfo is a jagged array optimization for which the loop
   *  can be cloned.
   *
   *  So LcOptInfo represents any type of optimization opportunity that
   *  occurs in a loop and the metadata for the optimization is stored in
   *  this class.
   */
  struct LcOptInfo
  {
      enum OptType
      {
  #undef LC_OPT
  #define LC_OPT(en) en,
  #include "loopcloningopts.h"
      };
  
      void*   optInfo;
      OptType optType;
      LcOptInfo(void* optInfo, OptType optType) : optInfo(optInfo), optType(optType)
      {
      }
  
      OptType GetOptType()
      {
          return optType;
      }
  #undef LC_OPT
  #define LC_OPT(en)                                                                                                     \
      en##OptInfo* As##en##OptInfo()                                                                                     \
      {                                                                                                                  \
          assert(optType == en);                                                                                         \
          return reinterpret_cast<en##OptInfo*>(this);                                                                   \
      }
  #include "loopcloningopts.h"
  };
  
  /**
   *
   * Optimization info for a multi-dimensional array.
   */
  struct LcMdArrayOptInfo : public LcOptInfo
  {
      GenTreeArrElem* arrElem; // "arrElem" node of an MD array.
      unsigned        dim;     // "dim" represents upto what level of the rank this optimization applies to.
                               //    For example, a[i,j,k] could be the MD array "arrElem" but if "dim" is 2,
                               //    then this node is treated as though it were a[i,j]
      ArrIndex* index;         // "index" cached computation in the form of an ArrIndex representation.
  
      LcMdArrayOptInfo(GenTreeArrElem* arrElem, unsigned dim)
          : LcOptInfo(this, LcMdArray), arrElem(arrElem), dim(dim), index(nullptr)
      {
      }
  
      ArrIndex* GetArrIndexForDim(CompAllocator alloc)
      {
          if (index == nullptr)
          {
              index       = new (alloc) ArrIndex(alloc);
              index->rank = arrElem->gtArrRank;
              for (unsigned i = 0; i < dim; ++i)
              {
                  index->indLcls.Push(arrElem->gtArrInds[i]->gtLclVarCommon.gtLclNum);
              }
              index->arrLcl = arrElem->gtArrObj->gtLclVarCommon.gtLclNum;
          }
          return index;
      }
  };
  
  /**
   *
   * Optimization info for a jagged array.
   */
  struct LcJaggedArrayOptInfo : public LcOptInfo
  {
      unsigned dim;      // "dim" represents upto what level of the rank this optimization applies to.
                         //    For example, a[i][j][k] could be the jagged array but if "dim" is 2,
                         //    then this node is treated as though it were a[i][j]
      ArrIndex arrIndex; // ArrIndex representation of the array.
      GenTree* stmt;     // "stmt" where the optimization opportunity occurs.
  
      LcJaggedArrayOptInfo(ArrIndex& arrIndex, unsigned dim, GenTree* stmt)
          : LcOptInfo(this, LcJaggedArray), dim(dim), arrIndex(arrIndex), stmt(stmt)
      {
      }
  };
  
  /**
   *
   * Symbolic representation of a.length, or a[i][j].length or a[i,j].length and so on.
   * OperType decides whether "arrLength" is invoked on the array or if it is just an array.
   */
  struct LC_Array
  {
      enum ArrType
      {
          Invalid,
          Jagged,
          MdArray
      };
  
      enum OperType
      {
          None,
          ArrLen,
      };
  
      ArrType   type;     // The type of the array on which to invoke length operator.
      ArrIndex* arrIndex; // ArrIndex representation of this array.
  
      OperType oper;
  
  #ifdef DEBUG
      void Print()
      {
          arrIndex->Print(dim);
          if (oper == ArrLen)
          {
              printf(".Length");
          }
      }
  #endif
  
      int dim; // "dim" = which index to invoke arrLen on, if -1 invoke on the whole array
               //     Example 1: a[0][1][2] and dim =  2 implies a[0][1].length
               //     Example 2: a[0][1][2] and dim = -1 implies a[0][1][2].length
      LC_Array() : type(Invalid), dim(-1)
      {
      }
      LC_Array(ArrType type, ArrIndex* arrIndex, int dim, OperType oper)
          : type(type), arrIndex(arrIndex), oper(oper), dim(dim)
      {
      }
  
      LC_Array(ArrType type, ArrIndex* arrIndex, OperType oper) : type(type), arrIndex(arrIndex), oper(oper), dim(-1)
      {
      }
  
      // Equality operator
      bool operator==(const LC_Array& that) const
      {
          assert(type != Invalid && that.type != Invalid);
  
          // Types match and the array base matches.
          if (type != that.type || arrIndex->arrLcl != that.arrIndex->arrLcl || oper != that.oper)
          {
              return false;
          }
  
          // If the dim ranks are not matching, quit.
          int rank1 = GetDimRank();
          int rank2 = that.GetDimRank();
          if (rank1 != rank2)
          {
              return false;
          }
  
          // Check for the indices.
          for (int i = 0; i < rank1; ++i)
          {
              if (arrIndex->indLcls[i] != that.arrIndex->indLcls[i])
              {
                  return false;
              }
          }
          return true;
      }
  
      // The max dim on which length is invoked.
      int GetDimRank() const
      {
          return (dim < 0) ? (int)arrIndex->rank : dim;
      }
  
      // Get a tree representation for this symbolic a.length
      GenTree* ToGenTree(Compiler* comp);
  };
  
  /**
   *
   * Symbolic representation of either a constant like 1, 2 or a variable V02, V03 etc. or an "LC_Array" or the null
   * constant.
   */
  struct LC_Ident
  {
      enum IdentType
      {
          Invalid,
          Const,
          Var,
          ArrLen,
          Null,
      };
  
      unsigned  constant; // The constant value if this node is of type "Const", or the lcl num if "Var"
      LC_Array  arrLen;   // The LC_Array if the type is "ArrLen"
      IdentType type;     // The type of this object
  
      // Equality operator
      bool operator==(const LC_Ident& that) const
      {
          switch (type)
          {
              case Const:
              case Var:
                  return (type == that.type) && constant == that.constant;
              case ArrLen:
                  return (type == that.type) && (arrLen == that.arrLen);
              case Null:
                  return (type == that.type);
              default:
                  assert(!"Unknown LC_Ident type");
                  unreached();
          }
      }
  
  #ifdef DEBUG
      void Print()
      {
          switch (type)
          {
              case Const:
                  printf("%u", constant);
                  break;
              case Var:
                  printf("V%02d", constant);
                  break;
              case ArrLen:
                  arrLen.Print();
                  break;
              case Null:
                  printf("null");
                  break;
              default:
                  assert(false);
                  break;
          }
      }
  #endif
  
      LC_Ident() : type(Invalid)
      {
      }
      LC_Ident(unsigned constant, IdentType type) : constant(constant), type(type)
      {
      }
      explicit LC_Ident(IdentType type) : type(type)
      {
      }
      explicit LC_Ident(const LC_Array& arrLen) : arrLen(arrLen), type(ArrLen)
      {
      }
  
      // Convert this symbolic representation into a tree node.
      GenTree* ToGenTree(Compiler* comp);
  };
  
  /**
   *
   *  Symbolic representation of an expr that involves an "LC_Ident"
   */
  struct LC_Expr
  {
      enum ExprType
      {
          Invalid,
          Ident,
      };
  
      LC_Ident ident;
      ExprType type;
  
      // Equality operator
      bool operator==(const LC_Expr& that) const
      {
          assert(type != Invalid && that.type != Invalid);
  
          // If the types don't match quit.
          if (type != that.type)
          {
              return false;
          }
  
          // Check if the ident match.
          return (ident == that.ident);
      }
  
  #ifdef DEBUG
      void Print()
      {
          if (type == Ident)
          {
              ident.Print();
          }
      }
  #endif
  
      LC_Expr() : type(Invalid)
      {
      }
      explicit LC_Expr(const LC_Ident& ident) : ident(ident), type(Ident)
      {
      }
  
      // Convert LC_Expr into a tree node.
      GenTree* ToGenTree(Compiler* comp);
  };
  
  /**
   *
   *  Symbolic representation of a conditional operation involving two "LC_Expr":
   *  LC_Expr < LC_Expr, for example: i > 0, i < a.length
   */
  struct LC_Condition
  {
      LC_Expr    op1;
      LC_Expr    op2;
      genTreeOps oper;
  
  #ifdef DEBUG
      void Print()
      {
          op1.Print();
          printf(" %s ", GenTree::OpName(oper));
          op2.Print();
      }
  #endif
  
      // Check if the condition evaluates statically to true or false, i < i => false, a.length > 0 => true
      // The result is put in "pResult" parameter and is valid if the method returns "true". Otherwise, the
      // condition could not be evaluated.
      bool Evaluates(bool* pResult);
  
      // Check if two conditions can be combined to yield one condition.
      bool Combines(const LC_Condition& cond, LC_Condition* newCond);
  
      LC_Condition()
      {
      }
      LC_Condition(genTreeOps oper, const LC_Expr& op1, const LC_Expr& op2) : op1(op1), op2(op2), oper(oper)
      {
      }
  
      // Convert this conditional operation into a GenTree.
      GenTree* ToGenTree(Compiler* comp);
  };
  
  /**
   *  A deref tree of an array expression.
   *  a[i][j][k], b[i] and a[i][y][k] are the occurrences in the loop, then, the tree would be:
   *      a => {
   *          i => {
   *              j => {
   *                  k => {}
   *              },
   *              y => {
   *                  k => {}
   *              },
   *          }
   *      },
   *      b => {
   *          i => {}
   *      }
   */
  struct LC_Deref
  {
      const LC_Array                  array;
      JitExpandArrayStack<LC_Deref*>* children;
  
      unsigned level;
  
      LC_Deref(const LC_Array& array, unsigned level) : array(array), children(nullptr), level(level)
      {
      }
  
      LC_Deref* Find(unsigned lcl);
  
      unsigned Lcl();
  
      bool HasChildren();
      void EnsureChildren(CompAllocator alloc);
      static LC_Deref* Find(JitExpandArrayStack<LC_Deref*>* children, unsigned lcl);
  
      void DeriveLevelConditions(JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* len);
  #ifdef DEBUG
      void Print(unsigned indent = 0)
      {
          unsigned tab = 4 * indent;
          printf("%*s%d,%d => {", tab, "", Lcl(), level);
          if (children != nullptr)
          {
              for (unsigned i = 0; i < children->Size(); ++i)
              {
                  if (i > 0)
                  {
                      printf(",");
                  }
                  printf("\n");
  #ifdef _MSC_VER
                  (*children)[i]->Print(indent + 1);
  #else  // _MSC_VER
                  (*((JitExpandArray<LC_Deref*>*)children))[i]->Print(indent + 1);
  #endif // _MSC_VER
              }
          }
          printf("\n%*s}", tab, "");
      }
  #endif
  };
  
  /**
   *
   *  The "context" represents data that is used for making loop-cloning decisions.
   *   - The data is the collection of optimization opportunities
   *   - and the conditions (LC_Condition) that decide between the fast
   *     path or the slow path.
   *
   *   BNF for LC_Condition:
   *       LC_Condition :  LC_Expr genTreeOps LC_Expr
   *       LC_Expr      :  LC_Ident | LC_Ident + Constant
   *       LC_Ident     :  Constant | Var | LC_Array
   *       LC_Array    :  .
   *       genTreeOps   :  GT_GE | GT_LE | GT_GT | GT_LT
   *
   */
  struct LoopCloneContext
  {
      CompAllocator                     alloc;   // The allocator
      JitExpandArrayStack<LcOptInfo*>** optInfo; // The array of optimization opportunities found in each loop. (loop x
                                                 // optimization-opportunities)
      JitExpandArrayStack<LC_Condition>** conditions; // The array of conditions that influence which path to take for
                                                      // each
                                                      // loop. (loop x cloning-conditions)
      JitExpandArrayStack<LC_Array>** derefs;         // The array of dereference conditions found in each loop. (loop x
                                                      // deref-conditions)
      JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>** blockConditions; // The array of block levels of
                                                                                 // conditions for
                                                                                 // each loop. (loop x level x conditions)
  
      LoopCloneContext(unsigned loopCount, CompAllocator alloc) : alloc(alloc)
      {
          optInfo         = new (alloc) JitExpandArrayStack<LcOptInfo*>*[loopCount];
          conditions      = new (alloc) JitExpandArrayStack<LC_Condition>*[loopCount];
          derefs          = new (alloc) JitExpandArrayStack<LC_Array>*[loopCount];
          blockConditions = new (alloc) JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>*[loopCount];
          for (unsigned i = 0; i < loopCount; ++i)
          {
              optInfo[i]         = nullptr;
              conditions[i]      = nullptr;
              derefs[i]          = nullptr;
              blockConditions[i] = nullptr;
          }
      }
  
      // Evaluate conditions into a JTRUE stmt and put it in the block. Reverse condition if 'reverse' is true.
      void CondToStmtInBlock(Compiler* comp, JitExpandArrayStack<LC_Condition>& conds, BasicBlock* block, bool reverse);
  
      // Get all the optimization information for loop "loopNum"; This information is held in "optInfo" array.
      // If NULL this allocates the optInfo[loopNum] array for "loopNum"
      JitExpandArrayStack<LcOptInfo*>* EnsureLoopOptInfo(unsigned loopNum);
  
      // Get all the optimization information for loop "loopNum"; This information is held in "optInfo" array.
      // If NULL this does not allocate the optInfo[loopNum] array for "loopNum"
      JitExpandArrayStack<LcOptInfo*>* GetLoopOptInfo(unsigned loopNum);
  
      // Cancel all optimizations for loop "loopNum" by clearing out the "conditions" member if non-null
      // and setting the optInfo to "null.", If "null", then the user of this class is not supposed to
      // clone this loop.
      void CancelLoopOptInfo(unsigned loopNum);
  
      // Get the conditions that decide which loop to take for "loopNum." If NULL allocate an empty array.
      JitExpandArrayStack<LC_Condition>* EnsureConditions(unsigned loopNum);
  
      // Get the conditions for loop. No allocation is performed.
      JitExpandArrayStack<LC_Condition>* GetConditions(unsigned loopNum);
  
      // Ensure that the "deref" conditions array is allocated.
      JitExpandArrayStack<LC_Array>* EnsureDerefs(unsigned loopNum);
  
      // Get block conditions for each loop, no allocation is performed.
      JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* GetBlockConditions(unsigned loopNum);
  
      // Ensure that the block condition is present, if not allocate space.
      JitExpandArrayStack<JitExpandArrayStack<LC_Condition>*>* EnsureBlockConditions(unsigned loopNum,
                                                                                     unsigned totalBlocks);
  
      // Print the block conditions for the loop.
      void PrintBlockConditions(unsigned loopNum);
  
      // Does the loop have block conditions?
      bool HasBlockConditions(unsigned loopNum);
  
      // Evaluate the conditions for "loopNum" and indicate if they are either all true or any of them are false.
      // "pAllTrue" implies all the conditions are statically known to be true.
      // "pAnyFalse" implies at least one condition is statically known to be false.
      // If neither of them are true, then some conditions' evaluations are statically unknown.
      //
      // If all conditions yield true, then the caller doesn't need to clone the loop, but it can perform
      // fast path optimizations.
      // If any condition yields false, then the caller needs to abort cloning the loop (neither clone nor
      // fast path optimizations.)
      //
      // Assumes the conditions involve an AND join operator.
      void EvaluateConditions(unsigned loopNum, bool* pAllTrue, bool* pAnyFalse DEBUGARG(bool verbose));
  
  private:
      void OptimizeConditions(JitExpandArrayStack<LC_Condition>& conds);
  
  public:
      // Optimize conditions to remove redundant conditions.
      void OptimizeConditions(unsigned loopNum DEBUGARG(bool verbose));
  
      void OptimizeBlockConditions(unsigned loopNum DEBUGARG(bool verbose));
  
  #ifdef DEBUG
      void PrintConditions(unsigned loopNum);
  #endif
  };
  