IndVars creates an invalid phi node after r367485

[llvmbot]

Bugzilla Link	45835
Resolution	FIXED
Resolved on	Jun 17, 2020 15:42
Version	trunk
OS	Windows NT
Blocks	#44654
Reporter	LLVM Bugzilla Contributor
CC	@efriedma-quic,@fhahn,@froydnj,@LebedevRI,@preames,@nikic,@tstellar
Fixed by commit(s)	b2df961 4d0626a

Extended Description

https://godbolt.org/z/Me95yj

After r367485/llvmorg-10-init-991-gf8e7b536571, this phi node:
%a.mux.lcssa4 = phi i8* [ %a.mux, %switch.early.test.i ], [ %a.mux, %switch.early.test.i ], [ %a.mux, %cond.end ]

becomes
%a.mux.lcssa4 = phi i8* [ %a.mux, %switch.early.test.i ], [ %scevgep, %switch.early.test.i ], [ %scevgep, %cond.end ]

which has two different values for %switch.early.test.i.

This started out as an investigation of a clang hang in LICM (full repro available on request) but this phi node is the first place that the verifier started complaining, so I assume the rest is GIGO from there.

The bad phi is no longer seen after llvmorg-11-init-4213-gd6f47aeb519, but as that is a cost model patch, I assume it's not really a fix but just an avoidance.

[nikic]

Link to referenced revision: f8e7b53

[llvmbot]

Shorter repro: https://godbolt.org/z/ypwWWr

The highlighted phi node has two (identical) values from the same BB, but the first is considered HighCost and the second is not. Therefore we skip rewriting the first but do rewrite the second:

llvm-project/llvm/lib/Transforms/Utils/LoopUtils.cpp

Lines 1412 to 1417 in 616657b

	// Only do the rewrite when the ExitValue can be expanded cheaply.
	// If LoopCanBeDel is true, rewrite exit value aggressively.
	if (ReplaceExitValue == OnlyCheapRepl && !LoopCanBeDel && Phi.HighCost) {
	DeadInsts.push_back(ExitVal);
	continue;
	}

To double check this, I confirmed that the phi remains valid under both of --replexitval={always,never}.

So, what to do? Any thoughts on...

• Scan for multiple values and skip them all if any are high cost?
• Scan for multiple values and rewrite them all if any are low cost?
• This mixed situation shouldn't have happened in the first place, the real problem is upstream from this?

[llvmbot]

For anyone curious where the different values of HighCost come from...

When we're recursively looking at the second NAry operand [0] of the first value, that operand is considered high cost due to [1]:

if (isa(S))
return true;

When we're looking at the second NAry operand of the second value, it is considered low cost due to [2]:

// If we can find an existing value for this scev available at the point "At"
// then consider the expression cheap.
if (At && getRelatedExistingExpansion(S, At, L))
return false;

[0] https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/ScalarEvolutionExpander.cpp#L2198-L2205
[1] https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/ScalarEvolutionExpander.cpp#L2193-L2196
[2] https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/ScalarEvolutionExpander.cpp#L2135-L2138

[llvmbot]

In IRC, LebedevRI wondered what kind of code generates such phi nodes. This comes from the pointer-overflow sanitizer. We have a line of C that does ptr += 8 and the sanitizer wants to insert if (-7 <= ptr <= 0) { abort(); }. It ends up becoming a strange switch:

switch.early.test141.i: ; preds = %cont9.i
switch i64 %247, label %cleanup.thread.i [
i64 -1, label %handler.pointer_overflow11.i
i64 -2, label %handler.pointer_overflow11.i
i64 -3, label %handler.pointer_overflow11.i
i64 -4, label %handler.pointer_overflow11.i
i64 -5, label %handler.pointer_overflow11.i
i64 -6, label %handler.pointer_overflow11.i
i64 -7, label %handler.pointer_overflow11.i
i64 0, label %handler.pointer_overflow11.i
], !dbg !​1924

handler.pointer_overflow11.i: ; preds = %switch.early.test141.i [...SNIP...], %cont9.i
%add.ptr96.lcssa4889 = phi i8* [ %add.ptr96, %switch.early.test141.i ], [ %add.ptr96, %switch.early.test141.i ], [...SNIP...] !dbg !​1913

[llvmbot]

Proposed patch: https://reviews.llvm.org/D79720

[LebedevRI]

Proposed patch: https://reviews.llvm.org/D79720

Alternative patch: https://reviews.llvm.org/D79787

[LebedevRI]

Landed in b2df961.
Needs cherry-picking into stable.
There's potential (but now-outdated) cherry-pick diff in https://reviews.llvm.org/D79787#2031793

[llvmbot]

Thanks again!

Here's an updated version of the diff against release/10.x: https://reviews.llvm.org/P8223

[tstellar]

Merged: 4d0626a