<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, 17 Jun 2019 at 17:30, Jakub (Kuba) Kuderski <<a href="mailto:kubakuderski@gmail.com">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"><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? </div></div></blockquote><div><br></div><div>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).</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> </div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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" 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"><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_-708364571160411936gmail-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-m_-708364571160411936gmail_signature"><div>Jakub Kuderski</div></div>
</blockquote></div></div>