[VPlan] Remove header masks whose tail lanes aren't used
Replace a use of header-mask && x with x if the user, transitively
through freeze, logical-and, not and mask.beforefirst(freeze ...), only
reaches masks that are and'ed with the header mask again. The header
mask is a prefix and lane i of mask.beforefirst only depends on lanes
0..i, so the lanes outside of the header mask are never used.
This avoids the i1 vp.merge that EVL tail folding needs for the inner
header mask, e.g. in the early exit mask.beforefirst(freeze(header-mask
&& c)) and in switch default edges.
[VPlan] Support tail folding uncountable early exits
Enables the first step towards #179595. After #237254, the MaskedHandleExitInVectorLoop early exit style uses the CFG to handle masking for early exit loops. This allows it to compose with tail folding which is also handled via the CFG in #176143.
This allows us to tail fold the following loop:
```c
extern char x[256];
int f(char * restrict y) {
for (int i = 0; i < 256; i++) {
if (x[i] == 0)
return i;
}
return -1;
}
```
Into this on RISC-V:
[18 lines not shown]
[VPlan] Allow tail folding early exits with side effects
Continues the work in #179595.
This allows us to tail fold e.g. the following loop:
```c
extern char a[1024], b[1024], c[1024], y[1024];
void two_guards(void) {
for (int i = 0; i < 1000; i++) {
if (a[i] == 0)
break;
if (b[i] > 3) {
if (c[i] < 9)
y[i] = 1;
}
}
}
```
[30 lines not shown]
[VPlan] Preserve SSA in early exit loops
MaskedCond is used to logically-and the condition to early exit with the current block in-mask. However because we use it in the latch block where the condition isn't defined on all paths, we have to workaround it not being in SSA in the verifier.
This fixes this by using reconstructSSA added in #212209 to preserve SSA in both the exit conditions and live outs in the exit blocks. It also means we get the right exit condition without MaskedCond and allows us to remove the MaskedCond exceptions in the verifier. MaskedCond is still kept since a followup PR will still use it.
One subtle point is that we need to freeze any branch conditions. Any lanes after and including the early exiting lane might contain poison and we can have branches on those poison lanes that didn't we didn't previously branch on in the scalar loop.
There's no miscompile on main today because we coincidentally don't keep SSA so exit conditions are read directly without being polluted by poison stemming from a branch past the early exit. But in this PR the exit conditions are polluted and we can end up with poison in the condition operand of a select, which causes an undefined result for AnyOf even if it freezes its operand. The poison in the branch will also cause problems in future if we decide to preserve uniform control flow and emit branches instead of blends. The exit_cond_merged_after_poison_branch test illustrates this.
[VPlan] Allow early exit loops with side effects by masking in the vector loop.
When all blocks with side effects are dominated by every early exit, we can vectorize the loop if we mask off any lanes past the exit. We can do this with control flow:
```mermaid
flowchart TD
header --> exiting
exiting -->| exit mask | sideeffects --> latch --> latch.split
exiting -->| !exit mask | latch.split
```
For every early exiting block we add a branch to the latch on `!mask.beforefirst(exitcond)`. This is implemented in UncountableExitStyle::ReadOnly which is now renamed to MaskedHandleExitInVectorLoop.
This is a complementary exit style to MaskedHandleExitInScalarLoop. If any of the side effects aren't dominated by the early exit it still falls back to the scalar loop style, which is why none of the existing early exit side effect tests changed. Masking in loop is profitable for RISC-V and I'm assuming it's also profitable for AArch64 too, but if not then we can add a TTI hook for a preferred exit style.
[VPlan] Use vputils::findCanonicalIVIncrement in more places. NFC
In a future patch we want to enable more scenarios with early exits and tail folding. In these scenarios the terminator will no longer be a BranchOnCount/BranchOnCond but a BranchOnTwoConds, so a bunch of canonical IV matchers break. Use vputils::findCanonicalIVIncrement instead since it searches the users of the canonical IV instead of looking at the terminator.
[VPlan] Simplify BLEND X/M, false, ..., false -> M && X
If an i1 blend has false for all but one incoming value, then we can simplify this to the one non-false value. Blends by construction never have any overlapping mask values, so we don't need to worry about the order as the masks can't "shortcut" each other.
[VPlan] Support interleaving early exit loops with side effects
We couldn't do this on main previously because the exit mask `active-lane-mask(0, FirstActiveLane(Cond))` doesn't get unrolled properly across parts. Now that we use mask.beforefirst we can unroll it properly in a chain. The unrolled form is:
unroll(mask.beforefirst, P) = mask.beforefirst(cond[P] | broadcast(anyof(not(unroll(mask.beforefirst, P-1)))))
On AArch64 this can be combined to brkpb in another patch.
[VPlan] Move extract-lane(0, canWideIV) combine before unrolling
Some extract-lane combines can't be performed before unrolling, e.g. the one that combines it to Instruction::ExtractElement can end up extracting from a different part. But the extract-lane(0, canWideIV) can because at index 0 you're always extracting from the first part. Do this before unrolling, which improves codegen of unrolled code.
[VPlan] Use llvm.mask.beforefirst for computing early exit mask
This makes the cost more accurate and improves codegen for RISC-V. The codegen for an early exit loop with side effects then goes from:
.LBB0_3: # %vector.body
# =>This Inner Loop Header: Depth=1
vl1r.v v16, (a3)
vsetvli zero, zero, e8, m1, ta, ma
vmseq.vi v16, v16, 0
vfirst.m a7, v16
srli t0, a7, 63
czero.nez a7, a7, t0
czero.eqz t0, a1, t0
or a7, t0, a7
vsetvli zero, zero, e64, m8, ta, ma
vmsltu.vx v0, v8, a7
vle8.v v17, (a5), v0.t
vcpop.m t1, v16
vsetvli zero, zero, e8, m1, ta, ma
[22 lines not shown]
[VPlan] Lower MaskedCond earlier in the predicator. NFC (#238023)
A MaskedCond is used to logically-and some condition with the current
block in mask.
It's currently lowered in convertToConcreteRecipes but we can just do it
earlier in VPlanPredicator, which removes the need for the separate fold
in simplifyRecipe. It also enables more logical-and simplifications
earlier on.
[IR] Accept various metadata on phi nodes (#202877)
This patch allows adding `!nonnull`, `!noundef`, `!range`, `!nofpclass`,
`!dereferenceable`, `!dereferenceable_or_null` and `!align` metadata to
phi nodes.
[LoongArch] Select [x]vbitclr for and-not of bitcasted shl(splat(1), y) (#241179)
When the shift of splat(1) is performed in a narrower element type than
the and-not, e.g.
```llvm
%s = shl <8 x i16> splat (i16 1), %y
%m = bitcast <8 x i16> %s to <2 x i64>
%n = xor <2 x i64> %m, splat (i64 -1)
%r = and <2 x i64> %x, %n
```
the VANDN node is created in v2i64 with a bitcast operand, so the
existing [x]vbitclr.{b/h/w} patterns fail to match and we emit vrepli +
vsll + vandn.v.
Fold VANDN(bitcast(shl(splat(1), y)), x) into
bitcast(VANDN(shl(splat(1), y), bitcast(x))) so that the operation is
done in the shift's element type and selected as a single [x]vbitclr.
Assisted-By: LLM
[LoongArch][NFC] Pre-commit tests for [x]vbitclr through bitcast (#241178)
Add tests where the shift of splat(1) is done in a narrower element type
and then bitcast to the type of the and-not operation.
Assisted-By: LLM
[flang] Give hoisted descriptor allocas the location of their region (#240953)
`genAllocaAndAddrCastWithType` hoists the alloca it creates into the
alloca block of the enclosing OpenMP region or function, but gave it the
location of the operation that needed it. When the alloca generates
code, the line table then shows that operation's line at the start of
the region, before the code that reaches it.
That happens on x86 for a descriptor load in the loop of a task:
```
!$omp task
do i = 1, 4
x(i) = 2.0 * x(i) ! x is allocatable
end do
!$omp end task
```
The alloca block of a task is not the entry block of the outlined
[12 lines not shown]
[SLP] Pass a lane as the vector cost context only if all lanes agree
getEntryCost prices a vector instruction with one scalar lane as the
context, while each scalar lane is priced in its own context. A target
that reads the context, like the users of an fmul that fuses into an fma
on AMDGPU or a sibling udiv of a urem on X86, gives the whole vector the
property of that one lane.
Pass the lane as the context only if the vector cost is the same with any
of the represented lanes as the context.
Assisted-by: Claude Opus
[AMDGPU][docs] Minor clean-ups for the GFX12.5 memory model docs (#239156)
- Use `GFX12.5` everywhere instead of a mix of `gfx125x` and others.
- Remove "WIP" disclaimer. The model hasn't seen huge changes in a
while. The remaining items are documented separately in their own
documents.
[AMDGPU][GlobalISel] Use v_cmpx/s_andn2_wrexec form in RegBankLegalize waterfall loops
Port the UseNewExecInstructions path from SIInstrInfo's waterfall emission
to RegBankLegalizeHelper::executeInWaterfallLoop. On subtargets with
no-sdst v_cmpx and s_andn2_wrexec, the loop now narrows exec with deferred
V_CMPX_EQ_*_nosdst_e32_term compares and computes the remaining lanes with
S_ANDN2 from an exec PHI, written back by S_MOV_term. SIOptimizeExecMasking
then folds the pair into s_and_not1_wrexec, matching SelectionDAG.
Co-authored-by: Cursor <cursoragent at cursor.com>
[X86] combineShiftToPMULH - fix lshr of sign-extended products on wider than i32 elements (#234420)
combineShiftToPMULH folds srl/sra(mul(ext a, ext b), 16) into
ext(mulh(a, b)), taking the outer extension from the shift kind. For i32
elements that works, but for wider elements the product's bits above 31
are copies of its sign bit (sext inputs) or zero (zext inputs). So srl
of a sign-extended i64 product was lowered to zext(pmulhw), which loses
bits 16..47 of negative products.
For elements wider than 32 bits I now extend the MULH result the same
way as the inputs. A logical shift of a sign-extended product also needs
its top 16 bits cleared, so that case becomes and(sext(mulhs),
0x0000FFFFFFFFFFFF) and still uses pmulhw. Simply bailing out also fixes
it, but on SSE2 the test then grows to a long pmuludq sequence, so I
kept the fold.
The first commit adds a zext/ashr i64 test. That case was already
correct, since the generic combine turns the ashr into lshr first. I
checked the new codegen natively for SSE2/SSE4.1/AVX2/AVX512F/AVX512BW
[5 lines not shown]
[DebugInfo][DWARF] Make CFIProgram::getOperandTypes() table constexpr (#227684)
Previously getOperandTypes() lazily filled a static table, but set its
flag before filling it, so a thread calling it concurrently with the
first call could return a partially filled table.
The table is now constexpr, so there is no runtime initialization for
concurrent callers to race on.
Assisted-by: Claude Opus 5.5
Signed-off-by: Steffen Holst Larsen <sholstla at amd.com>
[analyzer] Correct logic in 3-param addTransition (#241415)
The method `CheckerContext::addTransition` should create a new exploded
node when (1) there was a state change or (2) an explicit non-null `Tag`
is specified.
However, in the 3-parameter overload (which accepts an exploded node
`Pred` to allow chaining transitions) this logic compared the `State` to
`getState()` (the state at the construction of `CheckerContext`) and
returned early with `getPredecessor()` (the node that was passed to the
constructor of `CheckerContext`) instead of `Pred`.
This commit corrects this oversight by using `Pred` and its state -- but
preserves the corner case that a null `Pred` is accepted and handled as
if it was `getPredecessor()`. (Note that passing a null node to
`addTransitionImpl` is equivalent to passing `getPredecessor()`, some
checkers -- at least `FuchsiaHandleChecker` leak reporting -- rely on
that `addTransition` can gracefully handle a null node argument.)
[4 lines not shown]
