[SimplifyCFG] SimplifyCFG does not eliminate the UB branch after inlining

[dianqk]

I tried the following IR:

define internal ptr @bar(ptr %arg, i1 %arg1) {
bb:
  br i1 %arg1, label %bb4, label %bb2

bb2:
  %i = load ptr, ptr %arg, align 8
  %i3 = getelementptr inbounds i8, ptr %i, i64 1
  store ptr %i3, ptr %arg, align 8
  br label %bb4

bb4:
  %i5 = phi ptr [ %i, %bb2 ], [ null, %bb ]
  ret ptr %i5
}

define i32 @foo(ptr %arg, i1 %arg1) {
bb:
  %i = call ptr @bar(ptr %arg, i1 %arg1)
  %i2 = icmp ne ptr %i, null
  call void @llvm.assume(i1 %i2)
  %i3 = load i32, ptr %i, align 4
  ret i32 %i3
}

declare void @llvm.assume(i1)

We can eliminate the branch, but it doesn't. To my surprise, re-executing the output once simplifycfg eliminates this branch: https://llvm.godbolt.org/z/85zKbMdxe.

I've noticed that the user order is different after inlining and reading the text IR. See: #98799 (comment).

The passingValueIsAlwaysUndefined only considers the first user:

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

Lines 7567 to 7577 in 92f4001

	static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I, bool PtrValueMayBeModified) {
	Constant *C = dyn_cast<Constant>(V);
	if (!C)
	return false;
	if (I->use_empty())
	return false;
	if (C->isNullValue() || isa<UndefValue>(C)) {
	// Only look at the first use, avoid hurting compile time with long uselists
	auto *Use = cast<Instruction>(*I->user_begin());

Of course there are many ways to solve this problem, for example:

1. Handle all users
2. Choose an instruction that passingValueIsAlwaysUndefined can handle (I'd go with this one first.)
3. Support assume(%p == null)

But my biggest concern here is whether the user order needs to be consistent. I don't like it when an optimization happens randomly.

[dianqk]

I think I know why the order of uses is different. Refer to: ef55a1a. All uses are added to the front, so when reading the textual IR, this order is the reverse of the instruction order, and it reverses again during inlining.
I'm not sure how to fix it. Perhaps we need a method to sort them according to the instruction order?