The VectorCilk transformer performs the block transformations described in our PLDI 2015 paper. It takes as input a recursive method (where the recursive calls are assumed to be independent) and produces three variants of the method:

  1. A breadth-first version of the code, which restructures the recursive method to execute the program in a level-by-level fashion, with all the tasks at a particular level of the computation tree grouped together into a block.
  2. A depth-first version of the code, which takes a block of tasks and executes that block in a depth-first, lock-step manner (so each task executes its left subtree to completion, then its right subtree).
  3. A reexpansion version, which toggles between the breadth-first version to generate work and the depth-first version to control block size

The VectorCilk transformer does not perform vectorization. Instead, it produces block-based implementations of the recursive program that contains dense, parallel loops of tasks that can be vectorized using traditional vectorization techniques.