[Polly][CodeGen] Support partial write accesses.

[Meinersbur]

Summary

Allow the BlockGenerator to generate memory writes that are not defined over the complete statement domain, but only over a subset of it. It generates a condition that evaluates to 1 if executing the subdomain, and only then execute the access.

Only write accesses are supported. Read accesses would require a PHINode which has a value if the access is not executed.

Partial write makes DeLICM able to apply mappings that are not defined over the entire domain (for instance, a branch that leaves a loop with a PHINode in its header; a MemoryKind::PHI write when leaving is never read by its PHI read).

[grosser]

include/polly/ScopInfo.h

1032 ↗

(On Diff #99184)

MemoryAccess

lib/CodeGen/IslNodeBuilder.cpp

794 ↗

(On Diff #99184)

Why "if 0"?

[Meinersbur]

lib/CodeGen/IslNodeBuilder.cpp

794 ↗

(On Diff #99184)

Mmmh, I seem to have forgotten to adapt this function.

[Meinersbur]

Pre-commit update

• Address Tobias' comments
• Support empty partial write.

polly/trunk/include/polly/CodeGen/BlockGenerators.h

 // respectively.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_BLOCK_GENERATORS_H
 #define POLLY_BLOCK_GENERATORS_H
 
 #include "polly/CodeGen/IRBuilder.h"
+#include "polly/Support/GICHelper.h"
 #include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "isl/map.h"
 
 struct isl_ast_build;
 struct isl_id_to_ast_expr;
 
protected:
   /// @param LTS   A mapping from loops virtual canonical induction
   ///              variable to their new values.
   /// @param BBMap A mapping from old values to their new values in this block.
   /// @param NewAccesses A map from memory access ids to new ast expressions.
   void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT &LTS,
                            ValueMapT &BBMap,
                            __isl_keep isl_id_to_ast_expr *NewAccesses);
 
+  /// Generate instructions that compute whether one instance of @p Set is
+  /// executed.
+  ///
+  /// @param Stmt      The statement we generate code for.
+  /// @param Subdomain A set in the space of @p Stmt's domain. Elements not in
+  ///                  @p Stmt's domain are ignored.
+  ///
+  /// @return An expression of type i1, generated into the current builder
+  ///         position, that evaluates to 1 if the executed instance is part of
+  ///         @p Set.
+  Value *buildContainsCondition(ScopStmt &Stmt, const isl::set &Subdomain);
+
+  /// Generate code that executes in a subset of @p Stmt's domain.
+  ///
+  /// @param Stmt        The statement we generate code for.
+  /// @param Subdomain   The condition for some code to be executed.
+  /// @param Subject     A name for the code that is executed
+  ///                    conditionally. Used to name new basic blocks and
+  ///                    instructions.
+  /// @param GenThenFunc Callback which generates the code to be executed
+  ///                    when the current executed instance is in @p Set. The
+  ///                    IRBuilder's position is moved to within the block that
+  ///                    executes conditionally for this callback.
+  void generateConditionalExecution(ScopStmt &Stmt, const isl::set &Subdomain,
+                                    StringRef Subject,
+                                    const std::function<void()> &GenThenFunc);
+
   /// Generate the scalar stores for the given statement.
   ///
   /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction

polly/trunk/include/polly/ScopInfo.h

public:
   /// object. After the scop has been constructed, the original access relation
   /// should not be changed any more. Instead setNewAccessRelation should
   /// be called.
   void setAccessRelation(__isl_take isl_map *AccessRelation);
 
   /// Set the updated access relation read from JSCOP file.
   void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);
 
+  /// Return whether the MemoryyAccess is a partial access. That is, the access
+  /// is not executed in some instances of the parent statement's domain.
+  bool isLatestPartialAccess() const;
+
   /// Mark this a reduction like access
   void markAsReductionLike(ReductionType RT) { RedType = RT; }
 
   /// Align the parameters in the access relation to the scop context
   void realignParams();
 
   /// Update the dimensionality of the memory access.
   ///

polly/trunk/lib/Analysis/ScopInfo.cpp

#ifndef NDEBUG
   // Check domain space compatibility.
   auto *NewSpace = isl_map_get_space(NewAccess);
   auto *NewDomainSpace = isl_space_domain(isl_space_copy(NewSpace));
   auto *OriginalDomainSpace = getStatement()->getDomainSpace();
   assert(isl_space_has_equal_tuples(OriginalDomainSpace, NewDomainSpace));
   isl_space_free(NewDomainSpace);
   isl_space_free(OriginalDomainSpace);
 
+  // Reads must be executed unconditionally. Writes might be executed in a
+  // subdomain only.
+  if (isRead()) {
     // Check whether there is an access for every statement instance.
     auto *StmtDomain = getStatement()->getDomain();
     StmtDomain = isl_set_intersect_params(
         StmtDomain, getStatement()->getParent()->getContext());
     auto *NewDomain = isl_map_domain(isl_map_copy(NewAccess));
     assert(isl_set_is_subset(StmtDomain, NewDomain) &&
-         "Partial accesses not supported");
+           "Partial READ accesses not supported");
     isl_set_free(NewDomain);
     isl_set_free(StmtDomain);
+  }
 
   auto *NewAccessSpace = isl_space_range(NewSpace);
   assert(isl_space_has_tuple_id(NewAccessSpace, isl_dim_set) &&
          "Must specify the array that is accessed");
   auto *NewArrayId = isl_space_get_tuple_id(NewAccessSpace, isl_dim_set);
   auto *SAI = static_cast<ScopArrayInfo *>(isl_id_get_user(NewArrayId));
   assert(SAI && "Must set a ScopArrayInfo");
 
