# Iteration-space Pruning

Variable Iteration Space Pruning (VI-Prune) prunes the iteration space of a loop using information about the sparse computation. The iteration space for sparse codes can be considerably smaller than that for dense codes, since the computation needs to only consider iterations with nonzeros. The inspection stage of Sympiler generates an inspection set that enables transforming the unoptimized sparse code to a code with a reduced iteration space.

## Transformation

The VI-Prune transformation can be applied at a particular loop-level to
the sparse code to transform it as shown below. The loop that should be pruned
is annotated with `PRUNE`

internally. In the transformed code the
iteration space is pruned to `pruneSetSize`

, which is the inspection set size.
In addition to the new loop, all references to Ik (the loop index before
transformation) are replaced by its corresponding value from the inspection set,
pruneSet[Ik].

```
/// Input code (as an internal AST)
for(I1){
.
.
Prune: for(Ik < m) {
.
.
for(In (Ik , ..., In−1)) {
a[idx(I1,...,Ik ,...,In )];
}
}
}
```

```
/// After applying the VI-Prune transformation
for(I1){
.
.
for(Ik < pruneSetSize) {
J = pruneSet[Ik];
.
.
for(In (J,..., In−1)) {
a[idx(I1,...,J,...,In )];
}
}
}
```

## Inspector

In the VI-Prune inspector, the dependency graph of the loop is
traversed using depth-first search (DFS) to determine the new pruned
iteration space, i.e. `pruneSet`

and `pruneSetSize`

. The dependence
graph computation can be either done with code analysis or using domain
information. Sympiler uses domain information, such as knowing the
sparse method, to create the dependence graph.

More information and examples are available from here