[FIX] Restrict the AST build with the assumed context

[jdoerfert]

Summary

This is necessary as the dependence analysis is restricted by the
assumed context as well and the AST generation needs to be in-sync.
Otherwise this might generate not executed code that will crash the
scalar code generation. Additionally, this change can simplify the AST
as less conditions and code needs to be generated.

[grosser]

Hi Johannes,

thanks for the interesting test case.

jdoerfert created this revision.
jdoerfert added reviewers: grosser, Meinersbur.
jdoerfert added a subscriber: Polly.

This is necessary as the dependence analysis is restricted by the
assumed context as well and the AST generation needs to be in-sync.
Otherwise this might generate not executed code that will crash the
scalar code generation. Additionally, this change can simplify the AST
as less conditions and code needs to be generated.

This change may indeed make sense, but my feeling is that it only hides the
bug rather than actually solves it.

This is for two reasons:

1. The AST generator is not guaranteed to exploit the context.
2. The AST generator is not guaranteed to ensure a certain _textual_ order.

To my understanding it seems the scalar code generation has somehow a requirement
on the textual order code is emitted in. Is this right? Why is this needed?

The issue is that two statements with dependences A(i) -> B(i) can theoretically
be code generated in the following way:

for (i = 0; i <= n; i++) {

if (i > 0)
  B(i-1);
 A(i)

}
B(n);

This means, even though A(i) is guaranteed to be executed before B(i), their actual
textual order may be reversed.

In general we avoid this issue by _always_ going through memory, such that there is no
dominance needed, but such that for a valid execution the temporal order of memory
accesses is correct.

Best,
Tobias

Index: test/Isl/CodeGen/assumed_context_empty_domain_restriction.ll

• test/Isl/CodeGen/assumed_context_empty_domain_restriction.ll

+++ test/Isl/CodeGen/assumed_context_empty_domain_restriction.ll
@@ -1,18 +1,19 @@
-; RUN: opt %loadPolly -S -polly-opt-isl -polly-codegen < %s
+; RUN: opt %loadPolly -S -polly-opt-isl -polly-ast -analyze < %s | FileCheck --check-prefix=AST %s
+; RUN: opt %loadPolly -S -polly-opt-isl -polly-codegen < %s | FileCheck %s

;

-; TODO: This test will crash the scalar code generation. The problem step by step:
-; 1) The assumed context is empty because of the out-of-bounds array access.
-; 2) The dependence analysis will use the assumed context and determine
-; that there are not iterations executed, hence no dependences.
-; 3) The scheduler will transform the program somehow according to
-; the orginal domains and empty dependences but not the assumed context.
-; The new ast is shown below.
-; 4) The code generation will look for the new value of %0 when the
-; for_body_328_lr_ph statement is copied, however it has not yet seen %0
-; as the for_end_310 statement has been moved after for_body_328_lr_ph.
-; 5) Crash as no new value of %0 can be found.
+; This test crashed the scalar code generation. The problem step by step:
+; 1) The assumed context is empty because of the out-of-bounds array access.
+; 2) The dependence analysis will use the assumed context and determine
+; that there are not iterations executed, hence no dependences.
+; 3) The scheduler will transform the program somehow according to
+; the orginal domains and empty dependences but not the assumed context.
+; The new and the old ast is shown below.
+; 4) The code generation will look for the new value of %0 when the
+; for_body_328_lr_ph statement is copied, however it has not yet seen %0
+; as the for_end_310 statement has been moved after for_body_328_lr_ph.
+; 5) Crash as no new value of %0 can be found.

;

-; AST:
+; AST old:

;
;   if (0)
;       {

@@ -24,11 +25,12 @@

;   else
;       {  /* original code */ }
;

-; CHECK: polly.start
-;
-; TODO: This test should not crash Polly.
+; AST new:
+; AST: if (0)
+; AST: {
+; AST: }

;

-; XFAIL: *
+; CHECK: polly.start

;
@endposition = external global i32, align 4
@Bit = external global [0 x i32], align 4

Index: lib/CodeGen/IslAst.cpp

• lib/CodeGen/IslAst.cpp

+++ lib/CodeGen/IslAst.cpp
@@ -416,6 +416,13 @@

buildRunCondition(Build);

+ The assumed context restricts the dependence analysis, hence it also has
+ to restrict the AST generation otherwise the scalar code generation can
+ become unstable. However, we need to do this after we generated the runtime
+ checks as the context we use to restrict the AST generation with only holds
+ // if the runtime checks are true.
+ Build = isl_ast_build_restrict(Build, S->getAssumedContext());
+

Root = isl_ast_build_node_from_schedule(Build, S->getScheduleTree());

isl_ast_build_free(Build);

[jdoerfert]

Use the correct fix for the code generation problem at hand.

[grosser]

This new fix looks good to me.

Please update the commit message to explain the issue and the resolution. I would appreciate if you give some more details about the context, such that other people looking at your commit learn about the necessary context of our scalar code generation.

Regarding the other fix, I did not yet look into this, but would probably leave it for now
as it is. If you want to get it in, we need to check if restricting the ast_build does not
have a high cost in case of a complicated assumed context.

[llvm-commits]

• msg-2311-280.dat219 BDownload
• msg-2311-281.txt162 BDownload

polly/trunk/lib/CodeGen/BlockGenerators.cpp

if (!R.contains(ScalarValueInst)) {
     else
       return /* Case 2 */ ScalarValue;
   }
 
   if (Value *ScalarValueCopy = BBMap.lookup(ScalarValueInst))
     return /* Case (3a) */ ScalarValueCopy;
 
   // Case (3b)
-  assert(ReloadMap.count(ScalarValueInst) &&
-         "ScalarInst not mapped in the block and not in the given reload map!");
-  Value *ReloadAddr = ReloadMap[ScalarValueInst];
+  Value *ReloadAddr = getOrCreateAlloca(ScalarValueInst, ReloadMap, ".s2a");
   ScalarValue =
       Builder.CreateLoad(ReloadAddr, ReloadAddr->getName() + ".reload");
 
   return ScalarValue;
 }
 
 void BlockGenerator::generateScalarStores(ScopStmt &Stmt, BasicBlock *BB,
                                           ValueMapT &BBMap,

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

-; RUN: opt %loadPolly -S -polly-opt-isl -polly-codegen < %s
+; RUN: opt %loadPolly -S -polly-opt-isl -polly-codegen < %s | FileCheck %s
 ;
-; TODO: This test will crash the scalar code generation. The problem step by step:
-;         1) The assumed context is empty because of the out-of-bounds array access.
-;         2) The dependence analysis will use the assumed context and determine
-;            that there are not iterations executed, hence no dependences.
-;         3) The scheduler will transform the program somehow according to
-;            the orginal domains and empty dependences but not the assumed context.
-;            The new ast is shown below.
-;         4) The code generation will look for the new value of %0 when the
-;            for_body_328_lr_ph statement is copied, however it has not yet seen %0
-;            as the for_end_310 statement has been moved after for_body_328_lr_ph.
-;         5) Crash as no new value of %0 can be found.
-;
-; AST:
-;
-;   if (0)
-;       {
-;         for (int c0 = 0; c0 <= 32; c0 += 1)
-;           Stmt_for_body_328(c0);
-;         Stmt_for_body_328_lr_ph();
-;         Stmt_for_end_310();
-;       }
-;   else
-;       {  /* original code */ }
+; This test used to crash the scalar code generation.
 ;
 ; CHECK: polly.start
 ;
-; TODO: This test should not crash Polly.
-;
-; XFAIL: *
-;
 @endposition = external global i32, align 4
 @Bit = external global [0 x i32], align 4
 @Init = external global [0 x i32], align 4
 
 define void @maskgen() {
 entry:
   br label %for.body