Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Handle duplication of for-loop structures #58

Open
kumasento opened this issue Nov 7, 2020 · 1 comment
Open

Handle duplication of for-loop structures #58

kumasento opened this issue Nov 7, 2020 · 1 comment
Labels
bug Something isn't working

Comments

@kumasento
Copy link
Owner

Sometimes Pluto may generate a Scop like this:

<OpenScop>

# =============================================== Global
# Language
C

# Context
CONTEXT
2 4 0 0 0 2
# e/i| P0   P1 |  1  
   1    1    0   -1    ## P0-1 >= 0
   1    0    1   -1    ## P1-1 >= 0

# Parameters are provided
1
<strings>
P0 P1
</strings>

# Number of statements
2

# =============================================== Statement 1
# Number of relations describing the statement:
4

# ----------------------------------------------  1.1 Domain
DOMAIN
6 7 3 0 0 2
# e/i| fk0  fk1  i0 | P0   P1 |  1  
   1    0    0    1    0    0    0    ## i0 >= 0
   1    0    0   -1    1    0   -1    ## -i0+P0-1 >= 0
   1  -32    0    1    0    0    0    ## -32*fk0+i0 >= 0
   1   32    0   -1    0    0   31    ## 32*fk0-i0+31 >= 0
   1    0  -32    0    0    0    0    ## -32*fk1 >= 0
   1    0   32    0    0    0   31    ## 32*fk1+31 >= 0

# ----------------------------------------------  1.2 Scattering
SCATTERING
8 15 8 3 0 2
# e/i| c1   c2   c3   c4   c5   c6   c7   c8 | fk0  fk1  i0 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    0    0    0    0    0    0    0    ## c1 == 0
   0    0   -1    0    0    0    0    0    0    1    0    0    0    0    0    ## c2 == fk0
   0    0    0   -1    0    0    0    0    0    0    1    0    0    0    0    ## c3 == fk1
   0    0    0    0   -1    0    0    0    0    0    0    0    0    0    0    ## c4 == 0
   0    0    0    0    0   -1    0    0    0    0    0    1    0    0    0    ## c5 == i0
   0    0    0    0    0    0   -1    0    0    0    0    0    0    0    0    ## c6 == 0
   0    0    0    0    0    0    0   -1    0    0    0    0    0    0    0    ## c7 == 0
   0    0    0    0    0    0    0    0   -1    0    0    0    0    0    0    ## c8 == 0

# ----------------------------------------------  1.3 Access
WRITE
2 9 2 3 0 2
# e/i| Arr  [1]| fk0  fk1  i0 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    1    ## Arr == A1
   0    0   -1    0    0    1    0    0    0    ## [1] == i0

READ
2 9 2 3 0 2
# e/i| Arr  [1]| fk0  fk1  i0 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    2    ## Arr == A2
   0    0   -1    0    0    1    0    0    0    ## [1] == i0

# ----------------------------------------------  1.4 Statement Extensions
# Number of Statement Extensions
1
<body>
# Number of original iterators
3
# List of original iterators
fk0 fk1 i0
# Statement body expression
S0(A1, 1, A2, 1, i0)
</body>

# =============================================== Statement 2
# Number of relations describing the statement:
4

# ----------------------------------------------  2.1 Domain
DOMAIN
10 9 5 0 0 2
# e/i| fk0  fk1  fk2  i0   i1 | P0   P1 |  1  
   1    0    0    0    1    0    0    0    0    ## i0 >= 0
   1    0    0    0   -1    0    1    0   -1    ## -i0+P0-1 >= 0
   1    0    0    0    0    1    0    0    0    ## i1 >= 0
   1    0    0    0    0   -1    0    1   -1    ## -i1+P1-1 >= 0
   1  -32    0    0    1    0    0    0    0    ## -32*fk0+i0 >= 0
   1   32    0    0   -1    0    0    0   31    ## 32*fk0-i0+31 >= 0
   1    0  -32    0    0    0    0    0    1    ## -32*fk1+1 >= 0
   1    0   32    0    0    0    0    0   30    ## 32*fk1+30 >= 0
   1    0    0  -32    0    1    0    0    0    ## -32*fk2+i1 >= 0
   1    0    0   32    0   -1    0    0   31    ## 32*fk2-i1+31 >= 0

# ----------------------------------------------  2.2 Scattering
SCATTERING
8 17 8 5 0 2
# e/i| c1   c2   c3   c4   c5   c6   c7   c8 | fk0  fk1  fk2  i0   i1 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    0    0    0    0    0    0    0    0    0    ## c1 == 0
   0    0   -1    0    0    0    0    0    0    1    0    0    0    0    0    0    0    ## c2 == fk0
   0    0    0   -1    0    0    0    0    0    0    1    0    0    0    0    0    0    ## c3 == fk1
   0    0    0    0   -1    0    0    0    0    0    0    1    0    0    0    0    0    ## c4 == fk2
   0    0    0    0    0   -1    0    0    0    0    0    0    1    0    0    0    0    ## c5 == i0
   0    0    0    0    0    0   -1    0    0    0    0    0    0    0    0    0    1    ## c6 == 1
   0    0    0    0    0    0    0   -1    0    0    0    0    0    1    0    0    0    ## c7 == i1
   0    0    0    0    0    0    0    0   -1    0    0    0    0    0    0    0    0    ## c8 == 0

# ----------------------------------------------  2.3 Access
WRITE
3 12 3 5 0 2
# e/i| Arr  [1]  [2]| fk0  fk1  fk2  i0   i1 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    0    0    0    3    ## Arr == A3
   0    0   -1    0    0    0    0    1    0    0    0    0    ## [1] == i0
   0    0    0   -1    0    0    0    0    1    0    0    0    ## [2] == i1

READ
2 11 2 5 0 2
# e/i| Arr  [1]| fk0  fk1  fk2  i0   i1 | P0   P1 |  1  
   0   -1    0    0    0    0    0    0    0    0    1    ## Arr == A1
   0    0   -1    0    0    0    1    0    0    0    0    ## [1] == i0

# ----------------------------------------------  2.4 Statement Extensions
# Number of Statement Extensions
1
<body>
# Number of original iterators
5
# List of original iterators
fk0 fk1 fk2 i0 i1
# Statement body expression
S1(A3, 2, A1, 1, i0, i1)
</body>

# =============================================== Extensions
<arrays>
# Number of arrays
3
# Mapping array-identifiers/array-names
3 A3
2 A2
1 A1
</arrays>

<scatnames>
t1 t2 t3 t4 t5 t6 t7 t8
</scatnames>

<loop>
# Number of loops
2
# ===========================================
# Loop number 1 
# Iterator name
t2
# Number of stmts
2
# Statement identifiers
1
2
# Private variables
lbv, ubvt3,t4,t5,t6,t7,t8
# Directive
1
# ===========================================
# Loop number 2 
# Iterator name
t7
# Number of stmts
1
# Statement identifiers
2
# Private variables
(null)
# Directive
4
</loop>

</OpenScop>

When it is handled by CLooG, there might be duplicated loop structures that iterate the polyhedra. In that case, the same statement can exist at different places in the code. For different placement, they could have exactly the same naming for their loop IVs, however, if so, our code that generates MLIR from Scop cannot handle well since it relies the fact that IV names to be unique.

We might need to fundamentally change the design of the symbol table. Or maybe we need to add a new pass to make things easier to handle.

Also note that there are conflicts in the naming of the statements as well. For instance, one S1 can be different places of the code due to Pluto and CLooG.
@kumasento kumasento added the bug Something isn't working label Nov 7, 2020
@kumasento
Copy link
Owner Author

kumasento commented Nov 7, 2020 •
edited
Loading

One possible solution:

  • Update clast AST first to avoid conflicting iterator names. For instance, i will be renamed to i_2 if it appears the second time. All the subsequent statements that refer to this instance of i will be replaced its actual usage to i_2. In this way, we get a symbol table that contains all the unique instances of each IV.
  • One possible problem is that, even we update clast, the data stored in the body of user statement are not changed. We could update the body expression, e.g., from S0(i) to S0(i_2) if necessary, and leave the iterators field as it is. Such that we can figure out the mapping when finally processing the clast in ConvertFromOpenScop.
  • When inserting a caller/callee pair into the symbol table, we bind them with their corresponding IV instances. For instance, we will store the exact instance that S0(i) uses as its argument, which could be i, i_2, or i_3.
  • During the final op cloning stage, instead of building the mapping once and never update, we will update the mapping based on what IV instances that each statement binds to.

@kumasento kumasento mentioned this issue Nov 7, 2020
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@kumasento