Quasts

Each piecewise affine function is described by a quast (quasi affin selection tree), which is also used by PIP, to represent its solution. A quast is produced by the following grammar: 

                     solution        --> ( comment quastgroup )
                     quastgroup      --> quast
                     quast           --> ( list matrix ) 
                                         |( if vector quastgroup quastgroup )
                                         |()
                     matrix          --> vectorlist
                     vectorlist      --> vector vectorlist | void
                     vector          --> #[ coefficientlist ]
                     coefficientlist --> coeff coefficientlist | void
                     coefficient     --> INTEGER | INTEGER / INTEGER
Example: Given the following function 
			if j-n-6 >= 0
    				t(i,j) = i-1/2*j+1/2*n+2
			else
    				t(i,j) = i-1
the representation as quast yields: 
			( ( any comment )
			(if #[ 0 1 0 -1 -6 ]
			(list #[ 2/2 -1/2 0/2 1/2 4/2 ]
			)
			(list #[ 1 0 0 0 -1 ]
			)
			)
			)
where the additional information is needed, that the first two entries of each vector identify loop indices (i,j), the following two structure parameters (m,n) and the last one the constant part.

This gives the schedule of one statement.

File-Format

  1. the number of statements in the source program
  2. the number of loop indices in the whole program
  3. the number of structure parameters
After this the quast of each statement is given: Example: In the example above, we would get the following file assuming we have only one statement. 
			1
			2
			2
			1
			( ( Schedule for statement 1 )
			(if #[ 0 1 0 -1 -6 ]
			(list #[ 2/2 -1/2 0/2 1/2 4/2 ]
			)
			(list #[ 1 0 0 0 -1 ]
			)
			)
			)
			#
Andreas Dischinger