#ifndef NDEBUG
   isl_space_free(NewAccessSpace);
   isl_id_free(NewArrayId);
 #endif
 
   isl_map_free(NewAccessRelation);
   NewAccessRelation = NewAccess;
 }
 
+bool MemoryAccess::isLatestPartialAccess() const {
+  isl::set StmtDom = give(getStatement()->getDomain());
+  isl::set AccDom = give(isl_map_domain(getLatestAccessRelation()));
+
+  return isl_set_is_subset(StmtDom.keep(), AccDom.keep()) == isl_bool_false;
+}
+
 //===----------------------------------------------------------------------===//
 
 __isl_give isl_map *ScopStmt::getSchedule() const {
   isl_set *Domain = getDomain();
   if (isl_set_is_empty(Domain)) {
     isl_set_free(Domain);
     return isl_map_from_aff(
         isl_aff_zero_on_domain(isl_local_space_from_space(getDomainSpace())));

polly/trunk/lib/CodeGen/BlockGenerators.cpp

RuntimeDebugBuilder::createCPUPrinter(Builder, "Load from ", NewPointer,
                                           ": ", ScalarLoad, "\n");
 
   return ScalarLoad;
 }
 
 void BlockGenerator::generateArrayStore(ScopStmt &Stmt, StoreInst *Store,
                                         ValueMapT &BBMap, LoopToScevMapT &LTS,
                                         isl_id_to_ast_expr *NewAccesses) {
+  MemoryAccess &MA = Stmt.getArrayAccessFor(Store);
+  isl::set AccDom = give(isl_map_domain(MA.getAccessRelation()));
+  const char *Subject = isl_id_get_name(give(MA.getId()).keep());
+
+  generateConditionalExecution(Stmt, AccDom, Subject, [&, this]() {
     Value *NewPointer =
         generateLocationAccessed(Stmt, Store, BBMap, LTS, NewAccesses);
-  Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap, LTS,
-                                    getLoopForStmt(Stmt));
+    Value *ValueOperand = getNewValue(Stmt, Store->getValueOperand(), BBMap,
+                                      LTS, getLoopForStmt(Stmt));
 
     if (PollyDebugPrinting)
       RuntimeDebugBuilder::createCPUPrinter(Builder, "Store to  ", NewPointer,
                                             ": ", ValueOperand, "\n");
 
     Builder.CreateAlignedStore(ValueOperand, NewPointer, Store->getAlignment());
+  });
 }
 
 bool BlockGenerator::canSyntheziseInStmt(ScopStmt &Stmt, Instruction *Inst) {
   Loop *L = getLoopForStmt(Stmt);
   return (Stmt.isBlockStmt() || !Stmt.getRegion()->contains(L)) &&
          canSynthesize(Inst, *Stmt.getParent(), &SE, L);
 }
 
