[SCEVExpander] Recompute poison-generating flags on hoisting. PR57187

[mkazantsev]

Summary

Instruction being hoisted could have nuw/nsw flags inferred from the old
context, and we cannot simply move it to the new location keeping them
because we are going to introduce new uses to them that didn't exist before.

Example in https://github.com/llvm/llvm-project/issues/57187 shows how
this can produce branch by poison from initially well-defined program.

This patch forcefully recomputes poison-generating flag in the new context.

[mkazantsev]

Added context

[mkazantsev]

Rebased (test moved to X86).

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

This seems too pessimistic and unnecessarily drops flags that are not inferred based on the context instruction, e.g. because the original IV already had nuw/nsw.

Would it be possible to preserve the flags valid at entry of the loop when hoisting?

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

We can't do it here. But I guess this is mostly used in IndVars, and we can further strengthen no-wrap flags after this hoisting, if it happened. Didn't try it and don't know the consequences. Can it go as separate patch?

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

After another thought, shouldn't moving the IV be fine by itself? It might generate poison at the earlier location, but that is fine, as long as it is not used before the original location. in a context where poison triggers UB.

Isn't the real issue the code that later replaces uses of the original IV with the hoisted IV? When updating uses, whether all flags can be retained would depend on whether the UB-on-poison user may execute in cases where the original IV increment didn't?

[fhahn]

llvm/test/Transforms/IndVarSimplify/X86/pr57187.ll

39 ↗

(On Diff #453260)

using an addresspace(1) pointer here has the unfortunate side effect that Alive2 cannot handle the code. It would probably be good to remove at least addrspace(1) here and maybe even better to just use a function call as use.

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

Yes, I agree that moving is fine. The bug appears when we introduce a new use (in this case a trunc) to the hoisted IV in a point where the old IV didn't have any uses. I'll try to make a more targeted fix.

llvm/test/Transforms/IndVarSimplify/X86/pr57187.ll

39 ↗

(On Diff #453260)

Ok, I will update the test.

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

Unfortunately, in practice it's undoable. This function may hoist multiple instructions, and then the notion that their flags were context-dependent gets lost. If we dropt flags immediately, we can't figure it out later. I propose to stick to this fix and then try to restore flags when possible.

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

Actually we have all API available here, so let's just heal the flags.

[mkazantsev]

Healed poison flags. It also happened to improve some of the tests. :)

[mkazantsev]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1065

This piece of code replicates similar piece of code in IndVars, I propose refectoring as a separate patch. Now we just need a conceptual agreement on how we fix it.

[mkazantsev]

Ping?

[mkazantsev]

Ping

[nikic]

I'm confused. Why would the nuw be legal in the "old context"? Wouldn't we already branch on poison there as well, because %iv.next is used in %loop.exit.cond is used in br (unconditionally)?

[fhahn]

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

1056

Unfortunately, in practice it's undoable. This function may hoist multiple instructions, and then the notion that their flags were context-dependent gets lost

Yeah this is unfortunate indeed! I still think the right place to fix the flags would be where we actually introduce uses that cause UB on poison, but given the difficulty I guess our best option is doing it here. Could you add a comment explaining why this needs to be done here, even though hoisting in itself isn't a problem.

[nikic]

In D132022#3755012, @nikic wrote:

I'm confused. Why would the nuw be legal in the "old context"? Wouldn't we already branch on poison there as well, because %iv.next is used in %loop.exit.cond is used in br (unconditionally)?

Okay, the missing context here is that we create an additional IV with increment in the dead block and then perform a congruent IV replacement that hoists that increment and introduces uses in a live block.

[mkazantsev]

Ok, let's drop the flags right before introducing a new use.

[mkazantsev]

Made flag recomputation conditional to avoid unexpected impact. Because this logic may hoist multiple instruction, I don't think there is another place where it can easily done.

[nikic]

LGTM

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

2024

posion -> poison

[fhahn]

LGTM thanks!

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

   for (Instruction *I : llvm::reverse(IVIncs)) {
     fixupInsertPoints(I);
     I->moveBefore(InsertPos);
+    // Drop flags that are potentially inferred from old context.
+    I->dropPoisonGeneratingFlags();
   }
   return true;
 }

llvm/test/Transforms/IndVarSimplify/AArch64/widen-loop-comp.ll

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i64 [[INDVARS_IV]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:

 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[STORE_ADDR:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[TMP1]]
 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4

 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0

 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 -1 to i32

 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    invoke void @test14a-callee(i1 [[LOOP_COND]])
 ; CHECK-NEXT:    to label [[LOOP]] unwind label [[EXCEPTION:%.*]]
 ; CHECK:       exit:

 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 -1 to i32

 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 -1 to i32

 ; CHECK-NEXT:    [[LOAD_ADDR:%.*]] = getelementptr i32, i32* [[Q:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    call void @use(i32 -1)

 ; CHECK-NEXT:    [[LOAD_ADDR:%.*]] = getelementptr i32, i32* [[Q:%.*]], i64 [[INDEX]]
 ; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    call void @use(i32 -1)

 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[COND_1:%.*]] = icmp eq i64 [[INDVARS_IV]], 0
 ; CHECK-NEXT:    br i1 [[COND_1]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[INDVARS2:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
 ; CHECK-NEXT:    call void @bar(i32 [[INDVARS2]])
 ; CHECK-NEXT:    call void @foo(i64 [[INDVARS_IV]])

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[INDVARS:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
 ; CHECK-NEXT:    store i32 [[INDVARS]], i32* [[PTR]], align 4
 ; CHECK-NEXT:    call void @foo(i64 [[INDVARS_IV]])

llvm/test/Transforms/IndVarSimplify/X86/eliminate-congruent-ivs.ll

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[INDVARS2:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
 ; CHECK-NEXT:    call void @bar(i32 [[INDVARS2]])
 ; CHECK-NEXT:    call void @foo(i64 [[INDVARS_IV]])

 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[INDVARS:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
 ; CHECK-NEXT:    store i32 [[INDVARS]], i32* [[PTR]], align 4
 ; CHECK-NEXT:    call void @foo(i64 [[INDVARS_IV]])

llvm/test/Transforms/IndVarSimplify/X86/pr35406.ll

 ; CHECK:       loop2.exit.loopexit:
 ; CHECK-NEXT:    br label [[LOOP2_EXIT]]
 ; CHECK:       loop2.exit:
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 false, label [[EXIT]], label [[LOOP1]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i32 0

llvm/test/Transforms/IndVarSimplify/pr57187.ll

 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
 target triple = "x86_64-unknown-linux-gnu"
 
-; FIXME: This test is demonstrating a miscompile. The original program is well-defined,
-; and after opt for any start != 0 branch by poisoned add nuw nsw is introduced.
+; Make sure we do not introduce branch by poisoned value due to incorrect hoisting.
 define void @test(i32 %start) {
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:

 ; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], -1
+; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    [[INDVARS:%.*]] = trunc i64 [[INDVARS_IV_NEXT]] to i32
 ; CHECK-NEXT:    [[LOOP_EXIT_COND:%.*]] = icmp slt i32 [[INDVARS]], 11
 ; CHECK-NEXT:    br i1 [[LOOP_EXIT_COND]], label [[EXIT:%.*]], label [[STUCK_PREHEADER:%.*]]