[Polly]Fix code generation bug with Polly vectorizer

[annanay25]

Summary

This patch fixes bug - https://bugs.llvm.org/show_bug.cgi?id=32533

Bug description:
In VectorBlockGenerator::copyStmt() the argument Stmt does not satisfy the assertion Stmt.isBasicBlock() - which from its definition - Returns true if the statement represents a single basic block.

[Meinersbur]

Thank you for the patch. Some general hints:

• Try to run ninja check-polly (or make check-polly). It will complain about formatting (like missing spaces). You can automatically correct them using ninja polly-update-format
• Please add a test case.
• Please add context to the diff. See: http://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface
• Please add "llvm-commits" and "pollydev" to the subscribers. Also prefix the title with "[Polly]"

lib/CodeGen/IslNodeBuilder.cpp

362–363

If Stmt->isRegionStmt(), these are not used. createUser does the same work again.

365

We usually do not use braces around single statements.

366

Are you sure it is that simple? VectorBlockGenerator::generate generates code to process VectorWidth elements at once. create, which will call createUser, only code to process a single element.

[annanay25]

I have overlooked some details, I will go over the code again.

The cause of the bug is that VectorBlockGenerator::generate() only accepts a single basic block in the Stmt region. Hence,

if ( Stmt->isRegionStmt() )
  // Do some action
else
  VectorBlockGenerator::generate(BlockGen, *Stmt, VLTS, S, NewAccesses);

is one solution. Working out the details for the if part.

Thanks,
Annanay

[grosser]

Can we just fall back to generating non-vectorized code in these cases. This code path certainly should not break, but as we do not use the Polly vectorizer by default, it is likely not worth spending time on optimizing execution time performance before we find a test case where this is really useful.

[annanay25]

Yes sir, in this particular bug we are however, explicitly calling polly's vectorizer.

opt  -polly-process-unprofitable  -polly-remarks-minimal  -polly-vectorizer=polly -polly-codegen -S constants_0.ll

The fix that I suggested above is a strict no, it breaks too many test cases:

Failing Tests (24):
    Polly :: Isl/CodeGen/MemAccess/simple_analyze.ll
    Polly :: Isl/CodeGen/MemAccess/simple_stride_test.ll
    Polly :: Isl/CodeGen/invariant_load_hoist_alignment.ll
    Polly :: Isl/CodeGen/simple_vec_assign_scalar.ll
    Polly :: Isl/CodeGen/simple_vec_assign_scalar_2.ll
    Polly :: Isl/CodeGen/simple_vec_call.ll
    Polly :: Isl/CodeGen/simple_vec_call_2.ll
    Polly :: Isl/CodeGen/simple_vec_cast.ll
    Polly :: Isl/CodeGen/simple_vec_const.ll
    Polly :: Isl/CodeGen/simple_vec_large_width.ll
    Polly :: Isl/CodeGen/simple_vec_ptr_ptr_ty.ll
    Polly :: Isl/CodeGen/simple_vec_stride_negative_one.ll
    Polly :: Isl/CodeGen/simple_vec_stride_one.ll
    Polly :: Isl/CodeGen/simple_vec_stride_x.ll
    Polly :: Isl/CodeGen/simple_vec_strides_multidim.ll
    Polly :: Isl/CodeGen/simple_vec_two_stmts.ll
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_3.ll
    Polly :: ScopInfo/phi-in-non-affine-region.ll
    Polly :: ScopInfo/stride_detection.ll
    Polly :: ScopInfo/user_provided_assumptions-in-bb-unsigned.ll
    Polly :: ScopInfo/user_provided_assumptions.ll
    Polly :: ScopInfo/user_provided_assumptions_2.ll
    Polly :: ScopInfo/user_provided_assumptions_3.ll
    Polly :: ScopInfo/user_provided_non_dominating_assumptions.ll

  Expected Passes    : 719
  Expected Failures  : 11
  Unsupported Tests  : 35
  Unexpected Failures: 24

[grosser]

There is no guarantee that every statement must be vectorized. The only requirement is that we should not crash or assert. Feel free to add vectorization support for regions, but my advice is to delay further support until we have evidence that this could speed up performance. ;-)

