Program Analysis - Maple Help

 ProgramAnalysis

The ProgramAnalysis package is a new subpackage of the CodeTools package.  There are commands to analyze the data dependencies in for loops and to verify the correctness of while loops.

$\mathrm{with}\left(\mathrm{CodeTools}\left[\mathrm{ProgramAnalysis}\right]\right)$

 $\left[{\mathrm{CreateLoop}}{,}{\mathrm{DependenceCone}}{,}{\mathrm{GenerateProcedure}}{,}{\mathrm{IsLoopInvariant}}{,}{\mathrm{IterationSpace}}{,}{\mathrm{LoopInvariant}}{,}{\mathrm{TrajectoryPoints}}{,}{\mathrm{UnimodularTransformation}}{,}{\mathrm{VerifyLoop}}\right]$ (1)

For loops

For loops can be analyzed to determine their data dependencies and apply transformations to assist in their parallelization.  The commands support array indices that are polynomials with rational coefficients.  Here is an example of how a nested for loop can be transformed so that the inner loop can be parallelized:

The following procedure has dependencies across both the $i$ and the $j$ loop indices and cannot be easily parallelized in this form:

The dependencies in this loop cross both the $i$ and $j$ dimension, as can be seen in the equation of its dependence cone:

 $\left[{0}{\le }{\mathrm{dj}}{,}{\mathrm{dj}}{\le }{1}{,}{\mathrm{di}}{=}{1}{-}{\mathrm{dj}}\right]$ (1.1)

Applying a transformation to the loop will change the relationship between the data dependencies:

 $\left[\begin{array}{rr}{1}& {1}\\ {0}& {1}\end{array}\right]$ (1.2)

$\mathrm{GenerateProcedure}\left(\mathrm{transformed_loop}\right);$

 ${\mathbf{proc}}\left({A}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{local}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}{,}{j}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{i}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{2}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{6}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{for}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{j}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{from}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{max}}{}\left({1}{,}{i}{-}{3}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{to}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathrm{min}}{}\left({3}{,}{i}{-}{1}\right)\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{A}{[}{i}{-}{j}{,}{j}{]}{:=}{A}{[}{−}{1}{+}{i}{-}{j}{,}{j}{]}{+}{A}{[}{i}{-}{j}{,}{j}{-}{1}{]}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end do}}{;}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{return}}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}{\mathbf{end proc}}$ (1.3)

This transformed loop no longer has a relationship between the dimensions its distance vectors:

 $\left[{\mathrm{dn}}{=}{1}{,}{0}{\le }{\mathrm{dm}}{,}{\mathrm{dm}}{\le }{1}\right]$ (1.4)

The data dependencies in the loop body only depend on previously computed elements.  The pattern for updating the array in the original and transformed loops are shown below.  The inner loop of the transformed program corresponds to the anti-diagonal lines of the array updates.  These updated operations can be performed simultaneously since they only refer to previously updated array entries (those entries that point toward a particular array entry).

 Original loop's array updates Transformed loop's array updates Legend Red dots: Data points in array Blue arrows: Read/write dependency between array entries Green dotted lines: Order in which elements of the array are updated



The set of array indices for all values of the loop's index variables can also be computed:

 $\left[{1}{\le }{i}{,}{i}{\le }{3}{,}{1}{\le }{j}{,}{j}{\le }{3}\right]$ (1.5)

$\mathrm{isolve}\left(\mathrm{convert}\left(\mathrm{ispace},\mathrm{set}\right)\right);$

 $\left\{{i}{=}{1}{,}{j}{=}{1}\right\}{,}\left\{{i}{=}{1}{,}{j}{=}{2}\right\}{,}\left\{{i}{=}{1}{,}{j}{=}{3}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{1}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{2}\right\}{,}\left\{{i}{=}{2}{,}{j}{=}{3}\right\}{,}\left\{{i}{=}{3}{,}{j}{=}{1}\right\}{,}\left\{{i}{=}{3}{,}{j}{=}{2}\right\}{,}\left\{{i}{=}{3}{,}{j}{=}{3}\right\}$ (1.6)



While Loops

The while loop related commands can be used to formally verify that a procedure meets its specification.  The invariants of a while loop can be computed and, when combined with the pre-condition and guard condition of the loop, used to verify whether or not the post-condition will be satisfied.  This verification indicates whether or not the $\mathrm{ASSERT}$ statement after the loop will always be true.  Loops whose assignments are polynomials with rational coefficients are supported.

The following example shows how the invariants of a while loop can be computed and used to verify that the following program is free from errors and meets its specification encoded in the last $\mathrm{ASSERT}$ statement of the procedure:

Create the WhileLoop data structure:

In this case, a loop invariant needs to be computed to formally verify the loop:

 ${2}{}{p}{}{r}{+}{{q}}^{{2}}{-}{a}{=}{0}$ (2.1)

The return value of $\mathrm{true}$ indicates that the procedure is guaranteed to meet its specification:

 ${\mathrm{true}}$ (2.2)