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

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Nathan Ridge via cfe-dev
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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev
A polite ping, could someone please share a thought about this?

On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <[hidden email]> wrote:
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev
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 <[hidden email]> wrote:
A polite ping, could someone please share a thought about this?

On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <[hidden email]> wrote:
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev
Hi Jakub!

On Mon, 17 Jun 2019 at 17:01, Jakub (Kuba) Kuderski <[hidden email]> 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 <[hidden email]> wrote:
A polite ping, could someone please share a thought about this?

On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <[hidden email]> wrote:
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev
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 <[hidden email]> wrote:
Hi Jakub!

On Mon, 17 Jun 2019 at 17:01, Jakub (Kuba) Kuderski <[hidden email]> 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 <[hidden email]> wrote:
A polite ping, could someone please share a thought about this?

On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <[hidden email]> wrote:
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [IDF][analyzer] Generalizing IDFCalculator to be used for Clang's CFG

Nathan Ridge via cfe-dev


On Mon, 17 Jun 2019 at 17:30, Jakub (Kuba) Kuderski <[hidden email]> 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 <[hidden email]> wrote:
Hi Jakub!

On Mon, 17 Jun 2019 at 17:01, Jakub (Kuba) Kuderski <[hidden email]> 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 <[hidden email]> wrote:
A polite ping, could someone please share a thought about this?

On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <[hidden email]> wrote:
A polite ping on this matter :)

On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <[hidden email]> 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

_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev