[Analysis] Move `DomConditionCache::findAffectedValues` to a new file; NFC

[ValueTracking] Compute knownbits for `(and/or cond0, cond1)` on both sides of branch

The false branch for `and` and true branch for `or` provide less
information (intersection as opposed to union),

[ValueTracking] Compute knownbits for `(and/or cond0, cond1)` on both sides of branch

The false branch for `and` and true branch for `or` provide less
information (intersection as opposed to union), but still can give
some useful information.

Closes #82818

show more ...

[ValueTracking] Compute known FPClass from signbit idiom (#80740)

This patch improves `computeKnownFPClass` by using context-sensitive
information from `DomConditionCache`.
The motivation of this

[ValueTracking] Compute known FPClass from signbit idiom (#80740)

This patch improves `computeKnownFPClass` by using context-sensitive
information from `DomConditionCache`.
The motivation of this patch is to optimize the following case found in
[fmt/format.h](https://github.com/fmtlib/fmt/blob/e17bc67547a66cdd378ca6a90c56b865d30d6168/include/fmt/format.h#L3555-L3566):
```
define float @test(float %x, i1 %cond) {
%i32 = bitcast float %x to i32
%cmp = icmp slt i32 %i32, 0
br i1 %cmp, label %if.then1, label %if.else

if.then1:
%fneg = fneg float %x
br label %if.end

if.else:
br i1 %cond, label %if.then2, label %if.end

if.then2:
br label %if.end

if.end:
%value = phi float [ %fneg, %if.then1 ], [ %x, %if.then2 ], [ %x, %if.else ]
%ret = call float @llvm.fabs.f32(float %value)
ret float %ret
}
```
We can prove the sign bit of %value is always zero. Then the fabs can be
eliminated.

This pattern also exists in cpython/duckdb/oiio/openexr.

Compile-time impact:
https://llvm-compile-time-tracker.com/compare.php?from=f82e0809ba12170e2f648f8a1ac01e78ef06c958&to=041218bf5491996edd828cc15b3aec5a59ddc636&stat=instructions:u


|stage1-O3|stage1-ReleaseThinLTO|stage1-ReleaseLTO-g|stage1-O0-g|stage2-O3|stage2-O0-g|stage2-clang|
|--|--|--|--|--|--|--|
|-0.00%|+0.01%|+0.00%|-0.03%|+0.00%|+0.00%|+0.02%|

show more ...

[ValueTracking] Compute known FPClass from dominating condition (#80941)

This patch improves `computeKnownFPClass` by using context-sensitive
information from `DomConditionCache`.

[ValueTracking] Support dominating known bits condition in and/or (#74728)

This extends computeKnownBits() support for dominating conditions to
also handle and/or conditions. We'll look through eit

[ValueTracking] Support dominating known bits condition in and/or (#74728)

This extends computeKnownBits() support for dominating conditions to
also handle and/or conditions. We'll look through either and or or
depending on which edge we're considering.

This change is mainly for the sake of completeness, so we don't start
missing optimizations if SimplifyCFG decides to merge some branches.

show more ...

[DomCondCache] Remove unused variable (NFC)

[ValueTracking] Add dominating condition support in computeKnownBits() (#73662)

This adds support for using dominating conditions in computeKnownBits()
when called from InstCombine. The implementat

[ValueTracking] Add dominating condition support in computeKnownBits() (#73662)

This adds support for using dominating conditions in computeKnownBits()
when called from InstCombine. The implementation uses a
DomConditionCache, which stores which branches may provide information
that is relevant for a given value.

DomConditionCache is similar to AssumptionCache, but does not try to do
any kind of automatic tracking. Relevant branches have to be explicitly
registered and invalidated values explicitly removed. The necessary
tracking is done inside InstCombine.

The reason why this doesn't just do exactly the same thing as
AssumptionCache is that a lot more transforms touch branches and branch
conditions than assumptions. AssumptionCache is an immutable analysis
and mostly gets away with this because only a handful of places have to
register additional assumptions (mostly as a result of cloning). This is
very much not the case for branches.

This change regresses compile-time by about ~0.2%. It also improves
stage2-O0-g builds by about ~0.2%, which indicates that this change results
in additional optimizations inside clang itself.

Fixes https://github.com/llvm/llvm-project/issues/74242.

show more ...