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.

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

ConstraintElimination: incorrect fold of pointer comparison #49624

Closed
nunoplopes opened this issue May 9, 2021 · 2 comments
Closed

ConstraintElimination: incorrect fold of pointer comparison #49624

nunoplopes opened this issue May 9, 2021 · 2 comments
Labels
bugzilla Issues migrated from bugzilla llvm:optimizations miscompilation

Comments

@nunoplopes
Copy link
Member

nunoplopes commented May 9, 2021 •
edited by fhahn

Bugzilla Link 50280
Version trunk
OS All
CC @fhahn,@MaskRay,@aqjune,@LebedevRI

Extended Description

Test: Transforms/ConstraintElimination/gep-arithmetic.ll

The optimization below is incorrect as it misses one case:
lower < src.end < src < upper < src.step

define i4 @&#8203;ptr_N_signed_positive_assume(* %src, * %lower, * %upper, i16 %N, i16 %step) {
%entry:
  %src.end = gep inbounds * %src, 1 x i16 %N
  %cmp.src.start = icmp ult * %src, %lower
  %cmp.src.end = icmp uge * %src.end, %upper
  %N.neg = icmp slt i16 %N, 0
  assume i1 %N.neg
  %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end
  br i1 %or.precond.0, label %trap.bb, label %step.check

%step.check:
  %step.pos = icmp uge i16 %step, 0
  %step.ult.N = icmp ult i16 %step, %N
  %and.step = and i1 %step.pos, %step.ult.N
  br i1 %and.step, label %ptr.check, label %exit

%ptr.check:
  %src.step = gep inbounds * %src, 1 x i16 %step
  %cmp.step.start = icmp ult * %src.step, %lower
  %cmp.step.end = icmp uge * %src.step, %upper
  %or.check = or i1 %cmp.step.start, %cmp.step.end
  br i1 %or.check, label %trap.bb, label %exit

%exit:
  ret i4 3

%trap.bb:
  ret i4 2
}
=>
define i4 @&#8203;ptr_N_signed_positive_assume(* %src, * %lower, * %upper, i16 %N, i16 %step) {
%entry:
  %src.end = gep inbounds * %src, 1 x i16 %N
  %cmp.src.start = icmp ult * %src, %lower
  %cmp.src.end = icmp uge * %src.end, %upper
  %N.neg = icmp slt i16 %N, 0
  assume i1 %N.neg
  %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end
  br i1 %or.precond.0, label %trap.bb, label %step.check

%step.check:
  %step.pos = icmp uge i16 %step, 0
  %step.ult.N = icmp ult i16 %step, %N
  %and.step = and i1 %step.pos, %step.ult.N
  br i1 %and.step, label %ptr.check, label %exit

%ptr.check:
  %src.step = gep inbounds * %src, 1 x i16 %step
  %cmp.step.start = icmp ult * %src.step, %lower
  %cmp.step.end = icmp uge * %src.step, %upper
  %or.check = or i1 0, 0
  br i1 %or.check, label %trap.bb, label %exit

%exit:
  ret i4 3

%trap.bb:
  ret i4 2
}
Transformation doesn't verify!
ERROR: Value mismatch

Example:
* %src = pointer(non-local, block_id=1, offset=229377)
* %lower = pointer(non-local, block_id=0, offset=-393217)
* %upper = pointer(non-local, block_id=0, offset=-419450)
i16 %N = #x9014 (36884, -28652)
i16 %step = #x100d (4109)

Source:
* %src.end = pointer(non-local, block_id=1, offset=200725)
i1 %cmp.src.start = #x0 (0)
i1 %cmp.src.end = #x0 (0)
i1 %N.neg = #x1 (1)
i1 %or.precond.0 = #x0 (0)
i1 %step.pos = #x1 (1)
i1 %step.ult.N = #x1 (1)
i1 %and.step = #x1 (1)
* %src.step = pointer(non-local, block_id=1, offset=233486)
i1 %cmp.step.start = #x0 (0)
i1 %cmp.step.end = #x1 (1)
i1 %or.check = #x1 (1)

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 >	size: 0	align: 1	alloc type: 0	address: 0
Block 1 >	size: 524288	align: 4	alloc type: 0	address: 425988
Block 2 >	size: 100654	align: 8589934592	alloc type: 0	address: 263504
Block 3 >	size: 230832	align: 8589934592	alloc type: 0	address: 29184

Target:
* %src.end = pointer(non-local, block_id=1, offset=200725)
i1 %cmp.src.start = #x0 (0)
i1 %cmp.src.end = #x0 (0)
i1 %N.neg = #x1 (1)
i1 %or.precond.0 = #x0 (0)
i1 %step.pos = #x1 (1)
i1 %step.ult.N = #x1 (1)
i1 %and.step = #x1 (1)
* %src.step = pointer(non-local, block_id=1, offset=233486)
i1 %cmp.step.start = #x0 (0)
i1 %cmp.step.end = #x1 (1)
i1 %or.check = #x0 (0)
Source value: #x2 (2)
Target value: #x3 (3)
@llvmbot llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021
@nunoplopes
Copy link
Member Author

I think the testcase in Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll exposes a similar issue.

See the counterexample below. I think the issue is that it ignores that gep sign-extends the argument.
At the %loop.body.1 BB we know that:
src u>= lower && (src+sext(N)) u< upper

And then this expression
src+1 u< lower || src+1 >= upper
gets (incorrectly) optimized to:
src+1 u< lower || false

define void @test1(* %src, * noundef %lower, * noundef %upper, i8 %N) {
%entry:
  %src.end = gep inbounds * %src, 1 x i8 %N
  %cmp.src.start = icmp ult * %src, noundef %lower
  %cmp.src.end = icmp uge * %src.end, noundef %upper
  %or.0 = or i1 %cmp.src.start, %cmp.src.end
  br i1 %or.0, label %trap.bb, label %loop.header

%loop.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %ec = icmp uge i8 %iv, %N
  br i1 %ec, label %exit, label %loop.body

%exit:
  ret void

%loop.body:
  %src.iv = gep inbounds * %src, 1 x i8 %iv
  %cmp.iv.start = icmp ult * %src.iv, noundef %lower
  %cmp.iv.end = icmp uge * %src.iv, noundef %upper
  %or.1 = or i1 %cmp.iv.start, %cmp.iv.end
  br i1 %or.1, label %trap.bb, label %loop.body.1

%loop.body.1:
  %ptr.src.iv = bitcast * %src.iv to *
  store i32 0, * %ptr.src.iv, align 4
  %add.1 = add nsw nuw i8 %iv, 1
  %src.iv.1 = gep inbounds * %src, 1 x i8 %add.1
  %cmp.iv.1.start = icmp ult * %src.iv.1, noundef %lower
  %cmp.iv.1.end = icmp uge * %src.iv.1, noundef %upper
  %or.2 = or i1 %cmp.iv.1.start, %cmp.iv.1.end
  br i1 %or.2, label %trap.bb, label %loop.body.2

%loop.body.2:
  %ptr.src.iv.1 = bitcast * %src.iv.1 to *
  store i32 0, * %ptr.src.iv.1, align 4
  %add.2 = add nsw nuw i8 %iv, 2
  %src.iv.2 = gep inbounds * %src, 1 x i8 %add.2
  %cmp.iv.2.start = icmp ult * %src.iv.2, noundef %lower
  %cmp.iv.2.end = icmp uge * %src.iv.2, noundef %upper
  %or.3 = or i1 %cmp.iv.2.start, %cmp.iv.2.end
  br i1 %or.3, label %trap.bb, label %loop.latch

%loop.latch:
  %ptr.src.iv.2 = bitcast * %src.iv.2 to *
  store i32 0, * %ptr.src.iv.2, align 4
  %iv.next = add nsw nuw i8 %iv, 1
  br label %loop.header

%trap.bb:
  ret void
}
=>
define void @test1(* %src, * noundef %lower, * noundef %upper, i8 %N) {
%entry:
  %src.end = gep inbounds * %src, 1 x i8 %N
  %cmp.src.start = icmp ult * %src, noundef %lower
  %cmp.src.end = icmp uge * %src.end, noundef %upper
  %or.0 = or i1 %cmp.src.start, %cmp.src.end
  br i1 %or.0, label %trap.bb, label %loop.header

%loop.header:
  %iv = phi i8 [ 0, %entry ], [ %iv.next, %loop.latch ]
  %ec = icmp uge i8 %iv, %N
  br i1 %ec, label %exit, label %loop.body

%exit:
  ret void

%loop.body:
  %src.iv = gep inbounds * %src, 1 x i8 %iv
  %cmp.iv.start = icmp ult * %src.iv, noundef %lower
  %cmp.iv.end = icmp uge * %src.iv, noundef %upper
  %or.1 = or i1 %cmp.iv.start, 0
  br i1 %or.1, label %trap.bb, label %loop.body.1

%loop.body.1:
  %ptr.src.iv = bitcast * %src.iv to *
  store i32 0, * %ptr.src.iv, align 4
  %add.1 = add nsw nuw i8 %iv, 1
  %src.iv.1 = gep inbounds * %src, 1 x i8 %add.1
  %cmp.iv.1.start = icmp ult * %src.iv.1, noundef %lower
  %cmp.iv.1.end = icmp uge * %src.iv.1, noundef %upper
  %or.2 = or i1 0, 0
  br i1 %or.2, label %trap.bb, label %loop.body.2

%loop.body.2:
  %ptr.src.iv.1 = bitcast * %src.iv.1 to *
  store i32 0, * %ptr.src.iv.1, align 4
  %add.2 = add nsw nuw i8 %iv, 2
  %src.iv.2 = gep inbounds * %src, 1 x i8 %add.2
  %cmp.iv.2.start = icmp ult * %src.iv.2, noundef %lower
  %cmp.iv.2.end = icmp uge * %src.iv.2, noundef %upper
  %or.3 = or i1 0, %cmp.iv.2.end
  br i1 %or.3, label %trap.bb, label %loop.latch

%loop.latch:
  %ptr.src.iv.2 = bitcast * %src.iv.2 to *
  store i32 0, * %ptr.src.iv.2, align 4
  %iv.next = add nsw nuw i8 %iv, 1
  br label %loop.header

%trap.bb:
  ret void
}
Transformation doesn't verify!
ERROR: Source is more defined than target

