[llvm-dev] Finding label of basic block where a conditional branch merges

[Cranmer, Joshua via llvm-dev]

If I'm understanding your ask correctly, you want every value whose execution or non-execution was controlled by a condition. This isn't quite standard control-dependence, but you would want a variant of an algorithm to compute the set of basic blocks that are control-dependent on a value. (Contrary to what David Greene suggests, postdominance frontier is not the best way to compute that property--that is the set of values a basic block is control-dependent on, which is the inverse of the desired relation). Standard control-dependence is defined as a basic block postdominating a successor but not the basic block itself. You want to also consider basic blocks that don't necessarily postdominate a successor--essentially, you're looking for nodes which are on a path from the source basic block to the immediate postdominator.

Honestly, the best algorithm to use here would be to do a standard DFS traversal starting from the node with the condition, breaking off the traversal if it reaches the immediate postdominator.

-----Original Message-----
From: llvm-dev [mailto:llvm-dev-bounces at lists.llvm.org] On Behalf Of David Greene via llvm-dev
Sent: Tuesday, January 29, 2019 17:39
To: Sebastian Roland <seroland86 at gmail.com>
Cc: llvm-dev at lists.llvm.org
Subject: Re: [llvm-dev] Finding label of basic block where a conditional branch merges

Sebastian Roland via llvm-dev <llvm-dev at lists.llvm.org> writes:

> Joshua, David
>
> much appreciate your quick help!
>
> What I am actually doing is statically tracing values. If one of the 
> traced values is part of a condition (e.g. in an if statement) all 
> instructions in the then and else part are also traced. The automatic 
> tracing of instructions however needs to stop when I hit the first 
> instruction after the if statement (same for switch).
>
> Dominators seem to be a good starting point!

It sounds like you're looking for a control dependence analysis (which Instructions/BasicBlocks are dependent on the outcome of some branch and thus on the value input into the branch).  That can be computed from the "post-dominance frontier" of the graph (https://en.wikipedia.org/wiki/Data_dependency#Control_Dependency).  I don't think LLVM has a post-dominance frontier built-in, but it has a regular ol' DominanceFrontier.  It should be possible to adapt that to do what you want.

Good luck!

                                -David
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev