[Polly] fixed test cases after removing immediate dominator heuristic for error block detection.

[chelini]

Summary

This patch removes the heuristic in

• Polly :: lib/Support/ScopHelper.cpp

The heuristic forces blocks that directly follow a loop header to not to be considered error blocks.
It was introduced in r249611 with the following commit message:

This replaces the support for user defined error functions by a
heuristic that tries to determine if a call to a non-pure function
should be considered "an error". If so the block is assumed not to be
executed at runtime. While treating all non-pure function calls as
errors will allow a lot more regions to be analyzed, it will also
cause us to dismiss a lot again due to an infeasible runtime context.
This patch tries to limit that effect. A non-pure function call is
considered an error if it is executed only in conditionally with
regards to a cheap but simple heuristic.

In the code below CCK_Abort2() would be considered as an error block, but not CCK_Abort1() due to this heuristic.

for (int i = 0; i < n; i+=1) {
  if (ErrorCondition1)
    CCK_Abort1(); // No __attribute__((noreturn))
  if (ErrorCondition2)
    CCK_Abort2(); // No __attribute__((noreturn))
}

This does not seem useful. Checking error conditions in the beginning of some work is quite common. It causes a switch default-case to be not considered an error block in SPEC's cactuBSSN. The comment justifying the heuristic mentions a "load", which does not seem to be applicable here. It has been proposed to remove the heuristic.

In addition, the patch fixes the following test cases:

• Polly :: ScopDetect/mod_ref_read_pointer.ll
• Polly :: ScopInfo/max-loop-depth.ll
• Polly :: ScopInfo/mod_ref_access_pointee_arguments.ll
• Polly :: ScopInfo/mod_ref_read_pointee_arguments.ll
• Polly :: ScopInfo/mod_ref_read_pointer.ll
• Polly :: ScopInfo/mod_ref_read_pointers.ll

The test cases failed after removing the heuristic.

[Meinersbur]

Could you add the removal of the heuristic to this patch? Thanks.

[chelini]

Added the removal of the heuristic in lib/Support/ScopHelper.cpp to the patch.

[Meinersbur]

Thanks for the update. Can you run make polly-update-format on it (there seems to be some trailing whitespace)? The buildbots check the source code formatting and "fail" if some irregularity is found.

For reviews in Polly:

1. Add "pollydev" and "llvm-commits" to the subscribers
2. Add the tag [Polly] in front of the title. (adding llvm-commits to subscribers triggers a mail to the corresponding mailing list. Adding the tag is useful s.t. one doesn't need to open the mail to see that it is a change in Polly)
3. Use "rPLO" for repository.

[chelini]

removed trailing whitespaces.

[chelini]

In D45274#1058592, @Meinersbur wrote:

Thanks for the update. Can you run make polly-update-format on it (there seems to be some trailing whitespace)? The buildbots check the source code formatting and "fail" if some irregularity is found.

For reviews in Polly:

1. Add "pollydev" and "llvm-commits" to the subscribers
2. Add the tag [Polly] in front of the title. (adding llvm-commits to subscribers triggers a mail to the corresponding mailing list. Adding the tag is useful s.t. one doesn't need to open the mail to see that it is a change in Polly)
3. Use "rPLO" for repository.

I addressed the review comments. "pollydev" and "llvm-commits" were already added as subscribers. Could you please double-check?

[Meinersbur]

LGTM. Good work!

Yes, llvm-commits and pollydev are subscribers (I actually didn't check by myself before, just added as a general node).

Do you have commit rights yet? If not, I can commit for you (with an annotation: "Contributed-by: Lorenzo Chelini").

[chelini]

In D45274#1060245, @Meinersbur wrote:

LGTM. Good work!

Yes, llvm-commits and pollydev are subscribers (I actually didn't check by myself before, just added as a general node).

Do you have commit rights yet? If not, I can commit for you (with an annotation: "Contributed-by: Lorenzo Chelini").

I just checked, I do not have the commit rights yet. Please commit it for me. Thanks.

lib/Support/ScopHelper.cpp

for (BasicBlock &I : *R.getEntry()->getParent())
         DominatesAllPredecessors = false;
   } else {
     for (auto Pred : predecessors(R.getExit()))
       if (R.contains(Pred) && !DT.dominates(&BB, Pred))
         DominatesAllPredecessors = false;
   }
 
   if (DominatesAllPredecessors)
-    return false;
+    return false; 
 
-  // FIXME: This is a simple heuristic to determine if the load is executed
-  //        in a conditional. However, we actually would need the control
-  //        condition, i.e., the post dominance frontier. Alternatively we
-  //        could walk up the dominance tree until we find a block that is
-  //        not post dominated by the load and check if it is a conditional
-  //        or a loop header.
-  auto *DTNode = DT.getNode(&BB);
-  if (!DTNode)
-    return false;
-
-  DTNode = DTNode->getIDom();
-
-  if (!DTNode)
-    return false;
-
-  auto *IDomBB = DTNode->getBlock();
-  if (LI.isLoopHeader(IDomBB))
-    return false;
-
   for (Instruction &Inst : BB)
     if (CallInst *CI = dyn_cast<CallInst>(&Inst)) {
       if (isIgnoredIntrinsic(CI))
         continue;
 
       // memset, memcpy and memmove are modeled intrinsics.
       if (isa<MemSetInst>(CI) || isa<MemTransferInst>(CI))
         continue;

test/ScopDetect/mod_ref_read_pointer.ll

 ; RUN: opt %loadPolly -basicaa -polly-detect -analyze \
 ; RUN:  -polly-allow-modref-calls < %s | FileCheck %s -check-prefix=MODREF
 ; RUN: opt %loadPolly -basicaa -polly-detect -analyze \
 ; RUN:  < %s | FileCheck %s
 ;
-; CHECK-NOT: Valid Region for Scop: for.cond => for.end
-; MODREF: Valid Region for Scop: for.cond => for.end
+; CHECK-NOT: Valid Region for Scop: for.body => for.end
+; MODREF: Valid Region for Scop: for.body => for.end
 ;
 ;    #pragma readonly
 ;    int func(int *A);
 ;
 ;    void jd(int *A) {
 ;      for (int i = 0; i < 1024; i++)
 ;        A[i + 2] = func(A);
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 declare i32 @func(i32* %A) #1
 
 define void @jd(i32* %A) {
 entry:
-  br label %for.cond
+  br label %for.body
 
-for.cond:                                         ; preds = %for.inc, %entry
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
-  %exitcond = icmp ne i64 %indvars.iv, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
+for.body:                                         ; preds = %entry, %for.inc
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ]
   %call = call i32 @func(i32* %A)
-  %tmp = add nsw i64 %indvars.iv, 2
+  %tmp = add nsw i64 %i, 2
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp
   store i32 %call, i32* %arrayidx, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  br label %for.cond
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond = icmp ne i64 %i.next, 1024
+  br i1 %exitcond, label %for.body, label %for.end
 
-for.end:                                          ; preds = %for.cond
+for.end:                                          ; preds = %for.inc
   ret void
 }
 
 attributes #1 = { nounwind readonly }

test/ScopInfo/max-loop-depth.ll

 ;
 ; Test to check that the scop only counts loop depth for loops fully contained
 ; in the scop.
 ; CHECK: Max Loop Depth: 1
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo(i32* %A, i32* %B, i64 %N, i64 %M) {
 entry:
-  br label %for.cond
+  %cmp1 = icmp slt i64 0, %M
+  br i1 %cmp1, label %for.body1, label %for.end1
 
-for.cond:                                         ; preds = %for.inc13, %entry
-  %j.0 = phi i64 [ 0, %entry ], [ %inc14, %for.inc13 ]
-  %cmp = icmp slt i64 %j.0, %M
-  br i1 %cmp, label %for.body, label %for.end15
-
-for.body:                                         ; preds = %for.cond
-  call void (...) @bar() #2
-  br label %for.cond1
-
-for.cond1:                                        ; preds = %for.inc, %for.body
-  %i.0 = phi i64 [ 0, %for.body ], [ %inc, %for.inc ]
-  %cmp2 = icmp slt i64 %i.0, %N
-  br i1 %cmp2, label %for.body3, label %for.end
-
-for.body3:                                        ; preds = %for.cond1
-  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.0
+  for.body1:                                         ; preds = %entry, %for.inc1
+    %j.0 = phi i64 [ 0, %entry ], [ %j.next, %for.inc1 ]
+    call void (...) @bar() #0
+    %cmp2 = icmp slt i64 0, %N
+    br i1 %cmp2, label %for.body2, label %for.end2
+
+  for.body2:                                        ; preds = %for.body1, %for.inc2
+    %i.1 = phi i64 [ 0, %for.body1 ], [ %i.next.1, %for.inc2 ]
+    %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i.1
     %tmp = load i32, i32* %arrayidx, align 4
     %add = add nsw i32 %tmp, 1
     store i32 %add, i32* %arrayidx, align 4
-  br label %for.inc
+    br label %for.inc2
 
-for.inc:                                          ; preds = %for.body3
-  %inc = add nuw nsw i64 %i.0, 1
-  br label %for.cond1
-
-for.end:                                          ; preds = %for.cond1
-  br label %for.cond5
-
-for.cond5:                                        ; preds = %for.inc10, %for.end
-  %i4.0 = phi i64 [ 0, %for.end ], [ %inc11, %for.inc10 ]
-  %cmp6 = icmp slt i64 %i4.0, %N
-  br i1 %cmp6, label %for.body7, label %for.end12
-
-for.body7:                                        ; preds = %for.cond5
-  %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %i4.0
-  %tmp1 = load i32, i32* %arrayidx8, align 4
-  %add9 = add nsw i32 %tmp1, 1
-  store i32 %add9, i32* %arrayidx8, align 4
-  br label %for.inc10
-
-for.inc10:                                        ; preds = %for.body7
-  %inc11 = add nuw nsw i64 %i4.0, 1
-  br label %for.cond5
-
-for.end12:                                        ; preds = %for.cond5
-  br label %for.inc13
-
-for.inc13:                                        ; preds = %for.end12
-  %inc14 = add nuw nsw i64 %j.0, 1
-  br label %for.cond
+  for.inc2:                                          ; preds = %for.body2
+    %i.next.1 = add nuw nsw i64 %i.1, 1
+    %cmp3 = icmp slt i64 %i.next.1, %N
+    br i1 %cmp3, label %for.body2, label %for.end2
+
+
+  for.end2:                                          ; preds = %for.inc2, %for.body1
+    %cmp4 = icmp slt i64 0, %N
+    br i1 %cmp4, label %for.body3, label %for.end3
+
+  for.body3:             ; preds = %for.end2
+    %i.2 = phi i64 [ 0, %for.end2 ], [ %i.next.2, %for.inc3 ]
+    %arrayidx1 = getelementptr inbounds i32, i32* %A, i64 %i.2
+    %tmp1 = load i32, i32* %arrayidx1, align 4
+    %add1 = add nsw i32 %tmp1, 1
+    store i32 %add1, i32* %arrayidx1, align 4
+    br label %for.inc3
+
+  for.inc3:           ; preds = %for.body3
+    %i.next.2 = add nuw nsw i64 %i.2, 1
+    %cmp5 = icmp slt i64 %i.next.2, %N
+    br i1 %cmp5, label %for.body3, label %for.end3
+
+  for.end3:           ; preds = %for.inc3, %for.end2
+    br label %for.inc1
+
+  for.inc1:           ; preds = %for.end3
+    %j.next = add nuw nsw i64 %j.0, 1
+    %cmp6 = icmp slt i64 %j.next, %M
+    br i1 %cmp6, label %for.body1, label %for.end1
 
-for.end15:                                        ; preds = %for.cond
+  for.end1:                                        ; preds = %entry, %for.inc1
     ret void
   }
 
-declare void @bar(...) #1
-
+declare void @bar(...) #0

test/ScopInfo/mod_ref_access_pointee_arguments.ll

 ;        A[i] = B[i];
 ;      }
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* noalias %A, i32* noalias %B) {
 entry:
-  br label %for.cond
+  br label %for.body
 
-for.cond:                                         ; preds = %for.inc, %entry
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
-  %exitcond = icmp ne i64 %indvars.iv, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
-  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+for.body:                                         ; preds = %entry, %for.inc
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i
+  %arrayidx1 = getelementptr inbounds i32, i32* %B, i64 %i
   %bc = bitcast i32* %arrayidx to i8*
   call void @f(i8* %bc, i32 1, i32 1, i32 1)
-  %tmp = load i32, i32* %arrayidx2
+  %tmp = load i32, i32* %arrayidx1
   store i32 %tmp, i32* %arrayidx, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  br label %for.cond
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond = icmp ne i64 %i.next, 1024
+  br i1 %exitcond, label %for.body, label %for.end
 
-for.end:                                          ; preds = %for.cond
+for.end:                                          ; preds = %for.inc
   ret void
 }
 
 declare void @f(i8*, i32, i32, i32) #0
 
 attributes #0 = { argmemonly nounwind }

test/ScopInfo/mod_ref_read_pointee_arguments.ll

 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* noalias %A, i32* noalias %B) gc "dummy" {
 entry:
   %dummyloc = alloca i8*
   br label %entry.split
 
-entry.split:
-  br label %for.cond
+entry.split:            ; preds = %entry
+  br label %for.body
 
-for.cond:                                         ; preds = %for.inc, %entry.split
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry.split ]
-  %exitcond = icmp ne i64 %indvars.iv, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
-  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
-  %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+for.body:                                         ; preds = %entry.split, %for.inc
+  %i = phi i64 [ 0, %entry.split ], [ %i.next, %for.inc ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %i
+  %arrayidx1 = getelementptr inbounds i32, i32* %B, i64 %i
   %bc = bitcast i32* %arrayidx to i8*
   %dummy = call i8* @f(i8* %bc, i8** null)
   store i8* %dummy, i8** %dummyloc, align 4
-  %tmp = load i32, i32* %arrayidx2
+  %tmp = load i32, i32* %arrayidx1
   store i32 %tmp, i32* %arrayidx, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  br label %for.cond
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond = icmp ne i64 %i.next, 1024
+  br i1 %exitcond, label %for.body, label %for.end
 
-for.end:                                          ; preds = %for.cond
+for.end:                                          ; preds = %for.inc
   ret void
 }
 
 declare i8* @f(i8*, i8**) #0
 
 attributes #0 = { argmemonly readonly nounwind }

test/ScopInfo/mod_ref_read_pointer.ll

 ;      for (int i = 0; i < 1024; i++)
 ;        A[i + 2] = func(A);
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* %A) {
 entry:
-  br label %for.cond
+  br label %for.body
 
-for.cond:                                         ; preds = %for.inc, %entry
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
-  %exitcond = icmp ne i64 %indvars.iv, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
+for.body:                                         ; preds = %entry, %for.inc
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ]
   %call = call i32 @func(i32* %A) #2
-  %tmp = add nsw i64 %indvars.iv, 2
+  %tmp = add nsw i64 %i, 2
   %arrayidx = getelementptr inbounds i32, i32* %A, i64 %tmp
   store i32 %call, i32* %arrayidx, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  br label %for.cond
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond = icmp ne i64 %i.next, 1024
+  br i1 %exitcond, label %for.body, label %for.end
 
-for.end:                                          ; preds = %for.cond
+for.end:                                          ; preds = %for.inc
   ret void
 }
 
-declare i32 @func(i32*) #1
+declare i32 @func(i32*) #0
 
-attributes #1 = { nounwind readonly }
+attributes #0 = { nounwind readonly }

test/ScopInfo/mod_ref_read_pointers.ll

 ;      for (int i = 0; i < 1024; i++)
 ;        A[i + 2] = func(A) + B[i];
 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32* noalias %A, i32* noalias %B) {
 entry:
-  br label %for.cond
+  br label %for.body
 
-for.cond:                                         ; preds = %for.inc, %entry
-  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
-  %exitcond = icmp ne i64 %indvars.iv, 1024
-  br i1 %exitcond, label %for.body, label %for.end
-
-for.body:                                         ; preds = %for.cond
+for.body:                                         ; preds = %entry, %for.inc
+  %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc ]
   %call = call i32 @func(i32* %A)
-  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %arrayidx = getelementptr inbounds i32, i32* %B, i64 %i
   %tmp = load i32, i32* %arrayidx, align 4
   %add = add nsw i32 %call, %tmp
-  %tmp2 = add nsw i64 %indvars.iv, 2
-  %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %tmp2
-  store i32 %add, i32* %arrayidx3, align 4
+  %tmp1 = add nsw i64 %i, 2
+  %arrayidx1 = getelementptr inbounds i32, i32* %A, i64 %tmp1
+  store i32 %add, i32* %arrayidx1, align 4
   br label %for.inc
 
 for.inc:                                          ; preds = %for.body
-  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
-  br label %for.cond
+  %i.next = add nuw nsw i64 %i, 1
+  %exitcond = icmp ne i64 %i.next, 1024
+  br i1 %exitcond, label %for.body, label %for.end
 
-for.end:                                          ; preds = %for.cond
+for.end:                                          ; preds = %for.inc
   ret void
 }
 
-declare i32 @func(i32*) #1
+declare i32 @func(i32*) #0
 
-attributes #1 = { nounwind readonly }
+attributes #0 = { nounwind readonly }