This is an archive of the discontinued LLVM Phabricator instance.

MachineLoopInfo: add methods findLoopPreheader and getExitingBlock
ClosedPublic

Authored by SjoerdMeijer on Jul 29 2016, 5:41 AM.

Details

Summary

This adds two new utility functions findLoopPreheader and getExitingBlock to MachineLoopInfo.
These functions are refactored and taken from the Hexagon target as they are target independent.

Diff Detail

Repository
rL LLVM

Event Timeline

SjoerdMeijer retitled this revision from to MachineLoopInfo: add methods findLoopPreheader and getExitingBlock.
SjoerdMeijer updated this object.
SjoerdMeijer added a subscriber: llvm-commits.
kparzysz added inline comments.Aug 3 2016, 6:39 AM
lib/CodeGen/MachineLoopInfo.cpp
84 ↗(On Diff #66111)

This part is finding a block that can enter the loop header, but may also go somewhere else. On Hexagon we can use it to put the hardware loop setup here, since it can be safely speculated. Code that cannot be speculated cannot be placed here.
Maybe you could add a parameter to let the caller decide whether they want just the regular preheader, or a speculative one.

On a different note, have you checked how many potential users for this are there? Is there a demand for this?

lib/Target/Hexagon/HexagonHardwareLoops.cpp
1810 ↗(On Diff #66111)

The lines 1824-1825 must be present here. This function needs to return a regular preheader, and if the SpecPreheader is specified, the speculative one, if it can find it.

SjoerdMeijer added inline comments.Aug 3 2016, 7:12 AM
lib/CodeGen/MachineLoopInfo.cpp
84 ↗(On Diff #66111)

Thanks for reviewing! I will start making these changes.

About users for this: what I actually want is to have the "getLoopTripCount" available on the MachineLoop level, and the refactoring in this patch is the first exercise or groundwork to achieve that. It looks like you have done most of the hard work already in the Hexagon backend; looking at the getLoopTripCount implementation, there is actually very little Hexagon specific, only one place checks for Hexagon add instruction opcodes (which I think is not hard to nicely hide in a target hook). I think these MachineLoop utility functions such as getLoopTripCount, findLoopPreheader, getExitBlocks, etc., are mostly target independent and really nice to have (and I would definitely like to use them). In fact, for implementing more loop transformations on Machine blocks, these functions are required...

I've added a second argument SpeculativePreheader to function findLoopPreheader. This allowed more refactoring in the Hexagon backend as we can don't need a local implementation of that function anymore, but just a call to the one in MachineLoopInfo.

bcahoon edited edge metadata.Aug 4 2016, 3:44 PM

I think it's a good idea to try to move some of the code in the Hexagon hardware loop pass so that it can be reused. The getExitingBlock() function in HexagonHardwareLoops.cpp is probably poorly named since it's doing something different than the existing function that is in MachineLoop. If the function is moved, it seems to fit better in the MachineLoop class vs the MachineLoopInfo class.

The code in the getExitingBlock() function in HexagonHardwareLoops.cpp is attempting to enable the hardware loop pass to work on two special types of loops. In one case, we would like to generate a hardware loop even if there are multiple exiting blocks. If that's the case, then we use the latch block as the exiting block (if the latch block is one of the exiting block). It's ok to exit early from a hardware loop. In the second case, we would like to generate a hardware loop if there is a single exit, but the latch is not the exit. This case occurs, for example, when a critical edge is added to the loop (see the hwloop-crit-edge.ll as an example).

I just wanted to provide a little background as to how the hardware loop pass uses the function. Initially, I believe we used the latch block in all the cases where getExitingBlock() is now called. But, that caused problems when attempting to generate a hardware loop for the critical edge case.

Hi, thanks a lot for the info, that is very useful, and I am glad you like the idea of moving some of the code! I really think it is going to be useful.

I will take your feedback on board and create a new patch early next week for factoring out these 2 functions (as a first exercise). Then I will see if can take a slightly bigger chunk in one go to get the LoopTripCount function factored out.

Cheers,
Sjoerd.

SjoerdMeijer edited edge metadata.

I've renamed getExitingBlocks to findLoopControlBlock and moved it from class MachineLoopInfo to MachineLoop.

The changes look good to me. The only nitpick is that you should run clang-format on your changes.

Thanks. I've run clang-format.

is it okay to commit?

Rereading your comment, I missed the LGTM, so I wil go ahead and commit.
Thanks a lot for reviewing!

This revision was automatically updated to reflect the committed changes.