Visualization of Static Basic Block Versionning

Last year, we published a paper on Static Basic Block Versionning (SBBV) 1 . While very satisfied by the final version of the paper, I do not think we properly conveyed what the algorithm is actually doing under the hood. This is in great part due to the difficulty of showing the step-by-step inner working of SBBV without any kind of animated medium. At its core SBBV is a fully dynamic graph algorithm, with some suprising emerging behaviors.

In this blog post, I share a visualization tool for SBBV. I wish to show what the paper could not convey in the hope of guiding whoever wants to implement, improve, or simply understand SBBV.

If you are already familiar with basic block versionning and want to skip to the visualization tool, you can click here.

What is Static Basic Block Versionning?

Static Basic Block Versionning is an ahead-of-time optimization technique for dynamic languages. It takes in the control flow graph (CFG) of a program, or function, and a version limit (an integer). It outputs a specialized version of that CFG where some basic blocks have been duplicated in order to remove run time checks. The algorithm however ensures that no block is duplicated more than the version limit allows, preventing code bloat.

This specialization is achieved by performing a breadth-first traversal of the original CFG from its entry point. Initially, nothing is known about the run time context, but information is gathered as the traversal progresses. The example below shows the BLOCK #4, which branches to BLOCK #6 if r3 is an integer and BLOCK #7 otherwise. And so, we create versions of blocks #6 and #7 with these new contexts.

The information acquired about run time context allows the SBBV algorithm to specialize instructions of subsequent versions. The example below shows the specialized version of BLOCK #4 given a context where r3 is an int. This context allows removing the type check altogether from the resulting version.

This specialization process alone blissfully duplicates blocks for every new encountered context. In the best scenario, this leads to a code size explosion. In the worst case, this process never reaches a fixed point. The version limit is provided to prevent this.

On each iteration, the algorithm checks whether the dequeued block has more versions than allowed. Otherwise, some versions are merged to bring back the version count below the limit. Merging entails selecting excess versions, removing them from the graph and replacing them by a version whose context is the union of the merged versions. As for which versions to merge, we found that prioritizing the merge of similar versions works well in practice.

Once a version has been merged, it is permanently removed from the specialized CFG. This means that if the version is rediscovered through another path, it is immediately replaced by the result of its past merge. Otherwise, the algorithm may no longer converge as a new version may be infinitely rediscovered and merged.

This finally yields the algorithm for Static Basic Block Versionning:

SBBV(entryBlock, limit):
    queue = empty queue

    specialize(queue, entryBlock, empty context)

    while queue not empty:
        basicBlock, context = queue.dequeue()

        if |basicBlock.versions| > limit:
            excess = |basicBlock.versions| - limit

            merge (excess + 1) versions of basicBlock

            if context was merged:
                continue

        specialize(queue, basicBlock, context)

The SBBV algorithm is in essence quite simple: traverse, specialize, merge when needed. But a lot of its complexity lies in the fact that it is not traversing the original CFG, but rather the new specialized CFG as it is being constructed. Traversal of fully dynamic graphs involves some caveats.

When a merge takes place, any block that was accessible only through a path containing one of the merged blocks becomes unreachable. Consequently, the merge operator may remove whole subgraphs from the specialized CFG. Conversely, traversal may rediscover some of these unreachable blocks and add them back to the queue if needed.

It is this nonlocal effect of the merge operation that I initially wanted to visualize. As it turns out, I found the step-by-step visualization quite insightful, which led me to believe it would be worthwhile to share it here (hopefully, if you read to that point you will agree).

The visualization tool

The tool below executes Static Basic Block Versionnig step-by-step and shows the intermediate specialized control flow graph at each step. The first panel of each example contains the original CFG. The second panel contains the specialized CFG (initially empty, showing step 1).

• Navigate forward and backward through the execution of SBBV with the Reset, Back, Step and Complete buttons below the graph.

• Hover above a basic block to display its context.

• Change the version limit with the input in the bottom right corner of the SBBV panel.

• In the bottom left corner, a legend explains what events took place in the current step.

Examples use a factious dynamic language with simple types (int, float and array), and polymorphic operators with inlined type checks that closely ressembles the Bigloo and Gambit intermediate representations presented in the paper.

Example #1

This first example specializes a function that sums an array of numbers. This is a simple case where SBBV is well behaved due to very few merges taking place.

function sum(numbers):
    i = 0
    sum = 0

    while i < length(numbers):
        x = numbers[i]
        sum = sum + x
        i = i + 1

    return sum

In our factious language, the mixed arithmetic of an integer and a float returns a float. Notice how SBBV naturally generates a version of the loop for the case where sum is a float after the first iteration.

Original Control Flow Graph

Specialized Control Flow Graph

Example #2

This example specializes a function that checks that all numbers in an array are between low and high.

It demonstrates the impact of the merge heuristic. There are four sensible combinations of types for low and high. For version limits below 5 (a generic entry point is needed), this causes the algorithm to attempt to explore all four combinations, but to be rapidly steered toward one in particular by merging the others to a more generic version.

function inrange(numbers, low, high):
    i = 0

    while i < length(numbers):
        if low < numbers[i] < high:
            i = i + 1
            continue
        return 0
        
    return 1

Original Control Flow Graph

Specialized Control Flow Graph