Looks like the missing concern from Nikita is about the compile time impact. Marek is checking this using the compile time tracker.

Added ctpop test

In D154157#4648096, @nikic wrote:

Would you mind testing whether this also fixes https://github.com/llvm/llvm-project/issues/57476 and adding it as a test case if so?

Any comments to progress this further?

ping?

This is a POC of most of the changes for the RFC to follow. The change will be split into LangRef + API as one change, Verifier + pass updates as another change.

shall I go ahead and land this? Simple enough change.

rebased over changes from dmgreen with more accurate costs for ARM out-of-loop reductions.

Our X86 results are in. Over 244 workloads, the geomean changes by about ~0.4%. Looking at individual workloads, there are no major gains or regressions in large applications (unfortunately, we cannot share the exact benchmark names publicly). However, we do see big gains in 3 of these workloads where it performs a floating point minimum/maximum reduction over a float array of 3 elements (without this change we were vectorizing it).
Overall, I think the change is still reasonable to have since we now account for out of loop reductions more accurately.

Thanks @dantrushin for the patch. We have now had nasty miscompiles in practice (lowering memory intrinsics to regular loops and miss adding barriers for GC) and would like to make progress with this patch.

Rebase needed. thanks.

In D154157#4638288, @dmgreen wrote:

I've made some changes for the Arm MVE and NEON costs. Can you try a rebase? Thanks

In D154157#4628521, @fhahn wrote:

In D154157#4628496, @anna wrote:

Gentle ping @fhahn. Anything I could do to move this forward? I have kept the option as off by default, since I would need to help to test this on supported targets upstream. It helps our use-case where loops are not vectorized when out-of-loop reductions are present in small trip count loops.
There maybe some fallouts where correction in reductions cost modelling will be required.

What are the regressions on ARM/RISCV? I think we should aim to enable this by default for all platforms, otherwise it is at the risk of not getting enabled. Also, those tests may show issues with the current implementation.

The regressions on ARM and RISCV are because we have an updated minimum trip count we expect (to offset the cost of the out-of-loop reductions), so the CHECK lines have been updated accordingly. RISCV looks okay with the minimum trip count being at least 4 or 8 (we round the MinimumTripCount up to VF, so it is more conservative).

changed the flag to on by default. Fixed the ARM/RISCV tests (by updating the lines). More details will follow.

LGTM.

Gentle ping @fhahn. Anything I could do to move this forward? I have kept the option as off by default, since I would need to help to test this on supported targets upstream. It helps our use-case where loops are not vectorized when out-of-loop reductions are present in small trip count loops.
There maybe some fallouts where correction in reductions cost modelling will be required.

Thanks!

added an option which switches this off by default. The failures above are related to ARM and RISCV targets.

Rewrote the patch to extend existing logic for runtime checks calculation.
This now supports all kinds of out of loop reductions. Since we compute an upper-bound on MinProfitableTripCount, this maybe a more conservative estimate.

addressed review comment.

One thing to note though is we would need to future proof against incompatible types (whenever new return types are added), but that happens in the common API: AttributeFuncs::typeIncompatible.

remove incompatible return attributes at the point we change the return type.

In D158286#4599153, @nikic wrote:

Where is this update done? Shouldn't the code changing the return type drop incompatible attributes?

LGTM w/ comments.

do you need review for this? Could you pls state the review stack in the description so it is clear the order of reviews. Thanks.

do you need review for this? Could you pls state the review stack in the description so it is clear the order of reviews. Thanks.

LGTM w/ comments.

Thanks, I've moved the test and removed the x86-registered-target

Thanks everyone for the review and test cases. I'll try landing this again today.

LGTM - we don't use the legacy pass pipeline. In fact, we're moving away from guard representation completely (not sure if anyone else downstream uses it though).

added Ayal's minimal reproducer. Addressed review comments.

updated test case with correct check lines and comments.

thank you for the fix! Details of the diagnostic is here (for reference later) : https://reviews.llvm.org/D155145#4556178

thank you @craig.topper and @pengfei .

In D155145#4554786, @anna wrote:

