llvmcompiler-optimizationllvm-ir

I want to check if a call instruction is part of a control flow, say if(cond) call1 else call2 how do I check that?


I want to check if a call instruction is part of a control flow, say if(cond) call1 else call2, i want to check for each callsite CallBase object, if this callsite lies in a block that is in a conditional control flow, how do I check that?

define i32 @foo(i1 %condition) {
  entry:
    br i1 %condition, label %true_block, label %false_block

  true_block:
    %call_true = call i32 @bar()
    br label %exit_block

  false_block:
    %call_false = call i32 @baz()
    br label %exit_block

  exit_block:
    %result = phi i32 [ %call_true, %true_block ], [ %call_false, %false_block ]
    ret i32 %result
}

Here bar() and baz() are conditionally reached, so yes for those two call sites, but say if the entry had a call called foo() it would not be conditional.

Is there an API that can tell me this, if not what are the algorithmic steps I need to write to check it, I suspect I would need Dominator Information as well, I appreciate any help. Thanks!

I think, I need to evaluate the predecessor block's terminator, it should be condtional branch, and there must be only one predesessor, and that predesessor must dominate all of its successors, that is if, else.if and else.


Solution

  • This is difficult to do correctly. Allow me to outline the frustrating process of your failure (and if it sounds like I'm describing my own experience, that's because I've failed at things like this more than once):

    The code you want is called PostDominatorTree, and it answers the question "given this block, which other blocks are definitely executed after it?" You ask that question about the entry block and have your unconditional blocks. Doing that is easy, grepping the LLVM source for PostDominatorTree finds some code you can filch learn from. But then you add another unit test:

    a=1;
    while(a)
        b();
    c();
    

    b() is reachable and somehow unconditional but how do you solve this, now? Can it be solved? Maybe. You could try to move your pass later in the pass sequence, there may be a pass that simplifies the code so you get a branch straight into the body of the loop. Or you could try to do your own constant folding in order to detect the initial truth of the condition, that may be easier depending on your source language. If this all looks very difficult, add another test:

    while(somethingThatReturnsConstantTrue())
        a();
    b();
    

    b() definitely isn't called. And if your language uses exceptions:

    a();
    b();
    

    b() is conditional if the first call can throw an exception.

    At this point you may decide to tear all your hair out — or rewrite your problem statement to so that you're permitted to return true (or false) if you're in doubt about a call site. At this point you may be in luck, and the code you wrote using PostDominatorTree is all you need.