Skip to content

Commit 223be22

Browse files
SonicFieldSonicField
committed
Phase 4.X-full X2b (Batch 92): NEW PhxPtrSet open-address hash substrate + verifier
Per supervisor 03:17:18Z next-up dispatch + theologian docs/tier7-phase4x-full-entry-preanalysis-2026-05-01.md §2.4. X2b is substrate-only authoring (no migration this batch); X2c will replace std::unordered_set<BasicBlock*> processed/loop_headers at builder.cpp: 840-841 (translate() loop) → discharges E-7 substrate dependency. Pre-author substrate-grep per supervisor instruction: confirmed ZERO existing PhxPtrSet/PhxBlockPtrSet/phx_ptr_set tokens in Python/jit/hir/. Existing PhxBlockSet at licm_c.c:20-40 is dense bit-array indexed by block ID — different impl-class (use-class requires known max block ID upfront); cannot be reused for translate() pointer-keyed set semantic. Pre-commit chat-recheck applied per discipline (latest fixup checkpoint, no disposition reversal). NEW phx_ptr_set.h (137 LOC): - typedef struct PhxPtrSet { void **entries; size_t count; size_t capacity } - 7 static-inline ops: init/destroy/clear/contains/insert/insert_raw/resize + slot/size helpers - Open-addressed hash with linear probing - Power-of-2 capacity; PHX_PTR_SET_INITIAL_CAP=16u; load factor 0.7 triggers resize doubling - Knuth multiplicative hash on uintptr_t (64-bit constant 11400714819323198485) - Empty-slot sentinel: entries[i] == NULL - NULL-key invariant: cannot store NULL as a member (sentinel collision); callers must guard NULL-pointer insertion if NULL is a possible key - Allocator: plain calloc/realloc/free (matches phx_ptr_array.h sibling pattern; calloc zero-inits new entries to NULL sentinel) - Forward stance python#4: JIT_CHECK_C(new_entries != NULL, ...) loud-fail post-calloc per X1a 0bac3bc precedent Verifier (hir_instr_c_verify.cpp +90 LOC, batch92 6-section coverage): - (a) empty: contains 0, size 0, lazy-alloc invariant - (b) single insert + contains: returns 1 / size 1 / contains 1 - (c) duplicate insert: returns 0, size unchanged - (d) multi insert + contains across 3 keys + non-inserted-not-contained - (e) resize past initial cap (16): 20 distinct-key inserts; size 23 (3 prior + 20); capacity grew past 16; ALL pre-resize + post-resize keys still contained (validates rehash correctness) - (f) clear + reuse: count resets, contains returns 0; subsequent insert works without re-init; destroy resets all fields Substrate ready for X2c E-7 translate() std::unordered_set→PhxPtrSet migration. Header-only zero-cost abstraction; release-codegen IDENTICAL modulo new symbols. Phase 4.X-full progress: 2.1 ThreadedCompileSerialize DONE / 2.7 PhxBCOffsetSet (X1a-X1b, E-8 DISCHARGED) / 2.4 PhxPtrQueue (X2a) + PhxPtrSet (this) — all 4 substrate classes initiated. Phase 4.X-full inventory unchanged at 8 stay-C++ exceptions; X2c migration discharges E-7, X2d migration discharges E-5. Cumulative-drift watch counter: 12/5+. Header-only structural no-op (X2a precedent — substrate-only authoring is empirically variance-class); gatekeeper cap-check eligibility decision (13/20 since D3a reset). Per supervisor M-slate dispatch D-1777572112 + Phase 4.X-full ENTRY + X2b dispatch (LEAD: generalist, medium-STRUCT tier per pre-analysis §5).
1 parent f0673cf commit 223be22

2 files changed

Lines changed: 226 additions & 0 deletions

File tree

‎Python/jit/hir/hir_instr_c_verify.cpp‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@
1717
#include "cinderx/Jit/hir/typed_argument_c.h" /* phx_typed_argument_pytype_swap (Batch 76) */
1818
#include "cinderx/Jit/hir/phx_bc_offset_set.h" /* Phase 4.X-full X1a (Batch 89) */
1919
#include "cinderx/Jit/hir/phx_ptr_queue.h" /* Phase 4.X-full X2a (Batch 91) */
20+
#include "cinderx/Jit/hir/phx_ptr_set.h" /* Phase 4.X-full X2b (Batch 92) */
2021

