lib/choir/src/passes/pass/analysis.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const revision = @import("../../product/revision/root.zig");
3 const ir = @import("../../core/root.zig");
4 const passes = @import("../root.zig");
5 const subject = @import("root.zig");
6 const instrumentation = passes.instrumentation;
7
8 const AnalysisId = subject.AnalysisId;
9 const AnalysisInfo = instrumentation.AnalysisInfo;
10 const PassInfo = instrumentation.PassInfo;
11 const PassInstrumentor = instrumentation.PassInstrumentor;
12 const PassManagerRunOptions = subject.PassManagerRunOptions;
13 const PassManagerStats = subject.PassManagerStats;
14 const analysisId = subject.analysisId;
15
16 pub const AnalysisDescriptor = struct {
17 work_contract: ?subject.work.Contract = null,
18 id: AnalysisId,
19 name: []const u8,
20 required_interfaces: []const ir.InterfaceId = &.{},
21 };
22
23 pub fn Analysis(
24 comptime Value: type,
25 comptime name: []const u8,
26 comptime required_interfaces: []const ir.InterfaceId,
27 comptime compute: *const fn (*PassContext, *ir.Operation) anyerror!*Value,
28 comptime cleanup: ?*const fn (*Value, std.mem.Allocator) void,
29 comptime work_contract: ?subject.work.Contract,
30 ) type {
31 return struct {
32 pub const id = analysisId(name);
33 pub const value_type = Value;
34 pub const descriptor = AnalysisDescriptor{
35 .id = id,
36 .name = name,
37 .required_interfaces = required_interfaces,
38 .work_contract = work_contract,
39 };
40
41 pub fn get(ctx: *PassContext, op: *ir.Operation) !*Value {
42 const raw = try ctx.getAnalysis(op, &descriptor, computeOpaque, cleanupOpaque);
43 return @ptrCast(@alignCast(raw));
44 }
45
46 pub fn preserve(ctx: *PassContext) !void {
47 try ctx.preserveAnalysis(id);
48 }
49
50 fn computeOpaque(ctx: *PassContext, op: *ir.Operation) anyerror!*anyopaque {
51 return @ptrCast(try compute(ctx, op));
52 }
53
54 fn cleanupOpaque(raw: *anyopaque, allocator: std.mem.Allocator) void {
55 if (cleanup) |cleanup_fn| {
56 cleanup_fn(@ptrCast(@alignCast(raw)), allocator);
57 }
58 }
59 };
60 }
61
62 pub const PreservedAnalyses = struct {
63 allocator: std.mem.Allocator,
64 preserve_all: bool = false,
65 analysis_set: []const AnalysisId,
66 runtime_analyses: std.AutoHashMap(AnalysisId, void),
67 interfaces: std.AutoHashMap(ir.InterfaceId, void),
68
69 pub fn init(allocator: std.mem.Allocator) PreservedAnalyses {
70 return .{
71 .allocator = allocator,
72 .analysis_set = &.{},
73 .runtime_analyses = std.AutoHashMap(AnalysisId, void).init(allocator),
74 .interfaces = std.AutoHashMap(ir.InterfaceId, void).init(allocator),
75 .preserve_all = false,
76 };
77 }
78
79 pub fn deinit(self: *PreservedAnalyses) void {
80 self.runtime_analyses.deinit();
81 self.interfaces.deinit();
82 }
83
84 pub fn preserveAll(self: *PreservedAnalyses) void {
85 self.preserve_all = true;
86 }
87
88 pub fn preserveAnalysisSet(self: *PreservedAnalyses, comptime ids: []const AnalysisId) void {
89 std.debug.assert(self.analysis_set.len == 0);
90 self.analysis_set = ids;
91 }
92
93 pub fn preserveAnalysis(self: *PreservedAnalyses, id: AnalysisId) !void {
94 for (self.analysis_set) |preserved_id| {
95 if (preserved_id == id) return;
96 }
97 try self.runtime_analyses.put(id, {});
98 }
99
100 pub fn preserveInterface(self: *PreservedAnalyses, id: ir.InterfaceId) !void {
101 try self.interfaces.put(id, {});
102 }
103
104 fn preservesDescriptor(self: *const PreservedAnalyses, desc: *const AnalysisDescriptor) bool {
105 if (self.preserve_all) return true;
106 for (self.analysis_set) |id| {
107 if (id == desc.id) return true;
108 }
109 if (self.runtime_analyses.contains(desc.id)) return true;
110 if (desc.required_interfaces.len == 0) return false;
111 for (desc.required_interfaces) |iface| {
112 if (!self.interfaces.contains(iface)) return false;
113 }
114 return true;
115 }
116 };
117
118 const AnalysisKey = struct {
119 op: *ir.Operation,
120 analysis: AnalysisId,
121 };
122
123 const AnalysisEntry = struct {
124 descriptor: *const AnalysisDescriptor,
125 value: *anyopaque,
126 cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,
127 };
128
129 pub const AnalysisCache = struct {
130 allocator: std.mem.Allocator,
131 entries: std.AutoHashMap(AnalysisKey, AnalysisEntry),
132 stats: ?*PassManagerStats,
133 accounting: ?*revision.AccountingV1 = null,
134 allocation_failure: subject.work.AllocationFailure = .{},
135 entry_limit: ?u32 = null,
136
137 pub fn init(allocator: std.mem.Allocator, stats: ?*PassManagerStats) AnalysisCache {
138 return .{
139 .allocator = allocator,
140 .entries = std.AutoHashMap(AnalysisKey, AnalysisEntry).init(allocator),
141 .stats = stats,
142 };
143 }
144
145 /// The ledger outlives this fresh cache and every computation using it.
146 pub fn initAccounted(
147 allocator: std.mem.Allocator,
148 stats: ?*PassManagerStats,
149 accounting: *revision.AccountingV1,
150 allocation_failure: subject.work.AllocationFailure,
151 entry_limit: u32,
152 ) !AnalysisCache {
153 if (allocation_failure.exhausted()) {
154 accounting.fail(.exhausted);
155 return error.WorkExhausted;
156 }
157 var cache = init(allocator, stats);
158 cache.accounting = accounting;
159 cache.allocation_failure = allocation_failure;
160 cache.entry_limit = entry_limit;
161 errdefer cache.deinit();
162 const bytes = storageBound(entry_limit) catch |err| {
163 accounting.fail(.exhausted);
164 return err;
165 };
166 const token = try accounting.begin(.input, .{
167 .identity = .{ .name = "choir-analysis-cache", .version = 1 },
168 .work = .{ .allocation_capacity = bytes },
169 .workspace = bytes,
170 .retained_storage = bytes,
171 });
172 cache.entries.ensureTotalCapacity(entry_limit) catch |err| {
173 const failure = allocation_failure.classify(err);
174 accounting.fail(if (failure == error.WorkExhausted) .exhausted else .rejected);
175 try accounting.finish(token, .rejected, .{});
176 return failure;
177 };
178 try accounting.finish(token, .success, .{});
179 return cache;
180 }
181
182 /// Bounds the pinned HashMap header, aligned keys/values and one-byte slot metadata.
183 /// The table is allocated once, before the first computation, without later growth.
184 pub fn storageBound(entry_limit: u32) !u64 {
185 if (entry_limit == 0) return 0;
186 const load_capacity = @as(u64, entry_limit) * 100 / 80 + 1;
187 if (load_capacity > std.math.maxInt(u32)) return error.WorkOverflow;
188 const capacity = std.math.ceilPowerOfTwo(u32, @intCast(load_capacity)) catch
189 return error.WorkOverflow;
190 if (capacity > std.math.maxInt(u32) / 80) return error.WorkOverflow;
191 const slots: u64 = @max(8, capacity);
192 const slot_bytes = 1 + @sizeOf(AnalysisKey) + @sizeOf(AnalysisEntry);
193 const alignment = @max(@alignOf(usize), @alignOf(AnalysisKey), @alignOf(AnalysisEntry));
194 const bytes = 4 * @sizeOf(usize) + 3 * alignment + slots * slot_bytes;
195 if (bytes > std.math.maxInt(usize)) return error.WorkOverflow;
196 return bytes;
197 }
198
199 pub fn deinit(self: *AnalysisCache) void {
200 var iter = self.entries.valueIterator();
201 while (iter.next()) |entry| {
202 if (entry.cleanup) |cleanup| {
203 cleanup(entry.value, self.allocator);
204 }
205 }
206 self.entries.deinit();
207 }
208
209 pub fn getOrCompute(
210 self: *AnalysisCache,
211 ctx: *PassContext,
212 op: *ir.Operation,
213 descriptor: *const AnalysisDescriptor,
214 compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,
215 cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,
216 instrumentor: ?*const PassInstrumentor,
217 ) !*anyopaque {
218 try self.requireRunning();
219 const key = AnalysisKey{ .op = op, .analysis = descriptor.id };
220 if (self.entries.get(key)) |entry| {
221 if (self.accounting) |ledger| try ledger.observeCounters(.{ .analysis_hits = 1 });
222 if (self.stats) |stats| stats.analysis_hits += 1;
223 return entry.value;
224 }
225 const run = try Computation.begin(self.accounting, descriptor, op, ctx.run_options);
226 if (self.entry_limit) |limit| {
227 if (self.entries.count() >= limit) {
228 try run.finish(error.WorkExhausted, false);
229 return error.WorkExhausted;
230 }
231 }
232 const value = self.computeAndCache(
233 ctx,
234 op,
235 descriptor,
236 compute,
237 cleanup,
238 instrumentor,
239 ) catch |err| {
240 const failure = self.allocation_failure.classify(err);
241 try run.finish(failure, true);
242 return failure;
243 };
244 try run.finish(null, true);
245 return value;
246 }
247
248 /// Refresh replaces the cached value in place; failure must leave it intact.
249 pub fn refresh(
250 self: *AnalysisCache,
251 ctx: *PassContext,
252 op: *ir.Operation,
253 descriptor: *const AnalysisDescriptor,
254 refresh_value: *const fn (*PassContext, *ir.Operation, *anyopaque) anyerror!void,
255 instrumentor: ?*const PassInstrumentor,
256 ) !void {
257 try self.requireRunning();
258 const entry = self.entries.get(.{ .op = op, .analysis = descriptor.id }) orelse
259 return error.UncachedAnalysis;
260 const run = try Computation.begin(self.accounting, entry.descriptor, op, ctx.run_options);
261 const info = AnalysisInfo{
262 .id = descriptor.id,
263 .name = descriptor.name,
264 .target_op = op,
265 };
266 if (instrumentor) |inst| inst.runBeforeAnalysis(info);
267 refresh_value(ctx, op, entry.value) catch |err| {
268 if (instrumentor) |inst| inst.runAfterAnalysis(info);
269 const failure = self.allocation_failure.classify(err);
270 try run.finish(failure, true);
271 return failure;
272 };
273 if (instrumentor) |inst| inst.runAfterAnalysis(info);
274 self.requireRunning() catch |err| {
275 try run.finish(err, true);
276 return err;
277 };
278 if (self.stats) |stats| stats.analysis_misses += 1;
279 try run.finish(null, true);
280 }
281
282 fn computeAndCache(
283 self: *AnalysisCache,
284 ctx: *PassContext,
285 op: *ir.Operation,
286 descriptor: *const AnalysisDescriptor,
287 compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,
288 cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,
289 instrumentor: ?*const PassInstrumentor,
290 ) !*anyopaque {
291 const info = AnalysisInfo{
292 .id = descriptor.id,
293 .name = descriptor.name,
294 .target_op = op,
295 };
296 if (instrumentor) |inst| inst.runBeforeAnalysis(info);
297 const value = compute(ctx, op) catch |err| {
298 if (instrumentor) |inst| inst.runAfterAnalysis(info);
299 return err;
300 };
301 if (instrumentor) |inst| inst.runAfterAnalysis(info);
302 errdefer if (cleanup) |cleanup_fn| cleanup_fn(value, self.allocator);
303 try self.requireRunning();
304
305 const key = AnalysisKey{ .op = op, .analysis = descriptor.id };
306 const entry = AnalysisEntry{ .descriptor = descriptor, .value = value, .cleanup = cleanup };
307 if (self.entry_limit != null) {
308 self.entries.putAssumeCapacityNoClobber(key, entry);
309 } else {
310 try self.entries.put(key, entry);
311 }
312 if (self.stats) |stats| stats.analysis_misses += 1;
313 return value;
314 }
315
316 fn requireRunning(self: *AnalysisCache) !void {
317 const ledger = self.accounting orelse return;
318 if (ledger.view().outcome != .running) return error.TerminalWorkOutcome;
319 if (self.allocation_failure.exhausted()) {
320 ledger.fail(.exhausted);
321 return error.WorkExhausted;
322 }
323 }
324
325 pub fn invalidate(self: *AnalysisCache, preserved: *const PreservedAnalyses) void {
326 if (preserved.preserve_all) return;
327
328 var iter = self.entries.iterator();
329 while (iter.next()) |kv| {
330 if (!preserved.preservesDescriptor(kv.value_ptr.descriptor)) {
331 const entry = kv.value_ptr.*;
332 self.entries.removeByPtr(kv.key_ptr);
333 if (entry.cleanup) |cleanup| {
334 cleanup(entry.value, self.allocator);
335 }
336 if (self.stats) |stats| stats.analyses_invalidated += 1;
337 }
338 }
339 }
340 };
341
342 const Computation = struct {
343 ledger: ?*revision.AccountingV1,
344 token: ?u32,
345
346 fn begin(
347 ledger: ?*revision.AccountingV1,
348 descriptor: *const AnalysisDescriptor,
349 op: *ir.Operation,
350 options: PassManagerRunOptions,
351 ) !Computation {
352 return .{
353 .ledger = ledger,
354 .token = try subject.work.begin(
355 ledger,
356 .analysis,
357 descriptor.work_contract,
358 .{ .operation = op, .options = options },
359 ),
360 };
361 }
362
363 fn finish(self: Computation, err: ?anyerror, ran: bool) !void {
364 const ledger = self.ledger orelse return;
365 if (err) |failure| ledger.fail(if (failure == error.WorkExhausted or
366 failure == error.WorkOverflow) .exhausted else .rejected);
367 if (self.token) |token| {
368 try ledger.finish(token, if (err == null) .success else .rejected, .{
369 .work = .{ .analysis_computations = if (ran) 1 else 0 },
370 .counters = .{ .analysis_misses = if (err == null) 1 else 0 },
371 });
372 } else if (err == null) {
373 try ledger.observeCounters(.{ .analysis_misses = 1 });
374 }
375 }
376 };
377
378 pub const PassContext = struct {
379 op: *ir.Operation,
380
381 ir_ctx: *ir.Context,
382
383 allocator: std.mem.Allocator,
384
385 analysis_cache: *AnalysisCache,
386
387 preserved: PreservedAnalyses,
388
389 modified: bool,
390
391 instrumentor: ?*const PassInstrumentor,
392
393 run_options: PassManagerRunOptions,
394
395 pass_info: ?PassInfo,
396
397 pub fn init(
398 op: *ir.Operation,
399 ir_ctx: *ir.Context,
400 allocator: std.mem.Allocator,
401 analysis_cache: *AnalysisCache,
402 ) PassContext {
403 return initWithOptions(op, ir_ctx, allocator, analysis_cache, .{});
404 }
405
406 pub fn initWithOptions(
407 op: *ir.Operation,
408 ir_ctx: *ir.Context,
409 allocator: std.mem.Allocator,
410 analysis_cache: *AnalysisCache,
411 options: PassManagerRunOptions,
412 ) PassContext {
413 return initWithInstrumentorAndOptions(op, ir_ctx, allocator, analysis_cache, null, options);
414 }
415
416 pub fn initWithInstrumentor(
417 op: *ir.Operation,
418 ir_ctx: *ir.Context,
419 allocator: std.mem.Allocator,
420 analysis_cache: *AnalysisCache,
421 instrumentor: ?*const PassInstrumentor,
422 ) PassContext {
423 return initWithInstrumentorAndOptions(
424 op,
425 ir_ctx,
426 allocator,
427 analysis_cache,
428 instrumentor,
429 .{},
430 );
431 }
432
433 pub fn initWithInstrumentorAndOptions(
434 op: *ir.Operation,
435 ir_ctx: *ir.Context,
436 allocator: std.mem.Allocator,
437 analysis_cache: *AnalysisCache,
438 instrumentor: ?*const PassInstrumentor,
439 options: PassManagerRunOptions,
440 ) PassContext {
441 return .{
442 .op = op,
443 .ir_ctx = ir_ctx,
444 .allocator = allocator,
445 .analysis_cache = analysis_cache,
446 .preserved = PreservedAnalyses.init(allocator),
447 .modified = false,
448 .instrumentor = instrumentor,
449 .run_options = options,
450 .pass_info = null,
451 };
452 }
453
454 pub fn deinit(self: *PassContext) void {
455 self.preserved.deinit();
456 }
457
458 pub fn markModified(self: *PassContext) void {
459 self.modified = true;
460 }
461
462 pub fn preserveAllAnalyses(self: *PassContext) void {
463 self.preserved.preserveAll();
464 }
465
466 pub fn preserveAnalysisSet(self: *PassContext, comptime ids: []const AnalysisId) void {
467 self.preserved.preserveAnalysisSet(ids);
468 }
469
470 pub fn preserveAnalysis(self: *PassContext, id: AnalysisId) !void {
471 try self.preserved.preserveAnalysis(id);
472 }
473
474 pub fn preserveInterface(self: *PassContext, id: ir.InterfaceId) !void {
475 try self.preserved.preserveInterface(id);
476 }
477
478 pub fn getAnalysis(
479 self: *PassContext,
480 op: *ir.Operation,
481 descriptor: *const AnalysisDescriptor,
482 compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,
483 cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,
484 ) !*anyopaque {
485 return self.analysis_cache.getOrCompute(
486 self,
487 op,
488 descriptor,
489 compute,
490 cleanup,
491 self.instrumentor,
492 );
493 }
494
495 pub fn refreshAnalysis(
496 self: *PassContext,
497 op: *ir.Operation,
498 descriptor: *const AnalysisDescriptor,
499 refresh: *const fn (*PassContext, *ir.Operation, *anyopaque) anyerror!void,
500 ) !void {
501 try self.analysis_cache.refresh(self, op, descriptor, refresh, self.instrumentor);
502 }
503
504 pub fn incrementStatistic(
505 self: *PassContext,
506 name: []const u8,
507 description: []const u8,
508 ) void {
509 self.addStatistic(name, description, 1);
510 }
511
512 pub fn addStatistic(
513 self: *PassContext,
514 name: []const u8,
515 description: []const u8,
516 value: u64,
517 ) void {
518 const pass_info = self.pass_info orelse return;
519 const inst = self.instrumentor orelse return;
520 inst.runPassStatistic(.{
521 .pass = pass_info,
522 .name = name,
523 .description = description,
524 .value = value,
525 });
526 }
527
528 pub fn workerCount(self: *const PassContext, item_count: usize) usize {
529 return self.run_options.workerCount(item_count);
530 }
531
532 pub fn workerAllocator(self: *const PassContext) std.mem.Allocator {
533 return self.run_options.workerAllocator(self.allocator);
534 }
535 };