[Polly] [PPCGCodeGeneration] Construct array bounds correctly even when polly-ignore-parameter-bounds is turned on.

[bollu]

Summary

When we have -polly-ignore-parameter-bounds, Scop::Context does not contain
all the paramters present in the program.

The construction of the isl_multi_pw_aff requires all the indivisual pw_aff
to have the same parameter dimensions. To achieve this, we used to realign
every pw_aff with Scop::Context. However, in conjunction with
-polly-ignore-parameter-bounds, this is now incorrect, since Scop::Context
does not contain all parameters.

We set this up correctly by creating a space that has all the parameters
used by all the isl_pw_aff. Then, we realign all isl_pw_aff to this space.

[bollu]

• [NFC] comment out test explanation

[bollu]

• [NFC] clean up test case to be sensible.

[bollu]

• [NFC] remove debug code

lib/CodeGen/PPCGCodeGeneration.cpp

2819

I'm debating if I need a comment on this, or if I expect people to git blame this. Thoughts?

[philip.pfaffe]

Some nits inline.

lib/CodeGen/PPCGCodeGeneration.cpp

2789

Why copy the set and then immediately destroy it?

Happens further down as well.

2842

No need to free the space if you don't copy it here.

2849

Debug output should be wrapped in DEBUG()

[philip.pfaffe]

lib/CodeGen/PPCGCodeGeneration.cpp

2819

You should comment it. blame isn't available on, e.g., the distributed source.

[bollu]

• [NFC] take philip's comments into account. Write comment & remove a copy-free cycle

[bollu]

lib/CodeGen/PPCGCodeGeneration.cpp

2789

This is old code, I can update this in another [NFC] patch.

2849

It's a sanity check, so I disagree. the assert will be removed in release builds anyway.

[bollu]

@grosser: This test case still fails with this patch applied

failing-test-case-guard-node-params.ll

; RUN: opt -S -polly-process-unprofitable -polly-codegen-ppcg -polly-invariant-load-hoisting -polly-ignore-parameter-bounds test.ll
; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "bugpoint-output-4d01492.bc"
target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
target triple = "x86_64-unknown-linux-gnu"

%"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409" = type { i8*, i64, i64, [2 x %struct.descriptor_dimension.0.6.18.30.48.60.66.84.102.180.186.192.198.204.228.240.300.330.408] }
%struct.descriptor_dimension.0.6.18.30.48.60.66.84.102.180.186.192.198.204.228.240.300.330.408 = type { i64, i64, i64 }

@__m_dump_MOD_lmind_ilon = external unnamed_addr global %"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409", align 32

; Function Attrs: nounwind uwtable
define void @__m_dump_MOD_init_dump_block(i32* noalias %nblock) #0 {
entry:
  %0 = load i32, i32* %nblock, align 4
  br label %"137"

"137":                                            ; preds = %"140", %entry
  %1 = phi i32 [ %12, %"140" ], [ 1, %entry ]
  br label %"138"

"138":                                            ; preds = %"138", %"137"
  %2 = load i32*, i32** bitcast (%"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409"* @__m_dump_MOD_lmind_ilon to i32**), align 32
  %3 = sext i32 %1 to i64
  %4 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409", %"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409"* @__m_dump_MOD_lmind_ilon, i64 0, i32 3, i64 1, i32 0), align 8
  %5 = mul i64 %4, %3
  %6 = add i64 %5, 0
  %7 = load i64, i64* getelementptr inbounds (%"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409", %"struct.array2_real(kind=8).1.7.19.31.49.61.67.85.103.181.187.193.199.205.229.241.301.331.409"* @__m_dump_MOD_lmind_ilon, i64 0, i32 1), align 8
  %8 = add i64 %6, %7
  %9 = getelementptr i32, i32* %2, i64 %8
  store i32 undef, i32* %9, align 4
  %10 = icmp eq i32 0, 0
  br i1 %10, label %"140", label %"138"

"140":                                            ; preds = %"138"
  %11 = icmp eq i32 %1, %0
  %12 = add i32 %1, 1
  br i1 %11, label %return.loopexit, label %"137"

return.loopexit:                                  ; preds = %"140"
  ret void
}

attributes #0 = { nounwind uwtable }

Backtrace:

/Users/bollu/work/LLVM-all/polly/llvm/tools/polly/lib/External/isl/isl_ast_codegen.c:5419: guard node is not allowed to introduce new parameters
0  libLLVMSupport.dylib     0x000000010cb8349c llvm::sys::PrintStackTrace(llvm::raw_ostream&) + 60
1  libLLVMSupport.dylib     0x000000010cb839e9 PrintStackTraceSignalHandler(void*) + 25
2  libLLVMSupport.dylib     0x000000010cb7fa99 llvm::sys::RunSignalHandlers() + 425
3  libLLVMSupport.dylib     0x000000010cb83d32 SignalHandler(int) + 354
4  libsystem_platform.dylib 0x00007fffcd352b3a _sigtramp + 26
5  libsystem_platform.dylib 0x0000000100000001 _sigtramp + 852153569
6  libsystem_c.dylib        0x00007fffcd1d7420 abort + 129
7  libPollyISL.dylib        0x000000010dd5eca5 isl_handle_error + 213
8  libPollyISL.dylib        0x000000010dd39116 build_ast_from_guard + 166
9  libPollyISL.dylib        0x000000010dd387f7 build_ast_from_schedule_node + 311
10 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
11 libPollyISL.dylib        0x000000010dd38f8b build_ast_from_filter + 331
12 libPollyISL.dylib        0x000000010dd387dd build_ast_from_schedule_node + 285
13 libPollyISL.dylib        0x000000010dd3945d build_ast_from_sequence + 141
14 libPollyISL.dylib        0x000000010dd3882b build_ast_from_schedule_node + 363
15 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
16 libPollyISL.dylib        0x000000010dd38fbc build_ast_from_filter + 380
17 libPollyISL.dylib        0x000000010dd387dd build_ast_from_schedule_node + 285
18 libPollyISL.dylib        0x000000010dd3945d build_ast_from_sequence + 141
19 libPollyISL.dylib        0x000000010dd3882b build_ast_from_schedule_node + 363
20 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
21 libPollyISL.dylib        0x000000010dd38e2c build_ast_from_extension + 188
22 libPollyISL.dylib        0x000000010dd387c3 build_ast_from_schedule_node + 259
23 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
24 libPollyISL.dylib        0x000000010dd38fbc build_ast_from_filter + 380
25 libPollyISL.dylib        0x000000010dd387dd build_ast_from_schedule_node + 285
26 libPollyISL.dylib        0x000000010dd3945d build_ast_from_sequence + 141
27 libPollyISL.dylib        0x000000010dd3882b build_ast_from_schedule_node + 363
28 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
29 libPollyISL.dylib        0x000000010dd38e2c build_ast_from_extension + 188
30 libPollyISL.dylib        0x000000010dd387c3 build_ast_from_schedule_node + 259
31 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
32 libPollyISL.dylib        0x000000010dd391d3 build_ast_from_guard + 355
33 libPollyISL.dylib        0x000000010dd387f7 build_ast_from_schedule_node + 311
34 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
35 libPollyISL.dylib        0x000000010dd38bbf build_ast_from_context + 271
36 libPollyISL.dylib        0x000000010dd3875b build_ast_from_schedule_node + 155
37 libPollyISL.dylib        0x000000010dd383f6 build_ast_from_child + 54
38 libPollyISL.dylib        0x000000010dd37a3e build_ast_from_domain + 318
39 libPollyISL.dylib        0x000000010dd378d6 isl_ast_build_node_from_schedule + 198
40 libPollyPPCG.dylib       0x000000010dca3ae2 generate_code + 290
41 libPolly.dylib           0x00000001090039a7 (anonymous namespace)::PPCGCodeGeneration::generateGPU(ppcg_scop*, gpu_prog*) + 391
42 libPolly.dylib           0x0000000109002d06 (anonymous namespace)::PPCGCodeGeneration::runOnScop(polly::Scop&) + 342
43 libPolly.dylib           0x0000000108f4ee5e polly::ScopPass::runOnRegion(llvm::Region*, llvm::RGPassManager&) + 142
44 libLLVMAnalysis.dylib    0x0000000109c4b9ed llvm::RGPassManager::runOnFunction(llvm::Function&) + 2093
45 libLLVMCore.dylib        0x000000010a96711f llvm::FPPassManager::runOnFunction(llvm::Function&) + 399
46 libLLVMCore.dylib        0x000000010a967625 llvm::FPPassManager::runOnModule(llvm::Module&) + 117
47 libLLVMCore.dylib        0x000000010a9683f4 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) + 2196
48 libLLVMCore.dylib        0x000000010a9678e6 llvm::legacy::PassManagerImpl::run(llvm::Module&) + 342
49 libLLVMCore.dylib        0x000000010a969121 llvm::legacy::PassManager::run(llvm::Module&) + 33
50 opt                      0x00000001029dc0cf main + 27263
51 libdyld.dylib            0x00007fffcd143235 start + 1
52 libdyld.dylib            0x0000000000000007 start + 854314451
Stack dump:
0.	Program arguments: opt -S -polly-process-unprofitable -polly-codegen-ppcg -polly-invariant-load-hoisting -polly-ignore-parameter-bounds test.ll
1.	Running pass 'Function Pass Manager' on module 'test.ll'.
2.	Running pass 'Region Pass Manager' on function '@__m_dump_MOD_init_dump_block'
3.	Running pass 'Polly - Apply PPCG translation to SCOP' on basic block '%"137"'
./run.sh: line 1: 70072 Abort trap: 6           opt -S -polly-process-unprofitable -polly-codegen-ppcg -polly-invariant-load-hoisting -polly-ignore-parameter-bounds test.ll

