<div dir="ltr">Hi!<div><br></div><div>I am not sure what are you planning to do based on the AST, but you might want to look into the clang CFG and the ExprSequence class in clang-tidy [1]. They might prove useful for you.</div><div><br></div><div>Cheers,</div><div>Gabor</div><div><br></div><div>[1]: <a href="https://github.com/llvm/llvm-project/blob/master/clang-tools-extra/clang-tidy/utils/ExprSequence.h#L68">https://github.com/llvm/llvm-project/blob/master/clang-tools-extra/clang-tidy/utils/ExprSequence.h#L68</a></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jan 16, 2020 at 11:21 AM Fernandez, Matthew <<a href="mailto:matthew.fernandez@intel.com">matthew.fernandez@intel.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">The loop unrolling itself is not so much of a problem. However, I think the control flow in the body of the loop causes path explosion. A sample loop looks something like:<br>
<br>
    for (size_t i = 0; i < SOME_CONSTANT; i++) {<br>
      if (some condition) {<br>
        call_noreturn_function();<br>
      }<br>
    }<br>
<br>
However loop unrolling is a secondary problem to me (I have other work arounds for the target loops). I think the real problem is the branching structure. Much of the function looks like:<br>
<br>
    if (some condition)<br>
      call_noreturn_function1();<br>
<br>
    if (some other condition)<br>
      call_noreturn_function2();<br>
<br>
    ...<br>
<br>
Based on a quick eyeballing, there are roughly 20 such branches in the target function. Adding up the '&&' and '||' operators used in the branch conditions, there's about 30 of these, which no doubt compounds the problem. We are certainly talking about a lot of paths here and I anticipated I would need to do some optimization, but I was surprised that (a) I can't seem to tune how early analysis terminates and (b) there is no way for my checker to observe this. Wrt (a), analysis seems to give up after ~19 calculated branches, and given this is 2**19 paths maybe this is reasonable. Wrt (b) I can't find a callback or way to observe this truncation. I guess my checker could define a destructor that validates whether it ever saw the end of the function, but this seems pretty hacky.<br>
<br>
Given, as I mentioned, some of the properties I'm trying to check may be provable structurally, I'm going to try an AST visitor approach. Presumably this will scale far better than a path-sensitive analysis, but I was hoping I could leverage the path enumeration logic.<br>
<br>
> -----Original Message-----<br>
> From: Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" target="_blank">noqnoqneo@gmail.com</a>><br>
> Sent: Wednesday, January 15, 2020 16:09<br>
> To: Fernandez, Matthew <<a href="mailto:matthew.fernandez@intel.com" target="_blank">matthew.fernandez@intel.com</a>>; Gábor Horváth<br>
> <<a href="mailto:xazax@google.com" target="_blank">xazax@google.com</a>><br>
> Cc: <a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
> Subject: Re: [cfe-dev] exhaustiveness of CSA checkers<br>
> <br>
> Loop unrolling won't work on most loops if you don't remove the leashes in<br>
> Static Analyzer's LoopUnrolling.cpp that i mentioned before. We don't have<br>
> flags to control this yet (but i don't mind having some).<br>
> <br>
> Other than that, it works for me most of the time when i debug false<br>
> negatives. So your lack of success makes me curious about specifics. I might<br>
> have forgotten something or it might be that something really curious is going<br>
> on in your case.<br>
> <br>
> <br>
> On 1/16/20 2:17 AM, Fernandez, Matthew wrote:<br>
> > Thanks, Artem. Lots of useful flags. Unfortunately I have already<br>
> experimented with all of them though.<br>
> ><br>
> >> -----Original Message-----<br>
> >> From: Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" target="_blank">noqnoqneo@gmail.com</a>><br>
> >> Sent: Wednesday, January 15, 2020 14:36<br>
> >> To: Fernandez, Matthew <<a href="mailto:matthew.fernandez@intel.com" target="_blank">matthew.fernandez@intel.com</a>>; Gábor Horváth<br>
> >> <<a href="mailto:xazax@google.com" target="_blank">xazax@google.com</a>><br>
> >> Cc: <a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
> >> Subject: Re: [cfe-dev] exhaustiveness of CSA checkers<br>
> >><br>
> >> ...<br>
> >> and also removing the artificial heuristics for loop unrolling (that<br>
> >> attempt to discover whether the loop is statically bounded in<br>
> >> LoopUnrolling.cpp) ...<br>
<br>
</blockquote></div>