[Polly][Fix] Non i1 typed select condition for weird pw aff functions.

[jdoerfert]

Summary

In case the pieceweise affine function used to create an isl_ast_expr
had empty cases (e.g., with contradicting constraints on the
parameters), it was possible that the condition of the isl_ast_expr
select was not a comparison but a constant (thus of type i64).

This patch does two thing:
 1) Handle the case the condition of a select is not a i1 type like C.
 2) Try to simplify the pieceweise affine functions for the min/max
    access when we generate runtime alias checks. That step can often
    remove empty or redundant cases as well as redundant constrains.

This fixes bug: http://llvm.org/bugs/show_bug.cgi?id=21167

[grosser]

Nice patch! LGTM.

Tobias

http://llvm.org/bugs/show_bug.cgi?id=21167

You can reference bug reports with http://llvm.org/PR21167

test/Isl/CodeGen/test-invalid-operands-for-select-2.ll

3

If you could add a one sentence explanation of the bug, that would be great.

[jdoerfert]

Closed by commit rL219208 (authored by @jdoerfert).

lib/Analysis/ScopInfo.cpp

if (InvolvedParams > RunTimeChecksMaxParameters) {
       isl_set_free(Set);
       return -1;
     }
   }
 
   MinPMA = isl_set_lexmin_pw_multi_aff(isl_set_copy(Set));
   MaxPMA = isl_set_lexmax_pw_multi_aff(isl_set_copy(Set));
 
+  MinPMA = isl_pw_multi_aff_coalesce(MinPMA);
+  MaxPMA = isl_pw_multi_aff_coalesce(MaxPMA);
+
   // Adjust the last dimension of the maximal access by one as we want to
   // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
   // we test during code generation might now point after the end of the
   // allocated array but we will never dereference it anyway.
   assert(isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) &&
          "Assumed at least one output dimension");
   Pos = isl_pw_multi_aff_dim(MaxPMA, isl_dim_out) - 1;
   LastDimAff = isl_pw_multi_aff_get_pw_aff(MaxPMA, Pos);

lib/CodeGen/IslExprBuilder.cpp

 
 Value *IslExprBuilder::createOpSelect(__isl_take isl_ast_expr *Expr) {
   assert(isl_ast_expr_get_op_type(Expr) == isl_ast_op_select &&
          "Unsupported unary isl ast expression");
   Value *LHS, *RHS, *Cond;
   Type *MaxType = getType(Expr);
 
   Cond = create(isl_ast_expr_get_op_arg(Expr, 0));
+  if (!Cond->getType()->isIntegerTy(1))
+    Cond = Builder.CreateIsNotNull(Cond);
 
   LHS = create(isl_ast_expr_get_op_arg(Expr, 1));
   RHS = create(isl_ast_expr_get_op_arg(Expr, 2));
 
   MaxType = getWidestType(MaxType, LHS->getType());
   MaxType = getWidestType(MaxType, RHS->getType());
 
   if (MaxType != RHS->getType())

test/Isl/CodeGen/test-invalid-operands-for-select-2.ll

+; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl < %s | FileCheck %s
+;
+; Check that we do not crash as described here: http://llvm.org/bugs/show_bug.cgi?id=21167
+;
+; CHECK: polly.split_new_and_old
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @kernel_fdtd_apml(i32 %cxm, i32 %cym, [65 x [65 x double]]* %Bza, [65 x [65 x double]]* %Hz, double* %czp) #0 {
+entry:
+  br i1 false, label %for.cond4.preheader, label %for.end451
+
+for.cond4.preheader:                              ; preds = %for.inc449, %entry
+  %iz.08 = phi i32 [ undef, %for.inc449 ], [ 0, %entry ]
+  %cmp55 = icmp sgt i32 %cym, 0
+  br i1 %cmp55, label %for.cond7.preheader, label %for.inc449
+
+for.cond7.preheader:                              ; preds = %for.end, %for.cond4.preheader
+  %iy.06 = phi i32 [ %inc447, %for.end ], [ 0, %for.cond4.preheader ]
+  %cmp81 = icmp sgt i32 %cxm, 0
+  br i1 %cmp81, label %for.body9, label %for.end
+
+for.body9:                                        ; preds = %for.body9, %for.cond7.preheader
+  %ix.02 = phi i32 [ %inc, %for.body9 ], [ 0, %for.cond7.preheader ]
+  %idxprom74 = sext i32 %iz.08 to i64
+  %arrayidx75 = getelementptr inbounds double* %czp, i64 %idxprom74
+  %0 = load double* %arrayidx75, align 8
+  %idxprom102 = sext i32 %iz.08 to i64
+  %arrayidx105 = getelementptr inbounds [65 x [65 x double]]* %Hz, i64 %idxprom102, i64 0, i64 0
+  store double undef, double* %arrayidx105, align 8
+  %inc = add nsw i32 %ix.02, 1
+  br i1 false, label %for.body9, label %for.end
+
+for.end:                                          ; preds = %for.body9, %for.cond7.preheader
+  %idxprom209 = sext i32 %cxm to i64
+  %idxprom211 = sext i32 %iz.08 to i64
+  %arrayidx214 = getelementptr inbounds [65 x [65 x double]]* %Hz, i64 %idxprom211, i64 0, i64 %idxprom209
+  store double undef, double* %arrayidx214, align 8
+  %idxprom430 = sext i32 %cxm to i64
+  %idxprom431 = sext i32 %cym to i64
+  %idxprom432 = sext i32 %iz.08 to i64
+  %arrayidx435 = getelementptr inbounds [65 x [65 x double]]* %Hz, i64 %idxprom432, i64 %idxprom431, i64 %idxprom430
+  store double undef, double* %arrayidx435, align 8
+  %arrayidx445 = getelementptr inbounds [65 x [65 x double]]* %Bza, i64 0, i64 0, i64 0
+  store double undef, double* %arrayidx445, align 8
+  %inc447 = add nsw i32 %iy.06, 1
+  %cmp5 = icmp slt i32 %inc447, %cym
+  br i1 %cmp5, label %for.cond7.preheader, label %for.inc449
+
+for.inc449:                                       ; preds = %for.end, %for.cond4.preheader
+  br i1 undef, label %for.cond4.preheader, label %for.end451
+
+for.end451:                                       ; preds = %for.inc449, %entry
+  ret void
+}

