`a & ~(a - b)` optimizes to `a & (~a + b)` even though most targets have an `ANDN` instruction

[Validark]

Godbolt link

#include <stdint.h>

uint64_t foo(uint64_t a, uint64_t b) {
    return a & ~(a - b);
}

Optimized LLVM IR:

define dso_local i64 @foo(i64 %0, i64 %1) local_unnamed_addr {
Entry:
  %2 = xor i64 %0, -1
  %3 = add i64 %2, %1
  %4 = and i64 %3, %0
  ret i64 %4
}

Should be: (llc godbolt)

define dso_local i64 @foo(i64 %0, i64 %1) local_unnamed_addr {
Entry:
  %2 = sub i64 %0, %1
  %3 = xor i64 %2, -1
  %4 = and i64 %3, %0
  ret i64 %4
}

[dtcxzyw]

Alive2: https://alive2.llvm.org/ce/z/Z94_Lw
InstCombine canonicalizes ~(X - Y) -> ~X + Y to break dependency:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Lines 4632 to 4636 in 383e5f3

	// ~(X - Y) --> ~X + Y
	// FIXME: is it really beneficial to sink the `not` here?
	if (match(NotVal, m_Sub(m_Value(X), m_Value(Y))))
	if (isa<Constant>(X) || NotVal->hasOneUse())
	return BinaryOperator::CreateAdd(Builder.CreateNot(X), Y);

It would be better to perform this optimization in DAGCombiner since TLI.hasAndNot is available in codegen.

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Niles Salter (Validark)

[Godbolt link](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:2,lang:___c,selection:(endColumn:1,endLineNumber:6,positionColumn:1,positionLineNumber:6,selectionStartColumn:1,selectionStartLineNumber:6,startColumn:1,startLineNumber:6),source:'%23include+%3Cstdint.h%3E%0A%0Auint64_t+foo(uint64_t+a,+uint64_t+b)+%7B%0A++++return+a+%26+~(a+-+b)%3B%0A%7D%0A'),l:'5',n:'0',o:'C+source+%232',t:'0')),header:(),k:51.42491978027955,l:'4',m:100,n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cclang_trunk,filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1',verboseDemangling:'0'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:3,lang:___c,libs:!(),options:'-O3+-march%3Dznver5',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:2),l:'5',n:'0',o:'+x86-64+clang+(trunk)+(Editor+%232)',t:'0')),header:(),k:48.57508021972046,l:'4',m:100,n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)

#include <stdint.h>

uint64_t foo(uint64_t a, uint64_t b) {
    return a & ~(a - b);
}

Optimized LLVM IR:

define dso_local i64 @<!-- -->foo(i64 %0, i64 %1) local_unnamed_addr {
Entry:
  %2 = xor i64 %0, -1
  %3 = add i64 %2, %1
  %4 = and i64 %3, %0
  ret i64 %4
}

Should be: (llc godbolt)

define dso_local i64 @<!-- -->foo(i64 %0, i64 %1) local_unnamed_addr {
Entry:
  %2 = sub i64 %0, %1
  %3 = xor i64 %2, -1
  %4 = and i64 %3, %0
  ret i64 %4
}

[dtcxzyw]

BTW, this pattern can be generalized into a bitwiseop (~b + c) -> a bitwiseop ~(b - c).

[simonzgx]

I'd like to work on this.