[Polly][ForwardOpTree] Support read-only value uses.

[Meinersbur]

Summary

Read-only values (values defined before the SCoP) require special handing with -polly-analyze-read-only-scalars=true (which is the default). If active, each use of a value requires a read access. When a copied value uses a read-only value, we must also ensure that such a MemoryAccess is available or is created.

[grosser]

LGTM. Thank you!

include/polly/ScopBuilder.h

 
 #ifndef POLLY_SCOP_BUILDER_H
 #define POLLY_SCOP_BUILDER_H
 
 #include "polly/ScopInfo.h"
 
 namespace polly {
 
+/// Command line switch whether to model read-only accesses.
+extern bool ModelReadOnlyScalars;
+
 /// Build the Polly IR (Scop and ScopStmt) on a Region.
 class ScopBuilder {
   //===-------------------------------------------------------------------===//
   ScopBuilder(const ScopBuilder &) = delete;
   const ScopBuilder &operator=(const ScopBuilder &) = delete;
 
   /// The AliasAnalysis to build AliasSetTracker.
   AliasAnalysis &AA;

include/polly/ScopInfo.h

public:
   /// @param PrintInstructions Whether to print the statement's instructions as
   ///                          well.
   void print(raw_ostream &OS, bool PrintInstructions) const;
 
   /// Print the instructions in ScopStmt.
   ///
   void printInstructions(raw_ostream &OS) const;
 
+  /// Check whether there is a value read access for @p V in this statement, and
+  /// if not, create one.
+  ///
+  /// This allows to add MemoryAccesses after the initial creation of the Scop
+  /// by ScopBuilder.
+  ///
+  /// @return The already existing or newly created MemoryKind::Value READ
+  /// MemoryAccess.
+  ///
+  /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*)
+  MemoryAccess *ensureValueRead(Value *V);
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the ScopStmt to stderr.
   void dump() const;
 #endif
 };
 
 /// Print ScopStmt S to raw_ostream O.
 raw_ostream &operator<<(raw_ostream &O, const ScopStmt &S);

lib/Analysis/ScopBuilder.cpp

 
 #define DEBUG_TYPE "polly-scops"
 
 STATISTIC(ScopFound, "Number of valid Scops");
 STATISTIC(RichScopFound, "Number of Scops containing a loop");
 STATISTIC(InfeasibleScops,
           "Number of SCoPs with statically infeasible context.");
 
-static cl::opt<bool> ModelReadOnlyScalars(
+bool polly::ModelReadOnlyScalars;
+static cl::opt<bool, true> XModelReadOnlyScalars(
     "polly-analyze-read-only-scalars",
     cl::desc("Model read-only scalar values in the scop description"),
-    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
+    cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
+    cl::init(true), cl::cat(PollyCategory));
 
 static cl::opt<bool> UnprofitableScalarAccs(
     "polly-unprofitable-scalar-accs",
     cl::desc("Count statements with scalar accesses as not optimizable"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool> DetectFortranArrays(
     "polly-detect-fortran-arrays",
if (Stmt->lookupValueWriteOf(Inst))
     return;
 
   addMemoryAccess(Stmt, Inst, MemoryAccess::MUST_WRITE, Inst, Inst->getType(),
                   true, Inst, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), MemoryKind::Value);
 }
 
 void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
+  // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
+  // to be able to replace this one. Currently, there is a split responsibility.
+  // In a first step, the MemoryAccess is created, but without the
+  // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
+  // AccessRelation is created. At least for scalar accesses, there is no new
+  // information available at ScopStmt::buildAccessRelations(), so we could
+  // create the AccessRelation right away. This is what
+  // ScopStmt::ensureValueRead(Value*) does.
+
   auto *Scope = UserStmt->getSurroundingLoop();
   auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
   switch (VUse.getKind()) {
   case VirtualUse::Constant:
   case VirtualUse::Block:
   case VirtualUse::Synthesizable:
   case VirtualUse::Hoisted:
   case VirtualUse::Intra:

lib/Analysis/ScopInfo.cpp

void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA) {
   auto It = InstructionToAccess.find(MA->getAccessInstruction());
   if (It != InstructionToAccess.end()) {
     It->second.remove(MA);
     if (It->second.empty())
       InstructionToAccess.erase(MA->getAccessInstruction());
   }
 }
 
+MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
+  MemoryAccess *Access = lookupInputAccessOf(V);
+  if (Access)
+    return Access;
+
+  ScopArrayInfo *SAI =
+      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
+  Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
+                            true, {}, {}, V, MemoryKind::Value);
+  Parent.addAccessFunction(Access);
+  Access->buildAccessRelation(SAI);
+  addAccess(Access);
+  Parent.addAccessData(Access);
+  return Access;
+}
+
 raw_ostream &polly::operator<<(raw_ostream &O, const ScopStmt &S) {
   S.print(O, PollyPrintInstructions);
   return O;
 }
 
 //===----------------------------------------------------------------------===//
 /// Scop class implement
 

lib/Transform/ForwardOpTree.cpp

 //===------ 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/ScopBuilder.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/Analysis/ValueTracking.h"
 
 #define DEBUG_TYPE "polly-delicm"
 
 using namespace polly;
 using namespace llvm;
 
 STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