assert((!isa<Instruction>(Address) ||
             DT.dominates(cast<Instruction>(Address)->getParent(),
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     BBMap[MA->getAccessValue()] =
         Builder.CreateLoad(Address, Address->getName() + ".reload");
   }
 }
 
+Value *BlockGenerator::buildContainsCondition(ScopStmt &Stmt,
+                                              const isl::set &Subdomain) {
+  isl::ast_build AstBuild = give(isl_ast_build_copy(Stmt.getAstBuild()));
+  isl::set Domain = give(Stmt.getDomain());
+  isl::union_set UDomain = give(isl_union_set_from_set(Domain.copy()));
+
+  isl::union_map USchedule = give(isl_ast_build_get_schedule(AstBuild.keep()));
+  USchedule =
+      give(isl_union_map_intersect_domain(USchedule.take(), UDomain.copy()));
+  assert(isl_union_map_is_empty(USchedule.keep()) == isl_bool_false);
+  isl::map Schedule = give(isl_map_from_union_map(USchedule.copy()));
+
+  isl::set ScheduledDomain = give(isl_map_range(Schedule.copy()));
+  isl::set ScheduledSet =
+      give(isl_set_apply(Subdomain.copy(), Schedule.copy()));
+
+  isl::ast_build RestrictedBuild =
+      give(isl_ast_build_restrict(AstBuild.copy(), ScheduledDomain.copy()));
+
+  isl::ast_expr IsInSet = give(
+      isl_ast_build_expr_from_set(RestrictedBuild.keep(), ScheduledSet.copy()));
+  Value *IsInSetExpr = ExprBuilder->create(IsInSet.copy());
+  IsInSetExpr = Builder.CreateICmpNE(
+      IsInSetExpr, ConstantInt::get(IsInSetExpr->getType(), 0));
+
+  return IsInSetExpr;
+}
+
+void BlockGenerator::generateConditionalExecution(
+    ScopStmt &Stmt, const isl::set &Subdomain, StringRef Subject,
+    const std::function<void()> &GenThenFunc) {
+  isl::set StmtDom = give(Stmt.getDomain());
+
+  // Don't call GenThenFunc if it is never executed. An ast index expression
+  // might not be defined in this case.
+  bool IsEmpty = isl_set_is_empty(Subdomain.keep()) == isl_bool_true;
+  if (IsEmpty)
+    return;
+
+  // If the condition is a tautology, don't generate a condition around the
+  // code.
+  bool IsPartial =
+      isl_set_is_subset(StmtDom.keep(), Subdomain.keep()) == isl_bool_false;
+  if (!IsPartial) {
+    GenThenFunc();
+    return;
+  }
+
+  // Generate the condition.
+  Value *Cond = buildContainsCondition(Stmt, Subdomain);
+  BasicBlock *HeadBlock = Builder.GetInsertBlock();
+  StringRef BlockName = HeadBlock->getName();
+
+  // Generate the conditional block.
+  SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr,
+                            &DT, &LI);
+  BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
+  BasicBlock *ThenBlock = Branch->getSuccessor(0);
+  BasicBlock *TailBlock = Branch->getSuccessor(1);
+
+  // Assign descriptive names.
+  if (auto *CondInst = dyn_cast<Instruction>(Cond))
+    CondInst->setName("polly." + Subject + ".cond");
+  ThenBlock->setName(BlockName + "." + Subject + ".partial");
+  TailBlock->setName(BlockName + ".cont");
+
+  // Put the client code into the conditional block and continue in the merge
+  // block afterwards.
+  Builder.SetInsertPoint(ThenBlock, ThenBlock->getFirstInsertionPt());
+  GenThenFunc();
+  Builder.SetInsertPoint(TailBlock, TailBlock->getFirstInsertionPt());
+}
+
 void BlockGenerator::generateScalarStores(
     ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
     __isl_keep isl_id_to_ast_expr *NewAccesses) {
   Loop *L = LI.getLoopFor(Stmt.getBasicBlock());
 
   assert(Stmt.isBlockStmt() &&
          "Region statements need to use the generateScalarStores() function in "
          "the RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
     if (MA->isOriginalArrayKind() || MA->isRead())
       continue;
 
-#ifndef NDEBUG
-    auto *StmtDom = Stmt.getDomain();
-    auto *AccDom = isl_map_domain(MA->getAccessRelation());
-    assert(isl_set_is_subset(StmtDom, AccDom) &&
-           "Scalar must be stored in all statement instances");
-    isl_set_free(StmtDom);
-    isl_set_free(AccDom);
-#endif
+    isl::set AccDom = give(isl_map_domain(MA->getAccessRelation()));
+    const char *Subject = isl_id_get_name(give(MA->getId()).keep());
 
+    generateConditionalExecution(Stmt, AccDom, Subject, [&, this, MA]() {
       Value *Val = MA->getAccessValue();
       if (MA->isAnyPHIKind()) {
-      assert(MA->getIncoming().size() >= 1 &&
-             "Block statements have exactly one exiting block, or multiple but "
-             "with same incoming block and value");
+        assert(
+            MA->getIncoming().size() >= 1 &&
         assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
                            [&](std::pair<BasicBlock *, Value *> p) -> bool {
                              return p.first == Stmt.getBasicBlock();
                            }) &&
                "Incoming block must be statement's block");
         Val = MA->getIncoming()[0].second;
       }
-    auto Address =
-        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
+      auto Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap,
+                                        NewAccesses);
 
       Val = getNewValue(Stmt, Val, BBMap, LTS, L);
       assert((!isa<Instruction>(Val) ||
               DT.dominates(cast<Instruction>(Val)->getParent(),
                            Builder.GetInsertBlock())) &&
              "Domination violation");
       assert((!isa<Instruction>(Address) ||
               DT.dominates(cast<Instruction>(Address)->getParent(),
                            Builder.GetInsertBlock())) &&
              "Domination violation");
       Builder.CreateStore(Val, Address);
+
+    });
   }
 }
 
 void BlockGenerator::createScalarInitialization(Scop &S) {
   BasicBlock *ExitBB = S.getExit();
   BasicBlock *PreEntryBB = S.getEnteringBlock();
 
   Builder.SetInsertPoint(&*StartBlock->begin());
void RegionGenerator::generateScalarStores(
   assert(Stmt.getRegion() &&
          "Block statements need to use the generateScalarStores() "
          "function in the BlockGenerator");
 
   for (MemoryAccess *MA : Stmt) {
     if (MA->isOriginalArrayKind() || MA->isRead())
       continue;
 
+    isl::set AccDom = give(isl_map_domain(MA->getAccessRelation()));
+    const char *Subject = isl_id_get_name(give(MA->getId()).keep());
+    generateConditionalExecution(Stmt, AccDom, Subject, [&, this, MA]() {
+
       Value *NewVal = getExitScalar(MA, LTS, BBMap);
-    Value *Address =
-        getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap, NewAccesses);
+      Value *Address = getImplicitAddress(*MA, getLoopForStmt(Stmt), LTS, BBMap,
+                                          NewAccesses);
       assert((!isa<Instruction>(NewVal) ||
               DT.dominates(cast<Instruction>(NewVal)->getParent(),
                            Builder.GetInsertBlock())) &&
              "Domination violation");
       assert((!isa<Instruction>(Address) ||
               DT.dominates(cast<Instruction>(Address)->getParent(),
                            Builder.GetInsertBlock())) &&
              "Domination violation");
       Builder.CreateStore(NewVal, Address);
+    });
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       LoopToScevMapT &LTS) {
   // If the incoming block was not yet copied mark this PHI as incomplete.
   // Once the block will be copied the incoming value will be added.

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::createForParallel(__isl_take isl_ast_node *For) {
   for (const Loop *L : Loops)
     OutsideLoopIterations.erase(L);
 
   isl_ast_node_free(For);
   isl_ast_expr_free(Iterator);
   isl_id_free(IteratorID);
 }
 
+/// Return whether any of @p Node's statements contain partial accesses.
+///
+/// Partial accesses are not supported by Polly's vector code generator.
+static bool hasPartialAccesses(__isl_take isl_ast_node *Node) {
+  return isl_ast_node_foreach_descendant_top_down(
+             Node,
+             [](isl_ast_node *Node, void *User) -> isl_bool {
+               if (isl_ast_node_get_type(Node) != isl_ast_node_user)
+                 return isl_bool_true;
+
+               isl::ast_expr Expr = give(isl_ast_node_user_get_expr(Node));
+               isl::ast_expr StmtExpr =
+                   give(isl_ast_expr_get_op_arg(Expr.keep(), 0));
+               isl::id Id = give(isl_ast_expr_get_id(StmtExpr.keep()));
+
+               ScopStmt *Stmt =
+                   static_cast<ScopStmt *>(isl_id_get_user(Id.keep()));
+               isl::set StmtDom = give(Stmt->getDomain());
+               for (auto *MA : *Stmt) {
+                 if (MA->isLatestPartialAccess())
+                   return isl_bool_error;
+               }
+               return isl_bool_true;
+             },
+             nullptr) == isl_stat_error;
+}
+
 void IslNodeBuilder::createFor(__isl_take isl_ast_node *For) {
   bool Vector = PollyVectorizerChoice == VECTORIZER_POLLY;
 
   if (Vector && IslAstInfo::isInnermostParallel(For) &&
       !IslAstInfo::isReductionParallel(For)) {
     int VectorWidth = getNumberOfIterations(For);
-    if (1 < VectorWidth && VectorWidth <= 16) {
+    if (1 < VectorWidth && VectorWidth <= 16 && !hasPartialAccesses(For)) {
       createForVector(For, VectorWidth);
       return;
     }
   }
 
   if (IslAstInfo::isExecutedInParallel(For)) {
     createForParallel(For);
     return;
if (!MA->hasNewAccessRelation()) {
       }
     }
     assert(MA->isAffine() &&
            "Only affine memory accesses can be code generated");
 
     auto Schedule = isl_ast_build_get_schedule(Build);
 
 #ifndef NDEBUG
+    if (MA->isRead()) {
       auto Dom = Stmt->getDomain();
       auto SchedDom = isl_set_from_union_set(
           isl_union_map_domain(isl_union_map_copy(Schedule)));
       auto AccDom = isl_map_domain(MA->getAccessRelation());
       Dom = isl_set_intersect_params(Dom, Stmt->getParent()->getContext());
       SchedDom =
           isl_set_intersect_params(SchedDom, Stmt->getParent()->getContext());
       assert(isl_set_is_subset(SchedDom, AccDom) &&
              "Access relation not defined on full schedule domain");
       assert(isl_set_is_subset(Dom, AccDom) &&
              "Access relation not defined on full domain");
       isl_set_free(AccDom);
       isl_set_free(SchedDom);
       isl_set_free(Dom);
+    }
 #endif
 
     auto PWAccRel = MA->applyScheduleToAccessRelation(Schedule);
 
+    // isl cannot generate an index expression for access-nothing accesses.
+    isl::set AccDomain =
+        give(isl_pw_multi_aff_domain(isl_pw_multi_aff_copy(PWAccRel)));
+    if (isl_set_is_empty(AccDomain.keep()) == isl_bool_true) {
+      isl_pw_multi_aff_free(PWAccRel);
+      continue;
+    }
+
     auto AccessExpr = isl_ast_build_access_from_pw_multi_aff(Build, PWAccRel);
     NewAccesses = isl_id_to_ast_expr_set(NewAccesses, MA->getId(), AccessExpr);
   }
 
   return NewAccesses;
 }
 
 void IslNodeBuilder::createSubstitutions(__isl_take isl_ast_expr *Expr,

polly/trunk/lib/Exchange/JSONExporter.cpp

for (MemoryAccess *MA : Stmt) {
         return false;
       }
 
       NewAccessDomain =
           isl_set_intersect_params(NewAccessDomain, S.getContext());
       CurrentAccessDomain =
           isl_set_intersect_params(CurrentAccessDomain, S.getContext());
 
-      if (isl_set_is_subset(CurrentAccessDomain, NewAccessDomain) ==
+      if (MA->isRead() &&
+          isl_set_is_subset(CurrentAccessDomain, NewAccessDomain) ==
               isl_bool_false) {
         errs() << "Mapping not defined for all iteration domain elements\n";
         isl_set_free(CurrentAccessDomain);
         isl_set_free(NewAccessDomain);
         isl_map_free(CurrentAccessMap);
         isl_map_free(NewAccessMap);
         return false;
       }
 

polly/trunk/test/Isl/CodeGen/partial_write_array.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-codegen -S < %s | FileCheck %s
+;
+; Partial write of an array access.
+;
+; for (int j = 0; j < n; j += 1)
+;   A[0] = 42.0
+;
+
+define void @partial_write_array(i32 %n, double* noalias nonnull %A) {
+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 %body, label %exit
+
+    body:
+      store double 42.0, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      polly.stmt.body:
+; CHECK-NEXT:   %1 = icmp sge i64 %polly.indvar, 5
+; CHECK-NEXT:   %polly.Stmt_body_Write0.cond = icmp ne i1 %1, false
+; CHECK-NEXT:   br i1 %polly.Stmt_body_Write0.cond, label %polly.stmt.body.Stmt_body_Write0.partial, label %polly.stmt.body.cont
+
+; CHECK:      polly.stmt.body.Stmt_body_Write0.partial:
+; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i64 0
+; CHECK-NEXT:   store double 4.200000e+01, double* %polly.access.A, !alias.scope !0, !noalias !2
+; CHECK-NEXT:   br label %polly.stmt.body.cont
+
+; CHECK:      polly.stmt.body.cont:

polly/trunk/test/Isl/CodeGen/partial_write_array___%for---%return.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_array___%for---%return.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[j] -> MemRef_A[0] : j >= 5 }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_emptyset.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-codegen -S < %s | FileCheck %s
+;
+; Partial write, where "partial" is the empty set.
+; The store is never executed in this case and we do generate it in the
+; first place.
+;
+; for (int j = 0; j < n; j += 1)
+;   A[0] = 42.0
+;
+
+define void @partial_write_emptyset(i32 %n, double* noalias nonnull %A) {
+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 %body, label %exit
+
+    body:
+      store double 42.0, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK-LABEL: polly.stmt.body:
+; CHECK-NOT:     store

polly/trunk/test/Isl/CodeGen/partial_write_emptyset___%for---%return.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[0] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_emptyset___%for---%return.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[j] -> MemRef_A[0] : 1 = 0 }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-codegen -S < %s | FileCheck %s
+;
+; Partial write of a (mapped) scalar.
+;
+; for (int j = 0; j < n; j += 1) {
+;body:
+;   val = 21.0 + 21.0;
+;   if (j >= 5)
+;user:
+;     A[0] = val;
+; }
+
+define void @partial_write_mapped_scalar(i32 %n, double* noalias nonnull %A) {
+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 %body, label %exit
+
+    body:
+      %val = fadd double 21.0, 21.0
+      %if.cond = icmp sgt i32 %j, 5
+      br i1 %if.cond, label %user, label %inc
+
+    user:
+      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
+}
+
+
+; CHECK:      polly.stmt.body:
+; CHECK-NEXT:   %p_val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:   %1 = trunc i64 %polly.indvar to i32
+; CHECK-NEXT:   %p_if.cond = icmp sgt i32 %1, 5
+; CHECK-NEXT:   %2 = icmp sge i64 %polly.indvar, 5
+; CHECK-NEXT:   %polly.Stmt_body_Write0.cond = icmp ne i1 %2, false
+; CHECK-NEXT:   br i1 %polly.Stmt_body_Write0.cond, label %polly.stmt.body.Stmt_body_Write0.partial, label %polly.stmt.body.cont
+
+; CHECK:      polly.stmt.body.Stmt_body_Write0.partial:
+; CHECK-NEXT:   %polly.access.A = getelementptr double, double* %A, i64 1
+; CHECK-NEXT:   store double %p_val, double* %polly.access.A
+; CHECK-NEXT:   br label %polly.stmt.body.cont
+
+; CHECK:      polly.stmt.body.cont:
+; CHECK-NEXT:   br label %polly.cond

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar___%for---%return.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 6 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar___%for---%return.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body[j] -> MemRef_A[1] : j >= 5 }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body",
+         "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[j] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 6 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar_subregion.ll

+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-codegen -S < %s | FileCheck %s
+;
+; Partial write of a (mapped) scalar in a non-affine subregion.
+;
+; for (int j = 0; j < n; j += 1) {
+;subregion:
+;   val = 21.0 + 21.0;
+;   if (undef > undef)
+;subregion_true: ;
+;
+;subregion_exit:
+;   if (j >= 5)
+;user:
+;     A[0] = val;
+; }
+
+define void @partial_write_mapped_scalar_subregion(i32 %n, double* noalias nonnull %A) {
+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 %subregion, label %exit
+
+    subregion:
+      %val = fadd double 21.0, 21.0
+      %nonaffine.cond = fcmp ogt double undef, undef
+      br i1 %nonaffine.cond, label %subregion_true, label %subregion_exit
+
+    subregion_true:
+      br label %subregion_exit
+
+    subregion_exit:
+      %if.cond = icmp sgt i32 %j, 5
+      br i1 %if.cond, label %user, label %inc
+
+    user:
+      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
+}
+
+
+; CHECK-LABEL: polly.stmt.subregion_exit.exit:
+; CHECK-NEXT:    %1 = icmp sge i64 %polly.indvar, 5
+; CHECK-NEXT:    %polly.Stmt_subregion__TO__subregion_exit_Write0.cond = icmp ne i1 %1, false
+; CHECK-NEXT:    br i1 %polly.Stmt_subregion__TO__subregion_exit_Write0.cond, label %polly.stmt.subregion_exit.exit.Stmt_subregion__TO__subregion_exit_Write0.partial, label %polly.stmt.subregion_exit.exit.cont
+
+; CHECK-LABEL: polly.stmt.subregion_exit.exit.Stmt_subregion__TO__subregion_exit_Write0.partial:
+; CHECK-NEXT:    %polly.access.A = getelementptr double, double* %A, i64 1
+; CHECK-NEXT:    store double %p_val, double* %polly.access.A
+; CHECK-NEXT:    br label %polly.stmt.subregion_exit.exit.cont
+
+; CHECK-LABEL: polly.stmt.subregion_exit.exit.cont:

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar_subregion___%for---%return.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body__TO__subregion_exit[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body__TO__subregion_exit[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body__TO__subregion_exit",
+         "schedule" : "[n] -> { Stmt_body__TO__subregion_exit[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 6 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_scalar_subregion___%for---%return.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "[n] -> {  : -2147483648 <= n <= 2147483647 }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_body__TO__subregion_exit[j] -> MemRef_A[1] : j >= 5 }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_body__TO__subregion_exit[i0] : 0 <= i0 < n }",
+         "name" : "Stmt_body__TO__subregion_exit",
+         "schedule" : "[n] -> { Stmt_body__TO__subregion_exit[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "[n] -> { Stmt_user[i0] : 6 <= i0 < n }",
+         "name" : "Stmt_user",
+         "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_vector.ll

+; RUN: opt %loadPolly -basicaa -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-vectorizer=polly -polly-opt-isl -polly-ast -polly-codegen -S < %s | FileCheck %s
+;
+; Polly's vectorizer does not support partial accesses.
+;
+; for (int j = 0; j < 4; j += 1) {
+;body:
+;   val = 21.0 + 21.0;
+;   if (j > 1)
+;user:
+;     A[0] = val;
+; }
+
+define void @partial_write_mapped_vector(double* noalias nonnull %A) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, 4
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      %val = fadd double 21.0, 21.0
+      %if.cond = icmp sgt i32 %j, 1
+      br i1 %if.cond, label %user, label %inc
+
+    user:
+      %elt= getelementptr inbounds double, double* %A, i32 %j
+      store double %val, double* %elt
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK-LABEL: polly.stmt.body:
+; CHECK-NEXT:    %p_val = fadd double 2.100000e+01, 2.100000e+01
+; CHECK-NEXT:    %0 = trunc i64 %polly.indvar to i32
+; CHECK-NEXT:    %p_if.cond = icmp sgt i32 %0, 1
+; CHECK-NEXT:    %1 = icmp sge i64 %polly.indvar, 2
+; CHECK-NEXT:    %polly.Stmt_body_Write0.cond = icmp ne i1 %1, false
+; CHECK-NEXT:    br i1 %polly.Stmt_body_Write0.cond, label %polly.stmt.body.Stmt_body_Write0.partial, label %polly.stmt.body.cont
+
+; CHECK-LABEL:  polly.stmt.body.Stmt_body_Write0.partial:
+; CHECK-NEXT:    %polly.access.A = getelementptr double, double* %A, i64 1
+; CHECK-NEXT:    store double %p_val, double* %polly.access.A
+; CHECK-NEXT:    br label %polly.stmt.body.cont
+
+; CHECK-LABEL:  polly.stmt.body.cont:

polly/trunk/test/Isl/CodeGen/partial_write_mapped_vector___%for---%return.jscop

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_body[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "{ Stmt_body[i0] : 0 <= i0 <= 3 }",
+         "name" : "Stmt_body",
+         "schedule" : "{ Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_user[i0] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_user[i0] -> MemRef_val[] }"
+            }
+         ],
+         "domain" : "{ Stmt_user[i0] : 2 <= i0 <= 3 }",
+         "name" : "Stmt_user",
+         "schedule" : "{ Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}

polly/trunk/test/Isl/CodeGen/partial_write_mapped_vector___%for---%return.jscop.transformed

+{
+   "arrays" : [
+      {
+         "name" : "MemRef_A",
+         "sizes" : [ "*" ],
+         "type" : "double"
+      }
+   ],
+   "context" : "{  :  }",
+   "name" : "%for---%return",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_body[j] -> MemRef_A[1] : j > 1 }"
+            }
+         ],
+         "domain" : "{ Stmt_body[i0] : 0 <= i0 <= 3 }",
+         "name" : "Stmt_body",
+         "schedule" : "{ Stmt_body[i0] -> [i0, 0] }"
+      },
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_user[i0] -> MemRef_A[i0] }"
+            },
+            {
+               "kind" : "read",
+               "relation" : "{ Stmt_user[j] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "{ Stmt_user[i0] : 2 <= i0 <= 3 }",
+         "name" : "Stmt_user",
+         "schedule" : "{ Stmt_user[i0] -> [i0, 1] }"
+      }
+   ]
+}