//===- ForwardOpTree.h ------------------------------------------*- C++ -*-===//

//

//                     The LLVM Compiler Infrastructure

//

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

//

// Move instructions between statements.

//

//===----------------------------------------------------------------------===//

#include "polly/ForwardOpTree.h"

#include "polly/Options.h"

#include "polly/ScopBuilder.h"

#include "polly/ScopInfo.h"

#include "polly/ScopPass.h"

#include "polly/Support/GICHelper.h"

#include "polly/Support/ISLOStream.h"

#include "polly/Support/ISLTools.h"

#include "polly/Support/VirtualInstruction.h"

#include "polly/ZoneAlgo.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallVector.h"

#include "llvm/ADT/Statistic.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/ValueTracking.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/Value.h"

#include "llvm/Pass.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/CommandLine.h"

#include "llvm/Support/Compiler.h"

#include "llvm/Support/Debug.h"

#include "llvm/Support/ErrorHandling.h"

#include "llvm/Support/raw_ostream.h"

#include "isl/ctx.h"

#include "isl/isl-noexceptions.h"

#include <cassert>

#include <memory>

#define DEBUG_TYPE "polly-optree"

using namespace llvm;

using namespace polly;

static cl::opt<bool>

    AnalyzeKnown("polly-optree-analyze-known",

                 cl::desc("Analyze array contents for load forwarding"),

                 cl::cat(PollyCategory), cl::init(true), cl::Hidden);

static cl::opt<bool>

    NormalizePHIs("polly-optree-normalize-phi",

                  cl::desc("Replace PHIs by their incoming values"),

                  cl::cat(PollyCategory), cl::init(false), cl::Hidden);

static cl::opt<unsigned>

    MaxOps("polly-optree-max-ops",

           cl::desc("Maximum number of ISL operations to invest for known "

                    "analysis; 0=no limit"),

           cl::init(1000000), cl::cat(PollyCategory), cl::Hidden);

STATISTIC(KnownAnalyzed, "Number of successfully analyzed SCoPs");

STATISTIC(KnownOutOfQuota,

          "Analyses aborted because max_operations was reached");

STATISTIC(TotalInstructionsCopied, "Number of copied instructions");

STATISTIC(TotalKnownLoadsForwarded,

          "Number of forwarded loads because their value was known");

STATISTIC(TotalReloads, "Number of reloaded values");

STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");

STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");

STATISTIC(TotalModifiedStmts,

          "Number of statements with at least one forwarded tree");

STATISTIC(ScopsModified, "Number of SCoPs with at least one forwarded tree");

STATISTIC(NumValueWrites, "Number of scalar value writes after OpTree");

STATISTIC(NumValueWritesInLoops,

          "Number of scalar value writes nested in affine loops after OpTree");

STATISTIC(NumPHIWrites, "Number of scalar phi writes after OpTree");

STATISTIC(NumPHIWritesInLoops,

          "Number of scalar phi writes nested in affine loops after OpTree");

STATISTIC(NumSingletonWrites, "Number of singleton writes after OpTree");

STATISTIC(NumSingletonWritesInLoops,

          "Number of singleton writes nested in affine loops after OpTree");

namespace {

/// The state of whether an operand tree was/can be forwarded.

///

/// The items apply to an instructions and its operand tree with the instruction

/// as the root element. If the value in question is not an instruction in the

/// SCoP, it can be a leaf of an instruction's operand tree.

enum ForwardingDecision {

  /// The root instruction or value cannot be forwarded at all.

  FD_CannotForward,

  /// The root instruction or value can be forwarded as a leaf of a larger

  /// operand tree.

  /// It does not make sense to move the value itself, it would just replace it

  /// by a use of itself. For instance, a constant "5" used in a statement can

  /// be forwarded, but it would just replace it by the same constant "5".

  /// However, it makes sense to move as an operand of

  ///

  ///   %add = add 5, 5

  ///

  /// where "5" is moved as part of a larger operand tree. "5" would be placed

  /// (disregarding for a moment that literal constants don't have a location

  /// and can be used anywhere) into the same statement as %add would.

  FD_CanForwardLeaf,

  /// The root instruction can be forwarded and doing so avoids a scalar

  /// dependency.

  ///

  /// This can be either because the operand tree can be moved to the target

  /// statement, or a memory access is redirected to read from a different

  /// location.

  FD_CanForwardProfitably,

  /// Used to indicate that a forwarding has be carried out successfully, and

  /// the forwarded memory access can be deleted.

  FD_DidForwardTree,

  /// Used to indicate that a forwarding has be carried out successfully, and

  /// the forwarded memory access is being reused.

  FD_DidForwardLeaf,

  /// A forwarding method cannot be applied to the operand tree.

  /// The difference to FD_CannotForward is that there might be other methods

  /// that can handle it.

  /// The conditions that make an operand tree applicable must be checked even

  /// with DoIt==true because a method following the one that returned

  /// FD_NotApplicable might have returned FD_CanForwardTree.

