Extremely long type analysis time on constexpr tables

[SpeedyTurtle599]

I'm getting an extremely long (unbounded?) compile time on constexpr tables in my Kokkos C++23 code. This appears to be a regression between v0.0.282 and 0.0.283, bisected below with a reproduction script. Best I can tell, it's all TypeAnalysis, not actual AD pass work.

My system specs: M3 Max MacBook Pro, macOS 26.6 RC, Homebrew LLVM 22.1.8. I've been using it with Kokkos 5.1.1, OpenMP 22.1.8, and OpenMPI 5.0.9, but I can reproduce the issue without any of those dependencies on every version of Enzyme from 283-289 inclusive

Full disclosure: all diagnosis and reproduction below was generated using Claude Code's help and does not represent my own original work. I did my best to understand and condense it for easier conversation, but it may contain LLM-generated mistakes.

---

The behaviour is governed by the table's size in bytes relative to -enzyme-max-type-offset (default 500). A 264-byte table (double[3][11]) blows up; the same table at 120 bytes (double[3][5]) does not.

Bisect

cd3e577d132f8161d8a0d2b88ca23b96532da2af — "Remove mistaken constant type or
(#2947)". It is the only commit in v0.0.282..v0.0.283 touching TypeAnalysis.

Measured on the reproducer below (clang/LLVM 22, macOS arm64, -O3):

Revision	Time
3c65e661 (parent of cd3e577d)	2 s
cd3e577d	> 5 min, killed
v0.0.282	0 s
v0.0.289	> 90 s, killed

The commit deletes one line from the ConstantDataSequential branch of getConstantAnalysis in enzyme/Enzyme/TypeAnalysis/TypeAnalysis.cpp:

       Result |= mid.ShiftIndices(DL, /*init offset*/ 0,
                                  /*maxSize*/ ObjSize,
                                  /*addOffset*/ Off);
-
-      Result |= mid;
     }
     Result.CanonicalizeInPlace(...);

That line was collapsing the table's TypeTree to a single wildcard entry. Without it, one entry per element survives, and the fixpoint over (GEP, global, phi) re-visits the resulting tree without converging in practical time.

I appreciate the line was removed deliberately (the PR also fixes "ConstantDataSequential type poisoning"), so this is a report of the performance fallout rather than a request to revert it.

Self-contained reproduction, no Kokkos or MPI:

#include <cmath>

extern "C" int enzyme_dup;
template <typename... Args> void __enzyme_fwddiff(void*, Args...);

#ifndef NS
#define NS 11        // 11 -> 264 B table, blows up;  5 -> 120 B, fine
#endif
#define NTB 3
#define NR 24

namespace {

__attribute__((always_inline)) inline double thirdBodyEta(int r, int s) {
    constexpr double kAtom = 30.0 / 7.0;
    constexpr double eta[NTB][NS] = {
#if NS == 11
        {1.0, 1.0, 1.0, kAtom, kAtom, kAtom, kAtom, 1.0, 1.0, 1.0, 0.0},
        {1.0, 1.0, 1.0, 5.0, 5.0, 5.0, 5.0, 1.0, 1.0, 1.0, 0.0},
        {1.0, 1.0, 22.0, 22.0, 22.0, 22.0, 22.0, 1.0, 1.0, 1.0, 0.0},
#else
        {1.0, 1.0, 1.0, 5.0, 5.0},
        {1.0, 1.0, 1.0, kAtom, kAtom},
        {1.0, 1.0, 22.0, 22.0, 22.0},
#endif
    };
    return eta[r][s];
}

void primal(const double* C, double* out) {
    for (int s = 0; s < NS; ++s) out[s] = 0.0;
    for (int r = 0; r < NR; ++r) {
        double Mval = 0.0;
        if (r < NTB) {
            for (int s = 0; s < NS; ++s) Mval += thirdBodyEta(r, s) * C[s];
        } else {
            Mval = 1.0;
        }
        double fwd = Mval;
        for (int s = 0; s < NS; ++s) fwd *= std::pow(C[s], 0.5);
        for (int s = 0; s < NS; ++s) out[s] += fwd;
    }
}

} // namespace

extern "C" void seed(const double* C, const double* dC, double* out, double* dout) {
    __enzyme_fwddiff(reinterpret_cast<void*>(primal), enzyme_dup, C, dC,
                     enzyme_dup, out, dout);
}

clang++ -O3 -std=c++17 -fplugin=ClangEnzyme-22.dylib -c repro.cpp

Configuration	v0.0.282	v0.0.289
NS=11 (264 B table)	0 s	does not finish
NS=5 (120 B table)	0 s	0 s
NS=11, -mllvm -enzyme-max-type-offset=256	0 s	0 s

What the time is spent on

Sampling the stuck clang (100% of samples, single stack):

TypeAnalysis::analyzeFunction
  TypeAnalyzer::run
    TypeAnalyzer::visitValue
      TypeAnalyzer::visitCallBase
        TypeAnalyzer::visitIPOCall
          TypeAnalysis::analyzeFunction
            TypeAnalyzer::visitValue
              TypeAnalyzer::visitGEPOperator
                TypeAnalyzer::updateAnalysis
                  TypeTree::checkedOrIn
                    TypeTree::insert            <- std::map<vector<int>, ConcreteType>

-mllvm -enzyme-print-type shows the analysis cycling indefinitely over the
same three values — the table global, the GEP into it, and the loop induction
phi feeding the GEP:

updating analysis of val:   %109 = getelementptr inbounds nuw [11 x double], ptr @...eta, i64 %29
    current: {[-1]:Pointer, [-1,0]:Float@double, [-1,8]:Float@double, ...}
updating analysis of val: @...eta = private unnamed_addr constant [3 x [11 x double]] [...]
updating analysis of val:   %29 = phi i64 [ 0, %10 ], [ %128, %123 ]
    current: {[-1]:Integer} new {[-1]:Integer}

Notes

• Integer tables are not affected — mid.ReplaceIntWithAnything() collapses
  those — so this is specific to floating-point constant data.
• Layout and linkage do not matter, only total byte size: flattening
  double[3][11] to double[33], or hoisting it to namespace scope, both
  still blow up. Splitting it into three separate double[11] arrays is fine.
• Marking the table with __enzyme_inactive_global does not help, since
  TypeAnalysis runs regardless of activity.
• Workaround in use: -mllvm -enzyme-max-type-offset=256.

[wsmoses]

out of curiousity does https://github.com/EnzymeAD/Enzyme/compare/lcta?expand=1 speed it up much? or do I need to keep doing some perf debugging

[SpeedyTurtle599]

No immediate joy -- still hitting my enforced timeouts after a clean rebuild on your lcta branch. I'll dig in and see what I can turn up...

[wsmoses]

pushed another commit, can you retry?

[SpeedyTurtle599]

That does it! Works at the default offset with no extra flags needed

[SpeedyTurtle599]

Worth noting: the two combined commits improved performance vs 0.0.282 in my CFD context by up to 35%, no regressions

[wsmoses]

awesome! tangentially if you'd like, we're looking to add relevant code as integration tests to enzyme, if you want some greater assurances your code won't break [in excahnge for us asking you for some help if it does go wrong]

[SpeedyTurtle599]

I'd be glad to help -- I'm really a fan of this tool, and I'd like to pay it forward a bit.

Let me think about how to formulate some of my Jacobian tests so I don't drag a load of heavy dependencies into your codebase. I have a few solid ideas already!

[wsmoses]

sounds good, in any case going to close this issue here for now as resolved!