[grosser]

The other issue you are having seems to be another bug. Let's upstream this change and make this a new bug.

Regarding the new bug, I think we should add all parameters to the root node of the schedule tree right before AST generation. I think this should fix the bug.

[grosser]

But can you please factor the aligning of spaces into a separate function?

[bollu]

• [NFC] extract out alignment code into . It's not pretty.

[bollu]

@grosser - I extracted out the logic for alignment, but it's hardly pretty. Any ideas on how to make it neater?

[bollu]

• [NFC] fix mixup of __isl_{give/take}, change variable names to better indicate what they do.

[philip.pfaffe]

Some comments inline.

I don't understand the testcase. Instead of verifying the generated multi-aff, which is what your patch is creating, you're checking for a generated kernel launch. How is this related? IMO a test should check one specific thing. Otherwise, if this test fails, we have no idea whether it's because of the multi-aff being incorrectly generated or because of something entirely unrelated.

lib/CodeGen/PPCGCodeGeneration.cpp

2789

I think the isl ownership tags on this API are backwards.

2836

Why not have AlignPwAffs take an rvalue-reference to the vector, and then std::move PwAffs into the call?

That would make it clear directly on the interface that AlignPwAffs takes ownership of the entire vector.

Alternatively, if you don't like move and rvalue-refs, take PwAffs as a non-const reference out-parameter (and explain the modification AlignPwAffs makes to that parameter).

[bollu]

• [NFC] use an rvalue ref to make it clear that we drain the original vector.

[bollu]

• [NFC] extracted out creation of isl_pw_aff_list into separate function as well.

[bollu]

• [NFC] camelCase.

[philip.pfaffe]

LGTM.

[bollu]

Closed by r309934.

lib/CodeGen/PPCGCodeGeneration.cpp

std::string GPUNodeBuilder::finalizeKernelFunction() {
   if (DumpKernelASM)
     outs() << Assembly << "\n";
 
   GPUModule.release();
   KernelIDs.clear();
 
   return Assembly;
 }
