Performance regression since llvm 9 using pointers for array traversal

[outpaddling]

I wrote a simple benchmark using selection sort to compare performance of various compilers and interpreters:

https://github.com/outpaddling/Lang-speed

I noticed that clang 9 and later are much slower than clang 8 when using pointers to traverse the array. It is also much slower than the same program with subscripts. Clang 8 shows what I would expect, with pointers marginally faster than subscripts.

I see this issue on both FreeBSD (clang9 and later) and MacOS (clang13), though on MacOS the pointer version takes only about 1.5x as long as subscripts.

From the run times shown below, it looks like clang stopped doing some optimizations beyond -O starting at version 9. I don't see anything in the v9 release notes about this type of optimization.
https://releases.llvm.org/9.0.0/docs/ReleaseNotes.html

To reproduce:

git clone https://github.com/outpaddling/Lang-speed.git
cd Lang-speed
(Edit clang-check to use available clang compilers)
./clang-check

clang version 8.0.1 (tags/RELEASE_801/final)
Target: x86_64-portbld-freebsd13.0
Thread model: posix
InstalledDir: /usr/local/llvm80/bin
-O
Subscripts:         2.10 real         2.09 user         0.00 sys
Pointers:           2.02 real         2.02 user         0.00 sys
-O2
Subscripts:         2.11 real         2.11 user         0.00 sys
Pointers:           2.02 real         2.02 user         0.00 sys
-Ofast
Subscripts:         2.36 real         2.35 user         0.00 sys
Pointers:           2.23 real         2.22 user         0.00 sys
clang version 9.0.1 
Target: x86_64-portbld-freebsd13.0
Thread model: posix
InstalledDir: /usr/local/llvm90/bin
-O
Subscripts:         2.24 real         2.23 user         0.00 sys
Pointers:           4.67 real         4.67 user         0.00 sys
-O2
Subscripts:         2.08 real         2.07 user         0.00 sys
Pointers:           4.64 real         4.64 user         0.00 sys
-Ofast
Subscripts:         2.03 real         2.03 user         0.00 sys
Pointers:           3.15 real         3.15 user         0.00 sys
clang version 13.0.0
Target: x86_64-portbld-freebsd13.0
Thread model: posix
InstalledDir: /usr/local/llvm13/bin
-O
Subscripts:         4.69 real         4.69 user         0.00 sys
Pointers:           4.65 real         4.64 user         0.00 sys
-O2
Subscripts:         2.10 real         2.10 user         0.00 sys
Pointers:           4.81 real         4.80 user         0.00 sys
-Ofast
Subscripts:         2.13 real         2.13 user         0.00 sys
Pointers:           4.74 real         4.73 user         0.00 sys

[dwblaikie]

@aeubanks - /maybe/ this could be some loss due to opaque pointers? (not sure if we have a group or how to tag a group here... )

[outpaddling]

I don't think so, it's a simple array that's part of a fully defined structure. The code is here in case someone wants a quick peek without cloning:
https://github.com/outpaddling/Lang-speed/blob/master/selsort-pointers.c
https://github.com/outpaddling/Lang-speed/blob/master/selsort-subscripts.c

[outpaddling]

Performance with subscripts has also regressed in more recent releases, to the point where GCC is now about 30% faster for selection sort with integers:

Sorting with Unix sort command...
User time = 0.15 seconds (.00250 minutes) (.00004 hours).
RSS = 15452 KB

Sorting int array with clang18 and subscripts...
User time = 4.60 seconds (.07666 minutes) (.00127 hours).
RSS = 2852 KB

Sorting long array with clang18 and subscripts...
User time = 4.60 seconds (.07666 minutes) (.00127 hours).
RSS = 3240 KB

Sorting float array with clang18 and subscripts...
User time = 4.61 seconds (.07683 minutes) (.00128 hours).
RSS = 2848 KB

Sorting double array with clang18 and subscripts...
User time = 4.62 seconds (.07700 minutes) (.00128 hours).
RSS = 3240 KB

Sorting int array with clang18 and pointers...
User time = 4.66 seconds (.07766 minutes) (.00129 hours).
RSS = 2848 KB

Sorting long array with clang18 and pointers...
User time = 4.67 seconds (.07783 minutes) (.00129 hours).
RSS = 3240 KB

Sorting float array with clang18 and pointers...
User time = 6.12 seconds (.10200 minutes) (.00170 hours).
RSS = 2852 KB

Sorting double array with clang18 and pointers...
User time = 6.12 seconds (.10200 minutes) (.00170 hours).
RSS = 3240 KB

Sorting int array with gcc14 and subscripts...
User time = 3.10 seconds (.05166 minutes) (.00086 hours).
RSS = 2840 KB

Sorting long array with gcc14 and subscripts...
User time = 3.13 seconds (.05216 minutes) (.00086 hours).
RSS = 3228 KB

Sorting float array with gcc14 and subscripts...
User time = 3.12 seconds (.05200 minutes) (.00086 hours).
RSS = 2844 KB

Sorting double array with gcc14 and subscripts...
User time = 3.13 seconds (.05216 minutes) (.00086 hours).
RSS = 3236 KB

