[x86] Backend hangs during CodeGenPrepare due to infinitely sinking cmp expression

[HazyFish]

Description

The backend hangs with the following input during CodeGenPrepare when targeting x86_64 / i386.

Minimal Reproduction

https://godbolt.org/z/373K8TdhM

Code

define i32 @f(i32 %0) {
BB:
  %P0 = alloca i32, i32 8
  %P1 = getelementptr i32, ptr %P0, i32 1
  %B0 = icmp eq i32 %0, 0
  br label %BB1

BB1:                                              ; preds = %BB1, %BB
  %P2 = getelementptr i1, ptr %P1, i1 %B0
  br i1 false, label %BB1, label %BB2

BB2:                                              ; preds = %BB1
  %P3 = select i1 %B0, ptr %P1, ptr %P2
  %L1 = load i32, ptr %P3
  ret i32 %L1
}

Cause

sinkCmpExpression keeps adding code for every CodeGenPrepare iteration so the loop is never broken.

llvm-project/llvm/lib/CodeGen/CodeGenPrepare.cpp

Lines 1674 to 1738 in dacfdbc

	/// Sink the given CmpInst into user blocks to reduce the number of virtual
	/// registers that must be created and coalesced. This is a clear win except on
	/// targets with multiple condition code registers (PowerPC), where it might
	/// lose; some adjustment may be wanted there.
	///
	/// Return true if any changes are made.
	static bool sinkCmpExpression(CmpInst *Cmp, const TargetLowering &TLI) {
	if (TLI.hasMultipleConditionRegisters())
	return false;
	// Avoid sinking soft-FP comparisons, since this can move them into a loop.
	if (TLI.useSoftFloat() && isa<FCmpInst>(Cmp))
	return false;
	// Only insert a cmp in each block once.
	DenseMap<BasicBlock *, CmpInst *> InsertedCmps;
	bool MadeChange = false;
	for (Value::user_iterator UI = Cmp->user_begin(), E = Cmp->user_end();
	UI != E;) {
	Use &TheUse = UI.getUse();
	Instruction *User = cast<Instruction>(*UI);
	// Preincrement use iterator so we don't invalidate it.
	++UI;
	// Don't bother for PHI nodes.
	if (isa<PHINode>(User))
	continue;
	// Figure out which BB this cmp is used in.
	BasicBlock *UserBB = User->getParent();
	BasicBlock *DefBB = Cmp->getParent();
	// If this user is in the same block as the cmp, don't change the cmp.
	if (UserBB == DefBB)
	continue;
	// If we have already inserted a cmp into this block, use it.
	CmpInst *&InsertedCmp = InsertedCmps[UserBB];
	if (!InsertedCmp) {
	BasicBlock::iterator InsertPt = UserBB->getFirstInsertionPt();
	assert(InsertPt != UserBB->end());
	InsertedCmp = CmpInst::Create(Cmp->getOpcode(), Cmp->getPredicate(),
	Cmp->getOperand(0), Cmp->getOperand(1), "",
	&*InsertPt);
	// Propagate the debug info.
	InsertedCmp->setDebugLoc(Cmp->getDebugLoc());
	}
	// Replace a use of the cmp with a use of the new cmp.
	TheUse = InsertedCmp;
	MadeChange = true;
	++NumCmpUses;
	}
	// If we removed all uses, nuke the cmp.
	if (Cmp->use_empty()) {
	Cmp->eraseFromParent();
	MadeChange = true;
	}
	return MadeChange;
	}

Dump of IR for each iteration of CodeGenPrepare:

; Original
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %C4 = icmp eq i32 %L, 0
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %G1 = getelementptr i1, ptr %G3, i1 %C4
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %S = select i1 %C4, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 1
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %S1 = select i1 %1, i1 false, i1 %0
  %S = select i1 %1, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 2
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %S1 = select i1 %2, i1 false, i1 %1
  %S2 = select i1 %2, i1 false, i1 %0
  %S = select i1 %2, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 3
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %3 = icmp eq i32 %L, 0
  %S1 = select i1 %3, i1 false, i1 %2
  %S2 = select i1 %3, i1 false, i1 %1
  %S3 = select i1 %3, i1 false, i1 %0
  %S = select i1 %3, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 4
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %2 = icmp eq i32 %L, 0
  %3 = icmp eq i32 %L, 0
  %4 = icmp eq i32 %L, 0
  %S1 = select i1 %4, i1 false, i1 %3
  %S2 = select i1 %4, i1 false, i1 %2
  %S3 = select i1 %4, i1 false, i1 %1
  %S4 = select i1 %4, i1 false, i1 %0
  %S = select i1 %4, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

[HazyFish]

cc @DataCorrupted

[llvmbot]

@llvm/issue-subscribers-backend-x86

[DataCorrupted]

; Original
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %C4 = icmp eq i32 %L, 0
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %G1 = getelementptr i1, ptr %G3, i1 %C4
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %S = select i1 %C4, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

; Iteration 1
define i32 @f() {
BB:
  %RP = alloca i32, i32 20, align 4
  %L = load i32, ptr %RP, align 4
  %G = getelementptr i32, ptr %RP, i32 1
  %G3 = getelementptr i32, ptr %G, i32 4
  br label %BB3

BB3:                                              ; preds = %BB3, %BB
  %0 = icmp eq i32 %L, 0
  %G1 = getelementptr i1, ptr %G3, i1 %0
  br i1 false, label %BB3, label %BB1

BB1:                                              ; preds = %BB3
  %1 = icmp eq i32 %L, 0
  %S1 = select i1 %1, i1 false, i1 %0
  %S = select i1 %1, ptr %G3, ptr %G1
  %L1 = load i32, ptr %S, align 4
  ret i32 %L1
}

I believe the root cause is that after the first iteration, a new instruction is inserted: %S1 = select i1 %1, i1 false, i1 %0.
S1 is a deadcode, but it used a cmp value in other block, which encouraged the loop to iterate forever.

[DataCorrupted]

Candidate patch: https://reviews.llvm.org/D147041