This is an archive of the discontinued LLVM Phabricator instance.

[NFC][regalloc] Separate iteration from AllocationOrder
ClosedPublic

Authored by mtrofin on Sep 24 2020, 12:55 PM.

Details

Summary

This separates the two concerns - encapsulation of traversal order; and iteration.

Diff Detail

Event Timeline

mtrofin created this revision.Sep 24 2020, 12:55 PM
mtrofin requested review of this revision.Sep 24 2020, 12:55 PM
wmi added a comment.Sep 24 2020, 4:49 PM

Is the intention to have multiple iterators live for the same AllocationOrder?

llvm/lib/CodeGen/AllocationOrder.h
44–45

Can you have a reference of AllocationOrder in Iterator instead of defining multiple fields? It looks a little clearer to access parent's fields directly.

mtrofin marked an inline comment as done.Sep 24 2020, 6:23 PM
mtrofin added inline comments.
llvm/lib/CodeGen/AllocationOrder.h
44–45

With the current way, I'm leveraging the ability of constructing a view over the Order ArrayRef. Also, we could author a test very easily now, avoiding the need for a Matrix, RegClassInfo, etc (what AllocationOrder needs) - albeit currently the .h is under lib/CodeGen; but we could as a next step.

mtrofin marked an inline comment as done.Sep 24 2020, 6:28 PM
In D88256#2293981, @wmi wrote:

Is the intention to have multiple iterators live for the same AllocationOrder?

The main goal is to avoid this:

void fooBar(AllocationOrder &Order) {

Order.rewind();
while (...Order.next()) {
 <lots of code>
}

}

So if the while loop is large, you need to go see that the order has actually been reset. Also, the state post-while loop should be reset. The alternative I'm proposing allows allocation orders be passed around without worrying they get surprisingly mutated - so easier to read and maintain.

wmi added a comment.Sep 24 2020, 8:56 PM

Thanks for explaining the motivation of the change. That makes sense.

Since it changes the way how AllocationOrder will be used, add Quentin as reviewer.

qcolombet requested changes to this revision.Sep 25 2020, 1:51 PM

Hi,

I like that we take the iterator path, but I don't think the current patch is clearer than the previous implementation.

First we duplicate some logic from AllocationOrder to AllocationOrder::Iterator (see my inline comment), second, I found the AllocationOrder::getIterator not iterator friendly.
What I mean here is that I would have expected a AllocationOrder::begin and AllocationOrder::end, so that we can use range based loop and so on.

As is I don't really see the value of that refactoring.

Cheers,
-Quentin

llvm/lib/CodeGen/AllocationOrder.h
64

I don't like that we duplicate the logic of AllocationOrder::isHint here.

This revision now requires changes to proceed.Sep 25 2020, 1:51 PM

Hi,

I like that we take the iterator path, but I don't think the current patch is clearer than the previous implementation.

First we duplicate some logic from AllocationOrder to AllocationOrder::Iterator (see my inline comment), second, I found the AllocationOrder::getIterator not iterator friendly.
What I mean here is that I would have expected a AllocationOrder::begin and AllocationOrder::end, so that we can use range based loop and so on.

As is I don't really see the value of that refactoring.

Cheers,
-Quentin

SGTM - I'll send first another patch with unittests for the current behavior; then refresh this one.

mtrofin updated this revision to Diff 295059.Sep 29 2020, 11:11 AM

updated to follow iterator style (begin() / end())

mtrofin edited the summary of this revision. (Show Details)Sep 29 2020, 11:11 AM

gentle reminder - thanks!

Gentle reminder - thanks!

qcolombet accepted this revision.Oct 5 2020, 11:36 AM

LGTM with nitpicks

llvm/lib/CodeGen/RegAllocGreedy.cpp
811–813

Could we just stick to assigning PhysReg at the beginning of the loop?
That way we don't have to modify the body of the loop.

1859–1860

Could you call out the type here?
Put differently, I don't like the use of auto when the type is not immediately obvious.

2298–2299

Ditto with the use of auto

2616–2617

Ditto with the use of auto

This revision is now accepted and ready to land.Oct 5 2020, 11:36 AM
mtrofin updated this revision to Diff 296253.Oct 5 2020, 12:15 PM
mtrofin marked 4 inline comments as done.
mtrofin edited the summary of this revision. (Show Details)

feedback

mtrofin marked an inline comment as done.Oct 5 2020, 12:15 PM
mtrofin added inline comments.
llvm/lib/CodeGen/RegAllocGreedy.cpp
811–813

There's a slight nuance:

In the old code, suppose we never hit line 819 (the break). Then line 821 will have a 0 PhysReg (indicating loop completed, and no reg was found)

In the new code, if we just initialize PhysReg on line 812, then we'll never have a 0 PhysReg on line 826 (ok, not never - because it could be the loop is never entered).

We could have I in the outer scope, and check both on line 826; or - the path I preferred - we clarify that the loop searches for a value for PhysReg.

wdyt?

1859–1860

Done - also changed the type of operator*, in light of our discussion - we could type it as MCPhysReg, but I think MCRegister would also be correct, and help reduce the concept count - wdyt?

qcolombet added inline comments.Oct 5 2020, 1:33 PM
llvm/lib/CodeGen/RegAllocGreedy.cpp
811–813

Sounds fine.
Let's stick to the version in that patch.

1859–1860

I have a slight preference with MCPhysReg, but MCRegister is fine too.
That said, it is strange to have ArrayRef<MCPhysReg> getOrder returning a different type.
I would rather be consistent, but I can live with the iterator offering the richer type.

mtrofin updated this revision to Diff 296303.Oct 5 2020, 2:42 PM
mtrofin marked 3 inline comments as done.

feedback

llvm/lib/CodeGen/RegAllocGreedy.cpp
1859–1860

ack - fixed here and at line 2298. Left at 2617, which before was Register, and also in RegAllocBasic, same reason.

This revision was automatically updated to reflect the committed changes.