  FD_NotApplicable

};

/// Implementation of operand tree forwarding for a specific SCoP.

///

/// For a statement that requires a scalar value (through a value read

/// MemoryAccess), see if its operand can be moved into the statement. If so,

/// the MemoryAccess is removed and the all the operand tree instructions are

/// moved into the statement. All original instructions are left in the source

/// statements. The simplification pass can clean these up.

class ForwardOpTreeImpl : ZoneAlgorithm {

private:

  /// Scope guard to limit the number of isl operations for this pass.

  IslMaxOperationsGuard &MaxOpGuard;

  /// How many instructions have been copied to other statements.

  int NumInstructionsCopied = 0;

  /// Number of loads forwarded because their value was known.

  int NumKnownLoadsForwarded = 0;

  /// Number of values reloaded from known array elements.

  int NumReloads = 0;

  /// How many read-only accesses have been copied.

  int NumReadOnlyCopied = 0;

  /// How many operand trees have been forwarded.

  int NumForwardedTrees = 0;

  /// Number of statements with at least one forwarded operand tree.

  int NumModifiedStmts = 0;

  /// Whether we carried out at least one change to the SCoP.

  bool Modified = false;

  /// Contains the zones where array elements are known to contain a specific

  /// value.

  /// { [Element[] -> Zone[]] -> ValInst[] }

  /// @see computeKnown()

  isl::union_map Known;

  /// Translator for newly introduced ValInsts to already existing ValInsts such

  /// that new introduced load instructions can reuse the Known analysis of its

  /// original load. { ValInst[] -> ValInst[] }

  isl::union_map Translator;

  /// A cache for getDefToTarget().

  DenseMap<std::pair<ScopStmt *, ScopStmt *>, isl::map> DefToTargetCache;

  /// Get list of array elements that do contain the same ValInst[] at Domain[].

  ///

  /// @param ValInst { Domain[] -> ValInst[] }

  ///                The values for which we search for alternative locations,

  ///                per statement instance.

  ///

  /// @return { Domain[] -> Element[] }

  ///         For each statement instance, the array elements that contain the

  ///         same ValInst.

  isl::union_map findSameContentElements(isl::union_map ValInst) {

    assert(!ValInst.is_single_valued().is_false());

    // { Domain[] }

    isl::union_set Domain = ValInst.domain();

    // { Domain[] -> Scatter[] }

    isl::union_map Schedule = getScatterFor(Domain);

    // { Element[] -> [Scatter[] -> ValInst[]] }

    isl::union_map MustKnownCurried =

        convertZoneToTimepoints(Known, isl::dim::in, false, true).curry();

    // { [Domain[] -> ValInst[]] -> Scatter[] }

    isl::union_map DomValSched = ValInst.domain_map().apply_range(Schedule);

    // { [Scatter[] -> ValInst[]] -> [Domain[] -> ValInst[]] }

    isl::union_map SchedValDomVal =

        DomValSched.range_product(ValInst.range_map()).reverse();

    // { Element[] -> [Domain[] -> ValInst[]] }

    isl::union_map MustKnownInst = MustKnownCurried.apply_range(SchedValDomVal);

    // { Domain[] -> Element[] }

    isl::union_map MustKnownMap =

        MustKnownInst.uncurry().domain().unwrap().reverse();

    simplify(MustKnownMap);

    return MustKnownMap;

  }

  /// Find a single array element for each statement instance, within a single

  /// array.

  ///

  /// @param MustKnown { Domain[] -> Element[] }

  ///                  Set of candidate array elements.

  /// @param Domain    { Domain[] }

  ///                  The statement instance for which we need elements for.

  ///

  /// @return { Domain[] -> Element[] }

  ///         For each statement instance, an array element out of @p MustKnown.

  ///         All array elements must be in the same array (Polly does not yet

  ///         support reading from different accesses using the same

  ///         MemoryAccess). If no mapping for all of @p Domain exists, returns

  ///         null.

  isl::map singleLocation(isl::union_map MustKnown, isl::set Domain) {

    // { Domain[] -> Element[] }

    isl::map Result;

    // MemoryAccesses can read only elements from a single array

    // (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).

    // Look through all spaces until we find one that contains at least the

    // wanted statement instance.s

    MustKnown.foreach_map([&](isl::map Map) -> isl::stat {

      // Get the array this is accessing.

      isl::id ArrayId = Map.get_tuple_id(isl::dim::out);

      ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(ArrayId.get_user());

      // No support for generation of indirect array accesses.

      if (SAI->getBasePtrOriginSAI())

        return isl::stat::ok; // continue

      // Determine whether this map contains all wanted values.

      isl::set MapDom = Map.domain();

      if (!Domain.is_subset(MapDom).is_true())

        return isl::stat::ok; // continue

      // There might be multiple array elements that contain the same value, but

      // choose only one of them. lexmin is used because it returns a one-value

      // mapping, we do not care about which one.

      // TODO: Get the simplest access function.

      Result = Map.lexmin();

      return isl::stat::error; // break

    });

    return Result;

  }

public:

  ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)

      : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}

  /// Compute the zones of known array element contents.

  ///

  /// @return True if the computed #Known is usable.

  bool computeKnownValues() {

    isl::union_map MustKnown, KnownFromLoad, KnownFromInit;

    // Check that nothing strange occurs.

    collectCompatibleElts();

    {

      IslQuotaScope QuotaScope = MaxOpGuard.enter();

      computeCommon();

      if (NormalizePHIs)

        computeNormalizedPHIs();

      Known = computeKnown(true, true);

      // Preexisting ValInsts use the known content analysis of themselves.

      Translator = makeIdentityMap(Known.range(), false);

    }

    if (!Known || !Translator || !NormalizeMap) {

      assert(isl_ctx_last_error(IslCtx.get()) == isl_error_quota);

      Known = nullptr;

      Translator = nullptr;

      NormalizeMap = nullptr;

      LLVM_DEBUG(dbgs() << "Known analysis exceeded max_operations\n");

      return false;

    }

    KnownAnalyzed++;

    LLVM_DEBUG(dbgs() << "All known: " << Known << "\n");

    return true;

  }

  void printStatistics(raw_ostream &OS, int Indent = 0) {

    OS.indent(Indent) << "Statistics {\n";

    OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied

                          << '\n';

    OS.indent(Indent + 4) << "Known loads forwarded: " << NumKnownLoadsForwarded

                          << '\n';

    OS.indent(Indent + 4) << "Reloads: " << NumReloads << '\n';

    OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied

                          << '\n';

    OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees

                          << '\n';

    OS.indent(Indent + 4) << "Statements with forwarded operand trees: "

                          << NumModifiedStmts << '\n';

    OS.indent(Indent) << "}\n";

  }

  void printStatements(raw_ostream &OS, int Indent = 0) const {

    OS.indent(Indent) << "After statements {\n";

    for (auto &Stmt : *S) {

      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";

      for (auto *MA : Stmt)

        MA->print(OS);

      OS.indent(Indent + 12);

      Stmt.printInstructions(OS);

    }

    OS.indent(Indent) << "}\n";

  }

  /// Create a new MemoryAccess of type read and MemoryKind::Array.

  ///

  /// @param Stmt           The statement in which the access occurs.

  /// @param LI             The instruction that does the access.

  /// @param AccessRelation The array element that each statement instance

  ///                       accesses.

  ///

  /// @param The newly created access.

  MemoryAccess *makeReadArrayAccess(ScopStmt *Stmt, LoadInst *LI,

                                    isl::map AccessRelation) {

    isl::id ArrayId = AccessRelation.get_tuple_id(isl::dim::out);

    ScopArrayInfo *SAI = reinterpret_cast<ScopArrayInfo *>(ArrayId.get_user());

    // Create a dummy SCEV access, to be replaced anyway.

    SmallVector<const SCEV *, 4> Sizes;

    Sizes.reserve(SAI->getNumberOfDimensions());

    SmallVector<const SCEV *, 4> Subscripts;

    Subscripts.reserve(SAI->getNumberOfDimensions());

    for (unsigned i = 0; i < SAI->getNumberOfDimensions(); 
i += 116
) {

      Sizes.push_back(SAI->getDimensionSize(i));

      Subscripts.push_back(nullptr);

    }

    MemoryAccess *Access =

        new MemoryAccess(Stmt, LI, MemoryAccess::READ, SAI->getBasePtr(),

                         LI->getType(), true, {}, Sizes, LI, MemoryKind::Array);

    S->addAccessFunction(Access);

    Stmt->addAccess(Access, true);

    Access->setNewAccessRelation(AccessRelation);

    return Access;

  }

  /// For an llvm::Value defined in @p DefStmt, compute the RAW dependency for a

  /// use in every instance of @p UseStmt.

  ///

  /// @param UseStmt Statement a scalar is used in.

  /// @param DefStmt Statement a scalar is defined in.

  ///

  /// @return { DomainUse[] -> DomainDef[] }

  isl::map computeUseToDefFlowDependency(ScopStmt *UseStmt, ScopStmt *DefStmt) {

    // { DomainUse[] -> Scatter[] }

    isl::map UseScatter = getScatterFor(UseStmt);

    // { Zone[] -> DomainDef[] }

    isl::map ReachDefZone = getScalarReachingDefinition(DefStmt);

    // { Scatter[] -> DomainDef[] }

    isl::map ReachDefTimepoints =

        convertZoneToTimepoints(ReachDefZone, isl::dim::in, false, true);

    // { DomainUse[] -> DomainDef[] }

    return UseScatter.apply_range(ReachDefTimepoints);

  }

  /// Is @p InnerLoop nested inside @p OuterLoop?

  static bool isInsideLoop(Loop *OuterLoop, Loop *InnerLoop) {

    // If OuterLoop is nullptr, we cannot call its contains() method. In this

    // case OuterLoop represents the 'top level' and therefore contains all

    // loop.

    return !OuterLoop || 
OuterLoop->contains(InnerLoop)25
;

  }

  /// Get a domain translation map from a (scalar) definition to the statement

  /// where the definition is being moved to.

  ///

  /// @p TargetStmt can also be seen an llvm::Use of an llvm::Value in

  /// @p DefStmt. In addition, we allow transitive uses:

  ///

  /// DefStmt -> MiddleStmt -> TargetStmt

  ///

  /// where an operand tree of instructions in DefStmt and MiddleStmt are to be

  /// moved to TargetStmt. To be generally correct, we also need to know all the

  /// intermediate statements. However, we make use of the fact that we

  /// currently do not support a move from a loop body across its header such

  /// that only the first definition and the target statement are relevant.

  ///

  /// @param DefStmt    Statement from where a definition might be moved from.

  /// @param TargetStmt Statement where the definition is potentially being

  ///                   moved to (should contain a use of that definition).

  ///

  /// @return  { DomainDef[] -> DomainTarget[] }

  isl::map getDefToTarget(ScopStmt *DefStmt, ScopStmt *TargetStmt) {

    // No translation required if the definition is already at the target.

    if (TargetStmt == DefStmt)

      return isl::map::identity(

          getDomainFor(TargetStmt).get_space().map_from_set());

    isl::map &Result = DefToTargetCache[std::make_pair(TargetStmt, DefStmt)];

    // This is a shortcut in case the schedule is still the original and

    // TargetStmt is in the same or nested inside DefStmt's loop. With the

    // additional assumption that operand trees do not cross DefStmt's loop

    // header, then TargetStmt's instance shared coordinated are the same as

    // DefStmt's coordinated. All TargetStmt instances with this prefix share

    // the same DefStmt instance.

    // Model:

    //

    //   for (int i < 0; i < N; i+=1) {

    // DefStmt:

    //    D = ...;

    //    for (int j < 0; j < N; j+=1) {

    // TargetStmt:

    //      use(D);

    //    }

    //  }

    //

    // Here, the value used in TargetStmt is defined in the corresponding

    // DefStmt, i.e.

    //

    //   { DefStmt[i] -> TargetStmt[i,j] }

    //

    // In practice, this should cover the majority of cases.

    if (S->isOriginalSchedule() &&

        isInsideLoop(DefStmt->getSurroundingLoop(),

                     TargetStmt->getSurroundingLoop())) {

      isl::set DefDomain = getDomainFor(DefStmt);

      isl::set TargetDomain = getDomainFor(TargetStmt);

      assert(DefDomain.dim(isl::dim::set) <= TargetDomain.dim(isl::dim::set));

      Result = isl::map::from_domain_and_range(DefDomain, TargetDomain);

      for (unsigned i = 0, DefDims = DefDomain.dim(isl::dim::set); i < DefDims;

           
i += 119
)

        Result = Result.equate(isl::dim::in, i, isl::dim::out, i);

    }

    if (!Result) {

      // { DomainDef[] -> DomainTarget[] }

      Result = computeUseToDefFlowDependency(TargetStmt, DefStmt).reverse();

      simplify(Result);

    }

    return Result;

  }

  /// Forward a load by reading from an array element that contains the same

  /// value. Typically the location it was loaded from.

  ///

  /// @param TargetStmt  The statement the operand tree will be copied to.

  /// @param Inst        The (possibly speculatable) instruction to forward.

  /// @param UseStmt     The statement that uses @p Inst.

  /// @param UseLoop     The loop @p Inst is used in.

  /// @param DefStmt     The statement @p Inst is defined in.

  /// @param DefLoop     The loop which contains @p Inst.

  /// @param DoIt        If false, only determine whether an operand tree can be

  ///                    forwarded. If true, carry out the forwarding. Do not

  ///                    use DoIt==true if an operand tree is not known to be

  ///                    forwardable.

  ///

  /// @return FD_NotApplicable  if @p Inst cannot be forwarded by creating a new

  ///                           load.

  ///         FD_CannotForward  if the pointer operand cannot be forwarded.

  ///         FD_CanForwardProfitably if @p Inst is forwardable.

  ///         FD_DidForwardTree if @p DoIt was true.

  ForwardingDecision forwardKnownLoad(ScopStmt *TargetStmt, Instruction *Inst,

                                      ScopStmt *UseStmt, Loop *UseLoop,

                                      ScopStmt *DefStmt, Loop *DefLoop,

                                      bool DoIt) {

    // Cannot do anything without successful known analysis.

    if (Known.is_null() || Translator.is_null() ||

        MaxOpGuard.hasQuotaExceeded())

      return FD_NotApplicable;

    LoadInst *LI = dyn_cast<LoadInst>(Inst);

    if (!LI)

      return FD_NotApplicable;

    // If the load is already in the statement, no forwarding is necessary.

    // However, it might happen that the LoadInst is already present in the

    // statement's instruction list. In that case we do as follows:

    // - For the evaluation (DoIt==false), we can trivially forward it as it is

    //   benefit of forwarding an already present instruction.

    // - For the execution (DoIt==true), prepend the instruction (to make it

    //   available to all instructions following in the instruction list), but

    //   do not add another MemoryAccess.

    MemoryAccess *Access = TargetStmt->getArrayAccessOrNULLFor(LI);

    if (Access && 
!DoIt9
)

      return FD_CanForwardProfitably;

    ForwardingDecision OpDecision = forwardTree(

        TargetStmt, LI->getPointerOperand(), DefStmt, DefLoop, DoIt);

    switch (OpDecision) {

    case FD_CannotForward:

      assert(!DoIt);

      return OpDecision;

    case FD_CanForwardLeaf:

    case FD_CanForwardProfitably:

      assert(!DoIt);

      break;

    case FD_DidForwardLeaf:

    case FD_DidForwardTree:

      assert(DoIt);

      break;

    default:

      llvm_unreachable("Shouldn't return this");

    }

    IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);

    // { DomainDef[] -> ValInst[] }

    isl::map ExpectedVal = makeValInst(Inst, UseStmt, UseLoop);

    assert(!isNormalized(ExpectedVal).is_false() &&

           "LoadInsts are always normalized");

    // { DomainUse[] -> DomainTarget[] }

    isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);

    // { DomainTarget[] -> ValInst[] }

    isl::map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);

    isl::union_map TranslatedExpectedVal =

        isl::union_map(TargetExpectedVal).apply_range(Translator);

    // { DomainTarget[] -> Element[] }

    isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);

    isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));

    if (!SameVal)

      return FD_NotApplicable;

    if (DoIt)

      TargetStmt->prependInstruction(LI);

    if (!DoIt)

      return FD_CanForwardProfitably;

    if (Access) {

      LLVM_DEBUG(

          dbgs() << "    forwarded known load with preexisting MemoryAccess"

                 << Access << "\n");

    } else {

      Access = makeReadArrayAccess(TargetStmt, LI, SameVal);

      LLVM_DEBUG(dbgs() << "    forwarded known load with new MemoryAccess"

                        << Access << "\n");

      // { ValInst[] }

      isl::space ValInstSpace = ExpectedVal.get_space().range();

      // After adding a new load to the SCoP, also update the Known content

      // about it. The new load will have a known ValInst of

      // { [DomainTarget[] -> Value[]] }

      // but which -- because it is a copy of it -- has same value as the

      // { [DomainDef[] -> Value[]] }

      // that it replicates. Instead of  cloning the known content of

      // [DomainDef[] -> Value[]]

      // for DomainTarget[], we add a 'translator' that maps

      // [DomainTarget[] -> Value[]] to [DomainDef[] -> Value[]]

      // before comparing to the known content.

      // TODO: 'Translator' could also be used to map PHINodes to their incoming

      // ValInsts.

      if (ValInstSpace.is_wrapping()) {

        // { DefDomain[] -> Value[] }

        isl::map ValInsts = ExpectedVal.range().unwrap();

        // { DefDomain[] }

        isl::set DefDomain = ValInsts.domain();

        // { Value[] }

        isl::space ValSpace = ValInstSpace.unwrap().range();

        // { Value[] -> Value[] }

        isl::map ValToVal =

            isl::map::identity(ValSpace.map_from_domain_and_range(ValSpace));

        // { DomainDef[] -> DomainTarget[] }

        isl::map DefToTarget = getDefToTarget(DefStmt, TargetStmt);

        // { [TargetDomain[] -> Value[]] -> [DefDomain[] -> Value] }

        isl::map LocalTranslator = DefToTarget.reverse().product(ValToVal);

        Translator = Translator.add_map(LocalTranslator);

        LLVM_DEBUG(dbgs() << "      local translator is " << LocalTranslator

                          << "\n");

      }

    }

    LLVM_DEBUG(dbgs() << "      expected values where " << TargetExpectedVal

                      << "\n");

    LLVM_DEBUG(dbgs() << "      candidate elements where " << Candidates

                      << "\n");

    assert(Access);

    NumKnownLoadsForwarded++;

    TotalKnownLoadsForwarded++;

    return FD_DidForwardTree;

  }

  /// Forward a scalar by redirecting the access to an array element that stores

  /// the same value.

  ///

  /// @param TargetStmt  The statement the operand tree will be copied to.

  /// @param Inst        The scalar to forward.

  /// @param UseStmt     The statement that uses @p Inst.

  /// @param UseLoop     The loop @p Inst is used in.

  /// @param DefStmt     The statement @p Inst is defined in.

  /// @param DefLoop     The loop which contains @p Inst.

  /// @param DoIt        If false, only determine whether an operand tree can be

  ///                    forwarded. If true, carry out the forwarding. Do not

  ///                    use DoIt==true if an operand tree is not known to be

  ///                    forwardable.

  ///

  /// @return FD_NotApplicable        if @p Inst cannot be reloaded.

  ///         FD_CanForwardLeaf       if @p Inst can be reloaded.

  ///         FD_CanForwardProfitably if @p Inst has been reloaded.

  ///         FD_DidForwardLeaf       if @p DoIt was true.

  ForwardingDecision reloadKnownContent(ScopStmt *TargetStmt, Instruction *Inst,

                                        ScopStmt *UseStmt, Loop *UseLoop,

                                        ScopStmt *DefStmt, Loop *DefLoop,

                                        bool DoIt) {

    // Cannot do anything without successful known analysis.

    if (Known.is_null() || Translator.is_null() ||

        MaxOpGuard.hasQuotaExceeded())

      return FD_NotApplicable;

    MemoryAccess *Access = TargetStmt->lookupInputAccessOf(Inst);

    if (Access && 
Access->isLatestArrayKind()22
) {

      if (DoIt)

        return FD_DidForwardLeaf;

      return FD_CanForwardLeaf;

    }

    // Don't spend too much time analyzing whether it can be reloaded. When

    // carrying-out the forwarding, we cannot bail-out in the middle of the

    // transformation. It also shouldn't take as long because some results are

    // cached.

    IslQuotaScope QuotaScope = MaxOpGuard.enter(!DoIt);

    // { DomainDef[] -> ValInst[] }

    isl::union_map ExpectedVal = makeNormalizedValInst(Inst, UseStmt, UseLoop);

    // { DomainUse[] -> DomainTarget[] }

    isl::map UseToTarget = getDefToTarget(UseStmt, TargetStmt);

    // { DomainTarget[] -> ValInst[] }

    isl::union_map TargetExpectedVal = ExpectedVal.apply_domain(UseToTarget);

    isl::union_map TranslatedExpectedVal =

        TargetExpectedVal.apply_range(Translator);

    // { DomainTarget[] -> Element[] }

    isl::union_map Candidates = findSameContentElements(TranslatedExpectedVal);

    isl::map SameVal = singleLocation(Candidates, getDomainFor(TargetStmt));

    if (!SameVal)

      return FD_NotApplicable;

    if (!DoIt)

      return FD_CanForwardProfitably;

    if (!Access)

      Access = TargetStmt->ensureValueRead(Inst);

    simplify(SameVal);

    Access->setNewAccessRelation(SameVal);

    TotalReloads++;

    NumReloads++;

    return FD_DidForwardLeaf;

  }

  /// Forwards a speculatively executable instruction.

  ///

  /// @param TargetStmt  The statement the operand tree will be copied to.

  /// @param UseInst     The (possibly speculatable) instruction to forward.

  /// @param DefStmt     The statement @p UseInst is defined in.

  /// @param DefLoop     The loop which contains @p UseInst.

  /// @param DoIt        If false, only determine whether an operand tree can be

  ///                    forwarded. If true, carry out the forwarding. Do not

  ///                    use DoIt==true if an operand tree is not known to be

  ///                    forwardable.

  ///

  /// @return FD_NotApplicable  if @p UseInst is not speculatable.

  ///         FD_CannotForward  if one of @p UseInst's operands is not

  ///                           forwardable.

  ///         FD_CanForwardTree if @p UseInst is forwardable.

  ///         FD_DidForward     if @p DoIt was true.

  ForwardingDecision forwardSpeculatable(ScopStmt *TargetStmt,

                                         Instruction *UseInst,

                                         ScopStmt *DefStmt, Loop *DefLoop,

                                         bool DoIt) {

    // PHIs, unless synthesizable, are not yet supported.

    if (isa<PHINode>(UseInst))

      return FD_NotApplicable;

    // Compatible instructions must satisfy the following conditions:

    // 1. Idempotent (instruction will be copied, not moved; although its

    //    original instance might be removed by simplification)

    // 2. Not access memory (There might be memory writes between)

    // 3. Not cause undefined behaviour (we might copy to a location when the

    //    original instruction was no executed; this is currently not possible

    //    because we do not forward PHINodes)

    // 4. Not leak memory if executed multiple times (i.e. malloc)

    //

    // Instruction::mayHaveSideEffects is not sufficient because it considers

    // malloc to not have side-effects. llvm::isSafeToSpeculativelyExecute is

    // not sufficient because it allows memory accesses.

    if (mayBeMemoryDependent(*UseInst))

      return FD_NotApplicable;

    if (DoIt) {

      // To ensure the right order, prepend this instruction before its

      // operands. This ensures that its operands are inserted before the

      // instruction using them.

      // TODO: The operand tree is not really a tree, but a DAG. We should be

      // able to handle DAGs without duplication.

      TargetStmt->prependInstruction(UseInst);

      NumInstructionsCopied++;

      TotalInstructionsCopied++;

    }

    for (Value *OpVal : UseInst->operand_values()) {

      ForwardingDecision OpDecision =

          forwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DoIt);

      switch (OpDecision) {

      case FD_CannotForward:

        assert(!DoIt);

        return FD_CannotForward;

      case FD_CanForwardLeaf:

      case FD_CanForwardProfitably:

        assert(!DoIt);

        break;

      case FD_DidForwardLeaf:

      case FD_DidForwardTree:

        assert(DoIt);

        break;

      case FD_NotApplicable:

        llvm_unreachable("forwardTree should never return FD_NotApplicable");

      }

    }

    
if (32
DoIt32
)

      return FD_DidForwardTree;

    return FD_CanForwardProfitably;

  }

  /// Determines whether an operand tree can be forwarded or carries out a

  /// forwarding, depending on the @p DoIt flag.

  ///

  /// @param TargetStmt  The statement the operand tree will be copied to.

  /// @param UseVal      The value (usually an instruction) which is root of an

  ///                    operand tree.

  /// @param UseStmt     The statement that uses @p UseVal.

  /// @param UseLoop     The loop @p UseVal is used in.

  /// @param DoIt        If false, only determine whether an operand tree can be

  ///                    forwarded. If true, carry out the forwarding. Do not

  ///                    use DoIt==true if an operand tree is not known to be

  ///                    forwardable.

  ///

  /// @return If DoIt==false, return whether the operand tree can be forwarded.

  ///         If DoIt==true, return FD_DidForward.

  ForwardingDecision forwardTree(ScopStmt *TargetStmt, Value *UseVal,

                                 ScopStmt *UseStmt, Loop *UseLoop, bool DoIt) {

    ScopStmt *DefStmt = nullptr;

    Loop *DefLoop = nullptr;

    // { DefDomain[] -> TargetDomain[] }

    isl::map DefToTarget;

    VirtualUse VUse = VirtualUse::create(UseStmt, UseLoop, UseVal, true);

    switch (VUse.getKind()) {

    case VirtualUse::Constant:

    case VirtualUse::Block:

    case VirtualUse::Hoisted:

      // These can be used anywhere without special considerations.

      if (DoIt)

        return FD_DidForwardTree;

      return FD_CanForwardLeaf;

    case VirtualUse::Synthesizable: {

      // ScopExpander will take care for of generating the code at the new

      // location.

      if (DoIt)

        return FD_DidForwardTree;

      // Check if the value is synthesizable at the new location as well. This

      // might be possible when leaving a loop for which ScalarEvolution is

      // unable to derive the exit value for.

      // TODO: If there is a LCSSA PHI at the loop exit, use that one.

      // If the SCEV contains a SCEVAddRecExpr, we currently depend on that we

      // do not forward past its loop header. This would require us to use a

      // previous loop induction variable instead the current one. We currently

      // do not allow forwarding PHI nodes, thus this should never occur (the

      // only exception where no phi is necessary being an unreachable loop

      // without edge from the outside).

      VirtualUse TargetUse = VirtualUse::create(

          S, TargetStmt, TargetStmt->getSurroundingLoop(), UseVal, true);

      if (TargetUse.getKind() == VirtualUse::Synthesizable)

        return FD_CanForwardLeaf;

      LLVM_DEBUG(

          dbgs() << "    Synthesizable would not be synthesizable anymore: "

                 << *UseVal << "\n");

      return FD_CannotForward;

    }

    case VirtualUse::ReadOnly:

      // Note that we cannot return FD_CanForwardTree here. With a operand tree

      // depth of 0, UseVal is the use in TargetStmt that we try to replace.

      // With -polly-analyze-read-only-scalars=true we would ensure the

      // existence of a MemoryAccess (which already exists for a leaf) and be

      // removed again by tryForwardTree because it's goal is to remove this

      // scalar MemoryAccess. It interprets FD_CanForwardTree as the permission

      // to do so.

      if (!DoIt)

        return FD_CanForwardLeaf;

      // If we model read-only scalars, we need to create a MemoryAccess for it.

      if (ModelReadOnlyScalars)

        TargetStmt->ensureValueRead(UseVal);

      NumReadOnlyCopied++;

      TotalReadOnlyCopied++;

      return FD_DidForwardLeaf;

    case VirtualUse::Intra:

      // Knowing that UseStmt and DefStmt are the same statement instance, just

      // reuse the information about UseStmt for DefStmt

      DefStmt = UseStmt;

      LLVM_FALLTHROUGH;

    case VirtualUse::Inter:

      Instruction *Inst = cast<Instruction>(UseVal);

      if (!DefStmt) {

        DefStmt = S->getStmtFor(Inst);

        if (!DefStmt)

          return FD_CannotForward;

      }

      DefLoop = LI->getLoopFor(Inst->getParent());

      ForwardingDecision SpeculativeResult =

          forwardSpeculatable(TargetStmt, Inst, DefStmt, DefLoop, DoIt);

      if (SpeculativeResult != FD_NotApplicable)

        return SpeculativeResult;

      ForwardingDecision KnownResult = forwardKnownLoad(

          TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt);

      if (KnownResult != FD_NotApplicable)

        return KnownResult;

      ForwardingDecision ReloadResult = reloadKnownContent(

          TargetStmt, Inst, UseStmt, UseLoop, DefStmt, DefLoop, DoIt);

      if (ReloadResult != FD_NotApplicable)

        return ReloadResult;

      // When no method is found to forward the operand tree, we effectively

      // cannot handle it.

      LLVM_DEBUG(dbgs() << "    Cannot forward instruction: " << *Inst << "\n");

      return FD_CannotForward;

    }

    llvm_unreachable("Case unhandled");

  }

  /// Try to forward an operand tree rooted in @p RA.

  bool tryForwardTree(MemoryAccess *RA) {

    assert(RA->isLatestScalarKind());

    LLVM_DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");

    ScopStmt *Stmt = RA->getStatement();

    Loop *InLoop = Stmt->getSurroundingLoop();

    isl::map TargetToUse;

    if (!Known.is_null()) {

      isl::space DomSpace = Stmt->getDomainSpace();

      TargetToUse =

          isl::map::identity(DomSpace.map_from_domain_and_range(DomSpace));

    }

    ForwardingDecision Assessment =

        forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false);

    assert(Assessment != FD_DidForwardTree && Assessment != FD_DidForwardLeaf);

    if (Assessment != FD_CanForwardProfitably)

      return false;

    ForwardingDecision Execution =

        forwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, true);

    assert(((Execution == FD_DidForwardTree) ||

            (Execution == FD_DidForwardLeaf)) &&

           "A previous positive assessment must also be executable");

    if (Execution == FD_DidForwardTree)

      Stmt->removeSingleMemoryAccess(RA);

    return true;

  }

  /// Return which SCoP this instance is processing.

  Scop *getScop() const { return S; }

  /// Run the algorithm: Use value read accesses as operand tree roots and try

  /// to forward them into the statement.

  bool forwardOperandTrees() {

    for (ScopStmt &Stmt : *S) {

      bool StmtModified = false;

      // Because we are modifying the MemoryAccess list, collect them first to

      // avoid iterator invalidation.

      SmallVector<MemoryAccess *, 16> Accs;

      for (MemoryAccess *RA : Stmt) {

        if (!RA->isRead())

          continue;

        if (!RA->isLatestScalarKind())

          continue;

        Accs.push_back(RA);

      }

      for (MemoryAccess *RA : Accs) {

        if (tryForwardTree(RA)) {

          Modified = true;

          StmtModified = true;

          NumForwardedTrees++;

          TotalForwardedTrees++;

        }

      }

      if (StmtModified) {

        NumModifiedStmts++;

        TotalModifiedStmts++;

      }

    }

    if (Modified)

      ScopsModified++;

    return Modified;

  }

  /// Print the pass result, performed transformations and the SCoP after the

  /// transformation.

  void print(raw_ostream &OS, int Indent = 0) {

    printStatistics(OS, Indent);

    if (!Modified) {

      // This line can easily be checked in regression tests.

      OS << "ForwardOpTree executed, but did not modify anything\n";

      return;

    }

    printStatements(OS, Indent);

  }

};