Can you capture the values of EAX, EBX, ECX, and EDX after the two calls to getX86CpuIDAndInfoEx that have 0x7 as the first argument? Maybe there's a bug in CPUID on Sandy Bridge.

Sure, on the original code before the patch you suggested right?
The two calls are:

 bool HasLeaf7 =
        MaxLevel >= 7 && !getX86CpuIDAndInfoEx(0x7, 0x0, &EAX, &EBX, &ECX, &EDX);
+   llvm::errs() << "Before setting fsgsbase the value for EAX: " << EAX
+                     << " EBX: " << EBX << " ECX: " << ECX << "  EDX: " << EDX
+                     << "\n";
  
    Features["fsgsbase"]   = HasLeaf7 && ((EBX >>  0) & 1);
....
bool HasLeaf7Subleaf1 =
        MaxLevel >= 7 && !getX86CpuIDAndInfoEx(0x7, 0x1, &EAX, &EBX, &ECX, &EDX);
+   llvm::errs() << "Before setting sha512 the value for EAX: " << EAX
+                     << " EBX: " << EBX << " ECX: " << ECX << "  EDX: " << EDX
+                     << "\n";
    Features["sha512"]     = HasLeaf7Subleaf1 && ((EAX >> 0) & 1);
...
we set avxvnniint16 after this

Takes a while to get a build on this machine, should have the output soon.

Can you capture the values of EAX, EBX, ECX, and EDX after the two calls to getX86CpuIDAndInfoEx that have 0x7 as the first argument? Maybe there's a bug in CPUID on Sandy Bridge.

Sure, on the original code before the patch you suggested right?
The two calls are:

 bool HasLeaf7 =
        MaxLevel >= 7 && !getX86CpuIDAndInfoEx(0x7, 0x0, &EAX, &EBX, &ECX, &EDX);
+   llvm::errs() << "Before setting fsgsbase the value for EAX: " << EAX
+                     << " EBX: " << EBX << " ECX: " << ECX << "  EDX: " << EDX
+                     << "\n";

addressed review comment for use-after-free error (updated test to show the LoopAccessAnalysis bailout no longer present).

Thanks Ayal for the root cause. I'll update the patch

In D155145#4551621, @craig.topper wrote:

In D155145#4551526, @anna wrote:

In D155145#4544068, @pengfei wrote:

In D155145#4543326, @anna wrote:

We see a crash bisected to this patch about using an illegal instruction.
Here's the CPUInfo for the machine:

CPU info:
current cpu id: 22
total 32(physical cores 16) (assigned logical cores 32) (assigned physical cores 16) (assigned_sockets:2 of 2) (8 cores per cpu, 2 threads per core) family 6 model 45 stepping 7 microcode 0x71a, cmov, cx8, fxsr, mmx, sse, sse2, sse3, ssse3, sse4.1, sse4.2, popcnt, vzeroupper, avx, aes, clmul, ht, tsc, tscinvbit, tscinv, clflush
AvgLoads: 0.30, 0.10, 0.18
CPU Model and flags from /proc/cpuinfo:
model name      : Intel(R) Xeon(R) CPU E5-2650 0 @ 2.00GHz
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
Online cpus: 0-31
Offline cpus:
BIOS frequency limitation: <Not Available>
Frequency switch latency (ns): 20000
Available cpu frequencies: <Not Available>
Current governor: schedutil
Core performance/turbo boost: <Not Available>

I don't see avxvnniint16 in the flags list nor avx2. So, this (relatively new) instruction shouldn't be generated for this machine. Any ideas on why this might be happening?

As far as I can see from the patch, the only way to generate avxvnniint16 instructions is to call its specific intrinsics explicitly. And we will check compiling options in FE before allowing to call the intrinsics. We do have an optimization to generate vnni instructions without intrinsics, but we haven't extend it to avxvnniint16 so far.
So I don't know what's wrong in your case, could you provide a reproducer for your problem?

I've investigated what is going on. With this patch, we are now passing in +avxvnniint16 into machine attributes. With that attribute, we now generate an instruction which is illegal on sandybridge machine:

 0x3013f2af:	jmpq   0x3013f09b
   0x3013f2b4:	mov    %rax,%rdi
   0x3013f2b7:	and    $0xfffffffffffffff0,%rdi
