This is an archive of the discontinued LLVM Phabricator instance.

[RISCV] Implement branch analysis
ClosedPublic

Authored by asb on Dec 4 2017, 2:37 PM.

Details

Summary

This is a prerequisite for the branch relaxation pass, and allows a number of optimisation passes (e.g. BranchFolding and MachineBlockPlacement) to work.

Unfortunately it can only be tested somewhat indirectly (by checking machineblockplacement for instance). It would be helpful to have the ability to print the output of branch analysis to allow tests to be written directly against that.

analyzeBranch is adapted directly from the AArch64 implementation. The main difference is I check properties of the MCInstrDesc rather than introducing helper functions like isCondBranchOpcode and isUncondBranchOpcode which ducplicate information already specified in RISCVInstrInfo.td.

Diff Detail

Event Timeline

asb created this revision.Dec 4 2017, 2:37 PM
mgrang added inline comments.Dec 4 2017, 4:10 PM
lib/Target/RISCV/RISCVInstrInfo.cpp
81

Period after comment.

117

Period after comment.

242

Period after comment.

245

Can you add a comment to explain what 1 is here?

248

Period after comment.

252

Period after comment.

253

Braces not needed here.

254

Can you add a comment to explain what 1 is here?

257

Period after comment.

259

Can you add a comment to explain what 2 is here?

asb updated this revision to Diff 125478.Dec 5 2017, 1:09 AM
asb marked 10 inline comments as done.

Update patch to address review comments.

asb updated this revision to Diff 126356.Dec 11 2017, 6:50 AM

Refresh patch.

glasnak added inline comments.
lib/Target/RISCV/RISCVInstrInfo.cpp
190

isn't SecondLastInst always true?

asb added inline comments.Dec 13 2017, 9:36 AM
lib/Target/RISCV/RISCVInstrInfo.cpp
190

I believe you're right - thanks. I is only decremented in cases where I != MBB.begin() so is always valid, so there's no reason SecondLastInst should ever be NULL. Other code in this function also freely assumes SecondLastInst is non-null.

asb updated this revision to Diff 126774.Dec 13 2017, 9:44 AM

Remove unnecessary null-check as pointed out by @glasnak. Also add a comment which documents how the invariant that the iterator always points to a non-NULL MachineInstr is maintained. Being defensive and checking for non-null is of course generally a good thing, but the rest of the function works on the knowledge that SecondLastInst is non-null so the single check was confusing.

asb marked an inline comment as done.Dec 13 2017, 9:44 AM
reames requested changes to this revision.Dec 13 2017, 7:05 PM
reames added a subscriber: reames.

Adding a machine pass which just called analyzeBranch on each BB and printed the result would be straight-forward if you wanted to cleanup the testing.

lib/Target/RISCV/RISCVInstrInfo.cpp
152

Okay, this code structure is horrible. I get that you just copied the structure, but there's no reason to keep this. Suggested alternate structure:
if (!ends with predicated terminator) // i.e. fallthrough

return

scan back to first unconditional branch or indirect branch
if (allowmodify) {

// remove everything after that point

}
handle conditional branch case starting from last unconditional branch
handle unconditional branch case starting from last unconditional branch

Beyond this, there's a general invariant question. How do we end up with multiple unconditional branches? When we insert one, shouldn't we truncate the block at that point?

This revision now requires changes to proceed.Dec 13 2017, 7:05 PM
asb updated this revision to Diff 127105.Dec 15 2017, 4:49 AM

Thanks for the review Philip. I've rewritten analyzeBranch. It still handles the same cases, but the logic should be easier to follow. As you suggested, handling branch deletion at the beginning simplifies things.

lib/Target/RISCV/RISCVInstrInfo.cpp
152

I agree that truncating upon insertion might make sense, but I think we need to work within the constraints of the LLVM interfaces for this patch. analyzeBranch is free to modify a BB and it's not clear what would break if insertBranch did the same.

reames accepted this revision.Dec 17 2017, 12:02 PM

Much cleaner, thanks!

lib/Target/RISCV/RISCVInstrInfo.cpp
177

Minor:
if (NumTerminators == 1) {

if (isUnconditional()) {}
assert isConditional()
...

}

This revision is now accepted and ready to land.Dec 17 2017, 12:02 PM
This revision was automatically updated to reflect the committed changes.
asb added inline comments.Jan 10 2018, 12:49 PM
lib/Target/RISCV/RISCVInstrInfo.cpp
177

That's not quite equivalent, as branches can be 'conditional', 'unconditional', or 'indirect'.

Isn't the current code structure most aligned with the LLVM coding style aim of reducing indentation where possible?