Skip to content

Missed optimization in InstCombine: replace usub with or #56926

Closed
@chfast

Description

@chfast
Member

When you have usub instructions chained by overflow (borrow) flag (e.g. for big integer "less than") you can replace all except one usubs with or.

define i1 @src(i64 %0, i64 %1, i1 %2) {
  %4 = zext i1 %2 to i64
  %5 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %0, i64 %4)
  %6 = extractvalue { i64, i1 } %5, 1
  %7 = zext i1 %6 to i64
  %8 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %1, i64 %7)
  %9 = extractvalue { i64, i1 } %8, 1
  ret i1 %9
}

define i1 @tgt(i64 %0, i64 %1, i1 %2) {
  %4 = or i64 %1, %0
  %5 = zext i1 %2 to i64
  %6 = call { i64, i1 } @llvm.usub.with.overflow.i64(i64 %4, i64 %5)
  %7 = extractvalue { i64, i1 } %6, 1
  ret i1 %7
}

declare { i64, i1 } @llvm.usub.with.overflow.i64(i64, i64)

https://alive2.llvm.org/ce/z/yhrBrK

Activity

nikic

nikic commented on Aug 4, 2022

@nikic
Contributor

usub.with.overflow where only the overflow result is used should just be replaced with an icmp.

chfast

chfast commented on Aug 5, 2022

@chfast
MemberAuthor

usub.with.overflow where only the overflow result is used should just be replaced with an icmp.

This make sense, although I think this will move us to this bug where subtraction is changed to comparison and in the end the codegen is not able to generate optional sbb instructions: #53432.

rotateright

rotateright commented on Aug 9, 2022

@rotateright
Contributor

926e731 - both examples should now canonicalize to the same IR:

define i1 @src(i64 %0, i64 %1, i1 %2) {
  %4 = or i64 %1, %0
  %5 = icmp eq i64 %4, 0
  %6 = and i1 %5, %2
  ret i1 %6
}

We should deal with x86 codegen problems independently of that. Repurpose this bug for that or open a new one?

chfast

chfast commented on Aug 9, 2022

@chfast
MemberAuthor

I think this is very good solution for the particular problem. I will play with this once Compiler Explorer is updated.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @nikic@chfast@EugeneZelenko@rotateright

        Issue actions

          Missed optimization in InstCombine: replace usub with or · Issue #56926 · llvm/llvm-project