[InstCombine] Taking an order of magnitude longer in 12.0.0 than in 10.0.0 for some examples.

[mcandress]

Bugzilla Link	50155
Resolution	FIXED
Resolved on	Jun 14, 2021 16:23
Version	unspecified
OS	Linux
Blocks	#48661
Attachments	gzipped ir module exhibiting much slower InstCombine optimization pass.
CC	@aqjune,@RKSimon,@nikic,@rotateright,@tstellar
Fixed by commit(s)	2cd7868 ce77909

Extended Description

For some functions, the --instcombine optimization takes excessively longer with llvm 12.0.0 than it does with llvm 10.0.0.

In the attached example, a run of "opt -o=out.o --instcombine test_instcomb.ir" takes 53 seconds, where it used to take around 2 seconds when version 10.0.0 was used (albeit version 12.0.0 combines more instructions).

Is there a way to mitigate this speed performance degradation when using the library interface (i.e. from C++ library API, not from the opt tool)?

[nikic]

Looks like most of the time is spent in isGuaranteedNotToBeUndefOrPoison() -> programUndefinedIfUndefOrPoison().

[nikic]

llvm-project/llvm/lib/Analysis/ValueTracking.cpp

Lines 5392 to 5401 in 74d9a76

	for (auto &I : make_range(Begin, End)) {
	SmallPtrSet<const Value *, 4> WellDefinedOps;
	getGuaranteedWellDefinedOps(&I, WellDefinedOps);
	for (auto *Op : WellDefinedOps) {
	if (Op == V)
	return true;
	}
	if (!isGuaranteedToTransferExecutionToSuccessor(&I))
	break;
	}

performs an instruction scan from the instruction to the end of the block. The test case contains one very large basic block, so this scan ends up looking at approximately 100000 instructions. This obviously needs a limit.

[nikic]

Fixed on main by 2cd7868.

This should probably be backported to LLVM 12.0.1. I don't believe there is any way you can work around this.

[tstellar]

Fixed on main by
https://github.com/llvm/llvm-project/commit/
2cd7868.

This should probably be backported to LLVM 12.0.1. I don't believe there is
any way you can work around this.

Was there a pre-commit review for this patch?

[tstellar]

I couldn't find a phabricator review for this, so I would like to have someone else review it before it is backported.

[aqjune]

I'm the main author of the function programUndefinedIfUndefOrPoison and the change looks good to me.

[tstellar]

I'm the main author of the function programUndefinedIfUndefOrPoison and the
change looks good to me.

Thank you.

[tstellar]

The fix does not apply cleanly, could someone backport this and push a branch to their local github fork?

[aqjune]

Would aqjune@89d5009 be okay?

[tstellar]

Merged: ce77909