[LLVMbugs] [Bug 13214] New: Verify MachineBlockPlacement bias toward source order, simplify logic?

[bugzilla-daemon at llvm.org]

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

             Bug #: 13214
           Summary: Verify MachineBlockPlacement bias toward source order,
                    simplify logic?
           Product: new-bugs
           Version: trunk
          Platform: PC
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: new bugs
        AssignedTo: unassignedbugs at nondot.org
        ReportedBy: atrick at apple.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified


This PR is the result of discussions about whether MachineBlockPlacement should
be sensitive to the Loop's block iterator. There are a few loose ends...

I added clang/test/CodeGen/branch-target-layout.c to verify the front end
preserves source for at least trivial cases. I expect Function and
MachineFunction's block iterators to reflect that order.

Branch instruction label uses are not biased by source order. Instead they are
canonicalized as a result of canonicalizing the compare.

The loop's blocks are inserted in RPO order, but ties are broken by the order
of the branch instruction's labels. Currently LoopInfo's DFS follows branch
labels in forward order, which means that the first label appears later in the
Loop's block list. Maybe this should be reversed, but I don't have any evidence
either way since compare canonicalization seems to result in arbitrary order of
branch labels with respect to the original source.

It is desirable for loop's block iterator to follow the "canonical" branch
label order, because most optimizations should be insensitive to source order.
This is true regardless of whether branch labels are traversed forward or
backward as long as it is consistent. Note that it is also much simpler to
populate the loop tree without considering function block order. In fact, any
"unstable" optimizations that depend on Function/MachineFunction block order
should be rewritten to use DFS RPO at the function level.

Only MachineBlockPlacement needs to consider source order, so it makes sense to
deal with the complexity only in this pass. It might even make sense to
implement a separate DFS over the control flow graph within the MBP pass that
is biased by source order as opposed to canonical compare order. MBP may even
invert compares if the target makes it free to do so in order to preserve
source order.

Loose ends:
- should LoopInfo DFS follows labels in foward or reverse order?
- rewrite any Function passes that may be sensitive to block order (use DFS
order instead)
- verify that MachineBlockPlacement preserves source order in the absence of
contradictory profile data, and simplify the logic to make this bias easier to
apply (separate DFS?), see selectBestCandidateBlock().

-- 
Configure bugmail: http://llvm.org/bugs/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.