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

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/20190604/66ac16d0/attachment.html>

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/20190608/27cc4103/attachment.html>

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>