<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, May 2, 2017 at 5:36 AM, Evgeny Astigeevich <span dir="ltr"><<a href="mailto:Evgeny.Astigeevich@arm.com" target="_blank">Evgeny.Astigeevich@arm.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi,<br>
<br>
I have got experience of low-level manipulations of Phi-nodes whilst I was implementing an aggressive jump threading optimization for switches.<br></blockquote><div><br></div><div>And i've done it a lot in GVN and NewGVN</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Chandler's proposal will simplify code.</blockquote><div>With no offense to him, i strongly doubt this :)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <br></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Cases I had:<br>
<br>
1. A->B->C, A has multi-edges to B. A is redirected to C.<br>
<br>
I had to write the code something like this:<br>
<br>
int NumEdgesToB = changeteTerminatorTarget(A-><wbr>getTerminator(), B, C);<br>
for (phi: all Phi-nodes in C) {<br>
V = get incoming value to C from B<br>
for (int i = 0; i < NumEdgesToB; ++i) {<br>
phi->addIncoming(V, A);<br>
}<br>
}<br></blockquote><div><br></div><div>Yup.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
I also had to update phi-nodes in B like this:<br>
<br>
for (int i = 0; i < NumEdgesToB; ++i) {<br>
PhiInB-> removeIncomingValue (B, DontDeletePHIIfEmpty);<br>
}<br>
<br></blockquote><div>Yup</div><div><br></div><div>This seems perfectly normal to me, and you would need it regardless of what happens to switch statements :)</div><div><br></div><div>br i1 undef, bb2, bb2</div><div>etc</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
2. I needed to analyze all values incoming to B. As there can be multi-edges I had to write the code something like this:<br>
<br>
SmallPtrSet<BasicBlock *, 8> SeenBlocks;<br>
for (unsigned I = 0, E = CurPhi->getNumIncomingValues()<wbr>; I != E; ++I) {<br>
if (!SeenBlocks.insert(CurPhi-><wbr>getIncomingBlock(I)).second) {<br>
continue;<br>
}<br>
...<br>
}<br>
<br></blockquote><div>Errr, this is not safe in general</div><div>You actually *must* know whether there are single or multiple edges into a block to know whether it is safe to propagate a value.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
4. In order not to deal with duplicated incoming values I had to simplify a phi-nodes Def-Use graph by making some copy of it and removing redundant incoming values.<br></blockquote><div><br></div><div>I'd love to understand why.</div><div>You actually need to deal with them anyway.</div><div><br></div><div>The only thing chandler's representation saves is space at the cost of time.</div><div>The analysis code should generally have to do precisely the same thing it did before.</div><div><br></div><div>IE given:<br></div><div><br></div><div>switch (a)</div><div>{<br> case 32: br foo</div><div> case 64: br foo</div><div><br></div><div>}</div><div><br></div><div>Right now you would end up with:<br><br></div><div>phi({a, 1}, {a, 1})</div><div><br></div><div><br></div><div>You would know that, looking at this phi, it is unsafe to propagate into the value.</div><div><br></div><div>If it is was phi({a, 1}), you cannot tell this, you'd also have to "mix the dfg and cfg" as you say, to tell that there are multiple edges.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
So in all places where we modify/access a phi-node we have to take into account redundant incoming values and preserve this feature.<br></blockquote><div>Yes, and you will still have to do much the same analysis, just you'll end up doing it forwards from the switch, instead of also being able to do it backwards from the phi.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class=""><br>
> > So would this lead to a case where PHI->getNumOperands() !=<br>
> > std::distance(pred_begin(<wbr>phiblock), pred_end(phiblock))<br>
<br>
</span>I cannot imagine when this kind of code could be needed. </blockquote><div><br></div><div>As i said, you often need to know how many edges exist into a block to know whether it is safe to propagate along a path.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">When we work with phi-nodes we almost work with DFG they are part of. The code you provided is an attempt of mixing DFG and CFG.</blockquote><div><br></div><div>Except that PHI nodes exist precisely for this purpose? <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> I don't this is good.<br></blockquote><div><br></div><div>I'm going to strongly disagree.</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
As Chandler wrote connections among phi-node values and edges are not expressed in any way.<br>
<span class=""><br></span></blockquote><div>????<br>Sure it is.</div><div><br></div><div>There is *always* a correspondence between phi nodes and incoming edges.</div><div>That is why phi nodes exist.</div><div>To be able to say "when i came from this edge, i have this value".</div><div><br></div><div>If you mean "the operands of the switch are not uses of the phi", that's also true in every other compiler too.</div><div><br></div><div>This is even solvable if you like, by a bit of indirection, so that there is a 1:1 mapping from case successor to a unique phi operand.</div><div> </div></div></div></div>