Rollup merge of #144197 - KMJ-007:type-tree, r=ZuseZ4

TypeTree support in autodiff

# TypeTrees for Autodiff

## What are TypeTrees?
Memory layout descriptors for Enzyme. Tell Enzyme exactly how types are structured in memory so it can compute derivatives efficiently.

## Structure
```rust
TypeTree(Vec<Type>)

Type {
    offset: isize,  // byte offset (-1 = everywhere)
    size: usize,    // size in bytes
    kind: Kind,     // Float, Integer, Pointer, etc.
    child: TypeTree // nested structure
}
```

## Example: `fn compute(x: &f32, data: &[f32]) -> f32`

**Input 0: `x: &f32`**
```rust
TypeTree(vec![Type {
    offset: -1, size: 8, kind: Pointer,
    child: TypeTree(vec![Type {
        offset: -1, size: 4, kind: Float,
        child: TypeTree::new()
    }])
}])
```

**Input 1: `data: &[f32]`**
```rust
TypeTree(vec![Type {
    offset: -1, size: 8, kind: Pointer,
    child: TypeTree(vec![Type {
        offset: -1, size: 4, kind: Float,  // -1 = all elements
        child: TypeTree::new()
    }])
}])
```

**Output: `f32`**
```rust
TypeTree(vec![Type {
    offset: -1, size: 4, kind: Float,
    child: TypeTree::new()
}])
```

## Why Needed?
- Enzyme can't deduce complex type layouts from LLVM IR
- Prevents slow memory pattern analysis
- Enables correct derivative computation for nested structures
- Tells Enzyme which bytes are differentiable vs metadata

## What Enzyme Does With This Information:

Without TypeTrees (current state):
```llvm
; Enzyme sees generic LLVM IR:
define float ``@distance(ptr*`` %p1, ptr* %p2) {
; Has to guess what these pointers point to
; Slow analysis of all memory operations
; May miss optimization opportunities
}
```

With TypeTrees (our implementation):
```llvm
define "enzyme_type"="{[]:Float@float}" float ``@distance(``
    ptr "enzyme_type"="{[]:Pointer}" %p1,
    ptr "enzyme_type"="{[]:Pointer}" %p2
) {
; Enzyme knows exact type layout
; Can generate efficient derivative code directly
}
```

# TypeTrees - Offset and -1 Explained

## Type Structure

```rust
Type {
    offset: isize, // WHERE this type starts
    size: usize,   // HOW BIG this type is
    kind: Kind,    // WHAT KIND of data (Float, Int, Pointer)
    child: TypeTree // WHAT'S INSIDE (for pointers/containers)
}
```

## Offset Values

### Regular Offset (0, 4, 8, etc.)
**Specific byte position within a structure**

```rust
struct Point {
    x: f32, // offset 0, size 4
    y: f32, // offset 4, size 4
    id: i32, // offset 8, size 4
}
```

TypeTree for `&Point` (internal representation):
```rust
TypeTree(vec![
    Type { offset: 0, size: 4, kind: Float },   // x at byte 0
    Type { offset: 4, size: 4, kind: Float },   // y at byte 4
    Type { offset: 8, size: 4, kind: Integer }  // id at byte 8
])
```

Generates LLVM:
```llvm
"enzyme_type"="{[]:Float@float}"
```

### Offset -1 (Special: "Everywhere")
**Means "this pattern repeats for ALL elements"**

#### Example 1: Array `[f32; 100]`
```rust
TypeTree(vec![Type {
    offset: -1, // ALL positions
    size: 4,    // each f32 is 4 bytes
    kind: Float, // every element is float
}])
```

Instead of listing 100 separate Types with offsets `0,4,8,12...396`

#### Example 2: Slice `&[i32]`
```rust
// Pointer to slice data
TypeTree(vec![Type {
    offset: -1, size: 8, kind: Pointer,
    child: TypeTree(vec![Type {
        offset: -1, // ALL slice elements
        size: 4,    // each i32 is 4 bytes
        kind: Integer
    }])
}])
```

#### Example 3: Mixed Structure
```rust
struct Container {
    header: i64,        // offset 0
    data: [f32; 1000],  // offset 8, but elements use -1
}
```

```rust
TypeTree(vec![
    Type { offset: 0, size: 8, kind: Integer }, // header
    Type { offset: 8, size: 4000, kind: Pointer,
        child: TypeTree(vec![Type {
            offset: -1, size: 4, kind: Float // ALL array elements
        }])
    }
])
```

44 files changed, 631 insertions, 1 deletions

diff --git a/tests/codegen-llvm/autodiff/typetree.rs b/tests/codegen-llvm/autodiff/typetree.rs
new file mode 100644
index 00000000000..1cb0c2fb68b
--- /dev/null
+++ b/tests/codegen-llvm/autodiff/typetree.rs
@@ -0,0 +1,33 @@
+//@ compile-flags: -Zautodiff=Enable -C opt-level=3 -Clto=fat
+//@ no-prefer-dynamic
+//@ needs-enzyme
+
+// Test that basic autodiff still works with our TypeTree infrastructure
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_simple, Duplicated, Active)]
+#[no_mangle]
+#[inline(never)]
+fn simple(x: &f64) -> f64 {
+    2.0 * x
+}
+
+// CHECK-LABEL: @simple
+// CHECK: fmul double
+
+// The derivative function should be generated normally
+// CHECK-LABEL: diffesimple
+// CHECK: fadd fast double
+
+fn main() {
+    let x = std::hint::black_box(3.0);
+    let output = simple(&x);
+    assert_eq!(6.0, output);
+
+    let mut df_dx = 0.0;
+    let output_ = d_simple(&x, &mut df_dx, 1.0);
+    assert_eq!(output, output_);
+    assert_eq!(2.0, df_dx);
+}
diff --git a/tests/run-make/autodiff/type-trees/array-typetree/array.check b/tests/run-make/autodiff/type-trees/array-typetree/array.check
new file mode 100644
index 00000000000..0d38bdec17e
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/array-typetree/array.check
@@ -0,0 +1,4 @@
+; Check that array TypeTree metadata is correctly generated  
+; Should show Float@double at each array element offset (0, 8, 16, 24, 32 bytes)
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_array{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,-1]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/array-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/array-typetree/rmake.rs
new file mode 100644
index 00000000000..20b6a066906
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/array-typetree/rmake.rs
@@ -0,0 +1,9 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+    llvm_filecheck().patterns("array.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/array-typetree/test.rs b/tests/run-make/autodiff/type-trees/array-typetree/test.rs
new file mode 100644
index 00000000000..f54ebf5a4c7
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/array-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_array(arr: &[f64; 5]) -> f64 {
+    arr[0] + arr[1] + arr[2] + arr[3] + arr[4]
+}
+
+fn main() {
+    let arr = [1.0, 2.0, 3.0, 4.0, 5.0];
+    let mut d_arr = [0.0; 5];
+    let _result = d_test(&arr, &mut d_arr, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy-ir.check b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy-ir.check
new file mode 100644
index 00000000000..0e6351ac4d3
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy-ir.check
@@ -0,0 +1,8 @@
+; Check that enzyme_type attributes are present in the LLVM IR function definition
+; This verifies our TypeTree system correctly attaches metadata for Enzyme
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_memcpy({{.*}}"enzyme_type"="{[-1]:Pointer, [-1,-1]:Float@double}"
+
+; Check that llvm.memcpy exists (either call or declare)
+CHECK: {{(call|declare).*}}@llvm.memcpy
+
diff --git a/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.check b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.check
new file mode 100644
index 00000000000..ae70830297a
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.check
@@ -0,0 +1,13 @@
+CHECK: force_memcpy
+
+CHECK: @llvm.memcpy.p0.p0.i64
+
+CHECK: test_memcpy - {[-1]:Float@double} |{[-1]:Pointer}:{}
+
+CHECK-DAG: ptr %{{[0-9]+}}: {[-1]:Pointer, [-1,0]:Float@double, [-1,8]:Float@double, [-1,16]:Float@double, [-1,24]:Float@double}
+
+CHECK-DAG: load double{{.*}}: {[-1]:Float@double}
+
+CHECK-DAG: fmul double{{.*}}: {[-1]:Float@double}
+
+CHECK-DAG: fadd double{{.*}}: {[-1]:Float@double}
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.rs b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.rs
new file mode 100644
index 00000000000..3c1029190c8
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/memcpy-typetree/memcpy.rs
@@ -0,0 +1,36 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+use std::ptr;
+
+#[inline(never)]
+fn force_memcpy(src: *const f64, dst: *mut f64, count: usize) {
+    unsafe {
+        ptr::copy_nonoverlapping(src, dst, count);
+    }
+}
+
+#[autodiff_reverse(d_test_memcpy, Duplicated, Active)]
+#[no_mangle]
+fn test_memcpy(input: &[f64; 128]) -> f64 {
+    let mut local_data = [0.0f64; 128];
+
+    // Use a separate function to prevent inlining and optimization
+    force_memcpy(input.as_ptr(), local_data.as_mut_ptr(), 128);
+
+    // Sum only first few elements to keep the computation simple
+    local_data[0] * local_data[0]
+        + local_data[1] * local_data[1]
+        + local_data[2] * local_data[2]
+        + local_data[3] * local_data[3]
+}
+
+fn main() {
+    let input = [1.0; 128];
+    let mut d_input = [0.0; 128];
+    let result = test_memcpy(&input);
+    let result_d = d_test_memcpy(&input, &mut d_input, 1.0);
+
+    assert_eq!(result, result_d);
+    println!("Memcpy test passed: result = {}", result);
+}
diff --git a/tests/run-make/autodiff/type-trees/memcpy-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/memcpy-typetree/rmake.rs
new file mode 100644
index 00000000000..b4c650330fe
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/memcpy-typetree/rmake.rs
@@ -0,0 +1,39 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // First, compile to LLVM IR to check for enzyme_type attributes
+    let _ir_output = rustc()
+        .input("memcpy.rs")
+        .arg("-Zautodiff=Enable")
+        .arg("-Zautodiff=NoPostopt")
+        .opt_level("0")
+        .arg("--emit=llvm-ir")
+        .arg("-o")
+        .arg("main.ll")
+        .run();
+
+    // Then compile with TypeTree analysis output for the existing checks
+    let output = rustc()
+        .input("memcpy.rs")
+        .arg("-Zautodiff=Enable,PrintTAFn=test_memcpy")
+        .arg("-Zautodiff=NoPostopt")
+        .opt_level("3")
+        .arg("-Clto=fat")
+        .arg("-g")
+        .run();
+
+    let stdout = output.stdout_utf8();
+    let stderr = output.stderr_utf8();
+    let ir_content = rfs::read_to_string("main.ll");
+
+    rfs::write("memcpy.stdout", &stdout);
+    rfs::write("memcpy.stderr", &stderr);
+    rfs::write("main.ir", &ir_content);
+
+    llvm_filecheck().patterns("memcpy.check").stdin_buf(stdout).run();
+
+    llvm_filecheck().patterns("memcpy-ir.check").stdin_buf(ir_content).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/mixed-struct-typetree/mixed.check b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/mixed.check
new file mode 100644
index 00000000000..584f5840843
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/mixed.check
@@ -0,0 +1,2 @@
+; Check that mixed struct with large array generates correct detailed type tree
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@float}"{{.*}}@test_mixed_struct{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Integer, [-1,8]:Float@float}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/mixed-struct-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/rmake.rs
new file mode 100644
index 00000000000..1c19963bc36
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/rmake.rs
@@ -0,0 +1,16 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc()
+        .input("test.rs")
+        .arg("-Zautodiff=Enable")
+        .arg("-Zautodiff=NoPostopt")
+        .opt_level("0")
+        .emit("llvm-ir")
+        .run();
+
+    llvm_filecheck().patterns("mixed.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/mixed-struct-typetree/test.rs b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/test.rs
new file mode 100644
index 00000000000..7a734980e61
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/mixed-struct-typetree/test.rs
@@ -0,0 +1,23 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[repr(C)]
+struct Container {
+    header: i64,
+    data: [f32; 1000],
+}
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+#[inline(never)]
+fn test_mixed_struct(container: &Container) -> f32 {
+    container.data[0] + container.data[999]
+}
+
+fn main() {
+    let container = Container { header: 42, data: [1.0; 1000] };
+    let mut d_container = Container { header: 0, data: [0.0; 1000] };
+    let result = d_test(&container, &mut d_container, 1.0);
+    std::hint::black_box(result);
+}
diff --git a/tests/run-make/autodiff/type-trees/nott-flag/nott.check b/tests/run-make/autodiff/type-trees/nott-flag/nott.check
new file mode 100644
index 00000000000..8d23e2ee319
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/nott-flag/nott.check
@@ -0,0 +1,5 @@
+// Check that enzyme_type attributes are NOT present when NoTT flag is used
+// This verifies the NoTT flag correctly disables TypeTree metadata
+
+CHECK: define{{.*}}@square
+CHECK-NOT: "enzyme_type"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/nott-flag/rmake.rs b/tests/run-make/autodiff/type-trees/nott-flag/rmake.rs
new file mode 100644
index 00000000000..de540b990ca
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/nott-flag/rmake.rs
@@ -0,0 +1,30 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Test with NoTT flag - should not generate TypeTree metadata
+    rustc()
+        .input("test.rs")
+        .arg("-Zautodiff=Enable,NoTT")
+        .emit("llvm-ir")
+        .arg("-o")
+        .arg("nott.ll")
+        .run();
+
+    // Test without NoTT flag - should generate TypeTree metadata
+    rustc()
+        .input("test.rs")
+        .arg("-Zautodiff=Enable")
+        .emit("llvm-ir")
+        .arg("-o")
+        .arg("with_tt.ll")
+        .run();
+
+    // Verify NoTT version does NOT have enzyme_type attributes
+    llvm_filecheck().patterns("nott.check").stdin_buf(rfs::read("nott.ll")).run();
+
+    // Verify TypeTree version DOES have enzyme_type attributes
+    llvm_filecheck().patterns("with_tt.check").stdin_buf(rfs::read("with_tt.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/nott-flag/test.rs b/tests/run-make/autodiff/type-trees/nott-flag/test.rs
new file mode 100644
index 00000000000..de3549c37c6
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/nott-flag/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_square, Duplicated, Active)]
+#[no_mangle]
+fn square(x: &f64) -> f64 {
+    x * x
+}
+
+fn main() {
+    let x = 2.0;
+    let mut dx = 0.0;
+    let _result = d_square(&x, &mut dx, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/nott-flag/with_tt.check b/tests/run-make/autodiff/type-trees/nott-flag/with_tt.check
new file mode 100644
index 00000000000..0b4c9119179
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/nott-flag/with_tt.check
@@ -0,0 +1,4 @@
+// Check that enzyme_type attributes are present when TypeTree is enabled
+// This verifies our TypeTree metadata attachment is working
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@square{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/recursion-typetree/recursion.check b/tests/run-make/autodiff/type-trees/recursion-typetree/recursion.check
new file mode 100644
index 00000000000..1960e7b816c
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/recursion-typetree/recursion.check
@@ -0,0 +1,3 @@
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_deep{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double}"
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_graph{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Integer, [-1,8]:Integer, [-1,16]:Integer, [-1,24]:Float@double}"
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_node{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/recursion-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/recursion-typetree/rmake.rs
new file mode 100644
index 00000000000..78718f3a215
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/recursion-typetree/rmake.rs
@@ -0,0 +1,9 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+    llvm_filecheck().patterns("recursion.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/recursion-typetree/test.rs b/tests/run-make/autodiff/type-trees/recursion-typetree/test.rs
new file mode 100644
index 00000000000..9d40bec1bf1
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/recursion-typetree/test.rs
@@ -0,0 +1,100 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+// Self-referential struct to test recursion detection
+#[derive(Clone)]
+struct Node {
+    value: f64,
+    next: Option<Box<Node>>,
+}
+
+// Mutually recursive structs to test cycle detection
+#[derive(Clone)]
+struct GraphNodeA {
+    value: f64,
+    connections: Vec<GraphNodeB>,
+}
+
+#[derive(Clone)]
+struct GraphNodeB {
+    weight: f64,
+    target: Option<Box<GraphNodeA>>,
+}
+
+#[autodiff_reverse(d_test_node, Duplicated, Active)]
+#[no_mangle]
+fn test_node(node: &Node) -> f64 {
+    node.value * 2.0
+}
+
+#[autodiff_reverse(d_test_graph, Duplicated, Active)]
+#[no_mangle]
+fn test_graph(a: &GraphNodeA) -> f64 {
+    a.value * 3.0
+}
+
+// Simple depth test - deeply nested but not circular
+#[derive(Clone)]
+struct Level1 {
+    val: f64,
+    next: Option<Box<Level2>>,
+}
+#[derive(Clone)]
+struct Level2 {
+    val: f64,
+    next: Option<Box<Level3>>,
+}
+#[derive(Clone)]
+struct Level3 {
+    val: f64,
+    next: Option<Box<Level4>>,
+}
+#[derive(Clone)]
+struct Level4 {
+    val: f64,
+    next: Option<Box<Level5>>,
+}
+#[derive(Clone)]
+struct Level5 {
+    val: f64,
+    next: Option<Box<Level6>>,
+}
+#[derive(Clone)]
+struct Level6 {
+    val: f64,
+    next: Option<Box<Level7>>,
+}
+#[derive(Clone)]
+struct Level7 {
+    val: f64,
+    next: Option<Box<Level8>>,
+}
+#[derive(Clone)]
+struct Level8 {
+    val: f64,
+}
+
+#[autodiff_reverse(d_test_deep, Duplicated, Active)]
+#[no_mangle]
+fn test_deep(deep: &Level1) -> f64 {
+    deep.val * 4.0
+}
+
+fn main() {
+    let node = Node { value: 1.0, next: None };
+
+    let graph = GraphNodeA { value: 2.0, connections: vec![] };
+
+    let deep = Level1 { val: 5.0, next: None };
+
+    let mut d_node = Node { value: 0.0, next: None };
+
+    let mut d_graph = GraphNodeA { value: 0.0, connections: vec![] };
+
+    let mut d_deep = Level1 { val: 0.0, next: None };
+
+    let _result1 = d_test_node(&node, &mut d_node, 1.0);
+    let _result2 = d_test_graph(&graph, &mut d_graph, 1.0);
+    let _result3 = d_test_deep(&deep, &mut d_deep, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/f128.check b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/f128.check
new file mode 100644
index 00000000000..23db64eea52
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/f128.check
@@ -0,0 +1,4 @@
+; Check that f128 TypeTree metadata is correctly generated
+; Should show Float@fp128 for f128 values and Pointer for references
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@fp128}"{{.*}}@test_f128{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@fp128}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/rmake.rs
new file mode 100644
index 00000000000..44320ecdd57
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/rmake.rs
@@ -0,0 +1,12 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Compile with TypeTree enabled and emit LLVM IR
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+
+    // Check that f128 TypeTree metadata is correctly generated
+    llvm_filecheck().patterns("f128.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/test.rs b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/test.rs
new file mode 100644
index 00000000000..5c71baa3e69
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f128-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff, f128)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_f128(x: &f128) -> f128 {
+    *x * *x
+}
+
+fn main() {
+    let x = 2.0_f128;
+    let mut dx = 0.0_f128;
+    let _result = d_test(&x, &mut dx, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/f16.check b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/f16.check
new file mode 100644
index 00000000000..9adff68d36f
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/f16.check
@@ -0,0 +1,4 @@
+; Check that f16 TypeTree metadata is correctly generated
+; Should show Float@half for f16 values and Pointer for references
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@half}"{{.*}}@test_f16{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@half}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/rmake.rs
new file mode 100644
index 00000000000..0aebdbf5520
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/rmake.rs
@@ -0,0 +1,12 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Compile with TypeTree enabled and emit LLVM IR
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+
+    // Check that f16 TypeTree metadata is correctly generated
+    llvm_filecheck().patterns("f16.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/test.rs b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/test.rs
new file mode 100644
index 00000000000..6b68e8252f4
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f16-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff, f16)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_f16(x: &f16) -> f16 {
+    *x * *x
+}
+
+fn main() {
+    let x = 2.0_f16;
+    let mut dx = 0.0_f16;
+    let _result = d_test(&x, &mut dx, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/f32.check b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/f32.check
new file mode 100644
index 00000000000..176630f57e8
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/f32.check
@@ -0,0 +1,4 @@
+; Check that f32 TypeTree metadata is correctly generated
+; Should show Float@float for f32 values and Pointer for references
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@float}"{{.*}}@test_f32{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@float}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/rmake.rs
new file mode 100644
index 00000000000..ee3ab753bf5
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/rmake.rs
@@ -0,0 +1,12 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Compile with TypeTree enabled and emit LLVM IR
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+
+    // Check that f32 TypeTree metadata is correctly generated
+    llvm_filecheck().patterns("f32.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/test.rs b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/test.rs
new file mode 100644
index 00000000000..56c118399ee
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f32-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_f32(x: &f32) -> f32 {
+    x * x
+}
+
+fn main() {
+    let x = 2.0_f32;
+    let mut dx = 0.0_f32;
+    let _result = d_test(&x, &mut dx, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/f64.check b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/f64.check
new file mode 100644
index 00000000000..929cd379694
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/f64.check
@@ -0,0 +1,4 @@
+; Check that f64 TypeTree metadata is correctly generated  
+; Should show Float@double for f64 values and Pointer for references
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_f64{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/rmake.rs
new file mode 100644
index 00000000000..5fac9b23bc8
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/rmake.rs
@@ -0,0 +1,12 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Compile with TypeTree enabled and emit LLVM IR
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+
+    // Check that f64 TypeTree metadata is correctly generated
+    llvm_filecheck().patterns("f64.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/test.rs b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/test.rs
new file mode 100644
index 00000000000..235360b76b2
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/f64-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_f64(x: &f64) -> f64 {
+    x * x
+}
+
+fn main() {
+    let x = 2.0_f64;
+    let mut dx = 0.0_f64;
+    let _result = d_test(&x, &mut dx, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/i32.check b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/i32.check
new file mode 100644
index 00000000000..dee4aa5bbb6
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/i32.check
@@ -0,0 +1,4 @@
+; Check that i32 TypeTree metadata is correctly generated
+; Should show Integer for i32 values and Pointer for references
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Integer}"{{.*}}@test_i32{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Integer}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/rmake.rs
new file mode 100644
index 00000000000..a40fd55d88a
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/rmake.rs
@@ -0,0 +1,12 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    // Compile with TypeTree enabled and emit LLVM IR
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+
+    // Check that i32 TypeTree metadata is correctly generated
+    llvm_filecheck().patterns("i32.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/test.rs b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/test.rs
new file mode 100644
index 00000000000..249803c5d9f
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/scalar-types/i32-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_i32(x: &i32) -> i32 {
+    x * x
+}
+
+fn main() {
+    let x = 5_i32;
+    let mut dx = 0_i32;
+    let _result = d_test(&x, &mut dx, 1);
+}
diff --git a/tests/run-make/autodiff/type-trees/slice-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/slice-typetree/rmake.rs
new file mode 100644
index 00000000000..b81fb50bf1a
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/slice-typetree/rmake.rs
@@ -0,0 +1,9 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+    llvm_filecheck().patterns("slice.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/slice-typetree/slice.check b/tests/run-make/autodiff/type-trees/slice-typetree/slice.check
new file mode 100644
index 00000000000..6543b616115
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/slice-typetree/slice.check
@@ -0,0 +1,4 @@
+; Check that slice TypeTree metadata is correctly generated
+; Should show Float@double for slice elements
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_slice{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,-1]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/slice-typetree/test.rs b/tests/run-make/autodiff/type-trees/slice-typetree/test.rs
new file mode 100644
index 00000000000..7117fa3844f
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/slice-typetree/test.rs
@@ -0,0 +1,16 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_slice(slice: &[f64]) -> f64 {
+    slice.iter().sum()
+}
+
+fn main() {
+    let arr = [1.0, 2.0, 3.0, 4.0, 5.0];
+    let slice = &arr[..];
+    let mut d_slice = [0.0; 5];
+    let _result = d_test(slice, &mut d_slice[..], 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/struct-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/struct-typetree/rmake.rs
new file mode 100644
index 00000000000..0af1b65ee18
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/struct-typetree/rmake.rs
@@ -0,0 +1,9 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+    llvm_filecheck().patterns("struct.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/struct-typetree/struct.check b/tests/run-make/autodiff/type-trees/struct-typetree/struct.check
new file mode 100644
index 00000000000..54956317e1e
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/struct-typetree/struct.check
@@ -0,0 +1,4 @@
+; Check that struct TypeTree metadata is correctly generated
+; Should show Float@double at offsets 0, 8, 16 for Point struct fields
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_struct{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double, [-1,8]:Float@double, [-1,16]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/struct-typetree/test.rs b/tests/run-make/autodiff/type-trees/struct-typetree/test.rs
new file mode 100644
index 00000000000..cbe7b10e409
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/struct-typetree/test.rs
@@ -0,0 +1,22 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[repr(C)]
+struct Point {
+    x: f64,
+    y: f64,
+    z: f64,
+}
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_struct(point: &Point) -> f64 {
+    point.x + point.y * 2.0 + point.z * 3.0
+}
+
+fn main() {
+    let point = Point { x: 1.0, y: 2.0, z: 3.0 };
+    let mut d_point = Point { x: 0.0, y: 0.0, z: 0.0 };
+    let _result = d_test(&point, &mut d_point, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/tuple-typetree/rmake.rs b/tests/run-make/autodiff/type-trees/tuple-typetree/rmake.rs
new file mode 100644
index 00000000000..76913828901
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/tuple-typetree/rmake.rs
@@ -0,0 +1,9 @@
+//@ needs-enzyme
+//@ ignore-cross-compile
+
+use run_make_support::{llvm_filecheck, rfs, rustc};
+
+fn main() {
+    rustc().input("test.rs").arg("-Zautodiff=Enable").emit("llvm-ir").run();
+    llvm_filecheck().patterns("tuple.check").stdin_buf(rfs::read("test.ll")).run();
+}
diff --git a/tests/run-make/autodiff/type-trees/tuple-typetree/test.rs b/tests/run-make/autodiff/type-trees/tuple-typetree/test.rs
new file mode 100644
index 00000000000..32187b587a3
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/tuple-typetree/test.rs
@@ -0,0 +1,15 @@
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+#[autodiff_reverse(d_test, Duplicated, Active)]
+#[no_mangle]
+fn test_tuple(tuple: &(f64, f64, f64)) -> f64 {
+    tuple.0 + tuple.1 * 2.0 + tuple.2 * 3.0
+}
+
+fn main() {
+    let tuple = (1.0, 2.0, 3.0);
+    let mut d_tuple = (0.0, 0.0, 0.0);
+    let _result = d_test(&tuple, &mut d_tuple, 1.0);
+}
diff --git a/tests/run-make/autodiff/type-trees/tuple-typetree/tuple.check b/tests/run-make/autodiff/type-trees/tuple-typetree/tuple.check
new file mode 100644
index 00000000000..47647e78cc3
--- /dev/null
+++ b/tests/run-make/autodiff/type-trees/tuple-typetree/tuple.check
@@ -0,0 +1,4 @@
+; Check that tuple TypeTree metadata is correctly generated
+; Should show Float@double at offsets 0, 8, 16 for (f64, f64, f64)
+
+CHECK: define{{.*}}"enzyme_type"="{[-1]:Float@double}"{{.*}}@test_tuple{{.*}}"enzyme_type"="{[-1]:Pointer, [-1,0]:Float@double, [-1,8]:Float@double, [-1,16]:Float@double}"
\ No newline at end of file
diff --git a/tests/run-make/autodiff/type-trees/type-analysis/vec/vec.check b/tests/run-make/autodiff/type-trees/type-analysis/vec/vec.check
index dcf9508b69d..cdb70eb83fc 100644
--- a/tests/run-make/autodiff/type-trees/type-analysis/vec/vec.check
+++ b/tests/run-make/autodiff/type-trees/type-analysis/vec/vec.check
@@ -1,7 +1,7 @@
 // CHECK: callee - {[-1]:Float@float} |{[-1]:Pointer}:{}
 // CHECK: ptr %{{[0-9]+}}: {[-1]:Pointer}
 // CHECK-DAG: %{{[0-9]+}} = getelementptr inbounds nuw i8, ptr %{{[0-9]+}}, i64 8, !dbg !{{[0-9]+}}: {[-1]:Pointer}
-// CHECK-DAG: %{{[0-9]+}} = load ptr, ptr %{{[0-9]+}}, align 8, !dbg !{{[0-9]+}}, !nonnull !102, !noundef !{{[0-9]+}}: {}
+// CHECK-DAG: %{{[0-9]+}} = load ptr, ptr %{{[0-9]+}}, align 8, !dbg !{{[0-9]+}}, !nonnull !{{[0-9]+}}, !noundef !{{[0-9]+}}: {}
 // CHECK-DAG: %{{[0-9]+}} = getelementptr inbounds nuw i8, ptr %{{[0-9]+}}, i64 16, !dbg !{{[0-9]+}}: {[-1]:Pointer}
 // CHECK-DAG: %{{[0-9]+}} = load i64, ptr %{{[0-9]+}}, align 8, !dbg !{{[0-9]+}}, !noundef !{{[0-9]+}}: {}
 // CHECK-DAG: %{{[0-9]+}} = icmp eq i64 %{{[0-9]+}}, 0, !dbg !{{[0-9]+}}: {[-1]:Integer}
diff --git a/tests/ui/autodiff/flag_nott.rs b/tests/ui/autodiff/flag_nott.rs
new file mode 100644
index 00000000000..faa9949fe81
--- /dev/null
+++ b/tests/ui/autodiff/flag_nott.rs
@@ -0,0 +1,19 @@
+//@ compile-flags: -Zautodiff=Enable,NoTT
+//@ needs-enzyme
+//@ check-pass
+
+#![feature(autodiff)]
+
+use std::autodiff::autodiff_reverse;
+
+// Test that NoTT flag is accepted and doesn't cause compilation errors
+#[autodiff_reverse(d_square, Duplicated, Active)]
+fn square(x: &f64) -> f64 {
+    x * x
+}
+
+fn main() {
+    let x = 2.0;
+    let mut dx = 0.0;
+    let result = d_square(&x, &mut dx, 1.0);
+}