Example:
* %src = pointer(non-local, block_id=1, offset=529)
* noundef %lower = pointer(non-local, block_id=0, offset=83)
* noundef %upper = pointer(non-local, block_id=0, offset=487)
i8 %N = #x80 (128, -128)

Source:
* %src.end = pointer(non-local, block_id=1, offset=401)
i1 %cmp.src.start = #x0 (0)
i1 %cmp.src.end = #x0 (0)
i1 %or.0 = #x0 (0)
  >> Jump to %loop.header
i8 %iv = #x00 (0)
i1 %ec = #x0 (0)
  >> Jump to %loop.body
* %src.iv = pointer(non-local, block_id=1, offset=529)
i1 %cmp.iv.start = #x0 (0)
i1 %cmp.iv.end = #x1 (1)
i1 %or.1 = #x1 (1)
  >> Jump to %trap.bb

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 >	size: 0	align: 4	alloc type: 0	address: 0
Block 1 >	size: 2048	align: 2	alloc type: 0	address: 64

Target:
* %src.end = pointer(non-local, block_id=1, offset=401)
i1 %cmp.src.start = #x0 (0)
i1 %cmp.src.end = #x0 (0)
i1 %or.0 = #x0 (0)
  >> Jump to %loop.header
i8 %iv = #x00 (0)
i1 %ec = #x0 (0)
  >> Jump to %loop.body
* %src.iv = pointer(non-local, block_id=1, offset=529)
i1 %cmp.iv.start = #x0 (0)
i1 %cmp.iv.end = #x1 (1)
i1 %or.1 = #x0 (0)
  >> Jump to %loop.body.1
* %ptr.src.iv = pointer(non-local, block_id=1, offset=529)
void = UB triggered!

@fhahn
Copy link
Contributor

fhahn commented Feb 4, 2022

Thanks for the report! The issue was that it incorrectly assumed GEP indices are signed positive. The code was missing a corresponding pre-condition. That should be fixed in 06f3ef6

@fhahn fhahn closed this as completed Feb 4, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bugzilla Issues migrated from bugzilla llvm:optimizations miscompilation
Projects
None yet
Milestone
No milestone
Development

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