2122
#include <cassert>
2223
#include <cstring>
@@ -4237,6 +4238,94 @@ static void verify_phase4x_full_batch91_ptr_queue() {
42374238
"Phase 4.X-full Batch 91(e): destroy resets all fields");
42384239
}
42394240

4241+
/* Phase 4.X-full X2b Batch 92 (supervisor 03:17:18Z next-up): PhxPtrSet
4242+
* substrate falsifier. Generic void*-keyed open-address hash set with
4243+
* linear probing + load-factor-0.7 resize doubling. Discharges X2c E-7
4244+
* translate() std::unordered_set<BasicBlock*> processed/loop_headers
4245+
* substrate need. Coverage: empty/single insert+contains/duplicate
4246+
* insert/multi insert + contains/resize past initial cap/clear+reuse. */
4247+
static void verify_phase4x_full_batch92_ptr_set() {
4248+
PhxPtrSet s;
4249+
phx_ptr_set_init(&s);
4250+
4251+
/* (a) empty: contains returns 0; size 0; lazy-alloc invariant */
4252+
int marker_a = 0xA;
4253+
assert(phx_ptr_set_size(&s) == 0 &&
4254+
"Phase 4.X-full Batch 92(a): empty size==0");
4255+
assert(phx_ptr_set_contains(&s, &marker_a) == 0 &&
4256+
"Phase 4.X-full Batch 92(a): contains on empty returns 0");
4257+
assert(s.entries == NULL && s.capacity == 0 &&
4258+
"Phase 4.X-full Batch 92(a): lazy-alloc invariant");
4259+
4260+
/* (b) single insert + contains */
4261+
int r = phx_ptr_set_insert(&s, &marker_a);
4262+
assert(r == 1 &&
4263+
"Phase 4.X-full Batch 92(b): first insert returns 1");
4264+
assert(phx_ptr_set_size(&s) == 1 &&
4265+
"Phase 4.X-full Batch 92(b): size==1 after insert");
4266+
assert(phx_ptr_set_contains(&s, &marker_a) == 1 &&
4267+
"Phase 4.X-full Batch 92(b): contains returns 1 for inserted key");
4268+
4269+
/* (c) duplicate insert: returns 0, size unchanged */
4270+
int r_dup = phx_ptr_set_insert(&s, &marker_a);
4271+
assert(r_dup == 0 &&
4272+
"Phase 4.X-full Batch 92(c): dup insert returns 0");
4273+
assert(phx_ptr_set_size(&s) == 1 &&
4274+
"Phase 4.X-full Batch 92(c): size unchanged on dup");
4275+
4276+
/* (d) multi insert + contains across keys */
4277+
int marker_b = 0xB;
4278+
int marker_c = 0xC;
4279+
phx_ptr_set_insert(&s, &marker_b);
4280+
phx_ptr_set_insert(&s, &marker_c);
4281+
assert(phx_ptr_set_size(&s) == 3 &&
4282+
"Phase 4.X-full Batch 92(d): size==3 after multi-insert");
4283+
assert(phx_ptr_set_contains(&s, &marker_a) == 1 &&
4284+
phx_ptr_set_contains(&s, &marker_b) == 1 &&
4285+
phx_ptr_set_contains(&s, &marker_c) == 1 &&
4286+
"Phase 4.X-full Batch 92(d): all 3 keys contained");
4287+
int marker_z = 0xDEAD;
4288+
assert(phx_ptr_set_contains(&s, &marker_z) == 0 &&
4289+
"Phase 4.X-full Batch 92(d): non-inserted key not contained");
4290+
4291+
/* (e) resize past initial cap (16): insert 20 distinct keys; verify
4292+
* all original keys still contained post-resize. */
4293+
int markers[20];
4294+
for (int i = 0; i < 20; i++) {
4295+
markers[i] = i;
4296+
phx_ptr_set_insert(&s, &markers[i]);
4297+
}
4298+
/* count = 3 (a/b/c) + 20 (markers[0..19]) = 23 */
4299+
assert(phx_ptr_set_size(&s) == 23 &&
4300+
"Phase 4.X-full Batch 92(e): size 23 after 20-key resize");
4301+
assert(s.capacity >= 32 &&
4302+
"Phase 4.X-full Batch 92(e): capacity grew past initial 16");
4303+
/* Original 3 keys + all 20 markers must be contained post-resize */
4304+
assert(phx_ptr_set_contains(&s, &marker_a) == 1 &&
4305+
phx_ptr_set_contains(&s, &marker_b) == 1 &&
4306+
phx_ptr_set_contains(&s, &marker_c) == 1 &&
4307+
"Phase 4.X-full Batch 92(e): pre-resize keys preserved");
4308+
for (int i = 0; i < 20; i++) {
4309+
assert(phx_ptr_set_contains(&s, &markers[i]) == 1 &&
4310+
"Phase 4.X-full Batch 92(e): post-resize keys all contained");
4311+
}
4312+
4313+
/* (f) clear + reuse: count resets, contains returns 0; subsequent
4314+
* insert works without re-init */
4315+
phx_ptr_set_clear(&s);
4316+
assert(phx_ptr_set_size(&s) == 0 &&
4317+
"Phase 4.X-full Batch 92(f): clear sets size 0");
4318+
assert(phx_ptr_set_contains(&s, &marker_a) == 0 &&
4319+
"Phase 4.X-full Batch 92(f): post-clear contains returns 0");
4320+
phx_ptr_set_insert(&s, &marker_a);
4321+
assert(phx_ptr_set_contains(&s, &marker_a) == 1 &&
4322+
"Phase 4.X-full Batch 92(f): post-clear insert works");
4323+
4324+
phx_ptr_set_destroy(&s);
4325+
assert(s.entries == NULL && s.capacity == 0 && s.count == 0 &&
4326+
"Phase 4.X-full Batch 92(f): destroy resets all fields");
4327+
}
4328+
42404329
__attribute__((constructor))
42414330
static void hir_instr_runtime_check() {
42424331
verify_hir_instr_read_through_cast();
@@ -4308,4 +4397,5 @@ static void hir_instr_runtime_check() {
43084397
verify_phase4d_batch87_d5a_entries();
43094398
verify_phase4x_full_batch89_bc_offset_set();
43104399
verify_phase4x_full_batch91_ptr_queue();
4400+
verify_phase4x_full_batch92_ptr_set();
43114401
}

‎Python/jit/hir/phx_ptr_set.h‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
/* Copyright (c) Meta Platforms, Inc. and affiliates.
2+
*
3+
* PhxPtrSet — generic void*-keyed open-addressed hash set. Phase 4.X-full
4+
* X2b substrate per supervisor 03:17:18Z next-up + theologian
5+
* docs/tier7-phase4x-full-entry-preanalysis-2026-05-01.md §2.4.
6+
*
7+
* Use-class: hash-based set membership for pointer keys (e.g. translate()
8+
* processed BasicBlock*, loop_headers BasicBlock*). Replaces
9+
* std::unordered_set<T*> at the builder.cpp seam. X2c migration consumes
10+
* for E-7 translate() loop discharge.
11+
*
12+
* Implementation: power-of-2 capacity, linear probing, load factor 0.7
13+
* triggers resize (double). Hash: Knuth multiplicative on uintptr_t cast
14+
* of pointer. Empty slot sentinel: key==NULL.
15+
*
16+
* NULL-key invariant: PhxPtrSet cannot store NULL as a member — NULL is
17+
* reserved as the empty-slot sentinel. Callers must guard NULL-pointer
18+
* insertion if NULL is a possible key value.
19+
*
20+
* Allocator: plain calloc/realloc/free (matches phx_ptr_array.h sibling
21+
* pattern). Forward stance #4 discharged via JIT_CHECK_C(new_entries !=
22+
* NULL) loud-fail post-allocation per X1a 0bac3bc31d precedent.
23+
*/
24+
#pragma once
25+
26+
#include <stddef.h>
27+
#include <stdint.h>
28+
#include <stdlib.h>
29+
#include <string.h>
30+
31+
#include "cinderx/Common/jit_log_c.h" /* JIT_CHECK_C loud-fail on alloc OOM */
32+
33+
#ifdef __cplusplus
34+
extern "C" {
35+
#endif
36+
37+
typedef struct PhxPtrSet {
38+
void **entries;
39+
size_t count;
40+
size_t capacity; /* power-of-2; 0 ⇒ entries NULL (lazy init) */
41+
} PhxPtrSet;
42+
43+
#define PHX_PTR_SET_INITIAL_CAP 16u
44+
#define PHX_PTR_SET_LOAD_NUM 7u
45+
#define PHX_PTR_SET_LOAD_DEN 10u
46+
47+
static inline void phx_ptr_set_init(PhxPtrSet *s) {
48+
s->entries = NULL;
49+
s->count = 0;
50+
s->capacity = 0;
51+
}
52+
53+
static inline void phx_ptr_set_destroy(PhxPtrSet *s) {
54+
if (s->entries) {
55+
free(s->entries);
56+
s->entries = NULL;
57+
}
58+
s->count = 0;
59+
s->capacity = 0;
60+
}
61+
62+
static inline void phx_ptr_set_clear(PhxPtrSet *s) {
63+
if (s->entries && s->capacity) {
64+
memset(s->entries, 0, s->capacity * sizeof(void *));
65+
}
66+
s->count = 0;
67+
}
68+
69+
/* Knuth multiplicative hash on uintptr_t, mask to power-of-2 capacity. */
70+
static inline size_t phx_ptr_set_slot(size_t cap, const void *key) {
71+
uint64_t k = (uint64_t)(uintptr_t)key;
72+
/* Knuth 64-bit multiplicative constant; truncate to 32 bits before mask. */
73+
uint32_t h = (uint32_t)((k * 11400714819323198485ULL) >> 32);
74+
return (size_t)h & (cap - 1u);
75+
}
76+
77+
/* Returns 1 if key is present, 0 otherwise. */
78+
static inline int phx_ptr_set_contains(const PhxPtrSet *s, const void *key) {
79+
if (s->capacity == 0 || s->entries == NULL) return 0;
80+
size_t i = phx_ptr_set_slot(s->capacity, key);
81+
while (s->entries[i] != NULL) {
82+
if (s->entries[i] == key) return 1;
83+
i = (i + 1u) & (s->capacity - 1u);
84+
}
85+
return 0;
86+
}
87+
88+
/* Insert raw (assumes capacity > 0 and load not exceeded). */
89+
static inline int phx_ptr_set_insert_raw(PhxPtrSet *s, void *key) {
90+
size_t i = phx_ptr_set_slot(s->capacity, key);
91+
while (s->entries[i] != NULL) {
92+
if (s->entries[i] == key) return 0; /* already present */
93+
i = (i + 1u) & (s->capacity - 1u);
94+
}
95+
s->entries[i] = key;
96+
s->count++;
97+
return 1;
98+
}
99+
100+
static inline void phx_ptr_set_resize(PhxPtrSet *s, size_t new_cap) {
101+
void **old_entries = s->entries;
102+
size_t old_cap = s->capacity;
103+
void **new_entries = (void **)calloc(new_cap, sizeof(void *));
104+
JIT_CHECK_C(new_entries != NULL,
105+
"phx_ptr_set_resize calloc failed (new_cap=%zu)", new_cap);
106+
s->entries = new_entries;
107+
s->capacity = new_cap;
108+
s->count = 0;
109+
if (old_entries) {
110+
for (size_t i = 0; i < old_cap; i++) {
111+
if (old_entries[i] != NULL) {
112+
phx_ptr_set_insert_raw(s, old_entries[i]);
113+
}
114+
}
115+
free(old_entries);
116+
}
117+
}
118+
119+
/* Returns 1 if newly inserted, 0 if already present. */
120+
static inline int phx_ptr_set_insert(PhxPtrSet *s, void *key) {
121+
if (s->capacity == 0) {
122+
phx_ptr_set_resize(s, PHX_PTR_SET_INITIAL_CAP);
123+
} else if ((s->count + 1u) * PHX_PTR_SET_LOAD_DEN
124+
> s->capacity * PHX_PTR_SET_LOAD_NUM) {
125+
phx_ptr_set_resize(s, s->capacity * 2u);
126+
}
127+
return phx_ptr_set_insert_raw(s, key);
128+
}
129+
130+
static inline size_t phx_ptr_set_size(const PhxPtrSet *s) {
131+
return s->count;
132+
}
133+
134+
#ifdef __cplusplus
135+
} /* extern "C" */
136+
#endif

0 commit comments

Comments
 (0)