//===-------- polly/TempScopInfo.h - Extract TempScops ----------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Collect information about the control flow regions detected by the Scop
// detection, such that this information can be translated info its polyhedral
// representation.
//
//===----------------------------------------------------------------------===//

#ifndef POLLY_TEMP_SCOP_EXTRACTION_H
#define POLLY_TEMP_SCOP_EXTRACTION_H

#include "polly/ScopDetection.h"
#include "llvm/Analysis/RegionPass.h"
#include "llvm/IR/Instructions.h"

namespace llvm {
class DataLayout;
}

using namespace llvm;

namespace polly {

//===---------------------------------------------------------------------===//
/// @brief A memory access described by a SCEV expression and the access type.
class IRAccess {
public:
  Value *BaseAddress;

  const SCEV *Offset;

  // The type of the scev affine function
  enum TypeKind {
    READ = 0x1,
    MUST_WRITE = 0x2,
    MAY_WRITE = 0x3,
  };

private:
  unsigned ElemBytes;
  TypeKind Type;
  bool IsAffine;

public:
  SmallVector<const SCEV *, 4> Subscripts, Sizes;

  explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
                    unsigned elemBytes, bool Affine)
      : BaseAddress(BaseAddress), Offset(Offset), ElemBytes(elemBytes),
        Type(Type), IsAffine(Affine) {}

  explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
                    unsigned elemBytes, bool Affine,
                    SmallVector<const SCEV *, 4> Subscripts,
                    SmallVector<const SCEV *, 4> Sizes)
      : BaseAddress(BaseAddress), Offset(Offset), ElemBytes(elemBytes),
        Type(Type), IsAffine(Affine), Subscripts(Subscripts), Sizes(Sizes) {}

  enum TypeKind getType() const { return Type; }

  Value *getBase() const { return BaseAddress; }

  const SCEV *getOffset() const { return Offset; }

  unsigned getElemSizeInBytes() const { return ElemBytes; }

  bool isAffine() const { return IsAffine; }

  bool isRead() const { return Type == READ; }

  bool isWrite() const { return Type == MUST_WRITE; }

  void setMayWrite() { Type = MAY_WRITE; }

  bool isMayWrite() const { return Type == MAY_WRITE; }

  bool isScalar() const { return Subscripts.size() == 0; }

  void print(raw_ostream &OS) const;
};

class Comparison {
  const SCEV *LHS;
  const SCEV *RHS;

  ICmpInst::Predicate Pred;

public:
  Comparison(const SCEV *LHS, const SCEV *RHS, ICmpInst::Predicate Pred)
      : LHS(LHS), RHS(RHS), Pred(Pred) {}

  const SCEV *getLHS() const { return LHS; }
  const SCEV *getRHS() const { return RHS; }

  ICmpInst::Predicate getPred() const { return Pred; }
  void print(raw_ostream &OS) const;
};

//===---------------------------------------------------------------------===//
/// Types
// The condition of a Basicblock, combine brcond with "And" operator.
typedef SmallVector<Comparison, 4> BBCond;

/// Maps from a loop to the affine function expressing its backedge taken count.
/// The backedge taken count already enough to express iteration domain as we
/// only allow loops with canonical induction variable.
/// A canonical induction variable is:
/// an integer recurrence that starts at 0 and increments by one each time
/// through the loop.
typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;

/// Mapping BBs to its condition constrains
typedef std::map<const BasicBlock *, BBCond> BBCondMapType;

typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;

//===---------------------------------------------------------------------===//
/// @brief Scop represent with llvm objects.
///
/// A helper class for remembering the parameter number and the max depth in
/// this Scop, and others context.
class TempScop {
  // The Region.
  Region &R;

  // Remember the bounds of loops, to help us build iteration domain of BBs.
  const BBCondMapType &BBConds;

  // Access function of bbs.
  AccFuncMapType &AccFuncMap;

  friend class TempScopInfo;

  explicit TempScop(Region &r, BBCondMapType &BBCmps,
                    AccFuncMapType &accFuncMap)
      : R(r), BBConds(BBCmps), AccFuncMap(accFuncMap) {}

public:
  ~TempScop();

  /// @brief Get the maximum Region contained by this Scop.
  ///
  /// @return The maximum Region contained by this Scop.
  Region &getMaxRegion() const { return R; }

  /// @brief Get the condition from entry block of the Scop to a BasicBlock
  ///
  /// @param BB The BasicBlock
  ///
  /// @return The condition from entry block of the Scop to a BB
  ///
  const BBCond *getBBCond(const BasicBlock *BB) const {
    BBCondMapType::const_iterator at = BBConds.find(BB);
    return at != BBConds.end() ? &(at->second) : 0;
  }

  /// @brief Get all access functions in a BasicBlock
  ///
  /// @param  BB The BasicBlock that containing the access functions.
  ///
  /// @return All access functions in BB
  ///
  AccFuncSetType *getAccessFunctions(const BasicBlock *BB) {
    AccFuncMapType::iterator at = AccFuncMap.find(BB);
    return at != AccFuncMap.end() ? &(at->second) : 0;
  }
  //@}

