[llvm-dev] [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Mon Jun 17 08:29:53 PDT 2019

>
> This is used because the CFG used in LLVM changes all the time, right? If
> so, I don't see this being useful for us, since we don't mess with Clang's
> CFG much once it's built.
>
Yes, and IR doesn't have a clean interface for performing transformations
on graph edges/nodes. I'm not familiar with clang, but I was under
impression that the static analyzer doesn't transform the AST/CFG, so an
implementation of GraphDiff would always match the state of CFG, right?

On Mon, Jun 17, 2019 at 11:24 AM Kristóf Umann <dkszelethus at gmail.com>
wrote:

> Hi Jakub!
>
> On Mon, 17 Jun 2019 at 17:01, Jakub (Kuba) Kuderski <
> kubakuderski at gmail.com> wrote:
>
>> Hi Kristóf,
>>
>>
>>> 1. I read the article IDFCalculator is based on[1], but I found no
>>> references to IDFCalculator::setLiveInBlocks, and the file header seems to
>>> confirm that it's an implementation specific thing. Could I get away
>>> restricting the clang::CFG tailored version to not contain this function?
>>>
>> What's stopping you from implementing it for clang CFG? I looked at the
>> code and it seems like your new implementation handles it.
>>
>
> The link I sent is a diff of two branches, and I changed a lot of code
> yesterday. Initally, I "bruteforced" my way through generalizing GraphDiff
> and related classes, and that patch looked anything but appealing.
>
> Thanks for your comments by the way, to this and the related patches!
>
>
>> 2. I didn't really manage to understand the logic for GraphDiff. What
>>> does it really do in IDFCalculator's context? I dag out the patch[2] that
>>> added an extra constructor to use a snapshot of the CFG, but it seems to be
>>> unused. Is it also unlikely that we find any use for this? Mind you, the
>>> patch size grew a lot because I also "templatized" GraphDiff and all
>>> related classes to handle clang's CFG.
>>>
>>
>> GraphDiff is just a wrapper that was created to represent intermediate
>> states of CFG updates based on fully updated IR. For example, you can have
>> a transformation that replaces all uses of a basic block with another basic
>> block in one operation, and yet you want to have a way to perform some
>> analysis as if the transformation happened one change at a time. This was,
>> at least originally, used for the incremental domtree updater and for
>> memssa. (+cc Alina, as she is most familiar with GraphDiff)
>>
>
> This is used because the CFG used in LLVM changes all the time, right? If
> so, I don't see this being useful for us, since we don't mess with Clang's
> CFG much once it's built.
>
>
>> I'd separate out a base of IDFCalculator, to a new class called
>>> IDFCalculatorBase that wouldn't contain either of said functions.
>>>
>> If #2 if a lot of work/code, I'd say that separating it doesn't sound
>> that bad. It's not that complicated, then I wouldn't split it.
>>
>>
>> On Sun, Jun 16, 2019 at 10:56 AM Kristóf Umann <dkszelethus at gmail.com>
>> wrote:
>>
>>> A polite ping, could someone please share a thought about this?
>>>
>>> On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <dkszelethus at gmail.com>
>>> wrote:
>>>
>>>> A polite ping on this matter :)
>>>>
>>>> On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <dkszelethus at gmail.com>
>>>> wrote:
>>>>
>>>>> Hi!
>>>>>
>>>>> As the title suggests, I'd like to generalize llvm::IDFCalculator to
>>>>> be able to calculate control dependencies on clang's CFG. The issue is
>>>>> however, that many data structures it uses are "hardcoded" to use
>>>>> llvm::BasicBlock, and requires a lot of code to turn it into template
>>>>> arguments.
>>>>>
>>>>> I managed to pull this off by hammering the code until it compiled,
>>>>> and it works perfectly, but I'm not really happy with how the patch came
>>>>> out:
>>>>>
>>>>> https://github.com/Szelethus/llvm-project/compare/domtree_unittest...Szelethus:control_dependency?expand=1
>>>>>
>>>>> Sadly, my knowledge on LLVM IR and phi nodes in general is very
>>>>> limited. My questions are:
>>>>>
>>>>> 1. I read the article IDFCalculator is based on[1], but I found no
>>>>> references to IDFCalculator::setLiveInBlocks, and the file header seems to
>>>>> confirm that it's an implementation specific thing. Could I get away
>>>>> restricting the clang::CFG tailored version to not contain this function?
>>>>>
>>>>> 2. I didn't really manage to understand the logic for GraphDiff. What
>>>>> does it really do in IDFCalculator's context? I dag out the patch[2] that
>>>>> added an extra constructor to use a snapshot of the CFG, but it seems to be
>>>>> unused. Is it also unlikely that we find any use for this? Mind you, the
>>>>> patch size grew a lot because I also "templatized" GraphDiff and all
>>>>> related classes to handle clang's CFG.
>>>>>
>>>>> If the answer to both of these questions is "no", I'd separate out a
>>>>> base of IDFCalculator, to a new class called IDFCalculatorBase that
>>>>> wouldn't contain either of said functions.
>>>>>
>>>>> Cheers!
>>>>> Kristóf
>>>>>
>>>>>
>>>>> [1] Sreedhar, Vugranam C., and Guang R. Gao. "A linear time algorithm
>>>>> for placing ϕ-nodes." Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium
>>>>> on Principles of programming languages. ACM, 1995.
>>>>> [2] [IDF] Teach Iterated Dominance Frontier to use a snapshot CFG
>>>>> based on a GraphDiff. https://reviews.llvm.org/D50675
>>>>>
>>>>
>>
>> --
>> Jakub Kuderski
>>
>

-- 
Jakub Kuderski
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190617/b49423fc/attachment.html>