=> 0x3013f2bb:	vpbroadcastd %xmm0,%ymm2
   0x3013f2c0:	vpbroadcastd %xmm1,%ymm3

The instruction vpbroadcastd %xmm0,%ymm2 requires AVX2 CPU flag: https://www.felixcloutier.com/x86/vpbroadcast. However, the machine has only AVX flag.

This is the complete mattr generated:

!3 = !{!"-mattr=-prfchw,-cldemote,+avx,+aes,+sahf,+pclmul,-xop,+crc32,-xsaves,-avx512fp16,-sm4,+sse4.1,-avx512ifma,+xsave,-avx512pf,+sse4.2,-tsxldtrk,-ptwrite,-widekl,-sm3,-invpcid,+64bit,-xsavec,-avx512vpopcntdq,+cmov,-avx512vp2intersect,-avx512cd,-movbe,-avxvnniint8,-avx512er,-amx-int8,-kl,-sha512,-avxvnni,-rtm,-adx,-avx2,-hreset,-movdiri,-serialize,-vpclmulqdq,-avx512vl,-uintr,-clflushopt,-raoint,-cmpccxadd,-bmi,-amx-tile,+sse,-gfni,+avxvnniint16,-amx-fp16,+xsaveopt,-rdrnd,-avx512f,-amx-bf16,-avx512bf16,-avx512vnni,+cx8,-avx512bw,+sse3,-pku,-fsgsbase,-clzero,-mwaitx,-lwp,-lzcnt,-sha,-movdir64b,-wbnoinvd,-enqcmd,-prefetchwt1,-avxneconvert,-tbm,-pconfig,-amx-complex,+ssse3,+cx16,-bmi2,-fma,+popcnt,-avxifma,-f16c,-avx512bitalg,-rdpru,-clwb,+mmx,+sse2,-rdseed,-avx512vbmi2,-prefetchi,-rdpid,-fma4,-avx512vbmi,-shstk,-vaes,-waitpkg,-sgx,+fxsr,-avx512dq,-sse4a"}

I've confirmed if we changed to -avxvnniint16 we do not generate vpbroadcastd.

W.r.t. how we get the machine attributes generated through our front-end:

if (!sys::getHostCPUFeatures(Features))
      return std::move(mattr);
  
    // Fill mattr with default values.
    mattr.reserve(Features.getNumItems());
    for (auto &I : Features) {
      std::string attr(I.first());
      mattr.emplace_back(std::string(I.second ? "+" : "-") + attr);
    }

So, the problem is in getHostCPUFeatures, possibly this line from the patch :
Features["avxvnniint16"] = HasLeaf7Subleaf1 && ((EDX >> 10) & 1) && HasAVXSave;.

Does this patch help