  /// @brief Print the Temporary Scop information.
  ///
  /// @param OS The output stream the access functions is printed to.
  /// @param SE The ScalarEvolution that help printing Temporary Scop
  ///           information.
  /// @param LI The LoopInfo that help printing the access functions.
  void print(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI) const;

  /// @brief Print the access functions and loop bounds in this Scop.
  ///
  /// @param OS The output stream the access functions is printed to.
  /// @param SE The ScalarEvolution that help printing the access functions.
  /// @param LI The LoopInfo that help printing the access functions.
  void printDetail(raw_ostream &OS, ScalarEvolution *SE, LoopInfo *LI,
                   const Region *Reg, unsigned ind) const;
};

typedef std::map<const Region *, TempScop *> TempScopMapType;
//===----------------------------------------------------------------------===//
/// @brief The Function Pass to extract temporary information for Static control
///        part in llvm function.
///
class TempScopInfo : public FunctionPass {
  //===-------------------------------------------------------------------===//
  TempScopInfo(const TempScopInfo &) = delete;
  const TempScopInfo &operator=(const TempScopInfo &) = delete;

  // The ScalarEvolution to help building Scop.
  ScalarEvolution *SE;

  // LoopInfo for information about loops
  LoopInfo *LI;

  // The AliasAnalysis to build AliasSetTracker.
  AliasAnalysis *AA;

  // Valid Regions for Scop
  ScopDetection *SD;

  // For condition extraction support.
  DominatorTree *DT;
  PostDominatorTree *PDT;

  // Target data for element size computing.
  const DataLayout *TD;

  // And also Remember the constrains for BBs
  BBCondMapType BBConds;

  // Access function of statements (currently BasicBlocks) .
  AccFuncMapType AccFuncMap;

  // Pre-created zero for the scalar accesses, with it we do not need create a
  // zero scev every time when we need it.
  const SCEV *ZeroOffset;

  // Mapping regions to the corresponding Scop in current function.
  TempScopMapType TempScops;

  // Clear the context.
  void clear();

  /// @brief Build condition constrains to BBs in a valid Scop.
  ///
  /// @param BB The BasicBlock to build condition constrains
  /// @param R  The region for the current TempScop.
  void buildCondition(BasicBlock *BB, Region &R);

  // Build the affine function of the given condition
  Comparison buildAffineCondition(Value &V, bool inverted);

  // Return the temporary Scop information of Region R, where R must be a valid
  // part of Scop
  TempScop *getTempScop(Region &R);

  // Build the temprory information of Region R, where R must be a valid part
  // of Scop.
  TempScop *buildTempScop(Region &R);

  /// @brief Build an instance of IRAccess from the Load/Store instruction.
  ///
  /// @param Inst       The Load/Store instruction that access the memory
  /// @param L          The parent loop of the instruction
  /// @param R          The region on which we are going to build a TempScop
  /// @param BoxedLoops The set of loops that are overapproximated in @p R.
  ///
  /// @return     The IRAccess to describe the access function of the
  ///             instruction.
  IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R,
                         const ScopDetection::BoxedLoopsSetTy *BoxedLoops);

  /// @brief Analyze and extract the cross-BB scalar dependences (or,
  ///        dataflow dependencies) of an instruction.
  ///
  /// @param Inst               The instruction to be analyzed
  /// @param R                  The SCoP region
  /// @param NonAffineSubRegion The non affine sub-region @p Inst is in.
  ///
  /// @return     True if the Instruction is used in other BB and a scalar write
  ///             Access is required.
  bool buildScalarDependences(Instruction *Inst, Region *R,
                              Region *NonAffineSubRegio);

  /// @brief Create IRAccesses for the given PHI node in the given region.
  ///
  /// @param PHI                The PHI node to be handled
  /// @param R                  The SCoP region
  /// @param Functions          The access functions of the current BB
  /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
  void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
                        Region *NonAffineSubRegion);

  /// @brief Build the access functions for the subregion @p SR.
  ///
  /// @param R  The SCoP region.
  /// @param SR A subregion of @p R.
  void buildAccessFunctions(Region &R, Region &SR);

  /// @brief Build the access functions for the basic block @p BB
  ///
  /// @param R                  The SCoP region.
  /// @param BB                 A basic block in @p R.
  /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
  void buildAccessFunctions(Region &R, BasicBlock &BB,
                            Region *NonAffineSubRegion = nullptr);

public:
  static char ID;
  explicit TempScopInfo() : FunctionPass(ID) {}
  ~TempScopInfo();

  /// @brief Get the temporay Scop information in LLVM IR represent
  ///        for Region R.
  ///
  /// @return The Scop information in LLVM IR represent.
  TempScop *getTempScop(const Region *R) const;

  /// @name FunctionPass interface
  //@{
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  virtual void releaseMemory() { clear(); }
  virtual bool runOnFunction(Function &F);
  virtual void print(raw_ostream &OS, const Module *) const;
  //@}
};

} // end namespace polly

namespace llvm {
class PassRegistry;
void initializeTempScopInfoPass(llvm::PassRegistry &);
}

#endif