lib/choir/src/passes/pass/manager.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const revision = @import("../../product/revision/root.zig");
3 const choir = @import("../../root.zig");
4 const ir = @import("../../core/root.zig");
5 const passes = @import("../root.zig");
6 const subject = @import("root.zig");
7 const instrumentation = passes.instrumentation;
8
9 const textual_pipeline = passes.textual_pipeline;
10 const diagnostics = choir.diagnostics;
11 const AnalysisCache = subject.AnalysisCache;
12 const Pass = subject.Pass;
13 const PassContext = subject.PassContext;
14 const PassFailureKind = subject.PassFailureKind;
15 const PassFailureReproducer = subject.PassFailureReproducer;
16 const PassInfo = instrumentation.PassInfo;
17 const PassInstrumentation = instrumentation.PassInstrumentation;
18 const PassInstrumentor = instrumentation.PassInstrumentor;
19 const PassManagerFixedPointResult = subject.PassManagerFixedPointResult;
20 const PassManagerRunOptions = subject.PassManagerRunOptions;
21 const PassManagerStats = subject.PassManagerStats;
22 const PassResult = subject.PassResult;
23 const PassVerifierFailure = subject.PassVerifierFailure;
24 const PipelineInfo = instrumentation.PipelineInfo;
25
26 const CapturedPassFailure = struct {
27 kind: PassFailureKind,
28 pass_name: ?[]const u8 = null,
29 target_op_name: []const u8,
30 target_symbol_name: ?[]const u8 = null,
31 verifier_error: ?anyerror = null,
32 worker_count: usize = 1,
33 };
34
35 fn recordPassFailure(slot: ?*?CapturedPassFailure, failure: CapturedPassFailure) void {
36 if (slot) |captured| {
37 if (captured.* == null) captured.* = failure;
38 }
39 }
40
41 const PassVerifierConfig = struct {
42 options: ir.verify.VerifyOptions,
43 failure: *?PassVerifierFailure,
44
45 fn verifyAfterPass(self: *PassVerifierConfig, info: PassInfo) PassResult {
46 const op = info.target_op orelse return .success;
47 ir.verify.verifyOperation(op, self.options) catch |err| {
48 self.failure.* = .{
49 .pass_name = info.name,
50 .target_op_name = op.name.name,
51 .err = err,
52 };
53 return .failure;
54 };
55 return .success;
56 }
57 };
58
59 const PipelineRun = struct {
60 op: *ir.Operation,
61 ir_ctx: *ir.Context,
62 analysis_cache: *AnalysisCache,
63 stats: *PassManagerStats,
64 instrumentor: ?*const PassInstrumentor,
65 verifier: ?*PassVerifierConfig,
66 failure: ?*?CapturedPassFailure,
67 options: PassManagerRunOptions,
68 allocator: std.mem.Allocator,
69 };
70
71 const PassWork = struct {
72 ledger: ?*revision.AccountingV1,
73 token: ?u32 = null,
74 admitted: bool = true,
75 before: PassManagerStats,
76
77 fn begin(pass: Pass, run: *PipelineRun) PassWork {
78 var work = PassWork{
79 .ledger = run.analysis_cache.accounting,
80 .before = run.stats.*,
81 };
82 if (work.ledger) |ledger| {
83 if (run.analysis_cache.allocation_failure.exhausted()) {
84 ledger.fail(.exhausted);
85 work.admitted = false;
86 return work;
87 }
88 }
89 work.token = subject.work.begin(work.ledger, .pass, pass.work_contract, .{
90 .operation = run.op,
91 .state = pass.state,
92 .options = run.options,
93 }) catch {
94 work.admitted = false;
95 return work;
96 };
97 return work;
98 }
99
100 fn normalize(self: PassWork, native: PassResult, pass: Pass, run: *PipelineRun) PassResult {
101 const ledger = self.ledger orelse return native;
102 if (run.analysis_cache.allocation_failure.exhausted()) ledger.fail(.exhausted);
103 const outcome = ledger.view().outcome;
104 if (outcome == .exhausted) recordPassFailure(run.failure, .{
105 .kind = .exhausted,
106 .pass_name = pass.name,
107 .target_op_name = run.op.name.name,
108 .target_symbol_name = ir.SymbolTable.getSymbolName(run.op),
109 });
110 return if (outcome == .running) native else .failure;
111 }
112
113 fn finish(self: PassWork, result: PassResult, after: PassManagerStats) void {
114 const ledger = self.ledger orelse return;
115 const counters = revision.receipt.Counters{
116 .pass_runs = after.pass_runs - self.before.pass_runs,
117 .passes_modified = after.passes_modified - self.before.passes_modified,
118 };
119 if (self.token) |token| {
120 if (result == .failure) ledger.fail(.rejected);
121 ledger.finish(token, if (result == .success) .success else .rejected, .{
122 .counters = counters,
123 }) catch ledger.fail(.rejected);
124 } else {
125 ledger.observeCounters(counters) catch ledger.fail(.rejected);
126 if (result == .failure) ledger.fail(.rejected);
127 }
128 }
129 };
130
131 pub const PipelineEntry = union(enum) {
132 pass: Pass,
133 nested: *OpPassManager,
134 };
135
136 pub const OpPassManagerTargetKind = enum {
137 root,
138 any,
139 op,
140 };
141
142 pub const OpPassManager = struct {
143 allocator: std.mem.Allocator,
144 target_op_name: ?[]const u8,
145 target_kind: OpPassManagerTargetKind,
146 pipeline: std.ArrayListUnmanaged(PipelineEntry),
147 nested_managers: std.ArrayListUnmanaged(*OpPassManager),
148 parent: ?*OpPassManager,
149
150 pub fn init(allocator: std.mem.Allocator, target_op_name: ?[]const u8) OpPassManager {
151 return initWithTarget(
152 allocator,
153 if (target_op_name == null) .root else .op,
154 target_op_name,
155 );
156 }
157
158 pub fn initAny(allocator: std.mem.Allocator) OpPassManager {
159 return initWithTarget(allocator, .any, null);
160 }
161
162 pub fn initWithTarget(
163 allocator: std.mem.Allocator,
164 target_kind: OpPassManagerTargetKind,
165 target_op_name: ?[]const u8,
166 ) OpPassManager {
167 return .{
168 .allocator = allocator,
169 .target_op_name = target_op_name,
170 .target_kind = target_kind,
171 .pipeline = .empty,
172 .nested_managers = .empty,
173 .parent = null,
174 };
175 }
176
177 pub fn deinit(self: *OpPassManager) void {
178 for (self.nested_managers.items) |nested| {
179 nested.deinit();
180 self.allocator.destroy(nested);
181 }
182 for (self.pipeline.items) |*entry| {
183 switch (entry.*) {
184 .pass => |*pass| pass.deinit(self.allocator),
185 .nested => {},
186 }
187 }
188 self.nested_managers.deinit(self.allocator);
189 self.pipeline.deinit(self.allocator);
190 }
191
192 pub fn addPass(self: *OpPassManager, pass: Pass) !void {
193 if (!pass.validRerunContract()) return error.InvalidPassRerunContract;
194 try self.pipeline.append(self.allocator, .{ .pass = pass });
195 }
196
197 pub fn nest(self: *OpPassManager, op_name: []const u8) !*OpPassManager {
198 const nested = try self.allocator.create(OpPassManager);
199 nested.* = OpPassManager.init(self.allocator, op_name);
200 nested.parent = self;
201
202 try self.nested_managers.append(self.allocator, nested);
203 try self.pipeline.append(self.allocator, .{ .nested = nested });
204
205 return nested;
206 }
207
208 pub fn nestAny(self: *OpPassManager) !*OpPassManager {
209 const nested = try self.allocator.create(OpPassManager);
210 nested.* = OpPassManager.initAny(self.allocator);
211 nested.parent = self;
212
213 try self.nested_managers.append(self.allocator, nested);
214 try self.pipeline.append(self.allocator, .{ .nested = nested });
215
216 return nested;
217 }
218
219 pub fn collectDependentDialects(
220 self: *const OpPassManager,
221 allocator: std.mem.Allocator,
222 names: *std.ArrayListUnmanaged([]const u8),
223 ) !void {
224 for (self.pipeline.items) |entry| {
225 switch (entry) {
226 .pass => |pass| {
227 for (pass.dependent_dialects) |dialect_name| {
228 try appendDependentDialectName(allocator, names, dialect_name);
229 }
230 },
231 .nested => |nested_pm| try nested_pm.collectDependentDialects(allocator, names),
232 }
233 }
234 }
235
236 fn matchesOp(self: *const OpPassManager, op: *ir.Operation) bool {
237 return switch (self.target_kind) {
238 .root, .any => true,
239 .op => std.mem.eql(u8, op.name.name, self.target_op_name.?),
240 };
241 }
242
243 fn matchesScheduledOp(
244 self: *const OpPassManager,
245 op: *ir.Operation,
246 ir_ctx: *ir.Context,
247 ) bool {
248 return switch (self.target_kind) {
249 .root => true,
250 .op => self.matchesOp(op),
251 .any => self.isRegisteredIsolatedTarget(op, ir_ctx),
252 };
253 }
254
255 fn canRunOnTarget(
256 self: *const OpPassManager,
257 op: *ir.Operation,
258 ir_ctx: *ir.Context,
259 ) bool {
260 if (self.target_kind == .root) return true;
261 if (self.target_kind == .any) return self.isRegisteredIsolatedTarget(op, ir_ctx);
262 const info = op.name.getRegisteredInfo() orelse
263 ir_ctx.lookupOperation(op.name.name) orelse return false;
264 return info.hasTraitId(ir.traits.IsolatedFromAbove.id);
265 }
266
267 fn isRegisteredIsolatedTarget(
268 _: *const OpPassManager,
269 op: *ir.Operation,
270 ir_ctx: *ir.Context,
271 ) bool {
272 const info = op.name.getRegisteredInfo() orelse
273 ir_ctx.lookupOperation(op.name.name) orelse return false;
274 return info.hasTraitId(ir.traits.IsolatedFromAbove.id);
275 }
276
277 fn instrumentationTargetName(self: *const OpPassManager) ?[]const u8 {
278 return switch (self.target_kind) {
279 .root => null,
280 .any => "any",
281 .op => self.target_op_name,
282 };
283 }
284
285 pub fn runOnOperation(
286 self: *OpPassManager,
287 op: *ir.Operation,
288 ir_ctx: *ir.Context,
289 analysis_cache: *AnalysisCache,
290 stats: *PassManagerStats,
291 instrumentor: ?*const PassInstrumentor,
292 verifier: ?*PassVerifierConfig,
293 failure: ?*?CapturedPassFailure,
294 options: PassManagerRunOptions,
295 run_allocator: std.mem.Allocator,
296 ) PassResult {
297 if (!self.matchesScheduledOp(op, ir_ctx)) {
298 return .success;
299 }
300
301 const pipeline_info = PipelineInfo{
302 .target_op_name = self.instrumentationTargetName(),
303 .depth = self.getNestingDepth(),
304 };
305
306 if (instrumentor) |inst| {
307 inst.runBeforePipeline(pipeline_info, op);
308 }
309
310 if (!self.canRunOnTarget(op, ir_ctx)) {
311 if (instrumentor) |inst| {
312 inst.runAfterPipeline(pipeline_info, op, true);
313 }
314 recordPassFailure(failure, .{
315 .kind = .target,
316 .target_op_name = op.name.name,
317 .target_symbol_name = ir.SymbolTable.getSymbolName(op),
318 });
319 return .failure;
320 }
321
322 var run = PipelineRun{
323 .op = op,
324 .ir_ctx = ir_ctx,
325 .analysis_cache = analysis_cache,
326 .stats = stats,
327 .instrumentor = instrumentor,
328 .verifier = verifier,
329 .failure = failure,
330 .options = options,
331 .allocator = run_allocator,
332 };
333 const result = self.runPipelineEntries(&run);
334 if (instrumentor) |inst| {
335 inst.runAfterPipeline(pipeline_info, op, result == .failure);
336 }
337 return result;
338 }
339
340 fn runPipelineEntries(self: *const OpPassManager, run: *PipelineRun) PassResult {
341 var revision_start: usize = 0;
342
343 for (self.pipeline.items, 0..) |entry, entry_index| {
344 const result = switch (entry) {
345 .pass => |pass| self.runPassEntry(
346 pass,
347 entry_index,
348 &revision_start,
349 run,
350 ),
351 .nested => |nested_pm| runNestedEntry(
352 nested_pm,
353 entry_index,
354 &revision_start,
355 run,
356 ),
357 };
358 if (result == .failure) return .failure;
359 }
360 return .success;
361 }
362
363 /// A failing pass that reports IR modification preserves only analyses it declared preserved.
364 fn runPassEntry(
365 self: *const OpPassManager,
366 pass: Pass,
367 entry_index: usize,
368 revision_start: *usize,
369 run: *PipelineRun,
370 ) PassResult {
371 if (run.analysis_cache.accounting == null and
372 self.hasRerunIdentity(pass, revision_start.*, entry_index))
373 {
374 run.stats.passes_skipped += 1;
375 return .success;
376 }
377
378 const pass_info = PassInfo{
379 .name = pass.name,
380 .description = pass.description,
381 .target_op = run.op,
382 .mutation_scope = pass.mutation_scope,
383 };
384 if (run.instrumentor) |inst| inst.runBeforePass(pass_info);
385
386 var ctx = PassContext.initWithInstrumentorAndOptions(
387 run.op,
388 run.ir_ctx,
389 run.allocator,
390 run.analysis_cache,
391 run.instrumentor,
392 run.options,
393 );
394 ctx.pass_info = pass_info;
395 defer ctx.deinit();
396
397 const work = PassWork.begin(pass, run);
398 var finalized: PassResult = .failure;
399 defer work.finish(finalized, run.stats.*);
400 const native = if (work.admitted) pass.run(&ctx) else PassResult.failure;
401 const result = work.normalize(native, pass, run);
402 if (work.admitted) run.stats.pass_runs += 1;
403 if (ctx.modified) {
404 run.stats.passes_modified += 1;
405 run.analysis_cache.invalidate(&ctx.preserved);
406 revision_start.* = entry_index;
407 }
408 if (result == .failure) {
409 run.stats.pass_failures += 1;
410 if (run.instrumentor) |inst| inst.runAfterPassFailed(pass_info);
411 recordPassFailure(run.failure, .{
412 .kind = .pass,
413 .pass_name = pass.name,
414 .target_op_name = run.op.name.name,
415 .target_symbol_name = ir.SymbolTable.getSymbolName(run.op),
416 });
417 return .failure;
418 }
419
420 if (run.instrumentor) |inst| inst.runAfterPass(pass_info, ctx.modified);
421 finalized = verifyPass(pass, pass_info, run);
422 return finalized;
423 }
424
425 fn verifyPass(pass: Pass, pass_info: PassInfo, run: *PipelineRun) PassResult {
426 const verifier = run.verifier orelse return .success;
427 if (verifier.verifyAfterPass(pass_info) == .success) return .success;
428
429 run.stats.verifier_failures += 1;
430 recordPassFailure(run.failure, .{
431 .kind = .verifier,
432 .pass_name = pass.name,
433 .target_op_name = run.op.name.name,
434 .target_symbol_name = ir.SymbolTable.getSymbolName(run.op),
435 .verifier_error = if (verifier.failure.*) |failure| failure.err else null,
436 });
437 return .failure;
438 }
439
440 fn runNestedEntry(
441 nested: *OpPassManager,
442 entry_index: usize,
443 revision_start: *usize,
444 run: *PipelineRun,
445 ) PassResult {
446 const modified_before = run.stats.passes_modified;
447 const result = nested.walkAndRun(
448 run.op,
449 run.ir_ctx,
450 run.analysis_cache,
451 run.stats,
452 run.instrumentor,
453 run.verifier,
454 run.failure,
455 run.options,
456 run.allocator,
457 );
458 if (result == .failure) return .failure;
459 if (run.stats.passes_modified != modified_before) {
460 revision_start.* = entry_index + 1;
461 }
462 return .success;
463 }
464
465 fn hasRerunIdentity(
466 self: *const OpPassManager,
467 pass: Pass,
468 revision_start: usize,
469 entry_index: usize,
470 ) bool {
471 std.debug.assert(revision_start <= entry_index);
472 std.debug.assert(entry_index <= self.pipeline.items.len);
473 var previous_index = entry_index;
474 while (previous_index > revision_start) {
475 previous_index -= 1;
476 switch (self.pipeline.items[previous_index]) {
477 .pass => |previous| if (pass.sameRerunIdentity(previous)) return true,
478 .nested => {},
479 }
480 }
481 return false;
482 }
483
484 fn walkAndRun(
485 self: *OpPassManager,
486 root: *ir.Operation,
487 ir_ctx: *ir.Context,
488 analysis_cache: *AnalysisCache,
489 stats: *PassManagerStats,
490 instrumentor: ?*const PassInstrumentor,
491 verifier: ?*PassVerifierConfig,
492 failure: ?*?CapturedPassFailure,
493 options: PassManagerRunOptions,
494 run_allocator: std.mem.Allocator,
495 ) PassResult {
496 if (self.canRunNestedTargetsParallel(instrumentor, verifier, options)) {
497 const targets = self.collectMatchingTargets(root, ir_ctx) catch return .failure;
498 defer if (targets.len != 0) self.allocator.free(targets);
499
500 if (targets.len > 1 and !targetSetOverlaps(targets)) {
501 return self.runTargetsParallel(
502 targets,
503 ir_ctx,
504 analysis_cache,
505 stats,
506 verifier,
507 failure,
508 options,
509 );
510 }
511 }
512 return self.walkAndRunSerial(
513 root,
514 ir_ctx,
515 analysis_cache,
516 stats,
517 instrumentor,
518 verifier,
519 failure,
520 options,
521 run_allocator,
522 );
523 }
524
525 fn walkAndRunSerial(
526 self: *OpPassManager,
527 root: *ir.Operation,
528 ir_ctx: *ir.Context,
529 analysis_cache: *AnalysisCache,
530 stats: *PassManagerStats,
531 instrumentor: ?*const PassInstrumentor,
532 verifier: ?*PassVerifierConfig,
533 failure: ?*?CapturedPassFailure,
534 options: PassManagerRunOptions,
535 run_allocator: std.mem.Allocator,
536 ) PassResult {
537 for (root.regions.items) |*region| {
538 var block_iter = region.getBlocks();
539 while (block_iter.next()) |block| {
540 var current_op: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
541 while (current_op) |nested_op| {
542 if (self.matchesScheduledOp(nested_op, ir_ctx)) {
543 const result = self.runOnOperation(
544 nested_op,
545 ir_ctx,
546 analysis_cache,
547 stats,
548 instrumentor,
549 verifier,
550 failure,
551 options,
552 run_allocator,
553 );
554 if (result == .failure) {
555 return .failure;
556 }
557 }
558 const walk_result = self.walkAndRunSerial(
559 nested_op,
560 ir_ctx,
561 analysis_cache,
562 stats,
563 instrumentor,
564 verifier,
565 failure,
566 options,
567 run_allocator,
568 );
569 if (walk_result == .failure) {
570 return .failure;
571 }
572 current_op = nested_op.next_op;
573 }
574 }
575 }
576 return .success;
577 }
578
579 fn canRunNestedTargetsParallel(
580 self: *const OpPassManager,
581 instrumentor: ?*const PassInstrumentor,
582 verifier: ?*PassVerifierConfig,
583 options: PassManagerRunOptions,
584 ) bool {
585 if (instrumentor != null) return false;
586 _ = verifier;
587 if (!options.requestsParallelism()) return false;
588 return self.parallelReadOnlyPipeline();
589 }
590
591 fn parallelReadOnlyPipeline(self: *const OpPassManager) bool {
592 for (self.pipeline.items) |entry| {
593 switch (entry) {
594 .pass => |pass| {
595 if (!pass.readOnly() or !pass.parallelStateSafe()) return false;
596 },
597 .nested => |nested_pm| if (!nested_pm.parallelReadOnlyPipeline()) return false,
598 }
599 }
600 return true;
601 }
602
603 fn cloneForParallelTarget(
604 self: *const OpPassManager,
605 allocator: std.mem.Allocator,
606 ) anyerror!OpPassManager {
607 var cloned = OpPassManager.initWithTarget(
608 allocator,
609 self.target_kind,
610 self.target_op_name,
611 );
612 errdefer cloned.deinit();
613
614 for (self.pipeline.items) |entry| {
615 switch (entry) {
616 .pass => |pass| {
617 var pass_clone = try pass.cloneForParallelTarget(allocator);
618 var pass_registered = false;
619 errdefer if (!pass_registered) pass_clone.deinit(allocator);
620 try cloned.pipeline.append(allocator, .{ .pass = pass_clone });
621 pass_registered = true;
622 },
623 .nested => |nested_pm| {
624 const nested = try allocator.create(OpPassManager);
625 var nested_initialized = false;
626 var nested_registered = false;
627 errdefer if (!nested_registered) {
628 if (nested_initialized) nested.deinit();
629 allocator.destroy(nested);
630 };
631 nested.* = try nested_pm.cloneForParallelTarget(allocator);
632 nested_initialized = true;
633 nested.parent = &cloned;
634 try cloned.nested_managers.append(allocator, nested);
635 nested_registered = true;
636 try cloned.pipeline.append(allocator, .{ .nested = nested });
637 },
638 }
639 }
640
641 return cloned;
642 }
643
644 fn refreshParentLinks(self: *OpPassManager, parent: ?*OpPassManager) void {
645 self.parent = parent;
646 for (self.nested_managers.items) |nested| {
647 nested.refreshParentLinks(self);
648 }
649 }
650
651 fn collectMatchingTargets(
652 self: *OpPassManager,
653 root: *ir.Operation,
654 ir_ctx: *ir.Context,
655 ) ![]*ir.Operation {
656 var targets: std.ArrayListUnmanaged(*ir.Operation) = .empty;
657 errdefer targets.deinit(self.allocator);
658
659 try self.collectMatchingTargetsInto(root, ir_ctx, &targets);
660 return if (targets.items.len == 0)
661 &.{}
662 else
663 try targets.toOwnedSlice(self.allocator);
664 }
665
666 fn collectMatchingTargetsInto(
667 self: *OpPassManager,
668 root: *ir.Operation,
669 ir_ctx: *ir.Context,
670 targets: *std.ArrayListUnmanaged(*ir.Operation),
671 ) !void {
672 for (root.regions.items) |*region| {
673 var block_iter = region.getBlocks();
674 while (block_iter.next()) |block| {
675 var current_op: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));
676 while (current_op) |nested_op| {
677 if (self.matchesScheduledOp(nested_op, ir_ctx)) {
678 try targets.append(self.allocator, nested_op);
679 }
680 try self.collectMatchingTargetsInto(nested_op, ir_ctx, targets);
681 current_op = nested_op.next_op;
682 }
683 }
684 }
685 }
686
687 fn runTargetsParallel(
688 self: *OpPassManager,
689 targets: []const *ir.Operation,
690 ir_ctx: *ir.Context,
691 analysis_cache: *AnalysisCache,
692 stats: *PassManagerStats,
693 verifier: ?*PassVerifierConfig,
694 failure: ?*?CapturedPassFailure,
695 options: PassManagerRunOptions,
696 ) PassResult {
697 _ = analysis_cache;
698
699 const worker_allocator = options.workerAllocator(self.allocator);
700 const slots = self.allocator.alloc(ParallelTargetSlot, targets.len) catch return .failure;
701 defer self.allocator.free(slots);
702 for (slots) |*slot| slot.* = ParallelTargetSlot.init(worker_allocator);
703 defer deinitParallelTargetSlots(slots);
704 for (slots) |*slot| {
705 slot.manager = self.cloneForParallelTarget(worker_allocator) catch return .failure;
706 slot.manager.?.refreshParentLinks(null);
707 }
708
709 var batch = ParallelTargetBatch{
710 .manager = self,
711 .allocator = worker_allocator,
712 .ir_ctx = ir_ctx,
713 .targets = targets,
714 .verifier = verifier,
715 .failure = failure,
716 .options = options,
717 .slots = slots,
718 };
719
720 var execution_guard: ?ir.ThreadingExecutionGuard = null;
721 if (options.workerCount(targets.len) > 1) {
722 execution_guard = ir_ctx.enterMultithreadedExecution();
723 }
724 defer if (execution_guard) |*guard| guard.deinit();
725
726 ir.threading.parallelForEachIndex(
727 self.allocator,
728 options,
729 targets.len,
730 &batch,
731 runParallelTarget,
732 ) catch return .failure;
733
734 var result: PassResult = .success;
735 for (slots) |*slot| {
736 mergeStats(stats, slot.stats);
737 if (slot.result == .failure) result = .failure;
738 if (slot.failure) |captured_failure| {
739 var slot_failure = captured_failure;
740 slot_failure.worker_count = options.workerCount(targets.len);
741 recordPassFailure(failure, slot_failure);
742 }
743 if (slot.verifier_failure) |verifier_failure| {
744 if (verifier) |verify| {
745 if (verify.failure.* == null) verify.failure.* = verifier_failure;
746 }
747 }
748 _ = ir_ctx.replayDiagnostics(&slot.diagnostics) catch {
749 result = .failure;
750 continue;
751 };
752 }
753 return result;
754 }
755
756 pub fn getNestingDepth(self: *const OpPassManager) usize {
757 var depth: usize = 0;
758 var current: ?*const OpPassManager = self;
759 while (current) |pm| {
760 if (pm.parent) |parent| {
761 depth += 1;
762 current = parent;
763 } else {
764 break;
765 }
766 }
767 return depth;
768 }
769 };
770
771 pub const PassManager = struct {
772 allocator: std.mem.Allocator,
773 root: OpPassManager,
774 stats: PassManagerStats,
775 instrumentor: ?PassInstrumentor,
776 verifier_enabled: bool,
777 verifier_options: ir.verify.VerifyOptions,
778 last_verifier_failure: ?PassVerifierFailure,
779 last_failure_reproducer: ?PassFailureReproducer,
780
781 pub fn init(allocator: std.mem.Allocator) PassManager {
782 return .{
783 .allocator = allocator,
784 .root = OpPassManager.init(allocator, null),
785 .stats = .{},
786 .instrumentor = null,
787 .verifier_enabled = false,
788 .verifier_options = ir.verify.default_options,
789 .last_verifier_failure = null,
790 .last_failure_reproducer = null,
791 };
792 }
793
794 pub fn deinit(self: *PassManager) void {
795 self.clearLastFailureReproducer();
796 if (self.instrumentor) |*inst| {
797 inst.deinit();
798 }
799 self.root.deinit();
800 }
801
802 pub fn addPass(self: *PassManager, pass: Pass) !void {
803 try self.root.addPass(pass);
804 }
805
806 pub fn nest(self: *PassManager, op_name: []const u8) !*OpPassManager {
807 return self.root.nest(op_name);
808 }
809
810 pub fn nestAny(self: *PassManager) !*OpPassManager {
811 return self.root.nestAny();
812 }
813
814 pub fn resetStats(self: *PassManager) void {
815 self.stats.reset();
816 }
817
818 pub fn addInstrumentation(self: *PassManager, inst: PassInstrumentation) !void {
819 if (self.instrumentor == null) {
820 self.instrumentor = PassInstrumentor.init(self.allocator);
821 }
822 try self.instrumentor.?.addInstrumentation(inst);
823 }
824
825 pub fn getInstrumentor(self: *PassManager) ?*const PassInstrumentor {
826 if (self.instrumentor) |*inst| {
827 return inst;
828 }
829 return null;
830 }
831
832 pub fn enableVerifier(self: *PassManager) void {
833 self.enableVerifierWithOptions(ir.verify.default_options);
834 }
835
836 pub fn enableVerifierWithOptions(self: *PassManager, options: ir.verify.VerifyOptions) void {
837 self.verifier_enabled = true;
838 self.verifier_options = options;
839 self.last_verifier_failure = null;
840 }
841
842 pub fn disableVerifier(self: *PassManager) void {
843 self.verifier_enabled = false;
844 self.last_verifier_failure = null;
845 }
846
847 pub fn verifierEnabled(self: *const PassManager) bool {
848 return self.verifier_enabled;
849 }
850
851 pub fn getLastVerifierFailure(self: *const PassManager) ?PassVerifierFailure {
852 return self.last_verifier_failure;
853 }
854
855 pub fn getLastFailureReproducer(self: *const PassManager) ?*const PassFailureReproducer {
856 if (self.last_failure_reproducer) |*reproducer| return reproducer;
857 return null;
858 }
859
860 pub fn run(self: *PassManager, op: *ir.Operation, ir_ctx: *ir.Context) PassResult {
861 return self.runWithOptions(op, ir_ctx, .{});
862 }
863
864 pub fn runWithOptions(
865 self: *PassManager,
866 op: *ir.Operation,
867 ir_ctx: *ir.Context,
868 options: PassManagerRunOptions,
869 ) PassResult {
870 var analysis_cache = AnalysisCache.init(self.allocator, null);
871 defer analysis_cache.deinit();
872
873 return self.runWithAnalysisCache(op, ir_ctx, &analysis_cache, options);
874 }
875
876 pub fn runWithAnalysisCache(
877 self: *PassManager,
878 op: *ir.Operation,
879 ir_ctx: *ir.Context,
880 analysis_cache: *AnalysisCache,
881 options: PassManagerRunOptions,
882 ) PassResult {
883 if (analysis_cache.accounting) |ledger| {
884 if (ledger.view().outcome != .running) return .failure;
885 }
886 self.clearLastFailureReproducer();
887 self.last_verifier_failure = null;
888 if (analysis_cache.accounting) |ledger| {
889 if (options.max_threads != 1 or options.worker_allocator != null) {
890 ledger.missingContract();
891 ledger.fail(.rejected);
892 self.captureFailureReproducer(op, options, .{
893 .kind = .target,
894 .target_op_name = op.name.name,
895 .target_symbol_name = ir.SymbolTable.getSymbolName(op),
896 });
897 return .failure;
898 }
899 }
900
901 if (self.prepareDependentDialects(ir_ctx) == .failure) {
902 self.captureFailureReproducer(op, options, null);
903 return .failure;
904 }
905
906 const previous_stats = analysis_cache.stats;
907 analysis_cache.stats = &self.stats;
908 defer analysis_cache.stats = previous_stats;
909
910 const inst_ptr: ?*const PassInstrumentor = if (self.instrumentor) |*inst| inst else null;
911 var verifier_config = self.beginVerifierRun();
912 const verifier_ptr: ?*PassVerifierConfig = if (verifier_config) |*config| config else null;
913
914 const pass_runs_before = self.stats.pass_runs;
915 defer ir_ctx.recordPassRuns(self.stats.pass_runs - pass_runs_before);
916 var failure: ?CapturedPassFailure = null;
917 const result = self.root.runOnOperation(
918 op,
919 ir_ctx,
920 analysis_cache,
921 &self.stats,
922 inst_ptr,
923 verifier_ptr,
924 &failure,
925 options,
926 self.allocator,
927 );
928 if (result == .failure) self.captureFailureReproducer(op, options, failure);
929 return result;
930 }
931
932 pub fn runToFixedPoint(
933 self: *PassManager,
934 op: *ir.Operation,
935 ir_ctx: *ir.Context,
936 max_iterations: usize,
937 ) PassManagerFixedPointResult {
938 return self.runToFixedPointWithOptions(op, ir_ctx, max_iterations, .{});
939 }
940
941 pub fn runToFixedPointWithOptions(
942 self: *PassManager,
943 op: *ir.Operation,
944 ir_ctx: *ir.Context,
945 max_iterations: usize,
946 options: PassManagerRunOptions,
947 ) PassManagerFixedPointResult {
948 var fixed_point: PassManagerFixedPointResult = .{};
949 self.clearLastFailureReproducer();
950 self.last_verifier_failure = null;
951
952 if (self.prepareDependentDialects(ir_ctx) == .failure) {
953 fixed_point.result = .failure;
954 self.captureFailureReproducer(op, options, null);
955 return fixed_point;
956 }
957
958 var analysis_cache = AnalysisCache.init(self.allocator, &self.stats);
959 defer analysis_cache.deinit();
960
961 const inst_ptr: ?*const PassInstrumentor = if (self.instrumentor) |*inst| inst else null;
962 var verifier_config = self.beginVerifierRun();
963 const verifier_ptr: ?*PassVerifierConfig = if (verifier_config) |*config| config else null;
964
965 const pass_runs_before = self.stats.pass_runs;
966 defer ir_ctx.recordPassRuns(self.stats.pass_runs - pass_runs_before);
967 for (0..max_iterations) |_| {
968 const before_modified = self.stats.passes_modified;
969 fixed_point.iterations += 1;
970
971 var failure: ?CapturedPassFailure = null;
972 const result = self.root.runOnOperation(
973 op,
974 ir_ctx,
975 &analysis_cache,
976 &self.stats,
977 inst_ptr,
978 verifier_ptr,
979 &failure,
980 options,
981 self.allocator,
982 );
983 if (result == .failure) {
984 fixed_point.result = .failure;
985 self.captureFailureReproducer(op, options, failure);
986 return fixed_point;
987 }
988
989 const iteration_changed = self.stats.passes_modified != before_modified;
990 fixed_point.changed = fixed_point.changed or iteration_changed;
991 if (!iteration_changed) break;
992 }
993
994 return fixed_point;
995 }
996
997 fn clearLastFailureReproducer(self: *PassManager) void {
998 if (self.last_failure_reproducer) |*reproducer| {
999 reproducer.deinit(self.allocator);
1000 self.last_failure_reproducer = null;
1001 }
1002 }
1003
1004 fn captureFailureReproducer(
1005 self: *PassManager,
1006 op: *ir.Operation,
1007 options: PassManagerRunOptions,
1008 failure: ?CapturedPassFailure,
1009 ) void {
1010 self.clearLastFailureReproducer();
1011
1012 const pipeline_text = textual_pipeline.formatPassManagerPipelineAlloc(
1013 self.allocator,
1014 self,
1015 ) catch return;
1016
1017 const ir_text = ir.dump.operationAlloc(self.allocator, op) catch {
1018 self.allocator.free(pipeline_text);
1019 return;
1020 };
1021
1022 var reproducer = PassFailureReproducer{
1023 .pipeline = pipeline_text,
1024 .ir = ir_text,
1025 .max_threads = options.max_threads,
1026 .worker_count = if (failure) |captured| captured.worker_count else 1,
1027 .verifier_enabled = self.verifier_enabled,
1028 };
1029 var stored = false;
1030 defer if (!stored) reproducer.deinit(self.allocator);
1031
1032 if (failure) |captured| {
1033 reproducer.failure_kind = captured.kind;
1034 if (captured.pass_name) |name| {
1035 reproducer.pass_name = self.allocator.dupe(u8, name) catch return;
1036 }
1037 reproducer.target_op_name = self.allocator.dupe(
1038 u8,
1039 captured.target_op_name,
1040 ) catch return;
1041 if (captured.target_symbol_name) |name| {
1042 reproducer.target_symbol_name = self.allocator.dupe(u8, name) catch return;
1043 }
1044 reproducer.verifier_error = captured.verifier_error;
1045 if (captured.verifier_error) |err| {
1046 reproducer.verifier_error_name = self.allocator.dupe(
1047 u8,
1048 @errorName(err),
1049 ) catch return;
1050 }
1051 }
1052
1053 self.last_failure_reproducer = reproducer;
1054 stored = true;
1055 }
1056
1057 fn beginVerifierRun(self: *PassManager) ?PassVerifierConfig {
1058 if (!self.verifier_enabled) return null;
1059 return .{
1060 .options = self.verifier_options,
1061 .failure = &self.last_verifier_failure,
1062 };
1063 }
1064
1065 fn prepareDependentDialects(self: *PassManager, ir_ctx: *ir.Context) PassResult {
1066 var names: std.ArrayListUnmanaged([]const u8) = .empty;
1067 defer names.deinit(self.allocator);
1068
1069 self.root.collectDependentDialects(self.allocator, &names) catch return .failure;
1070
1071 for (names.items) |name| {
1072 _ = ir_ctx.getOrLoadDialect(name) catch return .failure;
1073 }
1074
1075 return .success;
1076 }
1077 };
1078
1079 fn appendDependentDialectName(
1080 allocator: std.mem.Allocator,
1081 names: *std.ArrayListUnmanaged([]const u8),
1082 name: []const u8,
1083 ) !void {
1084 if (name.len == 0) return error.EmptyDependentDialectName;
1085 for (names.items) |existing| {
1086 if (std.mem.eql(u8, existing, name)) return;
1087 }
1088 try names.append(allocator, name);
1089 }
1090
1091 fn mergeStats(into: *PassManagerStats, other: PassManagerStats) void {
1092 into.pass_runs += other.pass_runs;
1093 into.passes_skipped += other.passes_skipped;
1094 into.pass_failures += other.pass_failures;
1095 into.verifier_failures += other.verifier_failures;
1096 into.passes_modified += other.passes_modified;
1097 into.analysis_hits += other.analysis_hits;
1098 into.analysis_misses += other.analysis_misses;
1099 into.analyses_invalidated += other.analyses_invalidated;
1100 }
1101
1102 fn targetSetOverlaps(targets: []const *ir.Operation) bool {
1103 for (targets, 0..) |left, left_index| {
1104 for (targets[left_index + 1 ..]) |right| {
1105 if (left.isProperAncestor(right) or right.isProperAncestor(left)) return true;
1106 }
1107 }
1108 return false;
1109 }
1110
1111 const ParallelTargetSlot = struct {
1112 result: PassResult = .success,
1113 stats: PassManagerStats = .{},
1114 verifier_failure: ?PassVerifierFailure = null,
1115 failure: ?CapturedPassFailure = null,
1116 diagnostics: diagnostics.CaptureBuffer,
1117 manager: ?OpPassManager = null,
1118
1119 fn init(allocator: std.mem.Allocator) ParallelTargetSlot {
1120 return .{ .diagnostics = diagnostics.CaptureBuffer.init(allocator) };
1121 }
1122
1123 fn deinit(self: *ParallelTargetSlot) void {
1124 if (self.manager) |*manager| manager.deinit();
1125 self.diagnostics.deinit();
1126 self.* = undefined;
1127 }
1128 };
1129
1130 fn deinitParallelTargetSlots(slots: []ParallelTargetSlot) void {
1131 for (slots) |*slot| slot.deinit();
1132 }
1133
1134 const ParallelTargetBatch = struct {
1135 manager: *OpPassManager,
1136 allocator: std.mem.Allocator,
1137 ir_ctx: *ir.Context,
1138 targets: []const *ir.Operation,
1139 verifier: ?*PassVerifierConfig,
1140 failure: ?*?CapturedPassFailure,
1141 options: PassManagerRunOptions,
1142 slots: []ParallelTargetSlot,
1143 };
1144
1145 fn runParallelTarget(batch: *ParallelTargetBatch, index: usize) void {
1146 var capture = batch.ir_ctx.captureDiagnostics(&batch.slots[index].diagnostics);
1147 var capture_guard = capture.enter();
1148 defer capture_guard.deinit();
1149
1150 var stats: PassManagerStats = .{};
1151 var analysis_cache = AnalysisCache.init(batch.allocator, &stats);
1152 defer analysis_cache.deinit();
1153
1154 var local_verifier: PassVerifierConfig = undefined;
1155 const verifier_ptr: ?*PassVerifierConfig = if (batch.verifier) |verify| blk: {
1156 local_verifier = .{
1157 .options = verify.options,
1158 .failure = &batch.slots[index].verifier_failure,
1159 };
1160 break :blk &local_verifier;
1161 } else null;
1162
1163 const target_manager = &batch.slots[index].manager.?;
1164 const result = target_manager.runOnOperation(
1165 batch.targets[index],
1166 batch.ir_ctx,
1167 &analysis_cache,
1168 &stats,
1169 null,
1170 verifier_ptr,
1171 &batch.slots[index].failure,
1172 batch.options,
1173 batch.allocator,
1174 );
1175 batch.slots[index].result = result;
1176 batch.slots[index].stats = stats;
1177 }