[annanay25]

@grosser sure thing sir, thanks!

[annanay25]

This code falls back to generating scalar code when isl_ast_node_user is found to be a Region.

List of failed tests -

Failing Tests (7):
    Polly :: ScheduleOptimizer/pattern-matching-based-opts_3.ll
    Polly :: ScopInfo/phi-in-non-affine-region.ll
    Polly :: ScopInfo/user_provided_assumptions-in-bb-unsigned.ll
    Polly :: ScopInfo/user_provided_assumptions.ll
    Polly :: ScopInfo/user_provided_assumptions_2.ll
    Polly :: ScopInfo/user_provided_assumptions_3.ll
    Polly :: ScopInfo/user_provided_non_dominating_assumptions.ll

  Expected Passes    : 737
  Expected Failures  : 11
  Unsupported Tests  : 35
  Unexpected Failures: 7

[Meinersbur]

I added a check in D33255 that tests whether some code-to-be-vectorized contains a partial accesses (which it cannot vectorize). You could take a similar approach for region statements.

lib/CodeGen/IslNodeBuilder.cpp

void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
   std::vector<LoopToScevMapT> VLTS(IVS.size());
 
   isl_union_set *Domain = isl_union_set_from_set(Stmt->getDomain());
   Schedule = isl_union_map_intersect_domain(Schedule, Domain);
   isl_map *S = isl_map_from_union_map(Schedule);
 
   auto *NewAccesses = createNewAccesses(Stmt, User);
   createSubstitutionsVector(Expr, Stmt, VLTS, IVS, IteratorID);
+
+  if (Stmt->isRegionStmt())
+    createUser(User);
+  else {
     VectorBlockGenerator::generate(BlockGen, *Stmt, VLTS, S, NewAccesses);
+    isl_ast_node_free(User);
+  }
+
   isl_id_to_ast_expr_free(NewAccesses);
   isl_map_free(S);
   isl_id_free(Id);
-  isl_ast_node_free(User);
 }
 
 void IslNodeBuilder::createMark(__isl_take isl_ast_node *Node) {
   auto *Id = isl_ast_node_mark_get_id(Node);
   auto Child = isl_ast_node_mark_get_node(Node);
   isl_ast_node_free(Node);
   // If a child node of a 'SIMD mark' is a loop that has a single iteration,
   // it will be optimized away and we should skip it.

test/Isl/CodeGen/region-vec-fallback.ll

+; RUN: opt %loadPolly -polly-vectorizer=polly -polly-codegen -S < %s
+;
+; Check that we do not crash while attempting to vectorize a region stmt.
+;
+; CHECK : polly.start
+;
+source_filename = "bugpoint-output-4e649ba.bc"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @calcfreq_nuc(double* %datafreq) #0 {
+entry:
+  br label %for.body
+
+for.cond1.preheader:                              ; preds = %for.body
+  br label %for.body37
+
+for.body:                                         ; preds = %for.body, %entry
+  br i1 undef, label %for.body, label %for.cond1.preheader
+
+for.cond49.preheader:                             ; preds = %for.inc46
+  ret void
+
+for.body37:                                       ; preds = %for.inc46, %for.cond1.preheader
+  %indvars.iv116 = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next117, %for.inc46 ]
+  %arrayidx39 = getelementptr inbounds double, double* %datafreq, i64 %indvars.iv116
+  %cmp40 = fcmp olt double undef, 1.000000e-04
+  br i1 %cmp40, label %if.then42, label %for.inc46
+
+if.then42:                                        ; preds = %for.body37
+  store double 1.000000e-04, double* %arrayidx39, align 8, !tbaa !1
+  br label %for.inc46
+
+for.inc46:                                        ; preds = %if.then42, %for.body37
+  %indvars.iv.next117 = add nuw nsw i64 %indvars.iv116, 1
+  %exitcond118 = icmp ne i64 %indvars.iv.next117, 4
+  br i1 %exitcond118, label %for.body37, label %for.cond49.preheader
+}
+
+attributes #0 = { nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 5.0.0 "}
+!1 = !{!2, !2, i64 0}
+!2 = !{!"double", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C/C++ TBAA"}