Hi, Anna<div><br></div><div> I may not fully understand your point. Here are my thoughts:</div><div>First, In think changing the CFG::iterator to be in line with Function::iterator is too intrusive to clang, and not very necessary. I actually tried to do this. It involved so many changes that I finally gave up.</div>
<div><br></div><div>Second, on your comment on the approach I took. Even the current implementation of the recalculate function does not solely depend on GraphTraits. It also depends on Function::getEntryBlock or Function::front(), Function.size(), etc. Why do you think a clean implementation should only depend on GraphTraits? In addition, I actually have such a concern: is it reasonable enough to fill in GraphTraits more stuff only because dominators implementation needs this?</div>
<div><br></div><div>I believe it should be possible to change the recalculate function to only depend on GraphTraits. But I am not sure if this will be viewed as too intrusive to LLVM. In thinking of these I finally made that compromise. </div>
<div><br></div><div>Regarding the time, I am willing to do further refactoring until this code will finally become good enough, although I can only work on weekend on this. I just want to understand clearly the reasonable motivation behind each refactoring step.</div>
<div><br></div><div>--</div><div>Guoping<br><br><div class="gmail_quote">2011/11/6 Anna Zaks <span dir="ltr"><<a href="mailto:ganna@apple.com">ganna@apple.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div style="word-wrap:break-word">Hi Guoping,<div><br></div><div>Even though adding another method (getBlock()) to resolve the inconsistency is the least intrusive solution, it's not the cleanest one in my opinion. Ex: There is no interface that defines the API a graph class should implement to support the dominator computation. It's not a problem with your extension, but with the current dominator's implementation. The cleanest approach would be to change the dominators to only rely on GraphTraits. Though that would involve more work and I am not sure if you have the time to do it.</div>
<div><div><div><br></div><div>Cheers,</div><div>Anna.</div><div><div class="h5"><div>On Nov 5, 2011, at 8:10 PM, Guoping Long wrote:</div><br></div></div><blockquote type="cite"><div><div class="h5">Hi, Anna, Ted<div><br>
</div><div> Here is the approach I finally take, which I believe shall be least intrusive to both clang and LLVM:</div><div>The EntryBlock issue is easy to resolve, as you pointed out, I just changed the Clang's counterpart method into this name. Up to now, three classes involve dominators: the Function class, the Clang::CFG class, and the MachineFunction class. The MachineFunction class also does not have the getEntryBlock() method. It's trivial to just add this method into the class.</div>
<div><br></div><div>To deal with the iterator issue, either changing Clang or LLVM to use the other's iterator is too intrusive. The approach I am using is simply an interface method. On the Clang side, add this method to the CFG class:</div>
<div>CFGBlock * getBlock(iterator I) { return *I; }</div><div>While on the LLVM side, adding this method to both Function and MachineFunction classes:</div><div>BasicBlock * getBlock(iterator I) { return I; }</div>
<div>This fixes the issue.</div><div><br></div><div>Attached is the final patch to both LLVM and Clang. Hopefully this could conclude the addition of the dominator tree support for Clang. Please let me know your comments.</div>
<div><br></div><div>Thanks!</div><div><br></div><div>----</div><div>Guoping<br><br><div class="gmail_quote">2011/11/4 Anna Zaks <span dir="ltr"><<a href="mailto:ganna@apple.com" target="_blank">ganna@apple.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">Hi Guoping,<div><br></div><div>There are two possible solutions here. </div><div><br></div><div>First solution is to rewrite the recompute() routine to use the following GraphTraits instead of passing in the Function/clang::CFG object:</div>
<div>// From include/llvm/Support/CFG.h</div><div>template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*></div><div>GraphTraits already has most of the APIs used by the dominator computation. However, it does not have the size() method, which is used in the Calculate() function called from recalculate(). That would mean that we would possibly need to extend the traits.. Then, we could change the clang::CFG GraphTraits to have the nodes_iterator type consistent with that of Function's GraphTraits. This change is much more intrusive on LLVM side.</div>
<div><br></div><div>Another solution is to change the iterator type in clang::CFG to match the Function iterator. </div><div><br></div><div>As a side note, it's a bit strange that the nodes_iterator types are inconsistent between clang::CFG and Function GraphTraits. They are defined as iterators of clang::CFG and Function respectively. Everything still works because the GraphWriter, which relies on the traits, has an overloaded writeNode() function which allows it to work with NodeType and NodeType*. But either solution would fix the inconsistency.</div>
<div><br></div><div>Ted, do you have any preferences?</div><div><br></div><div>Cheers,</div><span><font color="#888888"><div>Anna.</div></font></span><div><div><div><br></div><div><br></div><div>
<br><div><div>On Nov 4, 2011, at 9:23 AM, Guoping Long wrote:</div><br><blockquote type="cite"><div>Hi, Anna</div><div><br></div><div> First, thank your for your time for commenting this code!</div><div> There is one more subtle difference. This is the major one that ended up the code this way. It is the difference between CFGBlock::iterator and Function::iterator, as shown in the code excerpt below.</div>
<div><br></div><div>Function::iterator. Each iterator I is used directly as BasicBlock * here.</div><div> // Initialize the roots list</div><div> for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {</div>
<div> if (std::distance(GraphTraits<FT*>::child_begin(I),</div><div> GraphTraits<FT*>::child_end(I)) == 0)</div><div> addRoot(I);</div><div><br></div><div>CFG::iterator. Each iterator has the CFGBlock ** type. In this case we need a pointer indirection here.</div>
<div><div> // Initialize the roots list</div><div> for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {</div><div> if (std::distance(GraphTraits<FT*>::child_begin(*I),</div><div> GraphTraits<FT*>::child_end(*I)) == 0)</div>
<div> addRoot(*I);</div></div><div><br></div><div>One approach is to change CFG or Function implementation to make them have the same interface. But I am afraid this may cause two many changes to the code base. I would love to hear your comments. Is there a decent solution that does not require too many changes to the code?</div>
<div><br></div><div>--</div><div>Guoping</div><div><br></div><br><div class="gmail_quote">2011/11/2 Anna Zaks <span dir="ltr"><<a href="mailto:ganna@apple.com" target="_blank">ganna@apple.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Hi Guoping,<br>
<br>
It seems that the only reason why you need to copy the recalculate function is that the names for the entry block in the clang CFG and LLVM function are different. Is that correct? (The bool parameter does not seem to be used..)<br>
<br>
A simple solution to that would be to make sure that we have the same name in both. I suggest using getEntryBlock().<br>
<br>
On llvm's side, it would involve changing the recalculate function to use getEntryBlock instead of front(). Looks like they are the same thing.<br>
<br>
On Clang's side, we could just rename CFG::getEntry() -> CFG::getEntryBlock().<br>
<br>
Thanks!<br>
Anna.<br>
<div><div>On Oct 29, 2011, at 3:58 PM, Guoping Long wrote:<br>
<br>
> Hi, Ted<br>
><br>
> The preliminary refactoring of the dominators patch for clang based on the more efficient LLVM core implementation is done. Attached is the patch. I am not very satisfied with this version because it relies a ugly hack to deal with the subtle differences between LLVM Function and Clang CFG. Since this version requires some modifications to include/llvm/Analysis/Dominators.h, so there is also a patch for llvm.<br>
><br>
> While I believe there should be a cleaner way to do this, I do not know how to achieve that. Please let me know your comments. I shall continue to improve until it become satisfactory.<br>
> Regards.<br>
><br>
> ----<br>
> Guoping<br>
</div></div>> <dominators-clang.patch><dominators-llvm.patch>_______________________________________________<br>
> cfe-dev mailing list<br>
> <a href="mailto:cfe-dev@cs.uiuc.edu" target="_blank">cfe-dev@cs.uiuc.edu</a><br>
> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev</a><br>
<br>
</blockquote></div><br>
</blockquote></div><br></div></div></div></div></blockquote></div><br></div>
</div></div><span><dominators-clang.patch></span><span><dominators-llvm.patch></span></blockquote></div><br></div></div></blockquote></div><br></div>