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

[Kristóf Umann via llvm-dev]

On Mon, 17 Jun 2019 at 17:30, Jakub (Kuba) Kuderski <kubakuderski at gmail.com>
wrote:

> 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?
>

As I understand it, yes, we only observe the CFG, and do not change it once
its built (in fact, I'm not aware of any use of it other than the Static
Analyzer that does).

>
>
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/67a3e060/attachment-0001.html>