Then I misunderstood it's purpose. I see now that constant propagation could remove branches because you know a value is true. I was looking at the problem through my 'register allocator' lens. Here is a more expressive example of what you are doing.<div>
<br><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">define i1 @t1(i1 %c) {<br> br i1 %c, label %t, label %f<br>t:<br> br i1 %c, label %t2, label %f2</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">t2:</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">f2:</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "><br>f:<span class="Apple-style-span" style="font-family: arial; font-size: small; border-collapse: separate; color: rgb(0, 0, 0); "><div>
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> br i1 %c, label %t3, label %f3</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">t3:</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">f3:</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div></span> }</span></div><div><font class="Apple-style-span" color="#500050" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br>
</span></font></div><div><font class="Apple-style-span" color="#500050" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">Would be changed into:<br></span></font><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">define i1 @t1(i1 %c) {<br>
br i1 %c, label %t2, label %f3</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">t2:</span></div><div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div>
<div><span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div><div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: arial; font-size: small; ">
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">f3:</span></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: arial; font-size: small; ">
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> code...</span></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: arial; font-size: small; ">
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "> ret something</span></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: arial; font-size: small; ">
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; ">}</span></div><div style="border-collapse: separate; color: rgb(0, 0, 0); font-family: arial; font-size: small; ">
<span class="Apple-style-span" style="border-collapse: collapse; color: rgb(80, 0, 80); font-family: arial, sans-serif; font-size: 13px; "><br></span></div><div><font class="Apple-style-span" color="#500050" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">Jeff Kunkel</span></font></div>
<font class="Apple-style-span" color="#500050" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"> </span></font></div><div class="gmail_quote">On Mon, Feb 7, 2011 at 8:37 AM, Duncan Sands <span dir="ltr"><<a href="mailto:baldrick@free.fr">baldrick@free.fr</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Hi Jeff,<div class="im"><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Are you sure this is really advantageous? '%c' is only one variable, but when<br>
you add the constant propagation, '%c' and false/true are two different<br>
variables. Thus<br>
</blockquote>
<br></div>
the example was explanatory, not typical. In fact I didn't ever see returns<br>
being split like this in practice. What I do see typically is branches<br>
being eliminated. For example, consider the effect on bzip2: 36 branches are<br>
completely removed, 1 is changed from conditional to unconditional, various<br>
bits of dead code are eliminated (not a lot, 4 stores and a few computations).<br>
I chose this example randomly, but it's typical of what I see elsewhere.<br>
<br>
Ciao, Duncan.<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div class="h5">
<br>
define i1 @t1(i1 %c) {<br>
br i1 %c, label %t, label %f<br>
t:<br>
ret i1 %c<br>
f:<br>
ret i1 %c<br>
}<br>
should be<br>
br i1 R0, label %t, label %f<br>
t:<br>
ret R0<br>
f:<br>
ret R0<br>
<br>
However, with your pass<br>
define i1 @t1(i1 %c) {<br>
br i1 %c, label %t, label %f<br>
t:<br>
ret i1 true<br>
f:<br>
ret i1 false<br>
}<br>
will be<br>
define i1 @t1(i1 %c) {<br>
br i1 R0, label %t, label %f<br>
t:<br>
R1 = true<br>
ret i1 R1<br>
f:<br>
R1 = false<br>
ret i1 R1<br>
}<br>
<br>
I am thinking X86 where '%c' would be allocated a register and the false/true<br>
statement would be allocated a different register which would be EAX/AX on the<br>
x86 machine.<br>
<br>
Honestly, I believe this pattern could be conditional constant propagation<br>
/ conditional re-materialization in the spiller. LLVM uses the spiller to<br>
propagate constants. This pass would be useful to identify some conditional<br>
re-materializations. You should look into hacking the spiller and see if this<br>
can be added to it.<br>
<br>
- My 2 cents,<br>
Jeff Kunkel<br>
<br>
On Mon, Feb 7, 2011 at 7:50 AM, Duncan Sands <<a href="mailto:baldrick@free.fr" target="_blank">baldrick@free.fr</a><br></div></div><div><div></div><div class="h5">
<mailto:<a href="mailto:baldrick@free.fr" target="_blank">baldrick@free.fr</a>>> wrote:<br>
<br>
Hi all, I wrote a little pass (attached) which does the following: if it sees a<br>
conditional branch instruction then it replaces all occurrences of the condition<br>
in the true block with "true" and in the false block with "false". Well, OK, it<br>
is a bit more sophisticated (and a bit more careful!) than that but you get the<br>
idea. It will turn this<br>
define i1 @t1(i1 %c) {<br>
br i1 %c, label %t, label %f<br>
t:<br>
ret i1 %c<br>
f:<br>
ret i1 %c<br>
}<br>
into this<br>
define i1 @t1(i1 %c) {<br>
br i1 %c, label %t, label %f<br>
t:<br>
ret i1 true<br>
f:<br>
ret i1 false<br>
}<br>
for example. Curiously enough LLVM doesn't seem to have a pass that does this.<br>
I took a look at the effect on the testsuite by scheduling a run of this pass<br>
just after each run of -correlated-propagation. In spite of being so simple<br>
(not to say simplistic) it has an enormous positive impact on Ada code and a<br>
substantial positive impact throughout the LLVM test-suite (I didn't check that<br>
programs still work after running the pass, so it could be that it has such a<br>
big effect because it is wrong!).<br>
<br>
So... should this kind of logic be incorporated into LLVM? Perhaps as part of<br>
an existing pass like -correlated-propagation?<br>
<br>
It would be easy to make the pass a bit more powerful. For example if the<br>
condition was "X == 0" then it could also replace X with 0 everywhere in the<br>
true block.<br>
<br>
Ciao, Duncan.<br>
<br>
PS: This was inspired by PR9004.<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br></div></div>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <mailto:<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><div class="im">
<br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
</div></blockquote>
<br>
</blockquote></div><br></div></div>