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

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

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.

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)

> 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/ddd4c097/attachment.html>

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>