"Consecutive statements" in Static control Part(SCoP)

Question

Context:

I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.

Paper Citation:

Bastoul, Cédric & Cohen, Albert & Girbal, Sylvain & Sharma, Saurabh & Temam, Olivier. (2003). Putting Polyhedral Loop Transformations to Work. LNCS. 2958. 209-225. 10.1007/978-3-540-24644-2_14.

Problem Description:

From the paper; Page no: 6, Point: 3, 2nd paragraph

Let us now introduce the representation of a SCoP and its elementary transformations. A static control part within the syntax tree is a pair ( S , i_gp ), where S is the set of consecutive statements in their polyhedral representation and i_gp is the vector of global parameters of the SCoP. Vector i_gp is constant for the SCoP but statically unknown; yet its value is known at runtime, when entering the SCoP. d_gp = dim(i_gp ) denotes the number of global parameters.

( S , i_gp ): They specifically mentioned S is the set of consecutive statements.

Example case:

In my example code below, I have included three statements: S1, S2, and S3. Additionally, there are two parameters, N and M, and one constant, C.

for (int i = 0; i < N; i++) {
 A[i] = B[i] + C; // Statement 1
 D[i] = A[i] * E[i]; // Statement 2
 if (i < M) {
 F[i] = D[i] - G[i]; // Statement 3
 }
}

So my doubts are:

1. Are S1 and S2, which are consecutive and right after one another, the only members of set S?

2. If the answer to question 1 is NO, meaning all statements (S1, S2, S3) belong to the set S, then what is meant by 'consecutive' in this context?

3. In the code below, are all statements S1, S2, S3, and S4 part of the set S? If not, please could you let me know which statements are member of S?

   for (int i = 0; i < N; i++) {
    A[i] = B[i] + C; // Statement 1 in the outer loop
    for (int j = 0; j < M; j++) {
    D[i][j] = A[i] * E[j]; // Statement 2 in the inner loop
    if (j % 2 == 0) {
    F[i][j] = D[i][j] + C; // Statement 3 in the inner loop, conditional
    }
    }
    G[i] = A[i] - C; // Statement 4 in the outer loop
   }
   

• D.W.: I recommend that you edit your post to add a full citation to the paper you are referring to, so that others with a similar question about the paper can find this page via web search, and so that people can still tell what paper you are referring to even if the link stops working. Thank you!
• F.C. Akhi: @D.W. Thank you for pointing this out. I added the citation in my post. I hope I added the way you suggested.
• F.C. Akhi: @KennethKho, Thank you. I got another paper which is of the same title but, this paper has some more details in it. I am putting the link here inria.hal.science/inria-00071681/document
• F.C. Akhi: @KennethKho, I think the term "consecutive statements" within the context of SCoP might not mean that every statement is executed one right after the other without any control flow in between. Instead, it might refer to a sequence of statements that are part of a single SCOP. But, I am not sure
• Kenneth Kho: Thanks, the paper you provided in the comments is substantially the same for our purposes, so we will just ignore that. I agree with "it might refer to a sequence of statements that are part of a single SCOP." I would draw attention to Figure 1 "Example of decomposition into static control parts" and Section 2.1 "A static control part is called rich when it holds at least one non-empty loop; rich SCoPs are the natural candidates for polyhedral loop transformations." Therefore, S1, S2, S3, S4 are all part of S, since they are in a for loop is treated as a do loop, not while loop.

Answer 1

According to Section 2.1 in the paper provided:

Loops are normalized and split in two categories: loops from 0 to some bound expression with an integer stride, called do loops; other kinds of loops, referred to as while loops. A static control part (SCoP) is a maximal set of consecutive statements without while loops, where loop bounds and conditionals may only depend on invariants within this set of statements. These invariants include symbolic constants, formal function parameters and surrounding loop counters: they are called the global parameters of the SCoP, as well as any invariant appearing in some array subscript within the SCoP. A static control part is called rich when it holds at least one non-empty loop; rich SCoPs are the natural candidates for polyhedral loop transformations. We will only consider rich SCoPs in the following.

We conclude that in the first code snippet below, S1, S2, and S3 are part of the same non-rich SCoP, since the SCoP do not hold at least one non-empty loop.

for (int i = 0; i < N; i++) {
 A[i] = B[i] + C; // Statement 1
 D[i] = A[i] * E[i]; // Statement 2
 if (i < M) {
 F[i] = D[i] - G[i]; // Statement 3
 }
}

We conclude that in the second code snippet below, S1, S2, S3, and S4 are part of the same rich SCoP, since the SCoP holds at least one non-empty loop, a for inner loop which is considered of type do instead of while for our purposes.

for (int i = 0; i < N; i++) {
 A[i] = B[i] + C; // Statement 1 in the outer loop
 for (int j = 0; j < M; j++) {
 D[i][j] = A[i] * E[j]; // Statement 2 in the inner loop
 if (j % 2 == 0) {
 F[i][j] = D[i][j] + C; // Statement 3 in the inner loop, conditional
 }
 }
 G[i] = A[i] - C; // Statement 4 in the outer loop
}