Sorting int array with gcc14 and pointers...
User time = 3.08 seconds (.05133 minutes) (.00085 hours).
RSS = 2840 KB

Sorting long array with gcc14 and pointers...
User time = 3.08 seconds (.05133 minutes) (.00085 hours).
RSS = 3228 KB

Sorting float array with gcc14 and pointers...
User time = 5.80 seconds (.09666 minutes) (.00161 hours).
RSS = 2844 KB

Sorting double array with gcc14 and pointers...
User time = 5.80 seconds (.09666 minutes) (.00161 hours).
RSS = 3232 KB

[nikic]

Godbolt: https://c.godbolt.org/z/Y4Y3ozs37

It looks like the difference is in runtime unrolling. Clang 9 unrolled both variants, clang 13 unrolled the pointer variant, current clang unrolls neither.

These are far enough back that I don't know whether the changes in unrolling behavior were intentional or incidental.

[nikic]

The loops don't get expanded because the trip count fails the high cost expansion check.

The trip counts are:

subscript: {(-1 + %0),+,-1}<nw><%for.body>
pointer: (1 + (({(-5 + (-1 * (ptrtoint ptr %0 to i64))),+,-4}<nw><%for.body> + (((4 * %1) + (ptrtoint ptr %0 to i64)) umax {(8 + (ptrtoint ptr %0 to i64)),+,4}<nw><%for.body>)) /u 4))<nuw><nsw>

The cost is probably over-estimated here, because (at least in final codegen) we wouldn't actually have a dedicated separate IV and just treat it as an offset of a canonical IV.

[nikic]

Something like this allows the subscript variant to unroll:

diff --git a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
index c7d758aa575e..1d249e84782a 100644
--- a/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp
@@ -2044,8 +2044,24 @@ bool SCEVExpander::isHighCostExpansionHelper(
     return Cost > Budget;
   }
   case scAddRecExpr: {
-    assert(cast<SCEVAddRecExpr>(S)->getNumOperands() >= 2 &&
-           "Polynomial should be at least linear");
+    auto *AR = cast<SCEVAddRecExpr>(S);
+    if (CanonicalMode && AR->isAffine()) {
+      PHINode *CanonicalIV = AR->getLoop()->getCanonicalInductionVariable();
+      if (CanonicalIV && CanonicalIV->getType() == AR->getType()) {
+        // The addrec will be emitted as %canonal.iv * %step + %start.
+        if (!AR->getOperand(1)->isOne()) {
+          Cost += TTI.getArithmeticInstrCost(Instruction::Mul, AR->getType(),
+                                             CostKind);
+          Worklist.emplace_back(Instruction::Mul, 1, AR->getOperand(1));
+        }
+        Cost += TTI.getArithmeticInstrCost(Instruction::Add, AR->getType(),
+                                           CostKind);
+        Worklist.emplace_back(Instruction::Add, 1, AR->getStart());
+        return Cost > Budget;
+      }
+    }
+
+    assert(AR->getNumOperands() >= 2 && "Polynomial should be at least linear");
     Cost += costAndCollectOperands<SCEVAddRecExpr>(
         WorkItem, TTI, CostKind, Worklist);
     return Cost > Budget;

I was going to submit that, but then I looked at how AddRec's are normally costed and ... it just doesn't make any sense. For {(-1 + %0),+,-1} what we're going to generate are two adds and a phi, while the cost model seems to think it will result in an add and two multiplies. I think if that gets fixed, we probably don't need to check for canonical IVs. I'll try to take a look tomorrow.

[outpaddling]

The loops don't get expanded because the trip count fails the high cost expansion check.

The trip counts are:

subscript: {(-1 + %0),+,-1}<nw><%for.body>
pointer: (1 + (({(-5 + (-1 * (ptrtoint ptr %0 to i64))),+,-4}<nw><%for.body> + (((4 * %1) + (ptrtoint ptr %0 to i64)) umax {(8 + (ptrtoint ptr %0 to i64)),+,4}<nw><%for.body>)) /u 4))<nuw><nsw>

The cost is probably over-estimated here, because (at least in final codegen) we wouldn't actually have a dedicated separate IV and just treat it as an offset of a canonical IV.

If that's the case, shouldn't adding -funroll-loops serve as a workaround? I tried and it doesn't change the results.

Compiling with clang18 -O2 -funroll-loops -march=native, subscripts, int...
...
Sorting with Unix sort command...
User time = 0.14 seconds (.00233 minutes) (.00003 hours).
RSS = 15528 KB

Sorting int array with clang18 and subscripts...
User time = 4.68 seconds (.07800 minutes) (.00130 hours).
RSS = 2844 KB

[outpaddling]

Godbolt: https://c.godbolt.org/z/Y4Y3ozs37

It looks like the difference is in runtime unrolling. Clang 9 unrolled both variants, clang 13 unrolled the pointer variant, current clang unrolls neither.

These are far enough back that I don't know whether the changes in unrolling behavior were intentional or incidental.

This info doesn't seem to match the results in my original comment above. They show that clang9 regressed for pointers, but not subscripts. Clang13 regressed for both with -O, but only regressed for pointers if -O2 or -Ofast was used. So subscripts were faster with clang13 and aggressive optimizations.