<div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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.<br></blockquote><div>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? <br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jun 17, 2019 at 11:24 AM Kristóf Umann <<a href="mailto:dkszelethus@gmail.com">dkszelethus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr">Hi Jakub!</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 17 Jun 2019 at 17:01, Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com" target="_blank">kubakuderski@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div>Hi Kristóf,</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div>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?</div></blockquote><div>What's stopping you from implementing it for clang CFG? I looked at the code and it seems like your new implementation handles it.<br></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div>Thanks for your comments by the way, to this and the related patches!</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">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.<br></blockquote><div> </div>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)</div></div></blockquote><div><br></div><div>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.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I'd separate out a base of IDFCalculator, to a new class called IDFCalculatorBase that wouldn't contain either of said functions.<br></blockquote><div>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.<br><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Jun 16, 2019 at 10:56 AM Kristóf Umann <<a href="mailto:dkszelethus@gmail.com" target="_blank">dkszelethus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">A polite ping, could someone please share a thought about this?</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, 8 Jun 2019 at 21:21, Kristóf Umann <<a href="mailto:dkszelethus@gmail.com" target="_blank">dkszelethus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">A polite ping on this matter :)</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 4 Jun 2019 at 01:51, Kristóf Umann <<a href="mailto:dkszelethus@gmail.com" target="_blank">dkszelethus@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi!<div><br></div><div>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.</div><div><br></div><div>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:<br><a href="https://github.com/Szelethus/llvm-project/compare/domtree_unittest...Szelethus:control_dependency?expand=1" target="_blank">https://github.com/Szelethus/llvm-project/compare/domtree_unittest...Szelethus:control_dependency?expand=1</a></div><div><br></div><div>Sadly, my knowledge on LLVM IR and phi nodes in general is very limited. My questions are:</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>Cheers!<br>Kristóf</div><div><br></div><div><br></div><div>[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.</div><div>[2] [IDF] Teach Iterated Dominance Frontier to use a snapshot CFG based on a GraphDiff. <a href="https://reviews.llvm.org/D50675" target="_blank">https://reviews.llvm.org/D50675</a></div></div>
</blockquote></div>
</blockquote></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail-m_-5196132845271236459gmail-m_-6028325269180143083gmail_signature"><div>Jakub Kuderski</div></div>
</blockquote></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div>Jakub Kuderski</div></div>