In D98232#3132500, @qcolombet wrote:

should we go ahead and revert (most of*) https://reviews.llvm.org/D35816?

Although I think that's the right approach, neither @aditya_nandakumar or I had time to clean up and push the fix for eviction chains yet.

@aditya_nandakumar do you have an ETA when you believe you can land that?

Hi Quentin, unfortunately I've not had the time to upstream this or think about cleaning this up and upstreaming it.

Should I just take over at this point?

If you have the cycles, please go for it. I don't want to hold up progress here. Thanks

Cheers,
-Quenitn

In D106881#2910097, @foad wrote:

In D106881#2907835, @aditya_nandakumar wrote:

In D106881#2907544, @foad wrote:

Any thoughts on this? I thought it would be cleaner to use the standard analysis verification API instead of ad hoc calls to CSEInfo->verify from the Legalizer and Combiner.

It does appear cleaner once we make sure that all backends are clean wrt reporting all mutations to the observers (last time I checked there were failures and I didn't get a chance to verify and fix). If that's indeed the case, then LGTM.

There are still some AMDGPU lit test failures, because we do some things in the legalizer that are not safe wrt observers.

On the other hand, the AMDGPU legalizer doesn't use CSEMIRBuilder, so is there any need for it to report stuff to the observers?

If CSE is not enabled, then I think the verifier should not complain (CSEs). The main contract is to notify Observers of mutations (technically not necessary if there's nothing observing, but still better to notify).

On the other other hand, the AMDGPU legalizer probably should use CSEMIRBuilder. The main problem I saw last time I tried this was with MRI->setRegClass(Reg, RC). As I understand it, this counts as a mutation of not just the instruction that defines Reg, but every instruction that uses Reg too. Is that correct? Is there a way to report that kind of widespread mutation to the observers?

Yes there is.

if (GISelChangeObserver *Observer = MF.getObserver()) {
  Register Reg = ...;
  Observer->changingAllUsesOfReg(MRI, Reg);
  // change it.
  Observer->finishedChangingAllUsesOfReg();
}

In D106881#2907544, @foad wrote:

Any thoughts on this? I thought it would be cleaner to use the standard analysis verification API instead of ad hoc calls to CSEInfo->verify from the Legalizer and Combiner.

In D105751#2868526, @paquette wrote:

I think I like this direction more just because the casting stuff is more consistent with the rest of LLVM. That might be more approachable for people who are more experienced with other parts of LLVM.

In D98232#2661823, @qcolombet wrote:

@aditya_nandakumar @qcolombet any idea when a better fix for that issue might be available?

Given Aditya did the prototype I let him comment on that, but I don't expect we land something anytime soon (i.e., at least a couple of months).

In D93423#2459018, @aemerson wrote:

In D93423#2459004, @aditya_nandakumar wrote:

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

It's possible it would help a bit. I think the localizer may also benefit from this. I don't see it making a big difference either way though in most code.

If slot indexes are preserved and used in other passes that use CSE, do you think the compile time impact is amortized/minimized?

In D93423#2458972, @arsenm wrote:

I still think the CSE MIR builder shouldn't be required to CSE and can bail early on long dominance queries

rGbed839404784

Updates as requested.

I attempted this in the past but abandoned it due to infinite loops in legalization like mentioned earlier. Constant folding during legalization seems okay as long as it operates on legal types (ie fold an operation of constants (which are already legal) to the same type.

Address Jay's comments.

In D88060#2329690, @foad wrote:

Reverse ping! If you just don't have time to work on this, I'd be interested in commandeering the "insert_vec_elt(build_vector) -> build_vector" part.

Committed in ef3d17482ff

Address latest comments by Matt

Also missed some unstaged changes locally
s/push_back/emplace_back

s/std::sort/llvm::sort

Insert undef during the apply phase instead of the match as mentioned in the feedback.

Updated to handle the missing index as well duplicate indices cases.

Updated to abandon combine if index is out of bounds.

Pushed in 97203cfd6ba

In D87668#2275249, @mkitzan wrote:

Thanks for the review. Still don't have commit access, will need someone to commit on my behalf. Thanks in advance!

Committed in 46f9137e43f

I can commit on your behalf.
Also we'll need to figure out how to get you access.

In D87297#2264223, @aemerson wrote:

In D87297#2264152, @qcolombet wrote:

Hi Amara,

dominates(A, B) tries to determine dominance by walking an iterator from the beginning of the block potentially until the end. In extremely large BBs this can result in very long compile times, since this is called often from the artifact combiner.

Instead of disabling the check, I think it would be best to fix the underlying compile time issue. The solution here would be to switch the list of MachineInstr to numbered instructions so that dominance checks become O(1).
I had meant to look at this for quite some time but didn't get a chance to do it.
Something similar has been done on LLVM IR (see https://reviews.llvm.org/D51664). I wish it was done in a way that could have benefited the Machine IR like I suggested in https://reviews.llvm.org/D51664#1389884, but this ship has sailed!

I understand this is a big under taking so I am fine with the threshold approach in the meantime.

I leave the final approval to Aditya and Matt.

Cheers,
-Quentin

Yes I saw that thread, it's a shame we didn't have a shared solution for MBB too. There's probably more places where we have hidden super-linear compile time waiting to be triggered.

It's actually not quite as simple as I previously thought. The current logic in getDominatingInstrForID seems to be this:

MachineInstr *A = CSE_lookup_in_same_bb(B)
if (!dominates(A, B))
    move A before B such that dominates(A, B) is true
else
    return pointer to A

If we hit our threshold, what should getDominatingInstrForID() do? Perhaps clone the instruction A instead?

In D86226#2250210, @arsenm wrote:

In D86226#2250056, @aditya_nandakumar wrote:

My thought on this Observer ownership is as follows (which I think I mentioned in another review).

• Each pass will setup an observer(wrapper) and install it to the MF. The MF at this point has the reference to the observer, and the pass owns each observer as it decides what it needs to observe and how.
• At the end of each pass, just reset the observer (there are RAII helpers for this).
• Remove the observer in MachineIRBuilder (is there a need for this?).
• No need to thread observer through APIs. Instead we get it through MF.getObserver().

Thoughts?

I'm mostly concerned with the wonky way we set register banks on new instructions with an observer. This isn't pass / function level, and is on an individual instruction we're legalizing.

My thought on this Observer ownership is as follows (which I think I mentioned in another review).

• Each pass will setup an observer(wrapper) and install it to the MF. The MF at this point has the reference to the observer, and the pass owns each observer as it decides what it needs to observe and how.
• At the end of each pass, just reset the observer (there are RAII helpers for this).
• Remove the observer in MachineIRBuilder (is there a need for this?).
• No need to thread observer through APIs. Instead we get it through MF.getObserver().

rGdb464a3dbf0e

rGdb464a3dbf0e

rG5c2db1655

I can commit for you if no one has gotten to it yet.

It's a fine balance in how much the builders should do compared to DAG. I also personally found SDAG's getNode to be doing too much (and some of that code was replicated in the DAGCombines).
CSEMIRBuilder builds on the other builders by adding CSE. ConstantFoldingBuilder was POC on how to extend/customize builders. While I'm not sure where the balance on how much the builders should do, assuming we wanted to fold copies, it should be structured to be in one of the base builders (as the change seems unrelated to CSEing in general).

Committed in 2144a3bdbba4

I can commit it for you.

Silly bug. Thanks for fixing.

Add G_EXTRACT to CSEConfigFull, and add unit test.

This looks much better. Looks good to me.

To enable rules {x,y}, you'd need to disable the universe, and specify rules you want to enable with !, all in a command called disable-rule*. This sounds inverse of what's necessary and is far from ergonomic.
I see this as similar to if opt/llc run-pass invocation was done by disable universe of passes, and enable some passes with !.
Additionally for the most common and immediately useful case of writing tests, I don't expect any need to both enable and disable rules in the same invocation. IOW, for testing purposes, only use the enable opt, and for bisecting and other tools (for future), use the disable opt. Perhaps we should rename the opt to make it explicit that it's used for testing only and perhaps even we assert that both are not used simultaneously (or make it abundantly clear in the docs).
TLDR; I'm suggesting we optimize the interface for the most common and immediately useful case of testing, and worry about enabling and disabling simultaneously later on?

In D81889#2096115, @paquette wrote:

The point here is to allow people to only enable specific rules, right?

Maybe an interface like this would be a bit simpler?

--my_combiner-only-enable-rules="rule1,rule2,rule3,..."

Doesn't https://reviews.llvm.org/D81863 make this unnecessary?

rG6239d6700184

Is there any interest in me checking in the above unit test? I initially didn't check it in as I thought this was more of a side effect of how things are implemented and not really how the APIs should be used.

In D81461#2082939, @arsenm wrote:

In D81461#2082923, @arsenm wrote:

In D81461#2082557, @aditya_nandakumar wrote:

In D81461#2082149, @arsenm wrote:

It seems both the MachineFunction and MachineIRBuilder have insertion observers; this seems redundant. I think the machine function observers should be removed?

MachineFunction observers are useful even if instructions are built without MIRBuilders (say using BuildMI) so CSE can be aware of it. Similar for deletions. To me, since the MF observer is always called, the one in MachineIRBuilder seems redundant.

I don't think I would expect CSE or any magic when using BuildMI or generally touching the function. I think anything before selection should be going through MachineIRBuilder?

I also don't see how CSE would work with BuildMI, since you don't see the full set of operands at construction as CSE requires. Even with MachineIRBuilder, you only get CSE if you construct the instruction with all of its operands initially. Trying to handle this for target instructions also generally starts to break down with implicit operands etc.

In D81461#2082624, @dsanders wrote:

LGTM

I'm not sure this is the correct instance to remove; now the visible
ordering is different. Now you will typically see the one erased
instruction message before all the new instructions in order. I think
this is the more logical view of typical legalization changes,
although it's mechanically backwards from the normal
insert-new-erase-old pattern.

Another reason for keeping the one in printNewInstrs() is that createInstr() sees the MI before its populated with operands. I think it's more useful to keep the one that's the fully built instruction

Actually I think this isn't the main source of double printing. The same observer seems to get called twice:
...

Was that with the same MI pointer? I assume it is but the dump doesn't make it clear

I think this is with the same MI pointer.

In D81461#2082557, @aditya_nandakumar wrote:

In D81461#2082149, @arsenm wrote:

It seems both the MachineFunction and MachineIRBuilder have insertion observers; this seems redundant. I think the machine function observers should be removed?

MachineFunction observers are useful even if instructions are built without MIRBuilders (say using BuildMI) so CSE can be aware of it. Similar for deletions. To me, since the MF observer is always called, the one in MachineIRBuilder seems redundant.

I'd lean towards the MachineFunction ones too although admittedly I haven't dug into the details there

In D81461#2082149, @arsenm wrote:

It seems both the MachineFunction and MachineIRBuilder have insertion observers; this seems redundant. I think the machine function observers should be removed?

In D81381#2080552, @arsenm wrote:

In D81381#2080450, @aditya_nandakumar wrote:

The construction APIs for MachineIRBuilder don't make much sense,

What exactly do you mean by this? I agree with the latter about these trivial methods getting in the way.

See D81382. I also think it's a problem that RegBankSelect and other backend users need to construct their own single purpose builders, when the builder is supposed to be maintaining CSE state for example

The construction APIs for MachineIRBuilder don't make much sense,

What exactly do you mean by this? I agree with the latter about these trivial methods getting in the way.

Looks good.

I'm beginning to wonder if maybe it makes sense to put all of these individual tests, in one place instead of being scattered across many tests (considering they're all testing the same thing) so it's easier to find.
Not related to this, but this patch LTGM.

Committed in b91d9ec0bb8

I'll go ahead and get this in (as it already received a LGTM before) - just posted an updated patch since it's been a while since received updates.

Updated based on feedback.
CSEInfo::verify now returns Error which we can assert.