[Polly] Align copied load/store instructions as the original.

[grosser]

Is this save?

For normal accesses, we can probably say that the different iterations
of a statement will always access the same set of memory locations,
independently of the schedule of this statement. If the original
accesses have been aligned to a certain boundary before, they accesses
of the rescheduled statements will be aligned again.

Regarding user modified access functions. The above reasoning only holds
if the new access function does only access data locations that have
also been accessed by this statement when using the old access function.
If we modified access functions to use data locations that have been
used in the scop, but not in the very same statement, this
assumption does not hold, as the uses in the other statement may have a
different alignment.

I see three approaches here:

1. Leave it as it is.

2. Have the jscop-importer check that access functions are only modified in the way described above.

3. Compute the new alignment correctly, by first deriving the alignment of the base ptr based on the alignments of the accesses and then recompute the alignment of the accesses from the possibly modified access function.

1. feels unsatisfying to me 3) would be nice to have, but is probably

too involved for this patch. 2) is hopefully just a two line change and
could possibly save us in the future.

Cheers,
Tobias

(You also miss a test case)

[jdoerfert]

• msg-27978-61.dat219 BDownload

[jdoerfert]

Added testcases and updated according to reviews

[jdoerfert]

Closed by commit rL218883 (authored by @jdoerfert).

