I'd like to point out some issues I encountered when using MVT::Flag<br>Basically, applying some transformations might introduce some cycles in the graph (it's not a DAG anymore !).<br><br>Let's consider your example:<br>
sub r2, r3, r2<br>cmp r2, #0<br>bge .LBB0_1<br><br>The initial graph might look like this one:<br>I1: sub(r3,r2) ==> I2: CopyToReg<br>I1 ==> I3: cmp r2, #0<br>I2 (input chain) & I3 (condition code) ==> I4: bge<br>
with I3 and I4 glued together.<br><br>Now let's assume you remove the cmp instruction:<br>I1: sub(r3,r2) ==> I2: CopyToReg<br>I2(input chain) & I1 (condition code) ==> I4:bge<br>with I1 and I4 glued together.<br>
And we just created a cycle in the graph:<br>- a successor of I1 is I4<br>- a successor of I4 is I2 (because I1 and I4 are glued & I2 is a successor of I1)<br>- a direct successor if I2 is I4<br>and so the cycle is there !<br>
<br>Please tell me if I missed something... But to me, it's "easy" to have some cycles in the graph even if it still looks a DAG when you draw the graph.<br><br> Damien<br><br><br><div class="gmail_quote">On Fri, Feb 18, 2011 at 7:31 AM, Edmund Grimley-Evans <span dir="ltr"><<a href="mailto:Edmund.Grimley-Evans@arm.com">Edmund.Grimley-Evans@arm.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">The log message for revision 122213 says:<br>
<br>
> Change the X86 backend to stop using the evil ADDC/ADDE/SUBC/SUBE nodes (which<br>
> their carry depenedencies with MVT::Flag operands) and use clean and beautiful<br>
> EFLAGS dependences instead.<br>
<br>
(MVT::Flag has since been renamed to MVT::Glue.)<br>
<br>
That revision made bug 8404 go away.<br>
<br>
Am I right in thinking that one of the problems with MVT::Glue is that<br>
it is hard to guarantee that other instructions won't come between the<br>
two instructions that are glued together? And another problem is that<br>
you actually want to allow some instructions to come between them?<br>
<br>
Suppose, for example, that we have a selection DAG with these edges:<br>
<br>
X -> G1 -> G2 -> Y<br>
X -> A -> Y<br>
<br>
where the dependency between G1 and G2 is Glue.<br>
<br>
Then if instruction selection replaces X and G1 by a single<br>
instruction I1, and G2 and Y by a single instruction I2, then we end<br>
up with this DAG:<br>
<br>
I1 -> I2<br>
I1 -> A -> I2<br>
<br>
Now I1 and I2 are glued together, but A has to come between them. It's<br>
hard to know when a combination of rules that each look all right on<br>
their own might lead to this happening.<br>
<br>
I'm guessing that something like this lead to the "Wrong topological<br>
sorting" assertion failure in bug 8404. (I've seen the same assertion<br>
failure in some other cases where I have more reason to think that<br>
that's roughly what happened.)<br>
<br>
A real example to consider might be code like this:<br>
<br>
do {<br>
a[i] -= b[i];<br>
} while (a[i++] >= 0);<br>
<br>
I'm currently getting ARM code like this:<br>
<br>
.LBB0_1:<br>
ldr r2, [r1], #4<br>
ldr r3, [r0]<br>
sub r2, r3, r2<br>
str r2, [r0], #4<br>
cmp r2, #0<br>
bge .LBB0_1<br>
<br>
This could be improved, I think, by getting the subtract to set the<br>
flags instead of comparing with zero, like this:<br>
<br>
.LBB0_1:<br>
ldr r2, [r1], #4<br>
ldr r3, [r0]<br>
subs r2, r3, r2<br>
str r2, [r0], #4<br>
bpl .LBB0_1<br>
<br>
But that code might be hard to generate if the flag-setting SUBS is<br>
"glued" to the conditional branch BPL so you can't put the store<br>
between them.<br>
<br>
So, some questions:<br>
<br>
* Is there a set of rules for using Glue to avoid getting "Wrong<br>
topological sorting"?<br>
<br>
* If not, should we be avoiding Glue altogether?<br>
<br>
* How hard is it to replace Glue in other back ends by something like<br>
EFLAGS? Should we be doing that?<br>
<br>
Edmund<br>
<font color="#888888">--<br>
IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</font></blockquote></div><br>