+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");
 
 namespace {
 
 /// The state of whether an operand tree was/can be forwarded.
 enum ForwardingDecision {
   FD_CannotForward,
   FD_CanForward,
+  FD_CanForwardTree,
   FD_DidForward,
 };
 
 /// 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 {
 private:
   /// The SCoP we are currently processing.
   Scop *S;
 
   /// LoopInfo is required for VirtualUse.
   LoopInfo *LI;
 
   /// How many instructions have been copied to other statements.
   int NumInstructionsCopied = 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;
 
   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) << "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(llvm::raw_ostream &OS, int Indent = 0) const {
case VirtualUse::Hoisted:
       return FD_CanForward;
 
     case VirtualUse::Synthesizable:
       // Not supported yet.
       DEBUG(dbgs() << "    Cannot forward synthesizable: " << *UseVal << "\n");
       return FD_CannotForward;
 
     case VirtualUse::ReadOnly:
-      // Not supported yet.
-      DEBUG(dbgs() << "    Cannot forward read-only val: " << *UseVal << "\n");
-      return FD_CannotForward;
+      if (!DoIt)
+        return FD_CanForward;
+
+      // If we model read-only scalars, we need to create a MemoryAccess for it.
+      if (ModelReadOnlyScalars)
+        TargetStmt->ensureValueRead(UseVal);
+
+      NumReadOnlyCopied++;
+      TotalReadOnlyCopied++;
+      return FD_DidForward;
 
     case VirtualUse::Intra:
     case VirtualUse::Inter:
       auto Inst = cast<Instruction>(UseVal);
 
       // Compatible instructions must satisfy the following conditions:
       // 1. Idempotent (instruction will be copied, not moved; although its
       // original instance might be removed by simplification)
case VirtualUse::Inter:
         ForwardingDecision OpDecision =
             canForwardTree(TargetStmt, OpVal, DefStmt, DefLoop, DoIt);
         switch (OpDecision) {
         case FD_CannotForward:
           assert(!DoIt);
           return FD_CannotForward;
 
         case FD_CanForward:
+        case FD_CanForwardTree:
           assert(!DoIt);
           break;
 
         case FD_DidForward:
           assert(DoIt);
           break;
         }
       }
 
       if (DoIt)
         return FD_DidForward;
-      return FD_CanForward;
+      return FD_CanForwardTree;
     }
 
     llvm_unreachable("Case unhandled");
   }
 
   /// Try to forward an operand tree rooted in @p RA.
   bool tryForwardTree(MemoryAccess *RA) {
     assert(RA->isLatestScalarKind());
     DEBUG(dbgs() << "Trying to forward operand tree " << RA << "...\n");
 
     ScopStmt *Stmt = RA->getStatement();
     Loop *InLoop = Stmt->getSurroundingLoop();
 
     ForwardingDecision Assessment =
         canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false);
     assert(Assessment != FD_DidForward);
-    if (Assessment == FD_CannotForward)
+    if (Assessment != FD_CanForwardTree)
       return false;
 
     ForwardingDecision Execution =
         canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, true);
     assert(Execution == FD_DidForward);
 
     Stmt->removeSingleMemoryAccess(RA);
     return true;

test/ForwardOpTree/forward_readonly.ll

+; RUN: opt %loadPolly -polly-analyze-read-only-scalars=true  -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,MODEL
+; RUN: opt %loadPolly -polly-analyze-read-only-scalars=false -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,NOMODEL
+;
+; Move %val to %bodyB, so %bodyA can be removed (by -polly-simplify)
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = arg + 21.0;
+;
+; bodyB:
+;   A[0] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double %arg) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %val = fadd double %arg, 21.0
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; STATS: Statistics {
+; STATS:     Instructions copied: 1
+; STATS:     Read-only accesses copied: 1
+; STATS:     Operand trees forwarded: 1
+; STATS:     Statements with forwarded operand trees: 1
+; STATS: }
+
+; MODEL:      After statements {
+; MODEL-NEXT:     Stmt_bodyA
+; MODEL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_arg[] };
+; MODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; MODEL-NEXT:             Instructions {
+; MODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; MODEL-NEXT:                 }
+; MODEL-NEXT:     Stmt_bodyB
+; MODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; MODEL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_arg[] };
+; MODEL-NEXT:             Instructions {
+; MODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; MODEL-NEXT:                   store double %val, double* %A
+; MODEL-NEXT:                 }
+; MODEL-NEXT: }
+
+; NOMODEL:      After statements {
+; NOMODEL-NEXT:     Stmt_bodyA
+; NOMODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; NOMODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; NOMODEL-NEXT:             Instructions {
+; NOMODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; NOMODEL-NEXT:                 }
+; NOMODEL-NEXT:     Stmt_bodyB
+; NOMODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; NOMODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; NOMODEL-NEXT:             Instructions {
+; NOMODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; NOMODEL-NEXT:                   store double %val, double* %A
+; NOMODEL-NEXT:                 }
+; NOMODEL-NEXT: }