+/// Construct an `isl_pw_aff_list` from a vector of `isl_pw_aff`
+/// @param PwAffs The list of piecewise affine functions to create an
+///               `isl_pw_aff_list` from. We expect an rvalue ref because
+///               all the isl_pw_aff are used up by this function.
+///
+/// @returns  The `isl_pw_aff_list`.
+__isl_give isl_pw_aff_list *
+createPwAffList(isl_ctx *Context,
+                const std::vector<__isl_take isl_pw_aff *> &&PwAffs) {
+  isl_pw_aff_list *List = isl_pw_aff_list_alloc(Context, PwAffs.size());
+
+  for (unsigned i = 0; i < PwAffs.size(); i++) {
+    List = isl_pw_aff_list_insert(List, i, PwAffs[i]);
+  }
+  return List;
+}
+
+/// Align all the `PwAffs` such that they have the same parameter dimensions.
+///
+/// We loop over all `pw_aff` and align all of their spaces together to
+/// create a common space for all the `pw_aff`. This common space is the
+/// `AlignSpace`. We then align all the `pw_aff` to this space. We start
+/// with the given `SeedSpace`.
+/// @param PwAffs    The list of piecewise affine functions we want to align.
+///                  This is an rvalue reference because the entire vector is
+///                  used up by the end of the operation.
+/// @param SeedSpace The space to start the alignment process with.
+/// @returns         A std::pair, whose first element is the aligned space,
+///                  whose second element is the vector of aligned piecewise
+///                  affines.
+static std::pair<__isl_give isl_space *, std::vector<__isl_give isl_pw_aff *>>
+alignPwAffs(const std::vector<__isl_take isl_pw_aff *> &&PwAffs,
+            __isl_take isl_space *SeedSpace) {
+  assert(SeedSpace && "Invalid seed space given.");
+
+  isl_space *AlignSpace = SeedSpace;
+  for (isl_pw_aff *PwAff : PwAffs) {
+    isl_space *PwAffSpace = isl_pw_aff_get_domain_space(PwAff);
+    AlignSpace = isl_space_align_params(AlignSpace, PwAffSpace);
+  }
+  std::vector<isl_pw_aff *> AdjustedPwAffs;
+
+  for (unsigned i = 0; i < PwAffs.size(); i++) {
+    isl_pw_aff *Adjusted = PwAffs[i];
+    assert(Adjusted && "Invalid pw_aff given.");
+    Adjusted = isl_pw_aff_align_params(Adjusted, isl_space_copy(AlignSpace));
+    AdjustedPwAffs.push_back(Adjusted);
+  }
+  return std::make_pair(AlignSpace, AdjustedPwAffs);
+}
 
 namespace {
 class PPCGCodeGeneration : public ScopPass {
 public:
   static char ID;
 
   GPURuntime Runtime = GPURuntime::CUDA;
 
public:
   ///
   /// For the first dimension we derive the bound of the array from the extent
   /// of this dimension. For inner dimensions we obtain their size directly from
   /// ScopArrayInfo.
   ///
   /// @param PPCGArray The array to compute bounds for.
   /// @param Array The polly array from which to take the information.
   void setArrayBounds(gpu_array_info &PPCGArray, ScopArrayInfo *Array) {
-    isl_pw_aff_list *BoundsList =
-        isl_pw_aff_list_alloc(S->getIslCtx(), PPCGArray.n_index);
-    std::vector<isl::pw_aff> PwAffs;
-
-    isl_space *AlignSpace = S->getParamSpace();
-    AlignSpace = isl_space_add_dims(AlignSpace, isl_dim_set, 1);
+    std::vector<isl_pw_aff *> Bounds;
 
     if (PPCGArray.n_index > 0) {
       if (isl_set_is_empty(PPCGArray.extent)) {
         isl_set *Dom = isl_set_copy(PPCGArray.extent);
         isl_local_space *LS = isl_local_space_from_space(
             isl_space_params(isl_set_get_space(Dom)));
         isl_set_free(Dom);
         isl_pw_aff *Zero = isl_pw_aff_from_aff(isl_aff_zero_on_domain(LS));
-        Zero = isl_pw_aff_align_params(Zero, isl_space_copy(AlignSpace));
-        PwAffs.push_back(isl::manage(isl_pw_aff_copy(Zero)));
-        BoundsList = isl_pw_aff_list_insert(BoundsList, 0, Zero);
+        Bounds.push_back(Zero);
       } else {
         isl_set *Dom = isl_set_copy(PPCGArray.extent);
         Dom = isl_set_project_out(Dom, isl_dim_set, 1, PPCGArray.n_index - 1);
         isl_pw_aff *Bound = isl_set_dim_max(isl_set_copy(Dom), 0);
         isl_set_free(Dom);
         Dom = isl_pw_aff_domain(isl_pw_aff_copy(Bound));
         isl_local_space *LS =
             isl_local_space_from_space(isl_set_get_space(Dom));
         isl_aff *One = isl_aff_zero_on_domain(LS);
         One = isl_aff_add_constant_si(One, 1);
         Bound = isl_pw_aff_add(Bound, isl_pw_aff_alloc(Dom, One));
         Bound = isl_pw_aff_gist(Bound, S->getContext());
-        Bound = isl_pw_aff_align_params(Bound, isl_space_copy(AlignSpace));
-        PwAffs.push_back(isl::manage(isl_pw_aff_copy(Bound)));
-        BoundsList = isl_pw_aff_list_insert(BoundsList, 0, Bound);
+        Bounds.push_back(Bound);
       }
     }
 
     for (unsigned i = 1; i < PPCGArray.n_index; ++i) {
       isl_pw_aff *Bound = Array->getDimensionSizePw(i).release();
       auto LS = isl_pw_aff_get_domain_space(Bound);
       auto Aff = isl_multi_aff_zero(LS);
       Bound = isl_pw_aff_pullback_multi_aff(Bound, Aff);
-      Bound = isl_pw_aff_align_params(Bound, isl_space_copy(AlignSpace));
-      PwAffs.push_back(isl::manage(isl_pw_aff_copy(Bound)));
-      BoundsList = isl_pw_aff_list_insert(BoundsList, i, Bound);
+      Bounds.push_back(Bound);
     }
 
-    isl_space_free(AlignSpace);
+    /// To construct a `isl_multi_pw_aff`, we need all the indivisual `pw_aff`
+    /// to have the same parameter dimensions. So, we need to align them to an
+    /// appropriate space.
+    /// Scop::Context is _not_ an appropriate space, because when we have
+    /// `-polly-ignore-parameter-bounds` enabled, the Scop::Context does not
+    /// contain all parameter dimensions.
+    /// So, use the helper `alignPwAffs` to align all the `isl_pw_aff` together.
+    isl_space *SeedAlignSpace = S->getParamSpace();
+    SeedAlignSpace = isl_space_add_dims(SeedAlignSpace, isl_dim_set, 1);
+
+    isl_space *AlignSpace = nullptr;
+    std::vector<isl_pw_aff *> AlignedBounds;
+    std::tie(AlignSpace, AlignedBounds) =
+        alignPwAffs(std::move(Bounds), SeedAlignSpace);
+
+    assert(AlignSpace && "alignPwAffs did not initialise AlignSpace");
+
+    isl_pw_aff_list *BoundsList =
+        createPwAffList(S->getIslCtx(), std::move(AlignedBounds));
+
     isl_space *BoundsSpace = isl_set_get_space(PPCGArray.extent);
+    BoundsSpace = isl_space_align_params(BoundsSpace, AlignSpace);
 
     assert(BoundsSpace && "Unable to access space of array.");
     assert(BoundsList && "Unable to access list of bounds.");
 
     PPCGArray.bound =
         isl_multi_pw_aff_from_pw_aff_list(BoundsSpace, BoundsList);
     assert(PPCGArray.bound && "PPCGArray.bound was not constructed correctly.");
   }
 
   /// Create the arrays for @p PPCGProg.
   ///
   /// @param PPCGProg The program to compute the arrays for.
   void createArrays(gpu_prog *PPCGProg,
                     const SmallVector<ScopArrayInfo *, 4> &ValidSAIs) {
     int i = 0;
     for (auto &Array : ValidSAIs) {
       std::string TypeName;

test/GPGPU/bounds-construction-with-ignore-param-bounds.ll

+; RUN: opt %loadPolly -S -polly-codegen-ppcg \
+; RUN: -polly-ignore-parameter-bounds \
+; RUN: -polly-invariant-load-hoisting < %s| FileCheck %s -check-prefix=HOST-IR
+
+; When we have `-polly-ignore-parameter-bounds`, `Scop::Context` does not contain
+; all the parameters present in the program.
+;
+; The construction of the `isl_multi_pw_aff` requires all the indivisual `pw_aff`
+; to have the same parameter dimensions. To achieve this, we used to realign
+; every `pw_aff` with `Scop::Context`. However, in conjunction with
+; `-polly-ignore-parameter-bounds`, this is now incorrect, since `Scop::Context`
+; does not contain all parameters.
+;
+; We check that Polly does the right thing in this case and sets up the parameter
+; dimensions correctly.
+
+
+; Check that kernel launch is generated in host IR.
+; the declare would not be generated unless a call to a kernel exists.
+; HOST-IR: declare void @polly_launchKernel(i8*, i32, i32, i32, i32, i32, i8*)
+; ModuleID = 'test/GPGPU/bounds-construction-with-ignore-param-bounds.ll'
+
+; C pseudocode
+; ------------
+; void f(int *arr, long niters, long stride) {
+;     for(int i = 0; i < niters; i++) {
+;       arr[i * stride] = 1;
+;     }
+; }
+
+target datalayout = "e-p:64:64:64-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f16:16:16-f32:32:32-f64:64:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nounwind uwtable
+define void @f(i32 *%arr, i64 %niters, i64 %stride) unnamed_addr #1 {
+entry:
+  br label %loop
+
+loop:                                             ; preds = %loop, %entry
+  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %loop ]
+  %idx = mul nuw nsw i64 %indvar, %stride
+  %slot = getelementptr i32, i32* %arr, i64 %idx
+  store i32 1, i32* %slot, align 4
+  %indvar.next = add nuw nsw i64 %indvar, 1
+  %check = icmp sgt i64 %indvar.next, %niters
+  br i1 %check, label %exit, label %loop
+
+exit:                                             ; preds = %loop
+  ret void
+}
+
+attributes #0 = { nounwind }
+attributes #1 = { nounwind uwtable }