llvm::isPotentiallyReachable() returned an incorrect result

LLVM Project
1

LLVM version: 14.0.0

target source code:

if (cd->compat_flag == true) {
    if (copy_from_user(&data_compat, argp,  // if.then.i189
        sizeof(data_compat))) {
        return -EFAULT;
    }
} else {
    if (copy_from_user(&data, argp,  // if.then.i
        sizeof(data))) {
        return -EFAULT;
    }
}

my code:

for (auto bb: bbs) {
    dbgs() << "[+] bb: " << bb->getName() << '\n';
    if (isPotentiallyReachable(bb, current_bb, nullptr, this->dom_tree, this->loopinfo)) {
        dbgs() << "[+] " << current_bb->getName() << " is reachable from " << bb->getName() << '\n';
        return false;
    }
}
dbgs() << "[+] " << current_bb->getName() << " is not reachable from all\n";
return true;

my log:

[+] current_bb: if.then.i
[+] bb: if.then.i189
[+] if.then.i is reachable from if.then.i189

I checked CFG and sure that if.then.i is not reachable from if.then.i189 but llvm::isPotentiallyReachable() returned an incorrect result:
image

Did I use it incorrectly? Or is there a problem with the implementation of the function itself? Is there any other function that can accomplish this?

2

Determine whether instruction ‘To’ is reachable from ‘From’, without passing through any blocks in ExclusionSet, returning true if uncertain.

Perhaps you hit the “uncertain” case (note the “Potentially” in the function name). Perhaps you hit the limit of BBs this function considers (your cfg looks quite convoluted). Try running with -dom-tree-reachability-max-bbs-to-explore set to some higher number (default is 32).

1 Like
3

Thanks for your reply. I added -dom-tree-reachability-max-bbs-to-explore=0 to opt and tried again. Now it’s OK:

[+] current_bb: if.then.i
[+] bb: if.then.i189
[+] if.then.i is not reachable from all

I found there is another function isReachable, can this function does the same thing? Which is better?

4

It depends on what you are using for. llvm::isPotentiallyReachable() should only be used if a conservative result is OK (as you noticed it may return true in some cases when they aren’t reachable). The reason llvm::isPotentiallyReachable() exists is to avoid excessive compile-time

1 Like
5

May I ask whether there is a function that can accurately determine whether there is path reachability between two Basicblocks based on the function CFG? If not, I will consider implementing such a function myself.