[Polly] Avoid unnecessay .s2a write access when used only in PHIs

[Meinersbur]

Summary

Accesses for exit node phis will be handled separately by buildPHIAccesses if there is more than one exiting edge, buildScalarDependences does not need to create additional SCALAR accesses.

This is a corrected version of r250517, which was reverted in r250607.

[grosser]

Hi Michael,

this now LGTM. I just had one comment on how to possibly make this code more understandable.

Best,
Tobias

lib/Analysis/ScopInfo.cpp

3277

is A single exiting block

What are 'node PHIs'? Do you mean PHI nodes?

The last sentence is incomplete. It does not contain a verb in the main phrase.

It also took me a little while to understand this condition. I have the feeling moving this check into its own condition and elaborating a little more on why we bail out may make this more understandable. Does the following explain correctly what is going on? If it does, maybe you want to add some of this information to your final commit.

// Check for PHI nodes in the region exit and skip them, if they will be modeled
// as PHI nodes.
// 
// PHI nodes in the region exit that have more than two incoming edges need to
// be modeled as PHI-Nodes to correctly model the fact that depending on the
// control flow a different value will be assigned to the PHI node. In case this
// is the case, there is no need to create an additional normal scalar dependence.
// Hence bail out, before we register an "out-of-region" use for this definition.
if (isa<PHINode>(UI) && UI->getParent() == R->getExit() &&                    
    !R->getExitingBlock())                                                    
  continue;                                                                   
                                                                              
// Check whether or not the use is in the SCoP.                               
if (!R->contains(UseParent)) {                                                
  AnyCrossStmtUse = true;                                                     
  continue;                                                                   
}

[Meinersbur]

Use Tobias' more detailed comment.

lib/Analysis/ScopInfo.cpp

for (User *U : Inst->users()) {
     if (UseParent == ParentBB)
       continue;
 
     // Do not build scalar dependences inside a non-affine subregion.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
       continue;
 
     // Check whether or not the use is in the SCoP.
-    if (!R->contains(UseParent)) {
+    // If there is single exiting block, the single incoming value exit for node
+    // PHIs are handled like any escaping SCALAR. Otherwise, as if the PHI
+    // belongs to the the scop region.
+    bool IsExitNodePHI = isa<PHINode>(UI) && UI->getParent() == R->getExit();
+    if (!R->contains(UseParent) && (R->getExitingBlock() || !IsExitNodePHI)) {
       AnyCrossStmtUse = true;
       continue;
     }
 
     // If the instruction can be synthesized and the user is in the region
     // we do not need to add scalar dependences.
     if (canSynthesizeInst)
       continue;

test/ScopInfo/exit_phi_accesses-2.ll

+; RUN: opt %loadPolly -analyze -polly-scops %s | FileCheck %s
+
+; CHECK-LABEL: Function: foo
+; CHECK:       Statements {
+; CHECK-NEXT:      Stmt_body
+; CHECK-NEXT:          Domain :=
+; CHECK-NEXT:              { Stmt_body[i0] : i0 <= 100 and i0 >= 0 };
+; CHECK-NEXT:          Schedule :=
+; CHECK-NEXT:              { Stmt_body[i0] -> [i0] };
+; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:              { Stmt_body[i0] -> MemRef_sum__phi[] };
+; CHECK-NEXT:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:              { Stmt_body[i0] -> MemRef_sum__phi[] };
+; CHECK-NEXT:          ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:              { Stmt_body[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:              { Stmt_body[i0] -> MemRef_sum_next[] };
+; CHECK-NEXT:  }
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define float @foo(float* %A) {
+entry:
+  br label %header
+
+header:
+  fence seq_cst
+  br i1 true, label %body, label %exit
+
+body:
+  %i = phi i64 [ 0, %header ], [ %next, %body ]
+  %sum = phi float [ 0.0, %header ], [ %sum.next, %body ]
+  %arrayidx = getelementptr float, float* %A, i64 %i
+  %scalar = fadd float 0.0, 0.0
+  %next = add nuw nsw i64 %i, 1
+  %val = load float, float* %arrayidx
+  %sum.next = fadd float %sum, %val
+  %cond = icmp ne i64 %i, 100
+  br i1 %cond, label %body, label %after
+
+after:
+  br label %exit
+
+exit:
+  %phi = phi float [%sum.next, %after], [0.0, %header]
+  ret float %phi
+}

test/ScopInfo/exit_phi_accesses.ll

 ; RUN: opt %loadPolly -analyze -polly-scops %s | FileCheck %s
 
 ; Check that PHI nodes only create PHI access and nothing else (e.g. unnecessary
-; SCALAR accesses)In this case, for a PHI in the exit node, hence there is no
+; SCALAR accesses). In this case, for a PHI in the exit node, hence there is no
 ; PHI ReadAccess.
 
-; XFAIL: *
-
 ; CHECK-LABEL: Function: foo
 ; CHECK:       Statements {
 ; CHECK-NEXT:      Stmt_header
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_header[] };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_header[] -> [0, 0] };
 ; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_header[] -> MemRef_phi[] };
 ; CHECK-NEXT:      Stmt_body
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_body[i0] : i0 <= 100 and i0 >= 0 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_body[i0] -> [1, i0] };
 ; CHECK-NEXT:          MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_body[i0] -> MemRef_phi[] };
-; CHECK-NEXT:   }
+; CHECK-NEXT:  }
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define float @foo(float %sum, float* %A) {
 entry:
   br label %header
 
 header:

test/ScopInfo/read-only-scalar-used-in-phi.ll

 ; CHECK:       Domain :=
 ; CHECK:           { Stmt_bb1[i0] : i0 <= 100 and i0 >= 0 };
 ; CHECK:       Schedule :=
 ; CHECK:           { Stmt_bb1[i0] -> [1, i0] };
 ; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_phisum__phi[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_phisum__phi[] };
-; CHECK:       MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:           { Stmt_bb1[i0] -> MemRef_phisum[] };
 ; CHECK:       ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:           { Stmt_bb1[i0] -> MemRef_A[i0] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define float @foo(float %sum, float* %A) {
 bb:
   br label %next