polly/trunk/lib/CodeGen/BlockGenerators.cpp

 Value *BlockGenerator::generateScalarLoad(const LoadInst *Load,
                                           ValueMapT &BBMap,
                                           ValueMapT &GlobalMap,
                                           LoopToScevMapT &LTS) {
   const Value *Pointer = Load->getPointerOperand();
   const Instruction *Inst = dyn_cast<Instruction>(Load);
   Value *NewPointer =
       generateLocationAccessed(Inst, Pointer, BBMap, GlobalMap, LTS);
-  Value *ScalarLoad =
-      Builder.CreateLoad(NewPointer, Load->getName() + "_p_scalar_");
+  Value *ScalarLoad = Builder.CreateAlignedLoad(
+      NewPointer, Load->getAlignment(), Load->getName() + "_p_scalar_");
   return ScalarLoad;
 }
 
 Value *BlockGenerator::generateScalarStore(const StoreInst *Store,
                                            ValueMapT &BBMap,
                                            ValueMapT &GlobalMap,
                                            LoopToScevMapT &LTS) {
   const Value *Pointer = Store->getPointerOperand();
   Value *NewPointer =
       generateLocationAccessed(Store, Pointer, BBMap, GlobalMap, LTS);
   Value *ValueOperand = getNewValue(Store->getValueOperand(), BBMap, GlobalMap,
                                     LTS, getLoopForInst(Store));
 
-  return Builder.CreateStore(ValueOperand, NewPointer);
+  Value *NewStore = Builder.CreateAlignedStore(ValueOperand, NewPointer,
+                                               Store->getAlignment());
+  return NewStore;
 }
 
 void BlockGenerator::copyInstruction(const Instruction *Inst, ValueMapT &BBMap,
                                      ValueMapT &GlobalMap,
                                      LoopToScevMapT &LTS) {
   // Terminator instructions control the control flow. They are explicitly
   // expressed in the clast and do not need to be copied.
   if (Inst->isTerminator())

polly/trunk/lib/Exchange/JSONExporter.cpp

for (MemoryAccess *MA : *Stmt) {
       if (isl_map_dim(newAccessMap, isl_dim_param) !=
           isl_map_dim(currentAccessMap, isl_dim_param)) {
         errs() << "JScop file changes the number of parameter dimensions\n";
         isl_map_free(currentAccessMap);
         isl_map_free(newAccessMap);
         return false;
       }
 
+      // We keep the old alignment, thus we cannot allow accesses to memory
+      // locations that were not accessed before.
+      isl_set *newAccessSet = isl_map_range(isl_map_copy(newAccessMap));
+      isl_set *currentAccessSet = isl_map_range(isl_map_copy(currentAccessMap));
+      bool isSubset = isl_set_is_subset(newAccessSet, currentAccessSet);
+      isl_set_free(newAccessSet);
+      isl_set_free(currentAccessSet);
+
+      if (!isSubset) {
+        errs() << "JScop file changes the accessed memory\n";
+        isl_map_free(currentAccessMap);
+        isl_map_free(newAccessMap);
+        return false;
+      }
+
       // We need to copy the isl_ids for the parameter dimensions to the new
       // map. Without doing this the current map would have different
       // ids then the new one, even though both are named identically.
       for (unsigned i = 0; i < isl_map_dim(currentAccessMap, isl_dim_param);
            i++) {
         isl_id *id = isl_map_get_dim_id(currentAccessMap, isl_dim_param, i);
         newAccessMap = isl_map_set_dim_id(newAccessMap, isl_dim_param, i, id);
       }

polly/trunk/test/Isl/CodeGen/MemAccess/bad_alignment.ll

+; RUN: opt %loadPolly -polly-codegen-scev -polly-import-jscop -polly-import-jscop-dir=%S -analyze 2>&1 < %s | FileCheck %s
+;
+; Check that we do not allow to access elements not accessed before because the
+; alignment information would become invalid.
+;
+; CHECK: JScop file changes the accessed memory
+;
+;    void bad_alignment(int *A) {
+;      for (int i = 0; i < 1024; i += 2)
+;        A[i] = i;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @bad_alignment(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

polly/trunk/test/Isl/CodeGen/MemAccess/bad_alignment___%for.cond---%for.end.jscop

+{
+   "context" : "{  :  }",
+   "name" : "for.cond => polly.merge_new_and_old",
+   "statements" : [
+      {
+         "accesses" : [
+            {
+               "kind" : "write",
+               "relation" : "{ Stmt_for_body[i0] -> MemRef_A[1] }"
+            }
+         ],
+         "domain" : "{ Stmt_for_body[i0] : i0 >= 0 and i0 <= 511 }",
+         "name" : "Stmt_for_body",
+         "schedule" : "{ Stmt_for_body[i0] -> scattering[0, i0, 0] }"
+      }
+   ]
+}

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

+; RUN: opt %loadPolly -polly-codegen-scev -polly-codegen-isl -S < %s | FileCheck %s
+;
+; Check that the special alignment information is kept
+;
+; CHECK: align 8
+; CHECK: align 8
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i += 2)
+;        A[i] = i;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, 1024
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx, align 8
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 2
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

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

 ; RUN: opt %loadPolly -polly-code-generator=isl -polly-codegen-isl -S < %s | FileCheck %s --check-prefix=SCOPES
 ; RUN: opt %loadPolly -polly-code-generator=isl -polly-codegen-isl -polly-annotate-alias-scopes=false -S < %s | FileCheck %s --check-prefix=NOSCOPES
 ;
 ; Check that we create alias scopes that indicate the accesses to A, B and C cannot alias in any way.
 ;
 ; SCOPES:      %[[BIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds i32* %B, i64 %polly.indvar
-; SCOPES:      load i32* %[[BIdx]], !alias.scope ![[AliasScopeB:[0-9]*]], !noalias ![[NoAliasB:[0-9]*]]
+; SCOPES:      load i32* %[[BIdx]], align 4, !alias.scope ![[AliasScopeB:[0-9]*]], !noalias ![[NoAliasB:[0-9]*]]
 ; SCOPES:      %[[CIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds float* %C, i64 %polly.indvar
-; SCOPES:      load float* %[[CIdx]], !alias.scope ![[AliasScopeC:[0-9]*]], !noalias ![[NoAliasC:[0-9]*]]
+; SCOPES:      load float* %[[CIdx]], align 4, !alias.scope ![[AliasScopeC:[0-9]*]], !noalias ![[NoAliasC:[0-9]*]]
 ; SCOPES:      %[[AIdx:[._a-zA-Z0-9]*]] = getelementptr inbounds i32* %A, i64 %polly.indvar
-; SCOPES:      store i32 %{{[._a-zA-Z0-9]*}}, i32* %[[AIdx]], !alias.scope ![[AliasScopeA:[0-9]*]], !noalias ![[NoAliasA:[0-9]*]]
+; SCOPES:      store i32 %{{[._a-zA-Z0-9]*}}, i32* %[[AIdx]], align 4, !alias.scope ![[AliasScopeA:[0-9]*]], !noalias ![[NoAliasA:[0-9]*]]
 ;
 ; SCOPES:      ![[AliasScopeB]] = metadata !{metadata ![[AliasScopeB]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.B"}
 ; SCOPES:      ![[NoAliasB]] = metadata !{
 ; SCOPES-DAG:     metadata ![[AliasScopeA]]
 ; SCOPES-DAG:     metadata ![[AliasScopeC]]
 ; SCOPES:       }
 ; SCOPES-DAG:  ![[AliasScopeA]] = metadata !{metadata ![[AliasScopeA]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.A"}
 ; SCOPES-DAG:  ![[AliasScopeC]] = metadata !{metadata ![[AliasScopeC]], metadata !{{[0-9]*}}, metadata !"polly.alias.scope.C"}