tiny.choir.passes.pass

1pub const AnalysisCache = struct {2    allocator: std.mem.Allocator,3    entries: std.AutoHashMap(AnalysisKey, AnalysisEntry),4    stats: ?*PassManagerStats,5    accounting: ?*revision.AccountingV1 = null,6    allocation_failure: subject.work.AllocationFailure = .{},7    entry_limit: ?u32 = null,89    pub fn init(allocator: std.mem.Allocator, stats: ?*PassManagerStats) AnalysisCache {10        return .{11            .allocator = allocator,12            .entries = std.AutoHashMap(AnalysisKey, AnalysisEntry).init(allocator),13            .stats = stats,14        };15    }1617    /// The ledger outlives this fresh cache and every computation using it.18    pub fn initAccounted(19        allocator: std.mem.Allocator,20        stats: ?*PassManagerStats,21        accounting: *revision.AccountingV1,22        allocation_failure: subject.work.AllocationFailure,23        entry_limit: u32,24    ) !AnalysisCache {25        if (allocation_failure.exhausted()) {26            accounting.fail(.exhausted);27            return error.WorkExhausted;28        }29        var cache = init(allocator, stats);30        cache.accounting = accounting;31        cache.allocation_failure = allocation_failure;32        cache.entry_limit = entry_limit;33        errdefer cache.deinit();34        const bytes = storageBound(entry_limit) catch |err| {35            accounting.fail(.exhausted);36            return err;37        };38        const token = try accounting.begin(.input, .{39            .identity = .{ .name = "choir-analysis-cache", .version = 1 },40            .work = .{ .allocation_capacity = bytes },41            .workspace = bytes,42            .retained_storage = bytes,43        });44        cache.entries.ensureTotalCapacity(entry_limit) catch |err| {45            const failure = allocation_failure.classify(err);46            accounting.fail(if (failure == error.WorkExhausted) .exhausted else .rejected);47            try accounting.finish(token, .rejected, .{});48            return failure;49        };50        try accounting.finish(token, .success, .{});51        return cache;52    }5354    /// Bounds the pinned HashMap header, aligned keys/values and one-byte slot metadata.55    /// The table is allocated once, before the first computation, without later growth.56    pub fn storageBound(entry_limit: u32) !u64 {57        if (entry_limit == 0) return 0;58        const load_capacity = @as(u64, entry_limit) * 100 / 80 + 1;59        if (load_capacity > std.math.maxInt(u32)) return error.WorkOverflow;60        const capacity = std.math.ceilPowerOfTwo(u32, @intCast(load_capacity)) catch61            return error.WorkOverflow;62        if (capacity > std.math.maxInt(u32) / 80) return error.WorkOverflow;63        const slots: u64 = @max(8, capacity);64        const slot_bytes = 1 + @sizeOf(AnalysisKey) + @sizeOf(AnalysisEntry);65        const alignment = @max(@alignOf(usize), @alignOf(AnalysisKey), @alignOf(AnalysisEntry));66        const bytes = 4 * @sizeOf(usize) + 3 * alignment + slots * slot_bytes;67        if (bytes > std.math.maxInt(usize)) return error.WorkOverflow;68        return bytes;69    }7071    pub fn deinit(self: *AnalysisCache) void {72        var iter = self.entries.valueIterator();73        while (iter.next()) |entry| {74            if (entry.cleanup) |cleanup| {75                cleanup(entry.value, self.allocator);76            }77        }78        self.entries.deinit();79    }8081    pub fn getOrCompute(82        self: *AnalysisCache,83        ctx: *PassContext,84        op: *ir.Operation,85        descriptor: *const AnalysisDescriptor,86        compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,87        cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,88        instrumentor: ?*const PassInstrumentor,89    ) !*anyopaque {90        try self.requireRunning();91        const key = AnalysisKey{ .op = op, .analysis = descriptor.id };92        if (self.entries.get(key)) |entry| {93            if (self.accounting) |ledger| try ledger.observeCounters(.{ .analysis_hits = 1 });94            if (self.stats) |stats| stats.analysis_hits += 1;95            return entry.value;96        }97        const run = try Computation.begin(self.accounting, descriptor, op, ctx.run_options);98        if (self.entry_limit) |limit| {99            if (self.entries.count() >= limit) {100                try run.finish(error.WorkExhausted, false);101                return error.WorkExhausted;102            }103        }104        const value = self.computeAndCache(105            ctx,106            op,107            descriptor,108            compute,109            cleanup,110            instrumentor,111        ) catch |err| {112            const failure = self.allocation_failure.classify(err);113            try run.finish(failure, true);114            return failure;115        };116        try run.finish(null, true);117        return value;118    }119120    /// Refresh replaces the cached value in place; failure must leave it intact.121    pub fn refresh(122        self: *AnalysisCache,123        ctx: *PassContext,124        op: *ir.Operation,125        descriptor: *const AnalysisDescriptor,126        refresh_value: *const fn (*PassContext, *ir.Operation, *anyopaque) anyerror!void,127        instrumentor: ?*const PassInstrumentor,128    ) !void {129        try self.requireRunning();130        const entry = self.entries.get(.{ .op = op, .analysis = descriptor.id }) orelse131            return error.UncachedAnalysis;132        const run = try Computation.begin(self.accounting, entry.descriptor, op, ctx.run_options);133        const info = AnalysisInfo{134            .id = descriptor.id,135            .name = descriptor.name,136            .target_op = op,137        };138        if (instrumentor) |inst| inst.runBeforeAnalysis(info);139        refresh_value(ctx, op, entry.value) catch |err| {140            if (instrumentor) |inst| inst.runAfterAnalysis(info);141            const failure = self.allocation_failure.classify(err);142            try run.finish(failure, true);143            return failure;144        };145        if (instrumentor) |inst| inst.runAfterAnalysis(info);146        self.requireRunning() catch |err| {147            try run.finish(err, true);148            return err;149        };150        if (self.stats) |stats| stats.analysis_misses += 1;151        try run.finish(null, true);152    }153154    fn computeAndCache(155        self: *AnalysisCache,156        ctx: *PassContext,157        op: *ir.Operation,158        descriptor: *const AnalysisDescriptor,159        compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,160        cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,161        instrumentor: ?*const PassInstrumentor,162    ) !*anyopaque {163        const info = AnalysisInfo{164            .id = descriptor.id,165            .name = descriptor.name,166            .target_op = op,167        };168        if (instrumentor) |inst| inst.runBeforeAnalysis(info);169        const value = compute(ctx, op) catch |err| {170            if (instrumentor) |inst| inst.runAfterAnalysis(info);171            return err;172        };173        if (instrumentor) |inst| inst.runAfterAnalysis(info);174        errdefer if (cleanup) |cleanup_fn| cleanup_fn(value, self.allocator);175        try self.requireRunning();176177        const key = AnalysisKey{ .op = op, .analysis = descriptor.id };178        const entry = AnalysisEntry{ .descriptor = descriptor, .value = value, .cleanup = cleanup };179        if (self.entry_limit != null) {180            self.entries.putAssumeCapacityNoClobber(key, entry);181        } else {182            try self.entries.put(key, entry);183        }184        if (self.stats) |stats| stats.analysis_misses += 1;185        return value;186    }187188    fn requireRunning(self: *AnalysisCache) !void {189        const ledger = self.accounting orelse return;190        if (ledger.view().outcome != .running) return error.TerminalWorkOutcome;191        if (self.allocation_failure.exhausted()) {192            ledger.fail(.exhausted);193            return error.WorkExhausted;194        }195    }196197    pub fn invalidate(self: *AnalysisCache, preserved: *const PreservedAnalyses) void {198        if (preserved.preserve_all) return;199200        var iter = self.entries.iterator();201        while (iter.next()) |kv| {202            if (!preserved.preservesDescriptor(kv.value_ptr.descriptor)) {203                const entry = kv.value_ptr.*;204                self.entries.removeByPtr(kv.key_ptr);205                if (entry.cleanup) |cleanup| {206                    cleanup(entry.value, self.allocator);207                }208                if (self.stats) |stats| stats.analyses_invalidated += 1;209            }210        }211    }212};

1pub const AnalysisDescriptor = struct {2    work_contract: ?subject.work.Contract = null,3    id: AnalysisId,4    name: []const u8,5    required_interfaces: []const ir.InterfaceId = &.{},6};

1pub const PassContext = struct {2    op: *ir.Operation,34    ir_ctx: *ir.Context,56    allocator: std.mem.Allocator,78    analysis_cache: *AnalysisCache,910    preserved: PreservedAnalyses,1112    modified: bool,1314    instrumentor: ?*const PassInstrumentor,1516    run_options: PassManagerRunOptions,1718    pass_info: ?PassInfo,1920    pub fn init(21        op: *ir.Operation,22        ir_ctx: *ir.Context,23        allocator: std.mem.Allocator,24        analysis_cache: *AnalysisCache,25    ) PassContext {26        return initWithOptions(op, ir_ctx, allocator, analysis_cache, .{});27    }2829    pub fn initWithOptions(30        op: *ir.Operation,31        ir_ctx: *ir.Context,32        allocator: std.mem.Allocator,33        analysis_cache: *AnalysisCache,34        options: PassManagerRunOptions,35    ) PassContext {36        return initWithInstrumentorAndOptions(op, ir_ctx, allocator, analysis_cache, null, options);37    }3839    pub fn initWithInstrumentor(40        op: *ir.Operation,41        ir_ctx: *ir.Context,42        allocator: std.mem.Allocator,43        analysis_cache: *AnalysisCache,44        instrumentor: ?*const PassInstrumentor,45    ) PassContext {46        return initWithInstrumentorAndOptions(47            op,48            ir_ctx,49            allocator,50            analysis_cache,51            instrumentor,52            .{},53        );54    }5556    pub fn initWithInstrumentorAndOptions(57        op: *ir.Operation,58        ir_ctx: *ir.Context,59        allocator: std.mem.Allocator,60        analysis_cache: *AnalysisCache,61        instrumentor: ?*const PassInstrumentor,62        options: PassManagerRunOptions,63    ) PassContext {64        return .{65            .op = op,66            .ir_ctx = ir_ctx,67            .allocator = allocator,68            .analysis_cache = analysis_cache,69            .preserved = PreservedAnalyses.init(allocator),70            .modified = false,71            .instrumentor = instrumentor,72            .run_options = options,73            .pass_info = null,74        };75    }7677    pub fn deinit(self: *PassContext) void {78        self.preserved.deinit();79    }8081    pub fn markModified(self: *PassContext) void {82        self.modified = true;83    }8485    pub fn preserveAllAnalyses(self: *PassContext) void {86        self.preserved.preserveAll();87    }8889    pub fn preserveAnalysisSet(self: *PassContext, comptime ids: []const AnalysisId) void {90        self.preserved.preserveAnalysisSet(ids);91    }9293    pub fn preserveAnalysis(self: *PassContext, id: AnalysisId) !void {94        try self.preserved.preserveAnalysis(id);95    }9697    pub fn preserveInterface(self: *PassContext, id: ir.InterfaceId) !void {98        try self.preserved.preserveInterface(id);99    }100101    pub fn getAnalysis(102        self: *PassContext,103        op: *ir.Operation,104        descriptor: *const AnalysisDescriptor,105        compute: *const fn (*PassContext, *ir.Operation) anyerror!*anyopaque,106        cleanup: ?*const fn (*anyopaque, std.mem.Allocator) void,107    ) !*anyopaque {108        return self.analysis_cache.getOrCompute(109            self,110            op,111            descriptor,112            compute,113            cleanup,114            self.instrumentor,115        );116    }117118    pub fn refreshAnalysis(119        self: *PassContext,120        op: *ir.Operation,121        descriptor: *const AnalysisDescriptor,122        refresh: *const fn (*PassContext, *ir.Operation, *anyopaque) anyerror!void,123    ) !void {124        try self.analysis_cache.refresh(self, op, descriptor, refresh, self.instrumentor);125    }126127    pub fn incrementStatistic(128        self: *PassContext,129        name: []const u8,130        description: []const u8,131    ) void {132        self.addStatistic(name, description, 1);133    }134135    pub fn addStatistic(136        self: *PassContext,137        name: []const u8,138        description: []const u8,139        value: u64,140    ) void {141        const pass_info = self.pass_info orelse return;142        const inst = self.instrumentor orelse return;143        inst.runPassStatistic(.{144            .pass = pass_info,145            .name = name,146            .description = description,147            .value = value,148        });149    }150151    pub fn workerCount(self: *const PassContext, item_count: usize) usize {152        return self.run_options.workerCount(item_count);153    }154155    pub fn workerAllocator(self: *const PassContext) std.mem.Allocator {156        return self.run_options.workerAllocator(self.allocator);157    }158};

1pub const PreservedAnalyses = struct {2    allocator: std.mem.Allocator,3    preserve_all: bool = false,4    analysis_set: []const AnalysisId,5    runtime_analyses: std.AutoHashMap(AnalysisId, void),6    interfaces: std.AutoHashMap(ir.InterfaceId, void),78    pub fn init(allocator: std.mem.Allocator) PreservedAnalyses {9        return .{10            .allocator = allocator,11            .analysis_set = &.{},12            .runtime_analyses = std.AutoHashMap(AnalysisId, void).init(allocator),13            .interfaces = std.AutoHashMap(ir.InterfaceId, void).init(allocator),14            .preserve_all = false,15        };16    }1718    pub fn deinit(self: *PreservedAnalyses) void {19        self.runtime_analyses.deinit();20        self.interfaces.deinit();21    }2223    pub fn preserveAll(self: *PreservedAnalyses) void {24        self.preserve_all = true;25    }2627    pub fn preserveAnalysisSet(self: *PreservedAnalyses, comptime ids: []const AnalysisId) void {28        std.debug.assert(self.analysis_set.len == 0);29        self.analysis_set = ids;30    }3132    pub fn preserveAnalysis(self: *PreservedAnalyses, id: AnalysisId) !void {33        for (self.analysis_set) |preserved_id| {34            if (preserved_id == id) return;35        }36        try self.runtime_analyses.put(id, {});37    }3839    pub fn preserveInterface(self: *PreservedAnalyses, id: ir.InterfaceId) !void {40        try self.interfaces.put(id, {});41    }4243    fn preservesDescriptor(self: *const PreservedAnalyses, desc: *const AnalysisDescriptor) bool {44        if (self.preserve_all) return true;45        for (self.analysis_set) |id| {46            if (id == desc.id) return true;47        }48        if (self.runtime_analyses.contains(desc.id)) return true;49        if (desc.required_interfaces.len == 0) return false;50        for (desc.required_interfaces) |iface| {51            if (!self.interfaces.contains(iface)) return false;52        }53        return true;54    }55};

1pub const OpPassManager = struct {2    allocator: std.mem.Allocator,3    target_op_name: ?[]const u8,4    target_kind: OpPassManagerTargetKind,5    pipeline: std.ArrayListUnmanaged(PipelineEntry),6    nested_managers: std.ArrayListUnmanaged(*OpPassManager),7    parent: ?*OpPassManager,89    pub fn init(allocator: std.mem.Allocator, target_op_name: ?[]const u8) OpPassManager {10        return initWithTarget(11            allocator,12            if (target_op_name == null) .root else .op,13            target_op_name,14        );15    }1617    pub fn initAny(allocator: std.mem.Allocator) OpPassManager {18        return initWithTarget(allocator, .any, null);19    }2021    pub fn initWithTarget(22        allocator: std.mem.Allocator,23        target_kind: OpPassManagerTargetKind,24        target_op_name: ?[]const u8,25    ) OpPassManager {26        return .{27            .allocator = allocator,28            .target_op_name = target_op_name,29            .target_kind = target_kind,30            .pipeline = .empty,31            .nested_managers = .empty,32            .parent = null,33        };34    }3536    pub fn deinit(self: *OpPassManager) void {37        for (self.nested_managers.items) |nested| {38            nested.deinit();39            self.allocator.destroy(nested);40        }41        for (self.pipeline.items) |*entry| {42            switch (entry.*) {43                .pass => |*pass| pass.deinit(self.allocator),44                .nested => {},45            }46        }47        self.nested_managers.deinit(self.allocator);48        self.pipeline.deinit(self.allocator);49    }5051    pub fn addPass(self: *OpPassManager, pass: Pass) !void {52        if (!pass.validRerunContract()) return error.InvalidPassRerunContract;53        try self.pipeline.append(self.allocator, .{ .pass = pass });54    }5556    pub fn nest(self: *OpPassManager, op_name: []const u8) !*OpPassManager {57        const nested = try self.allocator.create(OpPassManager);58        nested.* = OpPassManager.init(self.allocator, op_name);59        nested.parent = self;6061        try self.nested_managers.append(self.allocator, nested);62        try self.pipeline.append(self.allocator, .{ .nested = nested });6364        return nested;65    }6667    pub fn nestAny(self: *OpPassManager) !*OpPassManager {68        const nested = try self.allocator.create(OpPassManager);69        nested.* = OpPassManager.initAny(self.allocator);70        nested.parent = self;7172        try self.nested_managers.append(self.allocator, nested);73        try self.pipeline.append(self.allocator, .{ .nested = nested });7475        return nested;76    }7778    pub fn collectDependentDialects(79        self: *const OpPassManager,80        allocator: std.mem.Allocator,81        names: *std.ArrayListUnmanaged([]const u8),82    ) !void {83        for (self.pipeline.items) |entry| {84            switch (entry) {85                .pass => |pass| {86                    for (pass.dependent_dialects) |dialect_name| {87                        try appendDependentDialectName(allocator, names, dialect_name);88                    }89                },90                .nested => |nested_pm| try nested_pm.collectDependentDialects(allocator, names),91            }92        }93    }9495    fn matchesOp(self: *const OpPassManager, op: *ir.Operation) bool {96        return switch (self.target_kind) {97            .root, .any => true,98            .op => std.mem.eql(u8, op.name.name, self.target_op_name.?),99        };100    }101102    fn matchesScheduledOp(103        self: *const OpPassManager,104        op: *ir.Operation,105        ir_ctx: *ir.Context,106    ) bool {107        return switch (self.target_kind) {108            .root => true,109            .op => self.matchesOp(op),110            .any => self.isRegisteredIsolatedTarget(op, ir_ctx),111        };112    }113114    fn canRunOnTarget(115        self: *const OpPassManager,116        op: *ir.Operation,117        ir_ctx: *ir.Context,118    ) bool {119        if (self.target_kind == .root) return true;120        if (self.target_kind == .any) return self.isRegisteredIsolatedTarget(op, ir_ctx);121        const info = op.name.getRegisteredInfo() orelse122            ir_ctx.lookupOperation(op.name.name) orelse return false;123        return info.hasTraitId(ir.traits.IsolatedFromAbove.id);124    }125126    fn isRegisteredIsolatedTarget(127        _: *const OpPassManager,128        op: *ir.Operation,129        ir_ctx: *ir.Context,130    ) bool {131        const info = op.name.getRegisteredInfo() orelse132            ir_ctx.lookupOperation(op.name.name) orelse return false;133        return info.hasTraitId(ir.traits.IsolatedFromAbove.id);134    }135136    fn instrumentationTargetName(self: *const OpPassManager) ?[]const u8 {137        return switch (self.target_kind) {138            .root => null,139            .any => "any",140            .op => self.target_op_name,141        };142    }143144    pub fn runOnOperation(145        self: *OpPassManager,146        op: *ir.Operation,147        ir_ctx: *ir.Context,148        analysis_cache: *AnalysisCache,149        stats: *PassManagerStats,150        instrumentor: ?*const PassInstrumentor,151        verifier: ?*PassVerifierConfig,152        failure: ?*?CapturedPassFailure,153        options: PassManagerRunOptions,154        run_allocator: std.mem.Allocator,155    ) PassResult {156        if (!self.matchesScheduledOp(op, ir_ctx)) {157            return .success;158        }159160        const pipeline_info = PipelineInfo{161            .target_op_name = self.instrumentationTargetName(),162            .depth = self.getNestingDepth(),163        };164165        if (instrumentor) |inst| {166            inst.runBeforePipeline(pipeline_info, op);167        }168169        if (!self.canRunOnTarget(op, ir_ctx)) {170            if (instrumentor) |inst| {171                inst.runAfterPipeline(pipeline_info, op, true);172            }173            recordPassFailure(failure, .{174                .kind = .target,175                .target_op_name = op.name.name,176                .target_symbol_name = ir.SymbolTable.getSymbolName(op),177            });178            return .failure;179        }180181        var run = PipelineRun{182            .op = op,183            .ir_ctx = ir_ctx,184            .analysis_cache = analysis_cache,185            .stats = stats,186            .instrumentor = instrumentor,187            .verifier = verifier,188            .failure = failure,189            .options = options,190            .allocator = run_allocator,191        };192        const result = self.runPipelineEntries(&run);193        if (instrumentor) |inst| {194            inst.runAfterPipeline(pipeline_info, op, result == .failure);195        }196        return result;197    }198199    fn runPipelineEntries(self: *const OpPassManager, run: *PipelineRun) PassResult {200        var revision_start: usize = 0;201202        for (self.pipeline.items, 0..) |entry, entry_index| {203            const result = switch (entry) {204                .pass => |pass| self.runPassEntry(205                    pass,206                    entry_index,207                    &revision_start,208                    run,209                ),210                .nested => |nested_pm| runNestedEntry(211                    nested_pm,212                    entry_index,213                    &revision_start,214                    run,215                ),216            };217            if (result == .failure) return .failure;218        }219        return .success;220    }221222    /// A failing pass that reports IR modification preserves only analyses it declared preserved.223    fn runPassEntry(224        self: *const OpPassManager,225        pass: Pass,226        entry_index: usize,227        revision_start: *usize,228        run: *PipelineRun,229    ) PassResult {230        if (run.analysis_cache.accounting == null and231            self.hasRerunIdentity(pass, revision_start.*, entry_index))232        {233            run.stats.passes_skipped += 1;234            return .success;235        }236237        const pass_info = PassInfo{238            .name = pass.name,239            .description = pass.description,240            .target_op = run.op,241            .mutation_scope = pass.mutation_scope,242        };243        if (run.instrumentor) |inst| inst.runBeforePass(pass_info);244245        var ctx = PassContext.initWithInstrumentorAndOptions(246            run.op,247            run.ir_ctx,248            run.allocator,249            run.analysis_cache,250            run.instrumentor,251            run.options,252        );253        ctx.pass_info = pass_info;254        defer ctx.deinit();255256        const work = PassWork.begin(pass, run);257        var finalized: PassResult = .failure;258        defer work.finish(finalized, run.stats.*);259        const native = if (work.admitted) pass.run(&ctx) else PassResult.failure;260        const result = work.normalize(native, pass, run);261        if (work.admitted) run.stats.pass_runs += 1;262        if (ctx.modified) {263            run.stats.passes_modified += 1;264            run.analysis_cache.invalidate(&ctx.preserved);265            revision_start.* = entry_index;266        }267        if (result == .failure) {268            run.stats.pass_failures += 1;269            if (run.instrumentor) |inst| inst.runAfterPassFailed(pass_info);270            recordPassFailure(run.failure, .{271                .kind = .pass,272                .pass_name = pass.name,273                .target_op_name = run.op.name.name,274                .target_symbol_name = ir.SymbolTable.getSymbolName(run.op),275            });276            return .failure;277        }278279        if (run.instrumentor) |inst| inst.runAfterPass(pass_info, ctx.modified);280        finalized = verifyPass(pass, pass_info, run);281        return finalized;282    }283284    fn verifyPass(pass: Pass, pass_info: PassInfo, run: *PipelineRun) PassResult {285        const verifier = run.verifier orelse return .success;286        if (verifier.verifyAfterPass(pass_info) == .success) return .success;287288        run.stats.verifier_failures += 1;289        recordPassFailure(run.failure, .{290            .kind = .verifier,291            .pass_name = pass.name,292            .target_op_name = run.op.name.name,293            .target_symbol_name = ir.SymbolTable.getSymbolName(run.op),294            .verifier_error = if (verifier.failure.*) |failure| failure.err else null,295        });296        return .failure;297    }298299    fn runNestedEntry(300        nested: *OpPassManager,301        entry_index: usize,302        revision_start: *usize,303        run: *PipelineRun,304    ) PassResult {305        const modified_before = run.stats.passes_modified;306        const result = nested.walkAndRun(307            run.op,308            run.ir_ctx,309            run.analysis_cache,310            run.stats,311            run.instrumentor,312            run.verifier,313            run.failure,314            run.options,315            run.allocator,316        );317        if (result == .failure) return .failure;318        if (run.stats.passes_modified != modified_before) {319            revision_start.* = entry_index + 1;320        }321        return .success;322    }323324    fn hasRerunIdentity(325        self: *const OpPassManager,326        pass: Pass,327        revision_start: usize,328        entry_index: usize,329    ) bool {330        std.debug.assert(revision_start <= entry_index);331        std.debug.assert(entry_index <= self.pipeline.items.len);332        var previous_index = entry_index;333        while (previous_index > revision_start) {334            previous_index -= 1;335            switch (self.pipeline.items[previous_index]) {336                .pass => |previous| if (pass.sameRerunIdentity(previous)) return true,337                .nested => {},338            }339        }340        return false;341    }342343    fn walkAndRun(344        self: *OpPassManager,345        root: *ir.Operation,346        ir_ctx: *ir.Context,347        analysis_cache: *AnalysisCache,348        stats: *PassManagerStats,349        instrumentor: ?*const PassInstrumentor,350        verifier: ?*PassVerifierConfig,351        failure: ?*?CapturedPassFailure,352        options: PassManagerRunOptions,353        run_allocator: std.mem.Allocator,354    ) PassResult {355        if (self.canRunNestedTargetsParallel(instrumentor, verifier, options)) {356            const targets = self.collectMatchingTargets(root, ir_ctx) catch return .failure;357            defer if (targets.len != 0) self.allocator.free(targets);358359            if (targets.len > 1 and !targetSetOverlaps(targets)) {360                return self.runTargetsParallel(361                    targets,362                    ir_ctx,363                    analysis_cache,364                    stats,365                    verifier,366                    failure,367                    options,368                );369            }370        }371        return self.walkAndRunSerial(372            root,373            ir_ctx,374            analysis_cache,375            stats,376            instrumentor,377            verifier,378            failure,379            options,380            run_allocator,381        );382    }383384    fn walkAndRunSerial(385        self: *OpPassManager,386        root: *ir.Operation,387        ir_ctx: *ir.Context,388        analysis_cache: *AnalysisCache,389        stats: *PassManagerStats,390        instrumentor: ?*const PassInstrumentor,391        verifier: ?*PassVerifierConfig,392        failure: ?*?CapturedPassFailure,393        options: PassManagerRunOptions,394        run_allocator: std.mem.Allocator,395    ) PassResult {396        for (root.regions.items) |*region| {397            var block_iter = region.getBlocks();398            while (block_iter.next()) |block| {399                var current_op: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));400                while (current_op) |nested_op| {401                    if (self.matchesScheduledOp(nested_op, ir_ctx)) {402                        const result = self.runOnOperation(403                            nested_op,404                            ir_ctx,405                            analysis_cache,406                            stats,407                            instrumentor,408                            verifier,409                            failure,410                            options,411                            run_allocator,412                        );413                        if (result == .failure) {414                            return .failure;415                        }416                    }417                    const walk_result = self.walkAndRunSerial(418                        nested_op,419                        ir_ctx,420                        analysis_cache,421                        stats,422                        instrumentor,423                        verifier,424                        failure,425                        options,426                        run_allocator,427                    );428                    if (walk_result == .failure) {429                        return .failure;430                    }431                    current_op = nested_op.next_op;432                }433            }434        }435        return .success;436    }437438    fn canRunNestedTargetsParallel(439        self: *const OpPassManager,440        instrumentor: ?*const PassInstrumentor,441        verifier: ?*PassVerifierConfig,442        options: PassManagerRunOptions,443    ) bool {444        if (instrumentor != null) return false;445        _ = verifier;446        if (!options.requestsParallelism()) return false;447        return self.parallelReadOnlyPipeline();448    }449450    fn parallelReadOnlyPipeline(self: *const OpPassManager) bool {451        for (self.pipeline.items) |entry| {452            switch (entry) {453                .pass => |pass| {454                    if (!pass.readOnly() or !pass.parallelStateSafe()) return false;455                },456                .nested => |nested_pm| if (!nested_pm.parallelReadOnlyPipeline()) return false,457            }458        }459        return true;460    }461462    fn cloneForParallelTarget(463        self: *const OpPassManager,464        allocator: std.mem.Allocator,465    ) anyerror!OpPassManager {466        var cloned = OpPassManager.initWithTarget(467            allocator,468            self.target_kind,469            self.target_op_name,470        );471        errdefer cloned.deinit();472473        for (self.pipeline.items) |entry| {474            switch (entry) {475                .pass => |pass| {476                    var pass_clone = try pass.cloneForParallelTarget(allocator);477                    var pass_registered = false;478                    errdefer if (!pass_registered) pass_clone.deinit(allocator);479                    try cloned.pipeline.append(allocator, .{ .pass = pass_clone });480                    pass_registered = true;481                },482                .nested => |nested_pm| {483                    const nested = try allocator.create(OpPassManager);484                    var nested_initialized = false;485                    var nested_registered = false;486                    errdefer if (!nested_registered) {487                        if (nested_initialized) nested.deinit();488                        allocator.destroy(nested);489                    };490                    nested.* = try nested_pm.cloneForParallelTarget(allocator);491                    nested_initialized = true;492                    nested.parent = &cloned;493                    try cloned.nested_managers.append(allocator, nested);494                    nested_registered = true;495                    try cloned.pipeline.append(allocator, .{ .nested = nested });496                },497            }498        }499500        return cloned;501    }502503    fn refreshParentLinks(self: *OpPassManager, parent: ?*OpPassManager) void {504        self.parent = parent;505        for (self.nested_managers.items) |nested| {506            nested.refreshParentLinks(self);507        }508    }509510    fn collectMatchingTargets(511        self: *OpPassManager,512        root: *ir.Operation,513        ir_ctx: *ir.Context,514    ) ![]*ir.Operation {515        var targets: std.ArrayListUnmanaged(*ir.Operation) = .empty;516        errdefer targets.deinit(self.allocator);517518        try self.collectMatchingTargetsInto(root, ir_ctx, &targets);519        return if (targets.items.len == 0)520            &.{}521        else522            try targets.toOwnedSlice(self.allocator);523    }524525    fn collectMatchingTargetsInto(526        self: *OpPassManager,527        root: *ir.Operation,528        ir_ctx: *ir.Context,529        targets: *std.ArrayListUnmanaged(*ir.Operation),530    ) !void {531        for (root.regions.items) |*region| {532            var block_iter = region.getBlocks();533            while (block_iter.next()) |block| {534                var current_op: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));535                while (current_op) |nested_op| {536                    if (self.matchesScheduledOp(nested_op, ir_ctx)) {537                        try targets.append(self.allocator, nested_op);538                    }539                    try self.collectMatchingTargetsInto(nested_op, ir_ctx, targets);540                    current_op = nested_op.next_op;541                }542            }543        }544    }545546    fn runTargetsParallel(547        self: *OpPassManager,548        targets: []const *ir.Operation,549        ir_ctx: *ir.Context,550        analysis_cache: *AnalysisCache,551        stats: *PassManagerStats,552        verifier: ?*PassVerifierConfig,553        failure: ?*?CapturedPassFailure,554        options: PassManagerRunOptions,555    ) PassResult {556        _ = analysis_cache;557558        const worker_allocator = options.workerAllocator(self.allocator);559        const slots = self.allocator.alloc(ParallelTargetSlot, targets.len) catch return .failure;560        defer self.allocator.free(slots);561        for (slots) |*slot| slot.* = ParallelTargetSlot.init(worker_allocator);562        defer deinitParallelTargetSlots(slots);563        for (slots) |*slot| {564            slot.manager = self.cloneForParallelTarget(worker_allocator) catch return .failure;565            slot.manager.?.refreshParentLinks(null);566        }567568        var batch = ParallelTargetBatch{569            .manager = self,570            .allocator = worker_allocator,571            .ir_ctx = ir_ctx,572            .targets = targets,573            .verifier = verifier,574            .failure = failure,575            .options = options,576            .slots = slots,577        };578579        var execution_guard: ?ir.ThreadingExecutionGuard = null;580        if (options.workerCount(targets.len) > 1) {581            execution_guard = ir_ctx.enterMultithreadedExecution();582        }583        defer if (execution_guard) |*guard| guard.deinit();584585        ir.threading.parallelForEachIndex(586            self.allocator,587            options,588            targets.len,589            &batch,590            runParallelTarget,591        ) catch return .failure;592593        var result: PassResult = .success;594        for (slots) |*slot| {595            mergeStats(stats, slot.stats);596            if (slot.result == .failure) result = .failure;597            if (slot.failure) |captured_failure| {598                var slot_failure = captured_failure;599                slot_failure.worker_count = options.workerCount(targets.len);600                recordPassFailure(failure, slot_failure);601            }602            if (slot.verifier_failure) |verifier_failure| {603                if (verifier) |verify| {604                    if (verify.failure.* == null) verify.failure.* = verifier_failure;605                }606            }607            _ = ir_ctx.replayDiagnostics(&slot.diagnostics) catch {608                result = .failure;609                continue;610            };611        }612        return result;613    }614615    pub fn getNestingDepth(self: *const OpPassManager) usize {616        var depth: usize = 0;617        var current: ?*const OpPassManager = self;618        while (current) |pm| {619            if (pm.parent) |parent| {620                depth += 1;621                current = parent;622            } else {623                break;624            }625        }626        return depth;627    }628};

1pub const OpPassManagerTargetKind = enum {2    root,3    any,4    op,5};

1pub const PipelineEntry = union(enum) {2    pass: Pass,3    nested: *OpPassManager,4};

1pub const PassFailureKind = enum {2    pass,3    verifier,4    target,5    exhausted,6};

1pub const PassFailureReproducer = struct {2    pipeline: []const u8,3    ir: []const u8,4    max_threads: usize,5    worker_count: usize,6    verifier_enabled: bool,7    failure_kind: ?PassFailureKind = null,8    pass_name: ?[]const u8 = null,9    target_op_name: ?[]const u8 = null,10    target_symbol_name: ?[]const u8 = null,11    verifier_error: ?anyerror = null,12    verifier_error_name: ?[]const u8 = null,1314    pub fn deinit(self: *PassFailureReproducer, allocator: std.mem.Allocator) void {15        allocator.free(self.pipeline);16        allocator.free(self.ir);17        if (self.pass_name) |name| allocator.free(name);18        if (self.target_op_name) |name| allocator.free(name);19        if (self.target_symbol_name) |name| allocator.free(name);20        if (self.verifier_error_name) |name| allocator.free(name);21        self.* = undefined;22    }23};

1pub const PassManagerFixedPointResult = struct {2    result: PassResult = .success,3    iterations: usize = 0,4    changed: bool = false,5};

1pub const PassManagerStats = struct {2    pass_runs: u64 = 0,3    passes_skipped: u64 = 0,4    pass_failures: u64 = 0,5    verifier_failures: u64 = 0,6    passes_modified: u64 = 0,7    analysis_hits: u64 = 0,8    analysis_misses: u64 = 0,9    analyses_invalidated: u64 = 0,1011    pub fn reset(self: *PassManagerStats) void {12        self.* = .{};13    }14};

1pub const PassMutationScope = enum {2    read_only,3    isolated,4    whole_module,5};

1pub const PassRerunPolicy = enum {2    always,3    skip_if_unchanged,4};

1pub const PassResult = enum {2    success,3    failure,4};

1pub const PassStateConcurrency = enum {2    exclusive,3    shared,4};

1pub const PassVerifierFailure = struct {2    pass_name: []const u8,3    target_op_name: []const u8,4    err: anyerror,5};

1pub fn Analysis(2    comptime Value: type,3    comptime name: []const u8,4    comptime required_interfaces: []const ir.InterfaceId,5    comptime compute: *const fn (*PassContext, *ir.Operation) anyerror!*Value,6    comptime cleanup: ?*const fn (*Value, std.mem.Allocator) void,7    comptime work_contract: ?subject.work.Contract,8) type {9    return struct {10        pub const id = analysisId(name);11        pub const value_type = Value;12        pub const descriptor = AnalysisDescriptor{13            .id = id,14            .name = name,15            .required_interfaces = required_interfaces,16            .work_contract = work_contract,17        };1819        pub fn get(ctx: *PassContext, op: *ir.Operation) !*Value {20            const raw = try ctx.getAnalysis(op, &descriptor, computeOpaque, cleanupOpaque);21            return @ptrCast(@alignCast(raw));22        }2324        pub fn preserve(ctx: *PassContext) !void {25            try ctx.preserveAnalysis(id);26        }2728        fn computeOpaque(ctx: *PassContext, op: *ir.Operation) anyerror!*anyopaque {29            return @ptrCast(try compute(ctx, op));30        }3132        fn cleanupOpaque(raw: *anyopaque, allocator: std.mem.Allocator) void {33            if (cleanup) |cleanup_fn| {34                cleanup_fn(@ptrCast(@alignCast(raw)), allocator);35            }36        }37    };38}

1pub const AnalysisId = u64;

1pub const DependentDialects = []const []const u8;

1pub fn analysisId(comptime name: []const u8) AnalysisId {2    return ir.interfaceId(name);3}

1pub fn dialectDependencies(comptime names: DependentDialects) DependentDialects {2    comptime {3        for (names, 0..) |name, index| {4            if (name.len == 0) @compileError("dependent dialect name cannot be empty");5            for (names[0..index]) |prior| {6                if (std.mem.eql(u8, name, prior)) @compileError("duplicate dependent dialect name");7            }8        }9    }10    return names;11}

1pub fn OperationPass(2    comptime OpType: type,3    comptime run_on_op: fn (*OpType, *PassContext) PassResult,4) type {5    return struct {6        base: Pass,78        const Self = @This();910        pub fn init(11            name: []const u8,12            description: []const u8,13        ) Self {14            return initWithMutationScope(name, description, .whole_module);15        }1617        pub fn initWithMutationScope(18            name: []const u8,19            description: []const u8,20            mutation_scope: PassMutationScope,21        ) Self {22            return .{23                .base = .{24                    .name = name,25                    .description = description,26                    .run_fn = &runImpl,27                    .mutation_scope = mutation_scope,28                },29            };30        }3132        fn runImpl(ctx: *PassContext) PassResult {33            return walkAndApply(ctx.op, ctx);34        }3536        fn walkAndApply(op: *ir.Operation, ctx: *PassContext) PassResult {37            if (std.mem.eql(u8, op.name.name, OpType.operation_name)) {38                var typed_op = OpType{ .op = op };39                const result = run_on_op(&typed_op, ctx);40                if (result == .failure) {41                    return .failure;42                }43            }4445            for (op.regions.items) |*region| {46                var block_iter = region.getBlocks();47                while (block_iter.next()) |block| {48                    var current_op: ?*ir.Operation = @ptrCast(@alignCast(block.operations.head));49                    while (current_op) |nested_op| {50                        const result = walkAndApply(nested_op, ctx);51                        if (result == .failure) {52                            return .failure;53                        }54                        current_op = nested_op.next_op;55                    }56                }57            }5859            return .success;60        }61    };62}

1pub const work = @import("work.zig");2const model = @import("model.zig");3const base = @import("base.zig");4const analysis = @import("analysis.zig");5const manager = @import("manager.zig");6const operation = @import("operation.zig");78pub const PassMutationScope = model.PassMutationScope;9pub const PassStateConcurrency = model.PassStateConcurrency;10pub const PassRerunPolicy = model.PassRerunPolicy;11pub const DependentDialects = model.DependentDialects;12pub const dialectDependencies = model.dialectDependencies;13pub const Pass = base.Pass;14pub const PassManagerRunOptions = model.PassManagerRunOptions;15pub const PassManagerFixedPointResult = model.PassManagerFixedPointResult;16pub const AnalysisId = model.AnalysisId;17pub const analysisId = model.analysisId;18pub const AnalysisDescriptor = analysis.AnalysisDescriptor;19pub const Analysis = analysis.Analysis;20pub const PassManagerStats = model.PassManagerStats;21pub const PassVerifierFailure = model.PassVerifierFailure;22pub const PassFailureKind = model.PassFailureKind;23pub const PassFailureReproducer = model.PassFailureReproducer;24pub const PreservedAnalyses = analysis.PreservedAnalyses;25pub const AnalysisCache = analysis.AnalysisCache;26pub const PassContext = analysis.PassContext;27pub const PassResult = model.PassResult;28pub const PipelineEntry = manager.PipelineEntry;29pub const OpPassManagerTargetKind = manager.OpPassManagerTargetKind;30pub const OpPassManager = manager.OpPassManager;31pub const PassManager = manager.PassManager;32pub const OperationPass = operation.OperationPass;

1pub const pass = @import("pass/root.zig");