[Polly] Remove read-only statements from the SCoP

lib/Analysis/ScopInfo.cpp

 
 void Scop::simplifySCoP(bool RemoveIgnoredStmts) {
   for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {
     ScopStmt &Stmt = *StmtIt;
     RegionNode *RN = Stmt.isRegionStmt()
                          ? Stmt.getRegion()->getNode()
                          : getRegion().getBBNode(Stmt.getBasicBlock());
 
-    if (StmtIt->isEmpty() ||
-        isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]) ||
-        (RemoveIgnoredStmts && isIgnored(RN))) {
+    bool RemoveStmt = StmtIt->isEmpty();
+    if (!RemoveStmt)
+      RemoveStmt = isl_set_is_empty(DomainMap[getRegionNodeBasicBlock(RN)]);
+    if (!RemoveStmt)
+      RemoveStmt = (RemoveIgnoredStmts && isIgnored(RN));
+
+    // Remove read only statements only after invariant loop hoisting.
+    if (!RemoveStmt && !RemoveIgnoredStmts) {
+      bool OnlyRead = true;
+      for (MemoryAccess *MA : Stmt) {
+        if (MA->isRead())
+          continue;
+
+        OnlyRead = false;
+        break;
+      }
+
+      RemoveStmt = OnlyRead;
+    }
 
+    if (RemoveStmt) {
       // Remove the statement because it is unnecessary.
       if (Stmt.isRegionStmt())
         for (BasicBlock *BB : Stmt.getRegion()->blocks())
           StmtMap.erase(BB);
       else
         StmtMap.erase(Stmt.getBasicBlock());
 
       StmtIt = Stmts.erase(StmtIt);

test/DependenceInfo/different_schedule_dimensions.ll

 ; RUN: opt -S %loadPolly -polly-dependences \
 ; RUN:                   -analyze < %s | FileCheck %s
 
 ; CHECK: RAW dependences:
 ; CHECK:   { Stmt_bb9[0] -> Stmt_bb10[0] }
 ; CHECK: WAR dependences:
-; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
-; CHECK: WAW dependences:
 ; CHECK:   {  }
+; CHECK: WAW dependences:
+; CHECK:   { Stmt_bb3[0] -> Stmt_bb10[0] }
 ; CHECK: Reduction dependences:
 ; CHECK:   {  }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @hoge(i32 %arg, [1024 x double]* %arg1) {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb
   br label %bb3
 
 bb3:                                              ; preds = %bb10, %bb2
   %tmp = phi i64 [ 0, %bb10 ], [ 0, %bb2 ]
   %tmp4 = icmp sgt i32 %arg, 0
   %tmp5 = getelementptr inbounds [1024 x double], [1024 x double]* %arg1, i64 0, i64 0
   %tmp6 = load double, double* %tmp5, align 8
   %tmp7 = fadd double undef, %tmp6
+  store double %tmp7, double* %tmp5, align 8
   br i1 false, label %bb8, label %bb9
 
 bb8:                                              ; preds = %bb3
   br label %bb10
 
 bb9:                                              ; preds = %bb3
   br label %bb10
 

test/ScopInfo/invariant-loads-leave-read-only-statements.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen -analyze < %s
+;
+;
+; CHECK:         Statements {
+; CHECK-NEXT:      Stmt_top_split
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> [0, 0, 0, 0] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_25[] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_top_split[] -> MemRef_26[] };
+; CHECK-NEXT:      Stmt_L_4
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] : i0 >= 0 and i0 <= -1 + p_0 and i1 >= 0 and i1 <= -1 + p_0 and i2 >= 0 and i2 <= -1 + p_0 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> [1, i0, i1, i2] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_25[] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_5[i2, i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_12[i2, i1] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [p_0, p_1, p_2] -> { Stmt_L_4[i0, i1, i2] -> MemRef_19[i1, i0] };
+; CHECK-NEXT:    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%jl_value_t = type { %jl_value_t* }
+
+define %jl_value_t* @julia_gemm_22583(%jl_value_t*, %jl_value_t**, i32) {
+top:
+  br label %top.split
+
+top.split:                                        ; preds = %top
+  %3 = load %jl_value_t*, %jl_value_t** %1, align 8
+  %4 = bitcast %jl_value_t* %3 to double**
+  %5 = load double*, double** %4, align 8
+  %6 = getelementptr inbounds %jl_value_t, %jl_value_t* %3, i64 3, i32 0
+  %7 = bitcast %jl_value_t** %6 to i64*
+  %8 = load i64, i64* %7, align 8
+  %9 = getelementptr %jl_value_t*, %jl_value_t** %1, i64 1
+  %10 = load %jl_value_t*, %jl_value_t** %9, align 8
+  %11 = bitcast %jl_value_t* %10 to double**
+  %12 = load double*, double** %11, align 8
+  %13 = getelementptr inbounds %jl_value_t, %jl_value_t* %10, i64 3, i32 0
+  %14 = bitcast %jl_value_t** %13 to i64*
+  %15 = load i64, i64* %14, align 8
+  %16 = getelementptr %jl_value_t*, %jl_value_t** %1, i64 2
+  %17 = load %jl_value_t*, %jl_value_t** %16, align 8
+  %18 = bitcast %jl_value_t* %17 to double**
+  %19 = load double*, double** %18, align 8
+  %20 = getelementptr inbounds %jl_value_t, %jl_value_t* %17, i64 3, i32 0
+  %21 = bitcast %jl_value_t** %20 to i64*
+  %22 = load i64, i64* %21, align 8
+  %23 = icmp sgt i64 %8, 0
+  %24 = select i1 %23, i64 %8, i64 0
+  %25 = add i64 %24, 1
+  %26 = icmp eq i64 %24, 0
+  br i1 %26, label %L.11, label %L.preheader
+
+L.preheader:                                      ; preds = %top.split
+  br label %L
+
+L:                                                ; preds = %L.preheader, %L.9
+  %"#s5.0" = phi i64 [ %27, %L.9 ], [ 1, %L.preheader ]
+  %27 = add i64 %"#s5.0", 1
+  br i1 %26, label %L.9, label %L.2.preheader
+
+L.2.preheader:                                    ; preds = %L
+  br label %L.2
+
+L.2:                                              ; preds = %L.2.preheader, %L.7
+  %"#s4.0" = phi i64 [ %28, %L.7 ], [ 1, %L.2.preheader ]
+  %28 = add i64 %"#s4.0", 1
+  br i1 %26, label %L.7, label %L.4.preheader
+
+L.4.preheader:                                    ; preds = %L.2
+  br label %L.4
+
+L.4:                                              ; preds = %L.4.preheader, %L.4
+  %"#s3.0" = phi i64 [ %29, %L.4 ], [ 1, %L.4.preheader ]
+  %29 = add i64 %"#s3.0", 1
+  %30 = add i64 %"#s5.0", -1
+  %31 = add i64 %"#s4.0", -1
+  %32 = mul i64 %31, %22
+  %33 = add i64 %32, %30
+  %34 = getelementptr double, double* %19, i64 %33
+  %35 = load double, double* %34, align 8
+  %36 = add i64 %"#s3.0", -1
+  %37 = mul i64 %36, %8
+  %38 = add i64 %37, %30
+  %39 = getelementptr double, double* %5, i64 %38
+  %40 = load double, double* %39, align 8
+  %41 = mul i64 %36, %15
+  %42 = add i64 %41, %31
+  %43 = getelementptr double, double* %12, i64 %42
+  %44 = load double, double* %43, align 8
+  %45 = fmul double %40, %44
+  %46 = fadd double %35, %45
+  store double %46, double* %34, align 8
+  %47 = icmp eq i64 %29, %25
+  br i1 %47, label %L.7.loopexit, label %L.4
+
+L.7.loopexit:                                     ; preds = %L.4
+  br label %L.7
+
+L.7:                                              ; preds = %L.7.loopexit, %L.2
+  %48 = icmp eq i64 %28, %25
+  br i1 %48, label %L.9.loopexit, label %L.2
+
+L.9.loopexit:                                     ; preds = %L.7
+  br label %L.9
+
+L.9:                                              ; preds = %L.9.loopexit, %L
+  %49 = icmp eq i64 %27, %25
+  br i1 %49, label %L.11.loopexit, label %L
+
+L.11.loopexit:                                    ; preds = %L.9
+  br label %L.11
+
+L.11:                                             ; preds = %L.11.loopexit, %top.split
+  ret %jl_value_t* inttoptr (i64 140220477440016 to %jl_value_t*)
+}

test/ScopInfo/read-only-statements.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check we remove read only statements.
+;
+; CHECK:         Statements {
+; CHECK-NEXT:      Stmt_for_body_2
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                { Stmt_for_body_2[i0] : i0 <= 99 and i0 >= 0 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                { Stmt_for_body_2[i0] -> [i0] };
+; CHECK-NEXT:            ReadAccess := [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body_2[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: +] [Scalar: 0]
+; CHECK-NEXT:                { Stmt_for_body_2[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:    }
+;
+;    int g(int);
+;    void f(int *A) {
+;      for (int i = 0; i < 100; i++) {
+;        (A[i]);
+;        /* Split BB */
+;        (A[i]);
+;        /* Split BB */
+;        A[i] += 1;
+;        /* Split BB */
+;        (A[i]);
+;        /* Split BB */
+;        (A[i]);
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 100
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp = load i32, i32* %arrayidx, align 4
+  br label %for.body.1
+
+for.body.1:
+  %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp1 = load i32, i32* %arrayidx2, align 4
+  br label %for.body.2
+
+for.body.2:
+  %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp2 = load i32, i32* %arrayidx5, align 4
+  %add = add nsw i32 %tmp2, 1
+  store i32 %add, i32* %arrayidx5, align 4
+  br label %for.body.3
+
+for.body.3:
+  %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32, i32* %arrayidx7, align 4
+  br label %for.body.4
+
+for.body.4:
+  %arrayidx10 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp4 = load i32, i32* %arrayidx10, 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
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}

test/ScopInfo/variant_base_pointer.ll

 entry:
   br label %if.end
 
 if.end:                                           ; preds = %entry
   %call = call i16** @__ctype_b_loc() #0
   %tmp = load i16*, i16** %call, align 8
   %arrayidx = getelementptr inbounds i16, i16* %tmp, i64 0
   %tmp1 = load i16, i16* %arrayidx, align 2
+  store i16 3, i16 *%arrayidx, align 2
   br i1 false, label %if.then.2, label %if.end.3
 
 if.then.2:                                        ; preds = %if.end
   br label %cleanup
 
 if.end.3:                                         ; preds = %if.end
   br label %cleanup
 
 cleanup:                                          ; preds = %if.end.3, %if.then.2
   ret void
 }
 
 ; Function Attrs: nounwind readnone
 declare i16** @__ctype_b_loc() #0
 
 attributes #0 = { nounwind readnone }