Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

IRCE introduces UB by changing order of condition checks #57523

Open
nunoplopes opened this issue Sep 2, 2022 · 3 comments
Open

IRCE introduces UB by changing order of condition checks #57523

nunoplopes opened this issue Sep 2, 2022 · 3 comments
Labels
loopoptim miscompilation

Comments

@nunoplopes
Copy link
Member

IRCE reorders order of condition checks. For example see this minimized test case from IRCE/bad_expander.ll:

define void @test_03(i1 %maybe_exit, i64 %num) {
entry:
  br label %loop

loop:
  %iv = phi i64 [ 0, %entry ], [ %iv.next, %guarded ]
  %iv.next = add i64 %iv, 1
  br i1 %maybe_exit, label %range_check, label %exit

range_check:
  %rc = icmp slt i64 %iv.next, %num
  br i1 %rc, label %guarded, label %exit

guarded:
  %dummy = add i64 %iv.next, 0
  %tmp7 = icmp slt i64 %iv.next, 42
  br i1 %tmp7, label %loop, label %exit

exit:
  ret void
}

If %maybe_exit is false, the function returns straight away.
However, IRCE gives us this:

entry:
  %0 = add i64 %num, -9223372036854775807
  %smax = call i64 @llvm.smax.i64(i64 %0, i64 1)
  %1 = sub i64 %num, %smax
  %smin = call i64 @llvm.smin.i64(i64 %num, i64 0)
  %smax1 = call i64 @llvm.smax.i64(i64 %smin, i64 -1)
  %2 = add nsw i64 %smax1, 1
  %3 = mul i64 %1, %2
  %smin2 = call i64 @llvm.smin.i64(i64 %3, i64 42)
  %exit.mainloop.at = call i64 @llvm.smax.i64(i64 %smin2, i64 0)
  %4 = icmp slt i64 0, %exit.mainloop.at
  br i1 %4, label %loop.preheader, label %main.pseudo.exit

loop.preheader:
  br label %loop

loop:
  %iv = phi i64 [ %iv.next, %guarded ], [ 0, %loop.preheader ]
  %iv.next = add i64 %iv, 1
  %rc = icmp slt i64 %iv.next, %num
  %or.cond = select i1 %maybe_exit, i1 true, i1 false
  br i1 %or.cond, label %guarded, label %exit.loopexit4

So we branch first on a value derived from %num. If that's poison, we end up triggering UB.
Either the condition or the variables used by the hoisted condition must be frozen.

cc @max-quazan @nikic @serguei-katkov
@fhahn
Copy link
Contributor

fhahn commented Sep 2, 2022

@nunoplopes Do you know if this a recent regression?

@nunoplopes
Copy link
Member Author

@nunoplopes Do you know if this a recent regression?

No, it's not recent. It has been there since the early days of the pass AFAICT.
Alive2 didn't detect the problem earlier because the pass introduces metadata. Your patch to Alive2 exposed this bug.

@xortator
Copy link
Contributor

Thanks for report, it looks like another case of messing with poison we've earlier found in other passes. Need to understand what to do with it.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
loopoptim miscompilation
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@fhahn @nunoplopes @xortator