The patch currently implements variant 1 form the paper (TDMSC-I) as it is slightly simpler. I will follow up with variant 2 (TDMSC-II) in a bit and do some more detailed compile time measurement. Also the only reason MergeSets live in IteratedDominanceFrontier.h/cpp was convenience, they could be moved to their own files.

Sounds good to me, I'll move the code to LCSSA without DT checks. Thanks!

In D57033#1366842, @efriedma wrote:

If LCSSA just doesn't care that it's creating dead references to variables instead of undefs, it would be faster to completely skip the check. Otherwise, sure, that makes sense.

In D57033#1365676, @efriedma wrote:

SSAUpdater has code to insert undef in certain cases. Can you prove those cases don't apply to all callers of GetValueAtEndOfBlock?

In D56921#1363424, @davide wrote:

Just please make sure to run stage3 build and verify this doesn't break.

state explicitly that sub-loops must be in LCSSA form already for formLCSSA()

Fix typo.

Update places to use getMaxNumOperands, add more context to description.

updated to use SDNode::getMaxNumOperands

update to use getTokenFactor.

In D56739#1359828, @RKSimon wrote:

@fhahn Are you intending to look at the similar SDNode::NumValues limit? PR7250 + PR37000 ?

Thanks Eli, changed to getTokenFactor.

In D56738#1358379, @lebedev.ri wrote:

Can any test case be added here, or would it be just too big to realistically test?

Committed in rL351187, thanks!

Thanks, added check for ConstantExpr.

LGTM, thanks! Please wait a bit with committing, in case anybody else has additional comments.

LGTM, thanks! It would be great if you could extend the test cases a bit more before committing, covering cases with shifted regs and cases where some SUs have multiple successors and not all of them should be fused.

Requesting changes as additional info on the bzip and PDF regressions is needed.

Jessica, are you still planing on pushing this change? :)

The AArch64 side LGTM. Also adding Oliver and Sjoerd as they worked on FP16 side as well, in case they have any thoughts.

In D47949#1292403, @trentxintong wrote:

Thanks for the change @fhahn. I will dig up my test case and run it.

In D56572#1354350, @evandro wrote:

In D56572#1354333, @fhahn wrote:

Would it be possible to have a MIR test here, which just runs the scheduler?

I tried to keep the existing pattern, but I could add one too. Should it be done now or later?

Diego, are you still planning to land this patch?

Marking this as requiring changes, as the MachinePipeliner code is getting refactored a bit in D56084. Please let us know when you want us to review the patch again.

In D56135#1347626, @m4yers wrote:

In D56135#1343674, @fhahn wrote:

Are there any instances in the current codebase where this would be useful?

For example X86InstrInfo::AnalyzeBranchImpl can be rewritten with more natural reverse iterators.

Would it be possible to have a MIR test here, which just runs the scheduler?

In D56406#1350562, @arsenm wrote:

LGTM

In D56406#1348948, @fhahn wrote:

LGTM, thanks, but it would be good if someone more familiar with AMDGPU could also have a quick look.

Can you commit a regression testcase for this?

It might be good to mention those guidelines explicitly here https://llvm.org/docs/Contributing.html#how-to-submit-a-patch.

The bot is back to passing after reverting: http://green.lab.llvm.org/green/job/clang-stage1-configure-RA/52757/. Please let me know if you have trouble reproducing the failure.

One of the errors with TSan and this patch on macOS is the following while running binaries compiled with TSan:

It looks like this patch may have broken some bots on green dragon, e.g lots of ThreadSanitizer and UBSan-ThreadSanitizer-x86_64 tests stared failing after this went in: http://green.lab.llvm.org/green/job/clang-stage1-configure-RA/52725/

I am seeing lldb-cmake failing again, with the same error as with this patch earlier: http://green.lab.llvm.org/green/job/lldb-cmake/16557/

LGTM, thanks, but it would be good if someone more familiar with AMDGPU could also have a quick look.

Great thanks! IMO the caller of ShrinkDemandedConstant should make sure the demanded bits valid for all users, as the existing code in TargetLowering.cpp already should do.

I am seeing a regression with this change on AArch64, where we do not use shrinked constants, e.g. for and/or if they have multiple users. I am not entirely sure what the problem is this patch is solving, as I am not familiar with AMDGPU. Is it a case where shrinking the constant leads to shrinking the related Op and in the end this introduces unnecessary conversion code, as multiple users require different bitwidths?

In D38501#1346325, @hfinkel wrote:

In D38501#1346193, @fhahn wrote:

Thanks! Do you need someone to commit the change on your behalf?

He does. I'm planning to do it this morning, but if you do it first, that's fine too :-)

Thanks! Do you need someone to commit the change on your behalf?

Thanks for the patch! I plan to have a closer look in the next few days.

Looks like the patch has just been reverted in rL350345. Please let me know if you have problems reproducing the failure.

It looks like this commit breaks the lldb-cmake bot again, with the following error (http://green.lab.llvm.org/green/job/lldb-cmake/16085/consoleFull#-15612593049ba4694-19c4-4d7e-bec5-911270d8a58c) :

Are there any instances in the current codebase where this would be useful?

Updated to just use Defs = [CPSR], as suggested by Eli.

Reduced patch to just add CPSR to live-ins of newly created blocks, if required.

In D55909#1338092, @efriedma wrote:

The interesting constraint here is that ExpandISelPesudos runs immediately after ISel. And if you have an instruction which produces physical registers from an allocatable register class, ISel will COPY the values to virtual registers immediately after that instruction (and similarly for instructions that consume physical registers). So in practice, on ARM, the only physical register with a non-trivial live interval in ExpandISelPesudos is CPSR.

Granted, that's a bit fragile, and it isn't formally enforced anywhere.

In D55909#1338002, @efriedma wrote:

I'm a little concerned computeAndAddLiveIns is more expensive than checkAndUpdateCPSRKill. In theory, they're both quadratic, but in practice I would expect checkAndUpdateCPSRKill is much cheaper: it only tracks one register, and quits immediately when it finds a def of CPSR.

Use LivePhysRegs for liveins computation, pushed code to ARMISelLowering, handled all cases I could spot there. Adding Eli, as he fixed a similar problem in D54192, which I think should also be handled by the general liveins computation.

Rename to PossiblySafeWithRtChecks and FoundNonConstantDistanceDependence.

In D55538#1336581, @efriedma wrote:

I don't understand the implications of returning false here...

I'd like to see a general plan for eventually excising the use of "int" from all the interleaving code before we start making changes here, so it's clear we're heading in the right direction.