[LLVMdev] Control dependence analysis?

[Mark Lacey]

On Tue, Dec 20, 2011 at 9:08 AM, John Criswell <criswell at illinois.edu> wrote:
> On 12/19/11 9:55 PM, Mark Lacey wrote:
>>
>> Does LLVM contain any control dependence analysis pass?
>
>
> There is a PostDominatorTree analysis.  Control-dependence can be computed
> easily using it (see the paper "Efficiently computing static single
> assignment form and the control dependence graph" by Cytron et. al. for
> details on the algorithm).

Yes, I am aware that I can use the post-dominance frontier to
determine whether a given block is dependent on another block. I am
looking for something a little different, e.g. what is described in
Optimal Control Dependence Computation and the Roman Chariots Problem,
which computes three sets:
1. The set of blocks control-dependent on a given edge
2. The set of edges that a given block is control-dependent on
3. The set of blocks having the same control dependence as a given
block (e.g. the set of control dependence equivalence classes).

I can compute (3) easily enough from the post-dominance frontiers. The
edge relationships are not as straightforward I think given that
either edge from a block A could lead to a block B that is dependent
on A, but B can be dependent on only one of those edges. The algorithm
in the above paper is nice given that you can choose the space and
time trade-offs explicitly.

Mark