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

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190617/bd18bfb8/attachment.html>

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

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>