diff --git a/llvm/lib/TargetParser/Host.cpp b/llvm/lib/TargetParser/Host.cpp
index 1141df09307c..11a6879fb76a 100644
--- a/llvm/lib/TargetParser/Host.cpp
+++ b/llvm/lib/TargetParser/Host.cpp
@@ -1769,7 +1769,7 @@ bool sys::getHostCPUFeatures(StringMap<bool> &Features) {
   Features["amx-tile"]   = HasLeaf7 && ((EDX >> 24) & 1) && HasAMXSave;
   Features["amx-int8"]   = HasLeaf7 && ((EDX >> 25) & 1) && HasAMXSave;
   bool HasLeaf7Subleaf1 =
-      MaxLevel >= 7 && !getX86CpuIDAndInfoEx(0x7, 0x1, &EAX, &EBX, &ECX, &EDX);
+      HasLeaf7 && EAX >= 1 && !getX86CpuIDAndInfoEx(0x7, 0x1, &EAX, &EBX, &ECX, &EDX);
   Features["sha512"]     = HasLeaf7Subleaf1 && ((EAX >> 0) & 1);
   Features["sm3"]        = HasLeaf7Subleaf1 && ((EAX >> 1) & 1);
   Features["sm4"]        = HasLeaf7Subleaf1 && ((EAX >> 2) & 1);

In D155145#4544068, @pengfei wrote:

In D155145#4543326, @anna wrote:

We see a crash bisected to this patch about using an illegal instruction.
Here's the CPUInfo for the machine:

CPU info:
current cpu id: 22
total 32(physical cores 16) (assigned logical cores 32) (assigned physical cores 16) (assigned_sockets:2 of 2) (8 cores per cpu, 2 threads per core) family 6 model 45 stepping 7 microcode 0x71a, cmov, cx8, fxsr, mmx, sse, sse2, sse3, ssse3, sse4.1, sse4.2, popcnt, vzeroupper, avx, aes, clmul, ht, tsc, tscinvbit, tscinv, clflush
AvgLoads: 0.30, 0.10, 0.18
CPU Model and flags from /proc/cpuinfo:
model name      : Intel(R) Xeon(R) CPU E5-2650 0 @ 2.00GHz
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
Online cpus: 0-31
Offline cpus:
BIOS frequency limitation: <Not Available>
Frequency switch latency (ns): 20000
Available cpu frequencies: <Not Available>
Current governor: schedutil
Core performance/turbo boost: <Not Available>

I don't see avxvnniint16 in the flags list nor avx2. So, this (relatively new) instruction shouldn't be generated for this machine. Any ideas on why this might be happening?

As far as I can see from the patch, the only way to generate avxvnniint16 instructions is to call its specific intrinsics explicitly. And we will check compiling options in FE before allowing to call the intrinsics. We do have an optimization to generate vnni instructions without intrinsics, but we haven't extend it to avxvnniint16 so far.
So I don't know what's wrong in your case, could you provide a reproducer for your problem?

We see a crash bisected to this patch about using an illegal instruction.
Here's the CPUInfo for the machine:

CPU info:
current cpu id: 22
total 32(physical cores 16) (assigned logical cores 32) (assigned physical cores 16) (assigned_sockets:2 of 2) (8 cores per cpu, 2 threads per core) family 6 model 45 stepping 7 microcode 0x71a, cmov, cx8, fxsr, mmx, sse, sse2, sse3, ssse3, sse4.1, sse4.2, popcnt, vzeroupper, avx, aes, clmul, ht, tsc, tscinvbit, tscinv, clflush
AvgLoads: 0.30, 0.10, 0.18
CPU Model and flags from /proc/cpuinfo:
model name      : Intel(R) Xeon(R) CPU E5-2650 0 @ 2.00GHz
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
Online cpus: 0-31
Offline cpus:
BIOS frequency limitation: <Not Available>
Frequency switch latency (ns): 20000
Available cpu frequencies: <Not Available>
Current governor: schedutil
Core performance/turbo boost: <Not Available>

I don't see avxvnniint16 in the flags list nor avx2. So, this (relatively new) instruction shouldn't be generated for this machine. Any ideas on why this might be happening?

Fixed the bug caused by this patch.

fixed use-after-free error (with added testcase). This bug wasn't there before the patch because we would break out of the inner loop accessing A, whereas now we were continuing to see which other A accesses needed to release the group.

I reduced the testcase enough to show how GroupA can be same as GroupB, but there are two ways to fix this:

• Identify that GroupA is same as GroupB and once we released groupA, we should iterate to the next B instruction (in the outer loop).
• GroupA which is being released should never be same as GroupB and we do this by making sure that there's no dependency between *any of* the stores when inserting into GroupB. AFAICT, we don't do that since we check only between A and B when inserting (store) A into (store) groupB.

Thanks @mstorsjo and just for info, the use-after-free error shows up as a hang in non-asan builds (so its highly likely both reports are the same bug). I've reduced the first repro with bugpoint and it is due to GroupA == GroupB.

Thank you for the review Ayal!

Hi Ayal, any more comments? Thanks.

addressed review comments.

addressed most review comments: corrected if (DependentInst) check and couple other NFC.

thank you Florian, this is a nice idea. Working on it.

rebased over test in D155096

removed check tags