/// Pass that redirects scalar reads to array elements that are known to contain

/// the same value.

///

/// This reduces the number of scalar accesses and therefore potentially

/// increases the freedom of the scheduler. In the ideal case, all reads of a

/// scalar definition are redirected (We currently do not care about removing

/// the write in this case).  This is also useful for the main DeLICM pass as

/// there are less scalars to be mapped.

class ForwardOpTree : public ScopPass {

private:

  /// The pass implementation, also holding per-scop data.

  std::unique_ptr<ForwardOpTreeImpl> Impl;

public:

  static char ID;

  explicit ForwardOpTree() : ScopPass(ID) {}

  ForwardOpTree(const ForwardOpTree &) = delete;

  ForwardOpTree &operator=(const ForwardOpTree &) = delete;

  void getAnalysisUsage(AnalysisUsage &AU) const override {

    AU.addRequiredTransitive<ScopInfoRegionPass>();

    AU.addRequired<LoopInfoWrapperPass>();

    AU.setPreservesAll();

  }

  bool runOnScop(Scop &S) override {

    // Free resources for previous SCoP's computation, if not yet done.

    releaseMemory();

    LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();

    {

      IslMaxOperationsGuard MaxOpGuard(S.getIslCtx().get(), MaxOps, false);

      Impl = llvm::make_unique<ForwardOpTreeImpl>(&S, &LI, MaxOpGuard);

      if (AnalyzeKnown) {

        LLVM_DEBUG(dbgs() << "Prepare forwarders...\n");

        Impl->computeKnownValues();

      }

      LLVM_DEBUG(dbgs() << "Forwarding operand trees...\n");

      Impl->forwardOperandTrees();

      if (MaxOpGuard.hasQuotaExceeded()) {

        LLVM_DEBUG(dbgs() << "Not all operations completed because of "

                             "max_operations exceeded\n");