test/Isl/CodeGen/test-invalid-operands-for-select.ll

+; RUN: opt %loadPolly -S -polly-code-generator=isl -polly-codegen-isl -polly-codegen-scev < %s | FileCheck %s
+;
+; Check that we do not crash as described here: http://llvm.org/bugs/show_bug.cgi?id=21167
+;
+; CHECK: polly.split_new_and_old
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @dradb4(i32 %ido, i32 %l1, float* %cc, float* %ch, float* %wa1, float* %wa3) #0 {
+entry:
+  %mul = mul nsw i32 %l1, %ido
+  br i1 undef, label %for.end256, label %if.end
+
+if.end:                                           ; preds = %entry
+  br i1 undef, label %L105, label %for.cond45.preheader
+
+for.cond45.preheader:                             ; preds = %if.end
+  br i1 undef, label %for.body47, label %for.end198
+
+for.body47:                                       ; preds = %for.inc196, %for.cond45.preheader
+  br i1 undef, label %for.body53.lr.ph, label %for.inc196
+
+for.body53.lr.ph:                                 ; preds = %for.body47
+  br label %for.body53
+
+for.body53:                                       ; preds = %for.body53, %for.body53.lr.ph
+  %t7.014 = phi i32 [ 0, %for.body53.lr.ph ], [ %add58, %for.body53 ]
+  %i.013 = phi i32 [ 2, %for.body53.lr.ph ], [ %add193, %for.body53 ]
+  %add58 = add nsw i32 %t7.014, 2
+  %arrayidx70 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx72 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx77 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx81 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx84 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx95 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx105 = getelementptr inbounds float* %cc, i64 0
+  %arrayidx110 = getelementptr inbounds float* %ch, i64 0
+  store float undef, float* %arrayidx110, align 4
+  %arrayidx122 = getelementptr inbounds float* %wa1, i64 0
+  %add129 = add nsw i32 %add58, %mul
+  %idxprom142 = sext i32 %add129 to i64
+  %arrayidx143 = getelementptr inbounds float* %ch, i64 %idxprom142
+  store float undef, float* %arrayidx143, align 4
+  %add153 = add nsw i32 %add129, %mul
+  %arrayidx170 = getelementptr inbounds float* %wa3, i64 0
+  %arrayidx174 = getelementptr inbounds float* %wa3, i64 0
+  %add177 = add nsw i32 %add153, %mul
+  %sub178 = add nsw i32 %add177, -1
+  %idxprom179 = sext i32 %sub178 to i64
+  %arrayidx180 = getelementptr inbounds float* %ch, i64 %idxprom179
+  store float undef, float* %arrayidx180, align 4
+  %arrayidx183 = getelementptr inbounds float* %wa3, i64 0
+  %0 = load float* %arrayidx183, align 4
+  %mul184 = fmul float undef, %0
+  %add189 = fadd float %mul184, 0.000000e+00
+  %idxprom190 = sext i32 %add177 to i64
+  %arrayidx191 = getelementptr inbounds float* %ch, i64 %idxprom190
+  store float %add189, float* %arrayidx191, align 4
+  %add193 = add nsw i32 %i.013, 2
+  %cmp52 = icmp slt i32 %add193, %ido
+  br i1 %cmp52, label %for.body53, label %for.inc196
+
+for.inc196:                                       ; preds = %for.body53, %for.body47
+  br i1 undef, label %for.body47, label %for.end198
+
+for.end198:                                       ; preds = %for.inc196, %for.cond45.preheader
+  br i1 false, label %for.end256, label %L105
+
+L105:                                             ; preds = %for.end198, %if.end
+  br label %for.end256
+
+for.end256:                                       ; preds = %L105, %for.end198, %entry
+  ret void
+}