[LLVMbugs] [Bug 1075] NEW: bottom-up register-reduction scheduling actually increases register pressure

[bugzilla-daemon at cs.uiuc.edu]

http://llvm.org/bugs/show_bug.cgi?id=1075

           Summary: bottom-up register-reduction scheduling actually
                    increases register pressure
           Product: libraries
           Version: trunk
          Platform: PC
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Common Code Generator Code
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: djg at cray.com


A high Sethi-Ullman number for an operation indicates it should be scheduled
earlier rather than later -- from a top-down perspective. However, in bottom-up
scheduling currently Seth-Ullman numbers are translated directly to priority
values, so such operations end up being scheduled earlier from a *bottom-up*
perspective. The result is that register pressure is actually increased instead
of reduced. The effect is somewhat hidden because the special case values are
also inverted -- for example, a store is given a low Sethi-Ullman number, but it
ends up having the desired effect. In larger test cases, there are fewer nodes
that use the special cases, and the effect is much more visible.

I've experimented a little with having the priority function take the inverse of
the SethiUllman value, and inverting the special-case values, and I've seen
spill counts drop significantly in large test cases on x86-64. 

Here's a simple case that shows the problem:

float %foo(float %x) {
        %tmp1 = mul float %x, 3.000000e+00
        %tmp3 = mul float %x, 5.000000e+00
        %tmp5 = mul float %x, 7.000000e+00
        %tmp7 = mul float %x, 1.100000e+01
        %tmp10 = add float %tmp1, %tmp3
        %tmp12 = add float %tmp10, %tmp5
        %tmp14 = add float %tmp12, %tmp7
        ret float %tmp14
}

With -march=x86-64, the list-burr (default) schedule places all the multiplies
before all the adds. With the change mentioned above, the multiplies are
intermixed with the adds, so the register pressure is lower.



------- You are receiving this mail because: -------
You are on the CC list for the bug, or are watching someone who is.