lib/choir/src/passes/control.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const ir = @import("../core/root.zig");
4 const pass = @import("pass/root.zig");
5
6 pub const cfg_analysis_name = "choir-control-flow-graph";
7 pub const dominance_analysis_name = "choir-dominance";
8 pub const post_dominance_analysis_name = "choir-post-dominance";
9
10 const control_storage_alignment = @max(@alignOf(usize), @alignOf(*ir.Block));
11
12 const RegionControlFlowFacts = struct {
13 block_count: usize,
14 edge_count: usize,
15 };
16
17 const RegionControlFlowLimits = struct {
18 region: *ir.Region,
19 facts: RegionControlFlowFacts,
20
21 pub fn inspect(region: *ir.Region) !RegionControlFlowLimits {
22 var block_count: usize = 0;
23 var edge_count: usize = 0;
24 var iter = region.getBlocks();
25 while (iter.next()) |block| {
26 block_count = std.math.add(usize, block_count, 1) catch
27 return error.CapacityOverflow;
28 edge_count = std.math.add(
29 usize,
30 edge_count,
31 try countRegionSuccessors(block, region),
32 ) catch return error.CapacityOverflow;
33 }
34 if (block_count != region.blocks.size) return error.RegionChanged;
35 return .{
36 .region = region,
37 .facts = .{
38 .block_count = block_count,
39 .edge_count = edge_count,
40 },
41 };
42 }
43 };
44
45 const RegionControlFlowCapacity = struct {
46 working_bytes: usize,
47
48 pub fn derive(limits: RegionControlFlowLimits) !RegionControlFlowCapacity {
49 const layout = try RegionControlFlowLayout.derive(limits.facts);
50 return .{ .working_bytes = layout.working_bytes };
51 }
52 };
53
54 const RegionControlFlowLayout = struct {
55 facts: RegionControlFlowFacts,
56 block_offset: usize,
57 successor_offset: usize,
58 predecessor_offset: usize,
59 cursor_offset: usize,
60 working_bytes: usize,
61
62 fn derive(facts: RegionControlFlowFacts) !RegionControlFlowLayout {
63 if (facts.block_count <= 1) return .{
64 .facts = facts,
65 .block_offset = 0,
66 .successor_offset = 0,
67 .predecessor_offset = 0,
68 .cursor_offset = 0,
69 .working_bytes = 0,
70 };
71 var cursor: usize = 0;
72 const block_offset = try placeControlStorage(
73 try controlStorageBytes(RegionControlFlow.BlockInfo, facts.block_count),
74 @alignOf(RegionControlFlow.BlockInfo),
75 &cursor,
76 );
77 const successor_offset = try placeControlStorage(
78 try controlStorageBytes(*ir.Block, facts.edge_count),
79 @alignOf(*ir.Block),
80 &cursor,
81 );
82 const predecessor_offset = try placeControlStorage(
83 try controlStorageBytes(*ir.Block, facts.edge_count),
84 @alignOf(*ir.Block),
85 &cursor,
86 );
87 const cursor_offset = try placeControlStorage(
88 try controlStorageBytes(usize, facts.block_count),
89 @alignOf(usize),
90 &cursor,
91 );
92 return .{
93 .facts = facts,
94 .block_offset = block_offset,
95 .successor_offset = successor_offset,
96 .predecessor_offset = predecessor_offset,
97 .cursor_offset = cursor_offset,
98 .working_bytes = cursor,
99 };
100 }
101 };
102
103 pub const RegionControlFlow = struct {
104 pub const claim: alloc_phase.capacity.Declaration = .{
105 .source = .{
106 .id = "choir.region_control_flow",
107 .kind = .phase_static,
108 .limit_source = .caller,
109 .storage = .{
110 .covered = &.{
111 .{
112 .id = "sorted_block_records_and_retained_successor_and_pre_0939f1a2ec2f",
113 .lifetime = .steady,
114 .detail = "sorted block records and retained successor and predecessor edges",
115 },
116 .{
117 .id = "predecessor_construction_cursors_colocated_with_retained_records",
118 .lifetime = .initialization,
119 .detail = "predecessor construction cursors colocated with retained records",
120 },
121 .{
122 .id = "inline_empty_and_singleton_region_representation",
123 .lifetime = .steady,
124 .detail = "inline empty and singleton region representation",
125 },
126 },
127 .excluded = &.{
128 "enclosing analysis maps, order lists, and region owner objects",
129 "borrowed IR and control-flow interface callback state",
130 },
131 },
132 .capacity = .{
133 .inputs = &.{
134 alloc_phase.capacity.bindInput(Limits, "facts_block_count", "facts.block_count"),
135 alloc_phase.capacity.bindInput(Limits, "facts_edge_count", "facts.edge_count"),
136 },
137 .type_selectors = &.{
138 alloc_phase.capacity.bindType(RegionControlFlow.BlockInfo, "blockrecord"),
139 alloc_phase.capacity.bindType(*ir.Block, "block"),
140 alloc_phase.capacity.bindType(usize, "usize"),
141 },
142 .nodes = &.{
143 .{ .input = 0 },
144 .{ .constant = 0 },
145 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
146 .{ .input = 1 },
147 .{ .scale = .{ .node = 3, .coefficient = .{ .literal = 2 } } },
148 .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 1 } } },
149 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 2 } } },
150 .{ .add = .{ .left = 2, .right = 5 } },
151 .{ .add = .{ .left = 7, .right = 6 } },
152 .{ .constant = 1 },
153 .{ .alignment = .{ .node = 8, .alignment = .{ .literal = 16 } } },
154 .{ .conditional = .{ .predicate = .{ .comparison = .less_or_equal, .left = 0, .right = 9 }, .when_true = 1, .when_false = 10 } },
155 },
156 .assertions = &.{.{
157 .scope = .closure_total,
158 .measure = .retained,
159 .relation = .exact,
160 .expression = 11,
161 }},
162 },
163 .overload = .{
164 .kind = .reject_before_seal,
165 .detail = "incompatible graph cardinality, count arithmetic, capacity arithmetic, or OOM rejects before an active control-flow owner is published",
166 },
167 .risks = .{
168 .transitive = .{
169 .status = .witnessed,
170 .detail = "activated lookup and edge queries use only sealed records and borrowed block pointers",
171 },
172 .foreign = .{
173 .status = .excluded,
174 .detail = "control-flow interface callbacks are confined to initialization and steady queries cross no foreign boundary",
175 },
176 },
177 .obligations = &.{
178 .{ .key = "choir_region_cfg_capacity_capacity_model", .role = .capacity_model },
179 .{ .key = "choir_region_cfg_capacity_overload", .role = .overload },
180 .{ .key = "choir_region_cfg_acquisition", .role = .custom },
181 .{ .key = "choir_region_cfg_sealed_transitive_risk", .role = .transitive_risk },
182 .{ .key = "choir_region_cfg_sealed_foreign_risk", .role = .foreign_risk },
183 .{ .key = "choir_region_cfg_oom", .role = .overload },
184 },
185 },
186 .bindings = .{
187 .owner = @This(),
188 .seal = .{
189 .family = alloc_phase.capacity.selector(@This().activate),
190 .premise = .{
191 .class = .checked_semantic_fact,
192 .authority = .checker,
193 },
194 },
195 .teardown = .{
196 .family = alloc_phase.capacity.selector(@This().deinit),
197 .premise = .{
198 .class = .checked_semantic_fact,
199 .authority = .checker,
200 },
201 },
202 },
203 };
204
205 phase: alloc_phase.capacity.Phase,
206 capacity: RegionControlFlowCapacity,
207 region: *ir.Region,
208 storage: Storage,
209
210 pub const BlockInfo = struct {
211 block: *ir.Block,
212 successors: []const *ir.Block,
213 predecessors: []const *ir.Block,
214 };
215
216 const Single = struct {
217 info: BlockInfo,
218 };
219
220 const Multiple = struct {
221 bytes: []align(control_storage_alignment) u8,
222 blocks: []BlockInfo,
223 };
224
225 const Storage = union(enum) {
226 empty,
227 single: Single,
228 multiple: Multiple,
229 };
230
231 pub const Limits = RegionControlFlowLimits;
232 pub const Capacity = RegionControlFlowCapacity;
233
234 pub fn init(
235 allocator: std.mem.Allocator,
236 limits: Limits,
237 ) !RegionControlFlow {
238 const capacity = try Capacity.derive(limits);
239 var owner: RegionControlFlow = .{
240 .phase = .initialization,
241 .capacity = capacity,
242 .region = limits.region,
243 .storage = .empty,
244 };
245 if (limits.facts.block_count == 0) {
246 if (limits.region.blocks.size != 0) return error.RegionChanged;
247 return owner;
248 }
249 if (limits.facts.block_count == 1) {
250 try owner.initSingle(limits.facts.edge_count);
251 return owner;
252 }
253 try initializeRegionControlFlowMultiple(&owner, allocator, limits);
254 return owner;
255 }
256
257 pub fn initForRegion(
258 allocator: std.mem.Allocator,
259 region: *ir.Region,
260 ) !RegionControlFlow {
261 return init(allocator, try Limits.inspect(region));
262 }
263
264 pub fn activate(self: *RegionControlFlow) !void {
265 if (self.phase != .initialization) return error.AlreadyActive;
266 self.phase = .steady;
267 }
268
269 pub fn deinit(self: *RegionControlFlow, allocator: std.mem.Allocator) void {
270 if (self.phase == .teardown) @panic("control-flow teardown is terminal");
271 if (self.storage == .multiple) allocator.free(self.storage.multiple.bytes);
272 self.phase = .teardown;
273 self.storage = undefined;
274 }
275
276 pub fn blockCount(self: *const RegionControlFlow) usize {
277 return self.blockInfos().len;
278 }
279
280 pub fn entryBlock(self: *const RegionControlFlow) ?*ir.Block {
281 self.requireSteady();
282 return self.region.getEntryBlock();
283 }
284
285 pub fn indexOf(self: *const RegionControlFlow, block: *ir.Block) ?usize {
286 const blocks = self.blockInfos();
287 std.debug.assert(blockInfosOrdered(blocks));
288 return indexOfBlockInfo(blocks, block);
289 }
290
291 pub fn blockInfo(self: *const RegionControlFlow, block: *ir.Block) ?*const BlockInfo {
292 const blocks = self.blockInfos();
293 const index = indexOfBlockInfo(blocks, block) orelse return null;
294 return &blocks[index];
295 }
296
297 pub fn successors(self: *const RegionControlFlow, block: *ir.Block) ?[]const *ir.Block {
298 const info = self.blockInfo(block) orelse return null;
299 return info.successors;
300 }
301
302 pub fn predecessors(self: *const RegionControlFlow, block: *ir.Block) ?[]const *ir.Block {
303 const info = self.blockInfo(block) orelse return null;
304 return info.predecessors;
305 }
306
307 pub fn hasEdge(self: *const RegionControlFlow, from: *ir.Block, to: *ir.Block) bool {
308 const succs = self.successors(from) orelse return false;
309 for (succs) |succ| {
310 if (succ == to) return true;
311 }
312 return false;
313 }
314
315 fn initSingle(self: *RegionControlFlow, expected_edge_count: usize) !void {
316 var iter = self.region.getBlocks();
317 const block = iter.next() orelse return error.RegionChanged;
318 if (iter.next() != null) return error.RegionChanged;
319 self.storage = .{ .single = undefined };
320 const single = &self.storage.single;
321 single.info = .{
322 .block = block,
323 .successors = &.{},
324 .predecessors = &.{},
325 };
326 const edge = @as(*[1]*ir.Block, @ptrCast(&single.info.block))[0..];
327 const successor_count = try writeRegionSuccessors(
328 block,
329 self.region,
330 edge,
331 );
332 if (successor_count != expected_edge_count) return error.RegionChanged;
333 single.info.successors = edge[0..successor_count];
334 single.info.predecessors = edge[0..successor_count];
335 }
336
337 fn blockInfos(self: *const RegionControlFlow) []const BlockInfo {
338 self.requireSteady();
339 return switch (self.storage) {
340 .empty => &.{},
341 .single => |*single| @as(
342 *const [1]BlockInfo,
343 @ptrCast(&single.info),
344 )[0..],
345 .multiple => |multiple| multiple.blocks,
346 };
347 }
348
349 fn requireSteady(self: *const RegionControlFlow) void {
350 if (self.phase != .steady) {
351 @panic("control-flow region used outside its steady phase");
352 }
353 }
354 };
355
356 comptime {
357 alloc_phase.capacity.requireAllocatorExactOwnerShape(RegionControlFlow);
358 }
359
360 const control_flow_graph_gather_capacity: usize = 16;
361
362 const ControlFlowGraphSurvey = struct {
363 root: *ir.Operation,
364 region_count: usize,
365 gathered: [control_flow_graph_gather_capacity]*ir.Region,
366
367 fn inspect(root: *ir.Operation) !ControlFlowGraphSurvey {
368 var survey = ControlFlowGraphSurvey{
369 .root = root,
370 .region_count = 0,
371 .gathered = undefined,
372 };
373 try inspectControlFlowGraphOperation(root, &survey);
374 return survey;
375 }
376
377 fn limits(self: *const ControlFlowGraphSurvey) ControlFlowGraphLimits {
378 return .{
379 .root = self.root,
380 .region_count = self.region_count,
381 };
382 }
383
384 fn gatheredRegions(
385 self: *const ControlFlowGraphSurvey,
386 ) ?[]const *ir.Region {
387 if (self.region_count > self.gathered.len) return null;
388 return self.gathered[0..self.region_count];
389 }
390 };
391
392 const ControlFlowGraphLimits = struct {
393 root: *ir.Operation,
394 region_count: usize,
395
396 pub fn inspect(root: *ir.Operation) !ControlFlowGraphLimits {
397 const survey = try ControlFlowGraphSurvey.inspect(root);
398 return survey.limits();
399 }
400 };
401
402 const ControlFlowGraphCapacity = struct {
403 region_count: usize,
404 storage_bytes: usize,
405
406 pub fn derive(limits: ControlFlowGraphLimits) !ControlFlowGraphCapacity {
407 return .{
408 .region_count = limits.region_count,
409 .storage_bytes = std.math.mul(
410 usize,
411 limits.region_count,
412 @sizeOf(RegionControlFlow),
413 ) catch return error.CapacityOverflow,
414 };
415 }
416 };
417
418 pub const ControlFlowGraphAnalysis = struct {
419 pub const claim: alloc_phase.capacity.Declaration = .{
420 .source = .{
421 .id = "choir.control_flow_graph_analysis",
422 .kind = .phase_static,
423 .limit_source = .caller,
424 .storage = .{
425 .covered = &.{
426 .{
427 .id = "pointer_sorted_stable_in_place_region_control_flow_owners",
428 .lifetime = .steady,
429 .detail = "pointer-sorted stable in-place region control-flow owners",
430 },
431 },
432 .excluded = &.{
433 "per-region control-flow backing owned by RegionControlFlow",
434 "borrowed operation tree, IR storage, and control-flow callbacks",
435 "analysis cache records and the separately allocated analysis object",
436 },
437 },
438 .capacity = .{
439 .inputs = &.{
440 alloc_phase.capacity.bindInput(Limits, "region_count", "region_count"),
441 },
442 .type_selectors = &.{
443 alloc_phase.capacity.bindType(RegionControlFlow, "regioncontrolflow"),
444 },
445 .nodes = &.{
446 .{ .input = 0 },
447 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
448 },
449 .assertions = &.{.{
450 .scope = .closure_total,
451 .measure = .retained,
452 .relation = .exact,
453 .expression = 1,
454 }},
455 },
456 .overload = .{
457 .kind = .reject_before_seal,
458 .detail = "region count arithmetic, capacity arithmetic, operation-tree changes, duplicate region ownership, child construction, or OOM rejects before an active analysis is published",
459 },
460 .risks = .{
461 .transitive = .{
462 .status = .witnessed,
463 .detail = "activated lookup and edge queries use only the sorted owner array and sealed RegionControlFlow children",
464 },
465 .foreign = .{
466 .status = .excluded,
467 .detail = "control-flow callbacks are confined to child initialization and steady queries cross no foreign boundary",
468 },
469 },
470 .obligations = &.{
471 .{ .key = "choir_cfg_analysis_capacity_capacity_model", .role = .capacity_model },
472 .{ .key = "choir_cfg_analysis_capacity_overload", .role = .overload },
473 .{ .key = "choir_cfg_analysis_acquisition", .role = .custom },
474 .{ .key = "choir_cfg_analysis_sealed_transitive_risk", .role = .transitive_risk },
475 .{ .key = "choir_cfg_analysis_sealed_foreign_risk", .role = .foreign_risk },
476 .{ .key = "choir_cfg_analysis_oom", .role = .overload },
477 },
478 },
479 .bindings = .{
480 .owner = @This(),
481 .seal = .{
482 .family = alloc_phase.capacity.selector(@This().activate),
483 .premise = .{
484 .class = .checked_semantic_fact,
485 .authority = .checker,
486 },
487 },
488 .teardown = .{
489 .family = alloc_phase.capacity.selector(@This().deinit),
490 .premise = .{
491 .class = .checked_semantic_fact,
492 .authority = .checker,
493 },
494 },
495 },
496 };
497
498 phase: alloc_phase.capacity.Phase,
499 capacity: ControlFlowGraphCapacity,
500 regions: []RegionControlFlow,
501
502 pub const Limits: type = ControlFlowGraphLimits;
503 pub const Capacity: type = ControlFlowGraphCapacity;
504
505 pub fn init(
506 allocator: std.mem.Allocator,
507 limits: Limits,
508 ) !ControlFlowGraphAnalysis {
509 const capacity = try Capacity.derive(limits);
510 const regions = try allocator.alloc(
511 RegionControlFlow,
512 capacity.region_count,
513 );
514
515 var filled: usize = 0;
516 fillControlFlowGraphOperation(
517 limits.root,
518 regions,
519 &filled,
520 ) catch |err| {
521 allocator.free(regions);
522 return err;
523 };
524 if (filled != capacity.region_count) {
525 allocator.free(regions);
526 return error.OperationChanged;
527 }
528 return finishInitialization(allocator, capacity, regions);
529 }
530
531 pub fn initForOperation(
532 allocator: std.mem.Allocator,
533 root: *ir.Operation,
534 ) !ControlFlowGraphAnalysis {
535 const survey = try ControlFlowGraphSurvey.inspect(root);
536 const gathered = survey.gatheredRegions() orelse {
537 return init(allocator, survey.limits());
538 };
539 const capacity = try Capacity.derive(survey.limits());
540 const regions = try allocator.alloc(
541 RegionControlFlow,
542 capacity.region_count,
543 );
544 for (regions, gathered) |*region_cfg, region| {
545 region_cfg.* = undefined;
546 region_cfg.region = region;
547 }
548 return finishInitialization(allocator, capacity, regions);
549 }
550
551 fn finishInitialization(
552 allocator: std.mem.Allocator,
553 capacity: Capacity,
554 regions: []RegionControlFlow,
555 ) !ControlFlowGraphAnalysis {
556 sortControlFlowRegionPointers(regions);
557 if (!regionControlFlowsOrdered(regions)) {
558 allocator.free(regions);
559 return error.OperationChanged;
560 }
561
562 var initialized: usize = 0;
563 errdefer {
564 for (regions[0..initialized]) |*region_cfg| {
565 region_cfg.deinit(allocator);
566 }
567 allocator.free(regions);
568 }
569 while (initialized < regions.len) {
570 const region = regions[initialized].region;
571 regions[initialized] = try RegionControlFlow.initForRegion(
572 allocator,
573 region,
574 );
575 regions[initialized].activate() catch |err| {
576 regions[initialized].deinit(allocator);
577 return err;
578 };
579 initialized += 1;
580 }
581
582 return .{
583 .phase = .initialization,
584 .capacity = capacity,
585 .regions = regions,
586 };
587 }
588
589 pub fn activate(self: *ControlFlowGraphAnalysis) !void {
590 if (self.phase != .initialization) return error.AlreadyActive;
591 self.phase = .steady;
592 }
593
594 pub fn deinit(
595 self: *ControlFlowGraphAnalysis,
596 allocator: std.mem.Allocator,
597 ) void {
598 if (self.phase == .teardown) {
599 @panic("control-flow graph analysis teardown is terminal");
600 }
601 for (self.regions) |*region_cfg| {
602 region_cfg.deinit(allocator);
603 }
604 allocator.free(self.regions);
605 self.phase = .teardown;
606 self.regions = undefined;
607 }
608
609 pub fn regionCount(self: *const ControlFlowGraphAnalysis) usize {
610 self.requireSteady();
611 return self.regions.len;
612 }
613
614 pub fn getRegion(
615 self: *const ControlFlowGraphAnalysis,
616 region: *ir.Region,
617 ) ?*const RegionControlFlow {
618 const index = self.indexOfRegion(region) orelse return null;
619 return &self.regions[index];
620 }
621
622 pub fn getBlockRegion(
623 self: *const ControlFlowGraphAnalysis,
624 block: *ir.Block,
625 ) ?*const RegionControlFlow {
626 const region = block.getParentRegion() orelse return null;
627 return self.getRegion(region);
628 }
629
630 pub fn successors(self: *const ControlFlowGraphAnalysis, block: *ir.Block) ?[]const *ir.Block {
631 const region_cfg = self.getBlockRegion(block) orelse return null;
632 return region_cfg.successors(block);
633 }
634
635 pub fn predecessors(
636 self: *const ControlFlowGraphAnalysis,
637 block: *ir.Block,
638 ) ?[]const *ir.Block {
639 const region_cfg = self.getBlockRegion(block) orelse return null;
640 return region_cfg.predecessors(block);
641 }
642
643 fn regionSlice(self: *const ControlFlowGraphAnalysis) []const RegionControlFlow {
644 self.requireSteady();
645 return self.regions;
646 }
647
648 fn indexOfRegion(
649 self: *const ControlFlowGraphAnalysis,
650 region: *ir.Region,
651 ) ?usize {
652 self.requireSteady();
653 std.debug.assert(regionControlFlowsOrdered(self.regions));
654 const key = @intFromPtr(region);
655 var low: usize = 0;
656 var high = self.regions.len;
657 while (low < high) {
658 const middle = low + (high - low) / 2;
659 if (@intFromPtr(self.regions[middle].region) < key) {
660 low = middle + 1;
661 } else {
662 high = middle;
663 }
664 }
665 if (low == self.regions.len) return null;
666 if (self.regions[low].region != region) return null;
667 return low;
668 }
669
670 fn requireSteady(self: *const ControlFlowGraphAnalysis) void {
671 if (self.phase != .steady) {
672 @panic("control-flow graph analysis used outside its steady phase");
673 }
674 }
675 };
676
677 comptime {
678 alloc_phase.capacity.requireAllocatorExactOwnerShape(ControlFlowGraphAnalysis);
679 }
680
681 pub const DominanceKind = enum {
682 forward,
683 reverse,
684 };
685
686 const BlockDominanceLimits = struct {
687 cfg: *const ControlFlowGraphAnalysis,
688 kind: DominanceKind,
689 region_count: usize,
690
691 pub fn inspect(
692 cfg: *const ControlFlowGraphAnalysis,
693 kind: DominanceKind,
694 ) BlockDominanceLimits {
695 return .{
696 .cfg = cfg,
697 .kind = kind,
698 .region_count = cfg.regionCount(),
699 };
700 }
701 };
702
703 const BlockDominanceCapacity = struct {
704 region_count: usize,
705 storage_bytes: usize,
706
707 pub fn derive(limits: BlockDominanceLimits) !BlockDominanceCapacity {
708 return .{
709 .region_count = limits.region_count,
710 .storage_bytes = std.math.mul(
711 usize,
712 limits.region_count,
713 @sizeOf(RegionDominance),
714 ) catch return error.CapacityOverflow,
715 };
716 }
717 };
718
719 pub const BlockDominanceAnalysis = struct {
720 pub const claim: alloc_phase.capacity.Declaration = .{
721 .source = .{
722 .id = "choir.block_dominance_analysis",
723 .kind = .phase_static,
724 .limit_source = .caller,
725 .storage = .{
726 .covered = &.{
727 .{
728 .id = "in_place_region_dominance_owners_aligned_with_the_s_d1cee8fda637",
729 .lifetime = .steady,
730 .detail = "in-place region dominance owners aligned with the sorted control-flow region index",
731 },
732 },
733 .excluded = &.{
734 "per-region relation backing owned by RegionDominance",
735 "control-flow graph borrowed only during construction and IR storage",
736 "analysis cache records and the separately allocated analysis object",
737 },
738 },
739 .capacity = .{
740 .inputs = &.{
741 alloc_phase.capacity.bindInput(Limits, "region_count", "region_count"),
742 },
743 .type_selectors = &.{
744 alloc_phase.capacity.bindType(RegionDominance, "regiondominance"),
745 },
746 .nodes = &.{
747 .{ .input = 0 },
748 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
749 },
750 .assertions = &.{.{
751 .scope = .closure_total,
752 .measure = .retained,
753 .relation = .exact,
754 .expression = 1,
755 }},
756 },
757 .overload = .{
758 .kind = .reject_before_seal,
759 .detail = "capacity arithmetic, incompatible control-flow cardinality, child construction, or OOM rejects before an active analysis is published",
760 },
761 .risks = .{
762 .transitive = .{
763 .status = .witnessed,
764 .detail = "activated queries use only the sorted owner array and sealed RegionDominance children",
765 },
766 .foreign = .{
767 .status = .excluded,
768 .detail = "dominance construction and steady lookup cross no operating-system or foreign callback boundary",
769 },
770 },
771 .obligations = &.{
772 .{ .key = "choir_block_dominance_analysis_capacity_capacity_model", .role = .capacity_model },
773 .{ .key = "choir_block_dominance_analysis_capacity_overload", .role = .overload },
774 .{ .key = "choir_block_dominance_analysis_acquisition", .role = .custom },
775 .{ .key = "choir_block_dominance_analysis_sealed_transitive_risk", .role = .transitive_risk },
776 .{ .key = "choir_block_dominance_analysis_sealed_foreign_risk", .role = .foreign_risk },
777 .{ .key = "choir_block_dominance_analysis_oom", .role = .overload },
778 .{ .key = "choir_block_dominance_analysis_independent", .role = .transitive_risk },
779 },
780 },
781 .bindings = .{
782 .owner = @This(),
783 .seal = .{
784 .family = alloc_phase.capacity.selector(@This().activate),
785 .premise = .{
786 .class = .checked_semantic_fact,
787 .authority = .checker,
788 },
789 },
790 .teardown = .{
791 .family = alloc_phase.capacity.selector(@This().deinit),
792 .premise = .{
793 .class = .checked_semantic_fact,
794 .authority = .checker,
795 },
796 },
797 },
798 };
799
800 phase: alloc_phase.capacity.Phase,
801 capacity: BlockDominanceCapacity,
802 regions: []RegionDominance,
803
804 pub const Limits: type = BlockDominanceLimits;
805 pub const Capacity: type = BlockDominanceCapacity;
806
807 pub fn init(
808 allocator: std.mem.Allocator,
809 limits: Limits,
810 ) !BlockDominanceAnalysis {
811 const capacity = try Capacity.derive(limits);
812 const cfg_regions = limits.cfg.regionSlice();
813 if (cfg_regions.len != capacity.region_count) {
814 return error.ControlFlowChanged;
815 }
816 const regions = try allocator.alloc(
817 RegionDominance,
818 capacity.region_count,
819 );
820 errdefer allocator.free(regions);
821
822 var initialized: usize = 0;
823 errdefer for (regions[0..initialized]) |*region_dom| {
824 region_dom.deinit(allocator);
825 };
826 while (initialized < regions.len) {
827 regions[initialized] = try RegionDominance.initForRegion(
828 allocator,
829 &cfg_regions[initialized],
830 limits.kind,
831 );
832 regions[initialized].activate() catch |err| {
833 regions[initialized].deinit(allocator);
834 return err;
835 };
836 initialized += 1;
837 }
838 if (!regionDominancesOrdered(regions)) {
839 return error.ControlFlowChanged;
840 }
841
842 return .{
843 .phase = .initialization,
844 .capacity = capacity,
845 .regions = regions,
846 };
847 }
848
849 pub fn activate(self: *BlockDominanceAnalysis) !void {
850 if (self.phase != .initialization) return error.AlreadyActive;
851 self.phase = .steady;
852 }
853
854 pub fn deinit(
855 self: *BlockDominanceAnalysis,
856 allocator: std.mem.Allocator,
857 ) void {
858 if (self.phase == .teardown) {
859 @panic("block dominance analysis teardown is terminal");
860 }
861 for (self.regions) |*region_dom| {
862 region_dom.deinit(allocator);
863 }
864 allocator.free(self.regions);
865 self.phase = .teardown;
866 self.regions = undefined;
867 }
868
869 pub fn getRegion(
870 self: *const BlockDominanceAnalysis,
871 region: *ir.Region,
872 ) ?*const RegionDominance {
873 self.requireSteady();
874 std.debug.assert(regionDominancesOrdered(self.regions));
875 const key = @intFromPtr(region);
876 var low: usize = 0;
877 var high = self.regions.len;
878 while (low < high) {
879 const middle = low + (high - low) / 2;
880 if (@intFromPtr(self.regions[middle].regionPointer()) < key) {
881 low = middle + 1;
882 } else {
883 high = middle;
884 }
885 }
886 if (low == self.regions.len) return null;
887 if (self.regions[low].regionPointer() != region) return null;
888 return &self.regions[low];
889 }
890
891 pub fn dominatesBlock(
892 self: *const BlockDominanceAnalysis,
893 dominator: *ir.Block,
894 block: *ir.Block,
895 ) bool {
896 const region = block.getParentRegion() orelse return false;
897 if (dominator.getParentRegion() != region) return false;
898 const region_dom = self.getRegion(region) orelse return false;
899 return region_dom.contains(dominator, block);
900 }
901
902 pub fn postDominatesBlock(
903 self: *const BlockDominanceAnalysis,
904 postdominator: *ir.Block,
905 block: *ir.Block,
906 ) bool {
907 return self.dominatesBlock(postdominator, block);
908 }
909
910 pub fn strictlyDominatesBlock(
911 self: *const BlockDominanceAnalysis,
912 dominator: *ir.Block,
913 block: *ir.Block,
914 ) bool {
915 return dominator != block and self.dominatesBlock(dominator, block);
916 }
917
918 pub fn strictlyPostDominatesBlock(
919 self: *const BlockDominanceAnalysis,
920 postdominator: *ir.Block,
921 block: *ir.Block,
922 ) bool {
923 return postdominator != block and self.postDominatesBlock(postdominator, block);
924 }
925
926 pub fn dominatesOperation(
927 self: *const BlockDominanceAnalysis,
928 dominator: *ir.Operation,
929 op: *ir.Operation,
930 ) bool {
931 if (dominator == op) return true;
932 const dominator_block = dominator.getBlock() orelse return false;
933 const op_block = op.getBlock() orelse return false;
934 if (dominator_block == op_block) return operationPrecedesOrSame(dominator, op);
935 return self.dominatesBlock(dominator_block, op_block);
936 }
937
938 pub fn postDominatesOperation(
939 self: *const BlockDominanceAnalysis,
940 postdominator: *ir.Operation,
941 op: *ir.Operation,
942 ) bool {
943 if (postdominator == op) return true;
944 const postdominator_block = postdominator.getBlock() orelse return false;
945 const op_block = op.getBlock() orelse return false;
946 if (postdominator_block == op_block) return operationPrecedesOrSame(op, postdominator);
947 return self.postDominatesBlock(postdominator_block, op_block);
948 }
949
950 fn requireSteady(self: *const BlockDominanceAnalysis) void {
951 if (self.phase != .steady) {
952 @panic("block dominance analysis used outside its steady phase");
953 }
954 }
955 };
956
957 comptime {
958 alloc_phase.capacity.requireAllocatorExactOwnerShape(BlockDominanceAnalysis);
959 }
960
961 pub const DominanceAnalysis = BlockDominanceAnalysis;
962 pub const PostDominanceAnalysis = BlockDominanceAnalysis;
963
964 fn inspectControlFlowGraphOperation(
965 op: *ir.Operation,
966 survey: *ControlFlowGraphSurvey,
967 ) !void {
968 for (op.regions.items) |*region| {
969 if (survey.region_count < survey.gathered.len) {
970 survey.gathered[survey.region_count] = region;
971 }
972 survey.region_count = std.math.add(
973 usize,
974 survey.region_count,
975 1,
976 ) catch return error.CapacityOverflow;
977 var block_iter = region.getBlocks();
978 while (block_iter.next()) |block| {
979 var op_node = block.operations.head;
980 while (op_node) |node| {
981 const nested: *ir.Operation = @ptrCast(@alignCast(node));
982 try inspectControlFlowGraphOperation(nested, survey);
983 op_node = nested.next_op;
984 }
985 }
986 }
987 }
988
989 fn fillControlFlowGraphOperation(
990 op: *ir.Operation,
991 regions: []RegionControlFlow,
992 filled: *usize,
993 ) !void {
994 for (op.regions.items) |*region| {
995 if (filled.* >= regions.len) return error.OperationChanged;
996 regions[filled.*] = undefined;
997 regions[filled.*].region = region;
998 filled.* += 1;
999
1000 var block_iter = region.getBlocks();
1001 while (block_iter.next()) |block| {
1002 var op_node = block.operations.head;
1003 while (op_node) |node| {
1004 const nested: *ir.Operation = @ptrCast(@alignCast(node));
1005 try fillControlFlowGraphOperation(nested, regions, filled);
1006 op_node = nested.next_op;
1007 }
1008 }
1009 }
1010 }
1011
1012 noinline fn sortControlFlowRegionPointers(
1013 regions: []RegionControlFlow,
1014 ) void {
1015 if (regions.len < 2) return;
1016
1017 var root = regions.len / 2;
1018 while (root > 0) {
1019 root -= 1;
1020 siftControlFlowRegionPointer(regions, root, regions.len);
1021 }
1022
1023 var end = regions.len;
1024 while (end > 1) {
1025 end -= 1;
1026 swapControlFlowRegionPointers(®ions[0], ®ions[end]);
1027 siftControlFlowRegionPointer(regions, 0, end);
1028 }
1029 }
1030
1031 fn siftControlFlowRegionPointer(
1032 regions: []RegionControlFlow,
1033 start: usize,
1034 end: usize,
1035 ) void {
1036 std.debug.assert(end <= regions.len);
1037 std.debug.assert(start < end);
1038 var root = start;
1039 while (root < end / 2) {
1040 const doubled = std.math.mul(usize, root, 2) catch
1041 @panic("control-flow region heap index overflow");
1042 var child = std.math.add(usize, doubled, 1) catch
1043 @panic("control-flow region heap index overflow");
1044 const right = std.math.add(usize, child, 1) catch
1045 @panic("control-flow region heap index overflow");
1046 std.debug.assert(child < end);
1047 if (right < end and
1048 @intFromPtr(regions[child].region) <
1049 @intFromPtr(regions[right].region))
1050 {
1051 child = right;
1052 }
1053 if (@intFromPtr(regions[root].region) >=
1054 @intFromPtr(regions[child].region)) return;
1055 swapControlFlowRegionPointers(®ions[root], ®ions[child]);
1056 root = child;
1057 }
1058 }
1059
1060 fn swapControlFlowRegionPointers(
1061 lhs: *RegionControlFlow,
1062 rhs: *RegionControlFlow,
1063 ) void {
1064 const region = lhs.region;
1065 lhs.region = rhs.region;
1066 rhs.region = region;
1067 }
1068
1069 fn regionControlFlowsOrdered(regions: []const RegionControlFlow) bool {
1070 if (regions.len < 2) return true;
1071 var previous = @intFromPtr(regions[0].region);
1072 for (regions[1..]) |region_cfg| {
1073 const current = @intFromPtr(region_cfg.region);
1074 if (previous >= current) return false;
1075 previous = current;
1076 }
1077 return true;
1078 }
1079
1080 const RegionDominanceLimits = struct {
1081 cfg: *const RegionControlFlow,
1082 kind: DominanceKind,
1083 block_count: usize,
1084
1085 pub fn inspect(
1086 cfg: *const RegionControlFlow,
1087 kind: DominanceKind,
1088 ) RegionDominanceLimits {
1089 return .{
1090 .cfg = cfg,
1091 .kind = kind,
1092 .block_count = cfg.blockCount(),
1093 };
1094 }
1095 };
1096
1097 const RegionDominanceCapacity = struct {
1098 block_count: usize,
1099 working_bytes: usize,
1100
1101 pub fn derive(limits: RegionDominanceLimits) !RegionDominanceCapacity {
1102 const layout = try RegionDominanceLayout.derive(limits.block_count);
1103 return .{
1104 .block_count = limits.block_count,
1105 .working_bytes = layout.working_bytes,
1106 };
1107 }
1108 };
1109
1110 const RegionDominanceLayout = struct {
1111 block_count: usize,
1112 relation_count: usize,
1113 block_offset: usize,
1114 relation_offset: usize,
1115 root_offset: usize,
1116 scratch_offset: usize,
1117 working_bytes: usize,
1118
1119 fn derive(block_count: usize) !RegionDominanceLayout {
1120 const relation_count = std.math.mul(
1121 usize,
1122 block_count,
1123 block_count,
1124 ) catch return error.CapacityOverflow;
1125 if (block_count <= 1) return .{
1126 .block_count = block_count,
1127 .relation_count = relation_count,
1128 .block_offset = 0,
1129 .relation_offset = 0,
1130 .root_offset = 0,
1131 .scratch_offset = 0,
1132 .working_bytes = 0,
1133 };
1134 var cursor: usize = 0;
1135 const block_offset = try placeControlStorage(
1136 try controlStorageBytes(*ir.Block, block_count),
1137 @alignOf(*ir.Block),
1138 &cursor,
1139 );
1140 const relation_offset = try placeControlStorage(
1141 try controlStorageBytes(bool, relation_count),
1142 @alignOf(bool),
1143 &cursor,
1144 );
1145 const root_offset = try placeControlStorage(
1146 try controlStorageBytes(bool, block_count),
1147 @alignOf(bool),
1148 &cursor,
1149 );
1150 const scratch_offset = try placeControlStorage(
1151 try controlStorageBytes(bool, block_count),
1152 @alignOf(bool),
1153 &cursor,
1154 );
1155 return .{
1156 .block_count = block_count,
1157 .relation_count = relation_count,
1158 .block_offset = block_offset,
1159 .relation_offset = relation_offset,
1160 .root_offset = root_offset,
1161 .scratch_offset = scratch_offset,
1162 .working_bytes = cursor,
1163 };
1164 }
1165 };
1166
1167 pub const RegionDominance = struct {
1168 pub const claim: alloc_phase.capacity.Declaration = .{
1169 .source = .{
1170 .id = "choir.region_dominance",
1171 .kind = .phase_static,
1172 .limit_source = .caller,
1173 .storage = .{
1174 .covered = &.{
1175 .{
1176 .id = "sorted_block_pointers_and_exact_dominance_relation_matrix",
1177 .lifetime = .steady,
1178 .detail = "sorted block pointers and exact dominance relation matrix",
1179 },
1180 .{
1181 .id = "root_and_fixed_point_scratch_vectors_colocated_with_76bd11122433",
1182 .lifetime = .initialization,
1183 .detail = "root and fixed-point scratch vectors colocated with retained relations",
1184 },
1185 .{
1186 .id = "inline_empty_and_singleton_dominance_representation",
1187 .lifetime = .steady,
1188 .detail = "inline empty and singleton dominance representation",
1189 },
1190 },
1191 .excluded = &.{
1192 "borrowed region control-flow and IR storage",
1193 "enclosing analysis maps, order lists, and region owner objects",
1194 },
1195 },
1196 .capacity = .{
1197 .inputs = &.{
1198 alloc_phase.capacity.bindInput(Limits, "block_count", "block_count"),
1199 },
1200 .type_selectors = &.{
1201 alloc_phase.capacity.bindType(*ir.Block, "block"),
1202 },
1203 .nodes = &.{
1204 .{ .input = 0 },
1205 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
1206 .{ .product = .{ .left = 0, .right = 0 } },
1207 .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },
1208 .{ .add = .{ .left = 1, .right = 2 } },
1209 .{ .add = .{ .left = 4, .right = 3 } },
1210 .{ .constant = 1 },
1211 .{ .constant = 0 },
1212 .{ .alignment = .{ .node = 5, .alignment = .{ .literal = 16 } } },
1213 .{ .conditional = .{ .predicate = .{ .comparison = .less_or_equal, .left = 0, .right = 6 }, .when_true = 7, .when_false = 8 } },
1214 },
1215 .assertions = &.{.{
1216 .scope = .closure_total,
1217 .measure = .retained,
1218 .relation = .exact,
1219 .expression = 9,
1220 }},
1221 },
1222 .overload = .{
1223 .kind = .reject_before_seal,
1224 .detail = "incompatible control-flow cardinality, relation arithmetic, layout arithmetic, or OOM rejects before an active dominance owner is published",
1225 },
1226 .risks = .{
1227 .transitive = .{
1228 .status = .witnessed,
1229 .detail = "activated dominance queries use only the sealed relation matrix and retained block pointers",
1230 },
1231 .foreign = .{
1232 .status = .excluded,
1233 .detail = "dominance initialization and queries cross no operating-system or foreign callback boundary",
1234 },
1235 },
1236 .obligations = &.{
1237 .{ .key = "choir_region_dominance_capacity_capacity_model", .role = .capacity_model },
1238 .{ .key = "choir_region_dominance_capacity_overload", .role = .overload },
1239 .{ .key = "choir_region_dominance_acquisition", .role = .custom },
1240 .{ .key = "choir_region_dominance_sealed_transitive_risk", .role = .transitive_risk },
1241 .{ .key = "choir_region_dominance_sealed_foreign_risk", .role = .foreign_risk },
1242 .{ .key = "choir_region_dominance_oom", .role = .overload },
1243 },
1244 },
1245 .bindings = .{
1246 .owner = @This(),
1247 .seal = .{
1248 .family = alloc_phase.capacity.selector(@This().activate),
1249 .premise = .{
1250 .class = .checked_semantic_fact,
1251 .authority = .checker,
1252 },
1253 },
1254 .teardown = .{
1255 .family = alloc_phase.capacity.selector(@This().deinit),
1256 .premise = .{
1257 .class = .checked_semantic_fact,
1258 .authority = .checker,
1259 },
1260 },
1261 },
1262 };
1263
1264 phase: alloc_phase.capacity.Phase,
1265 capacity: RegionDominanceCapacity,
1266 storage: Storage,
1267
1268 const Multiple = struct {
1269 bytes: []align(control_storage_alignment) u8,
1270 blocks: [*]*ir.Block,
1271 relations: [*]bool,
1272 };
1273
1274 const Storage = union(enum) {
1275 empty: *ir.Region,
1276 single: *ir.Block,
1277 multiple: Multiple,
1278 };
1279
1280 pub const Limits = RegionDominanceLimits;
1281 pub const Capacity = RegionDominanceCapacity;
1282
1283 pub fn init(
1284 allocator: std.mem.Allocator,
1285 limits: Limits,
1286 ) !RegionDominance {
1287 const blocks = limits.cfg.blockInfos();
1288 const capacity = try Capacity.derive(limits);
1289 if (blocks.len != capacity.block_count) return error.RegionChanged;
1290 var owner: RegionDominance = .{
1291 .phase = .initialization,
1292 .capacity = capacity,
1293 .storage = .{ .empty = limits.cfg.region },
1294 };
1295 if (blocks.len == 0) return owner;
1296 if (blocks.len == 1) {
1297 owner.storage = .{ .single = blocks[0].block };
1298 return owner;
1299 }
1300 try initializeRegionDominanceMultiple(&owner, allocator, limits);
1301 return owner;
1302 }
1303
1304 pub fn initForRegion(
1305 allocator: std.mem.Allocator,
1306 cfg: *const RegionControlFlow,
1307 kind: DominanceKind,
1308 ) !RegionDominance {
1309 return init(allocator, Limits.inspect(cfg, kind));
1310 }
1311
1312 pub fn activate(self: *RegionDominance) !void {
1313 if (self.phase != .initialization) return error.AlreadyActive;
1314 self.phase = .steady;
1315 }
1316
1317 pub fn deinit(self: *RegionDominance, allocator: std.mem.Allocator) void {
1318 if (self.phase == .teardown) @panic("dominance teardown is terminal");
1319 if (self.storage == .multiple) allocator.free(self.storage.multiple.bytes);
1320 self.phase = .teardown;
1321 self.storage = undefined;
1322 }
1323
1324 pub fn contains(self: *const RegionDominance, dominator: *ir.Block, block: *ir.Block) bool {
1325 self.requireSteady();
1326 return switch (self.storage) {
1327 .empty => false,
1328 .single => |single| dominator == single and block == single,
1329 .multiple => |multiple| containsMultiple(
1330 multiple,
1331 self.capacity.block_count,
1332 dominator,
1333 block,
1334 ),
1335 };
1336 }
1337
1338 fn blockSlice(self: *const RegionDominance) []const *ir.Block {
1339 self.requireSteady();
1340 return switch (self.storage) {
1341 .empty => &.{},
1342 .single => |*single| @as(
1343 *const [1]*ir.Block,
1344 @ptrCast(single),
1345 )[0..],
1346 .multiple => |multiple| multiple.blocks[0..self.capacity.block_count],
1347 };
1348 }
1349
1350 fn regionPointer(self: *const RegionDominance) *ir.Region {
1351 self.requireSteady();
1352 return switch (self.storage) {
1353 .empty => |region| region,
1354 .single => |block| block.getParentRegion() orelse
1355 @panic("dominance block lost its parent region"),
1356 .multiple => |multiple| multiple.blocks[0].getParentRegion() orelse
1357 @panic("dominance block lost its parent region"),
1358 };
1359 }
1360
1361 fn requireSteady(self: *const RegionDominance) void {
1362 if (self.phase != .steady) {
1363 @panic("dominance region used outside its steady phase");
1364 }
1365 }
1366 };
1367
1368 comptime {
1369 alloc_phase.capacity.requireAllocatorExactOwnerShape(RegionDominance);
1370 }
1371
1372 fn regionDominancesOrdered(regions: []const RegionDominance) bool {
1373 if (regions.len < 2) return true;
1374 var previous = @intFromPtr(regions[0].regionPointer());
1375 for (regions[1..]) |region_dom| {
1376 const current = @intFromPtr(region_dom.regionPointer());
1377 if (previous >= current) return false;
1378 previous = current;
1379 }
1380 return true;
1381 }
1382
1383 fn initializeRegionDominanceMultiple(
1384 owner: *RegionDominance,
1385 allocator: std.mem.Allocator,
1386 limits: RegionDominance.Limits,
1387 ) !void {
1388 const capacity = owner.capacity;
1389 const layout = try RegionDominanceLayout.derive(limits.block_count);
1390 if (layout.working_bytes != capacity.working_bytes) {
1391 return error.RegionChanged;
1392 }
1393 const bytes = try allocator.alignedAlloc(
1394 u8,
1395 .fromByteUnits(control_storage_alignment),
1396 capacity.working_bytes,
1397 );
1398 errdefer allocator.free(bytes);
1399 const blocks = controlTypedSlice(
1400 *ir.Block,
1401 bytes,
1402 layout.block_offset,
1403 layout.block_count,
1404 );
1405 for (limits.cfg.blockInfos(), blocks) |info, *block| block.* = info.block;
1406 std.debug.assert(blocksOrdered(blocks));
1407 const relations = controlTypedSlice(
1408 bool,
1409 bytes,
1410 layout.relation_offset,
1411 layout.relation_count,
1412 );
1413 const roots = controlTypedSlice(
1414 bool,
1415 bytes,
1416 layout.root_offset,
1417 layout.block_count,
1418 );
1419 const scratch = controlTypedSlice(
1420 bool,
1421 bytes,
1422 layout.scratch_offset,
1423 layout.block_count,
1424 );
1425 computeRelations(limits.cfg, limits.kind, relations, roots, scratch);
1426 owner.storage = .{ .multiple = .{
1427 .bytes = bytes,
1428 .blocks = blocks.ptr,
1429 .relations = relations.ptr,
1430 } };
1431 }
1432
1433 fn containsMultiple(
1434 multiple: RegionDominance.Multiple,
1435 block_count: usize,
1436 dominator: *ir.Block,
1437 block: *ir.Block,
1438 ) bool {
1439 const blocks = multiple.blocks[0..block_count];
1440 const relation_count = std.math.mul(
1441 usize,
1442 block_count,
1443 block_count,
1444 ) catch unreachable;
1445 const relations = multiple.relations[0..relation_count];
1446 std.debug.assert(blocksOrdered(blocks));
1447 const dominator_index = indexOfBlock(blocks, dominator) orelse
1448 return false;
1449 const block_index = indexOfBlock(blocks, block) orelse return false;
1450 return relations[
1451 relationIndex(
1452 block_count,
1453 block_index,
1454 dominator_index,
1455 )
1456 ];
1457 }
1458
1459 const ControlWork = struct {
1460 regions: u64 = 0,
1461 cfg_visits: u64 = 0,
1462 dominance_visits: u64 = 0,
1463 cfg_bytes: u64 = @sizeOf(ControlFlowGraphAnalysis) + 2 * @alignOf(ControlFlowGraphAnalysis),
1464 dominance_bytes: u64 = @sizeOf(BlockDominanceAnalysis) + 2 * @alignOf(BlockDominanceAnalysis),
1465
1466 fn inspect(op: *ir.Operation) !ControlWork {
1467 var counts: ControlWork = .{};
1468 _ = try op.walk(.{ .order = .pre_order }, &counts, inspectOperation);
1469 const ordering = try pass.work.multiply(
1470 16,
1471 try pass.work.multiply(counts.regions, counts.regions),
1472 );
1473 counts.cfg_visits = try pass.work.add(counts.cfg_visits, ordering);
1474 counts.dominance_visits = try pass.work.add(counts.dominance_visits, ordering);
1475 return counts;
1476 }
1477
1478 fn inspectOperation(self: *ControlWork, op: *ir.Operation) !ir.Operation.WalkResult {
1479 self.cfg_visits = try pass.work.add(self.cfg_visits, 1);
1480 self.dominance_visits = try pass.work.add(self.dominance_visits, 1);
1481 for (op.regions.items) |*region| try self.inspectRegion(region);
1482 return .advance;
1483 }
1484
1485 fn inspectRegion(self: *ControlWork, region: *ir.Region) !void {
1486 self.regions = try pass.work.add(self.regions, 1);
1487 const limits = try RegionControlFlow.Limits.inspect(region);
1488 const cfg = try RegionControlFlow.Capacity.derive(limits);
1489 const dom = try RegionDominanceLayout.derive(limits.facts.block_count);
1490 self.cfg_bytes = try pass.work.add(self.cfg_bytes, try pass.work.add(
1491 @sizeOf(RegionControlFlow) + 2 * control_storage_alignment,
1492 cfg.working_bytes,
1493 ));
1494 self.dominance_bytes = try pass.work.add(self.dominance_bytes, try pass.work.add(
1495 @sizeOf(RegionDominance) + 2 * control_storage_alignment,
1496 dom.working_bytes,
1497 ));
1498 var edges: u64 = 0;
1499 var iter = region.getBlocks();
1500 while (iter.next()) |block| edges = try pass.work.add(edges, controlSuccessorCount(block));
1501 try self.includeVisits(limits.facts.block_count, edges);
1502 }
1503
1504 fn includeVisits(self: *ControlWork, blocks: u64, raw_edges: u64) !void {
1505 const scale = try pass.work.add(try pass.work.add(blocks, raw_edges), 1);
1506 self.cfg_visits = try pass.work.add(self.cfg_visits, try pass.work.multiply(
1507 16,
1508 try pass.work.multiply(scale, scale),
1509 ));
1510 const relations = try pass.work.multiply(blocks, blocks);
1511 const rounds = try pass.work.add(relations, 1);
1512 const rows = try pass.work.add(blocks, 1);
1513 const per_round = try pass.work.multiply(rows, scale);
1514 self.dominance_visits = try pass.work.add(self.dominance_visits, try pass.work.multiply(
1515 16,
1516 try pass.work.multiply(rounds, per_round),
1517 ));
1518 }
1519 };
1520
1521 /// CFG surveys, duplicate-edge checks, ordered records and edge construction fit
1522 /// sixteen quadratic visits over blocks plus raw successor occurrences per region.
1523 /// Storage uses the existing owner layouts, including alignment between allocations.
1524 fn cfgWorkBounds(input: pass.work.Input) !pass.work.Bounds {
1525 const counts = ControlWork.inspect(input.operation) catch |err| return switch (err) {
1526 error.CapacityOverflow => error.WorkOverflow,
1527 else => err,
1528 };
1529 return .{
1530 .work = .{
1531 .analysis_computations = 1,
1532 .structural_visits = counts.cfg_visits,
1533 .allocation_capacity = counts.cfg_bytes,
1534 },
1535 .workspace = counts.cfg_bytes,
1536 .retained_storage = counts.cfg_bytes,
1537 };
1538 }
1539
1540 /// The monotone relation matrix can lose at most B*B bits before the final round.
1541 /// Each round covers row scans, predecessor/successor intersections and lookups.
1542 /// CFG computation is its own nested obligation and is not included in this bound.
1543 fn dominanceWorkBounds(input: pass.work.Input) !pass.work.Bounds {
1544 const counts = ControlWork.inspect(input.operation) catch |err| return switch (err) {
1545 error.CapacityOverflow => error.WorkOverflow,
1546 else => err,
1547 };
1548 return .{
1549 .work = .{
1550 .analysis_computations = 1,
1551 .structural_visits = counts.dominance_visits,
1552 .allocation_capacity = counts.dominance_bytes,
1553 },
1554 .workspace = counts.dominance_bytes,
1555 .retained_storage = counts.dominance_bytes,
1556 };
1557 }
1558
1559 const ControlFlowGraphRegistration = pass.Analysis(
1560 ControlFlowGraphAnalysis,
1561 cfg_analysis_name,
1562 &.{ir.interfaces.ControlFlowInterface.id},
1563 computeControlFlowGraphAnalysis,
1564 cleanupControlFlowGraphAnalysis,
1565 .{ .identity = .{ .name = cfg_analysis_name, .version = 1 }, .estimate = cfgWorkBounds },
1566 );
1567
1568 const DominanceRegistration = pass.Analysis(
1569 DominanceAnalysis,
1570 dominance_analysis_name,
1571 &.{ir.interfaces.ControlFlowInterface.id},
1572 computeDominanceAnalysis,
1573 cleanupDominanceAnalysis,
1574 .{
1575 .identity = .{ .name = dominance_analysis_name, .version = 1 },
1576 .estimate = dominanceWorkBounds,
1577 },
1578 );
1579
1580 const PostDominanceRegistration = pass.Analysis(
1581 PostDominanceAnalysis,
1582 post_dominance_analysis_name,
1583 &.{ir.interfaces.ControlFlowInterface.id},
1584 computePostDominanceAnalysis,
1585 cleanupPostDominanceAnalysis,
1586 .{
1587 .identity = .{ .name = post_dominance_analysis_name, .version = 1 },
1588 .estimate = dominanceWorkBounds,
1589 },
1590 );
1591
1592 pub const cfg_analysis_descriptor = ControlFlowGraphRegistration.descriptor;
1593 pub const dominance_analysis_descriptor = DominanceRegistration.descriptor;
1594 pub const post_dominance_analysis_descriptor = PostDominanceRegistration.descriptor;
1595 pub const analysis_ids: []const pass.AnalysisId = &.{
1596 cfg_analysis_descriptor.id,
1597 dominance_analysis_descriptor.id,
1598 post_dominance_analysis_descriptor.id,
1599 };
1600
1601 pub fn getControlFlowGraphAnalysis(ctx: *pass.PassContext, op: *ir.Operation) !*ControlFlowGraphAnalysis {
1602 return ControlFlowGraphRegistration.get(ctx, op);
1603 }
1604
1605 pub fn getDominanceAnalysis(ctx: *pass.PassContext, op: *ir.Operation) !*DominanceAnalysis {
1606 return DominanceRegistration.get(ctx, op);
1607 }
1608
1609 pub fn getPostDominanceAnalysis(ctx: *pass.PassContext, op: *ir.Operation) !*PostDominanceAnalysis {
1610 return PostDominanceRegistration.get(ctx, op);
1611 }
1612
1613 fn computeControlFlowGraphAnalysis(ctx: *pass.PassContext, op: *ir.Operation) anyerror!*ControlFlowGraphAnalysis {
1614 const analysis = try ctx.allocator.create(ControlFlowGraphAnalysis);
1615 errdefer ctx.allocator.destroy(analysis);
1616 analysis.* = try ControlFlowGraphAnalysis.initForOperation(
1617 ctx.allocator,
1618 op,
1619 );
1620 errdefer analysis.deinit(ctx.allocator);
1621 try analysis.activate();
1622 return analysis;
1623 }
1624
1625 fn cleanupControlFlowGraphAnalysis(analysis: *ControlFlowGraphAnalysis, allocator: std.mem.Allocator) void {
1626 analysis.deinit(allocator);
1627 allocator.destroy(analysis);
1628 }
1629
1630 fn computeDominanceAnalysis(ctx: *pass.PassContext, op: *ir.Operation) anyerror!*DominanceAnalysis {
1631 const cfg = try getControlFlowGraphAnalysis(ctx, op);
1632 const analysis = try ctx.allocator.create(DominanceAnalysis);
1633 errdefer ctx.allocator.destroy(analysis);
1634 analysis.* = try DominanceAnalysis.init(
1635 ctx.allocator,
1636 DominanceAnalysis.Limits.inspect(cfg, .forward),
1637 );
1638 errdefer analysis.deinit(ctx.allocator);
1639 try analysis.activate();
1640 return analysis;
1641 }
1642
1643 fn cleanupDominanceAnalysis(analysis: *DominanceAnalysis, allocator: std.mem.Allocator) void {
1644 analysis.deinit(allocator);
1645 allocator.destroy(analysis);
1646 }
1647
1648 fn computePostDominanceAnalysis(ctx: *pass.PassContext, op: *ir.Operation) anyerror!*PostDominanceAnalysis {
1649 const cfg = try getControlFlowGraphAnalysis(ctx, op);
1650 const analysis = try ctx.allocator.create(PostDominanceAnalysis);
1651 errdefer ctx.allocator.destroy(analysis);
1652 analysis.* = try PostDominanceAnalysis.init(
1653 ctx.allocator,
1654 PostDominanceAnalysis.Limits.inspect(cfg, .reverse),
1655 );
1656 errdefer analysis.deinit(ctx.allocator);
1657 try analysis.activate();
1658 return analysis;
1659 }
1660
1661 fn cleanupPostDominanceAnalysis(analysis: *PostDominanceAnalysis, allocator: std.mem.Allocator) void {
1662 analysis.deinit(allocator);
1663 allocator.destroy(analysis);
1664 }
1665
1666 fn controlSuccessorCount(block: *ir.Block) usize {
1667 const term_any = block.getTerminator() orelse return 0;
1668 const term: *ir.Operation = @ptrCast(@alignCast(term_any));
1669 if (term.interface(ir.interfaces.ControlFlowInterface)) |iface| {
1670 return iface.call(.getSuccessorCount, .{});
1671 }
1672 return term.successors.items.len;
1673 }
1674
1675 fn controlSuccessorAt(block: *ir.Block, index: usize) ?*ir.Block {
1676 const term_any = block.getTerminator() orelse return null;
1677 const term: *ir.Operation = @ptrCast(@alignCast(term_any));
1678 if (term.interface(ir.interfaces.ControlFlowInterface)) |iface| {
1679 return iface.call(.getSuccessor, .{index});
1680 }
1681 if (index >= term.successors.items.len) return null;
1682 return term.successors.items[index];
1683 }
1684
1685 fn controlSuccessorAppeared(block: *ir.Block, index: usize, successor: *ir.Block) bool {
1686 for (0..index) |prior_index| {
1687 if (controlSuccessorAt(block, prior_index) == successor) return true;
1688 }
1689 return false;
1690 }
1691
1692 fn initializeRegionControlFlowMultiple(
1693 owner: *RegionControlFlow,
1694 allocator: std.mem.Allocator,
1695 limits: RegionControlFlow.Limits,
1696 ) !void {
1697 const capacity = owner.capacity;
1698 const layout = try RegionControlFlowLayout.derive(limits.facts);
1699 if (layout.working_bytes != capacity.working_bytes) {
1700 return error.RegionChanged;
1701 }
1702 const bytes = try allocator.alignedAlloc(
1703 u8,
1704 .fromByteUnits(control_storage_alignment),
1705 capacity.working_bytes,
1706 );
1707 errdefer allocator.free(bytes);
1708 const blocks = controlTypedSlice(
1709 RegionControlFlow.BlockInfo,
1710 bytes,
1711 layout.block_offset,
1712 layout.facts.block_count,
1713 );
1714 try initializeControlBlocks(owner.region, blocks);
1715 try initializeControlEdges(owner.region, layout, bytes, blocks);
1716 owner.storage = .{ .multiple = .{
1717 .bytes = bytes,
1718 .blocks = blocks,
1719 } };
1720 }
1721
1722 fn countRegionSuccessors(block: *ir.Block, region: *ir.Region) !usize {
1723 var count: usize = 0;
1724 for (0..controlSuccessorCount(block)) |index| {
1725 const successor = controlSuccessorAt(block, index) orelse continue;
1726 if (successor.getParentRegion() != region) continue;
1727 if (controlSuccessorAppeared(block, index, successor)) continue;
1728 count = std.math.add(usize, count, 1) catch return error.CapacityOverflow;
1729 }
1730 return count;
1731 }
1732
1733 fn writeRegionSuccessors(
1734 block: *ir.Block,
1735 region: *ir.Region,
1736 output: []*ir.Block,
1737 ) !usize {
1738 var count: usize = 0;
1739 for (0..controlSuccessorCount(block)) |index| {
1740 const successor = controlSuccessorAt(block, index) orelse continue;
1741 if (successor.getParentRegion() != region) continue;
1742 if (controlSuccessorAppeared(block, index, successor)) continue;
1743 if (count == output.len) return error.RegionChanged;
1744 output[count] = successor;
1745 count += 1;
1746 }
1747 return count;
1748 }
1749
1750 fn initializeControlBlocks(
1751 region: *ir.Region,
1752 blocks: []RegionControlFlow.BlockInfo,
1753 ) !void {
1754 var iter = region.getBlocks();
1755 var index: usize = 0;
1756 while (iter.next()) |block| {
1757 if (index == blocks.len) return error.RegionChanged;
1758 blocks[index] = .{
1759 .block = block,
1760 .successors = &.{},
1761 .predecessors = &.{},
1762 };
1763 index += 1;
1764 }
1765 if (index != blocks.len) return error.RegionChanged;
1766 std.sort.heap(RegionControlFlow.BlockInfo, blocks, {}, blockInfoAddressLessThan);
1767 std.debug.assert(blockInfosOrdered(blocks));
1768 }
1769
1770 fn initializeControlEdges(
1771 region: *ir.Region,
1772 layout: RegionControlFlowLayout,
1773 bytes: []align(control_storage_alignment) u8,
1774 blocks: []RegionControlFlow.BlockInfo,
1775 ) !void {
1776 const successors = controlTypedSlice(
1777 *ir.Block,
1778 bytes,
1779 layout.successor_offset,
1780 layout.facts.edge_count,
1781 );
1782 const predecessors = controlTypedSlice(
1783 *ir.Block,
1784 bytes,
1785 layout.predecessor_offset,
1786 layout.facts.edge_count,
1787 );
1788 const cursors = controlTypedSlice(
1789 usize,
1790 bytes,
1791 layout.cursor_offset,
1792 layout.facts.block_count,
1793 );
1794 try initializeControlSuccessors(region, blocks, successors);
1795 try initializeControlPredecessors(region, blocks, predecessors, cursors);
1796 }
1797
1798 fn initializeControlSuccessors(
1799 region: *ir.Region,
1800 blocks: []RegionControlFlow.BlockInfo,
1801 storage: []*ir.Block,
1802 ) !void {
1803 var edge_count: usize = 0;
1804 var iter = region.getBlocks();
1805 while (iter.next()) |block| {
1806 const info_index = indexOfBlockInfo(blocks, block) orelse
1807 return error.RegionChanged;
1808 const count = try writeRegionSuccessors(block, region, storage[edge_count..]);
1809 blocks[info_index].successors = storage[edge_count..][0..count];
1810 edge_count += count;
1811 }
1812 if (edge_count != storage.len) return error.RegionChanged;
1813 }
1814
1815 fn initializeControlPredecessors(
1816 region: *ir.Region,
1817 blocks: []RegionControlFlow.BlockInfo,
1818 storage: []*ir.Block,
1819 cursors: []usize,
1820 ) !void {
1821 @memset(cursors, 0);
1822 for (blocks) |info| {
1823 for (info.successors) |successor| {
1824 const index = indexOfBlockInfo(blocks, successor) orelse
1825 return error.RegionChanged;
1826 cursors[index] = std.math.add(usize, cursors[index], 1) catch
1827 return error.CapacityOverflow;
1828 }
1829 }
1830 try assignPredecessorSlices(blocks, storage, cursors);
1831 @memset(cursors, 0);
1832 try fillControlPredecessors(region, blocks, cursors);
1833 }
1834
1835 fn assignPredecessorSlices(
1836 blocks: []RegionControlFlow.BlockInfo,
1837 storage: []*ir.Block,
1838 counts: []const usize,
1839 ) !void {
1840 var offset: usize = 0;
1841 for (blocks, counts) |*info, count| {
1842 const end = std.math.add(usize, offset, count) catch
1843 return error.CapacityOverflow;
1844 if (end > storage.len) return error.RegionChanged;
1845 info.predecessors = storage[offset..end];
1846 offset = end;
1847 }
1848 if (offset != storage.len) return error.RegionChanged;
1849 }
1850
1851 fn fillControlPredecessors(
1852 region: *ir.Region,
1853 blocks: []RegionControlFlow.BlockInfo,
1854 cursors: []usize,
1855 ) !void {
1856 var iter = region.getBlocks();
1857 while (iter.next()) |block| {
1858 const source_index = indexOfBlockInfo(blocks, block) orelse
1859 return error.RegionChanged;
1860 for (blocks[source_index].successors) |successor| {
1861 const target_index = indexOfBlockInfo(blocks, successor) orelse
1862 return error.RegionChanged;
1863 const cursor = cursors[target_index];
1864 if (cursor == blocks[target_index].predecessors.len) {
1865 return error.RegionChanged;
1866 }
1867 @constCast(blocks[target_index].predecessors)[cursor] = block;
1868 cursors[target_index] += 1;
1869 }
1870 }
1871 for (blocks, cursors) |info, cursor| {
1872 if (cursor != info.predecessors.len) return error.RegionChanged;
1873 }
1874 }
1875
1876 fn controlStorageBytes(comptime T: type, count: usize) !usize {
1877 return std.math.mul(usize, count, @sizeOf(T)) catch
1878 error.CapacityOverflow;
1879 }
1880
1881 fn placeControlStorage(byte_count: usize, alignment: usize, cursor: *usize) !usize {
1882 std.debug.assert(std.math.isPowerOfTwo(alignment));
1883 const padded = std.math.add(usize, cursor.*, alignment - 1) catch
1884 return error.CapacityOverflow;
1885 const offset = padded & ~(alignment - 1);
1886 cursor.* = std.math.add(usize, offset, byte_count) catch
1887 return error.CapacityOverflow;
1888 return offset;
1889 }
1890
1891 fn controlTypedSlice(
1892 comptime T: type,
1893 bytes: []align(control_storage_alignment) u8,
1894 offset: usize,
1895 count: usize,
1896 ) []T {
1897 if (count == 0) return &.{};
1898 const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
1899 const region: []align(@alignOf(T)) u8 = @alignCast(
1900 bytes[offset..][0..byte_count],
1901 );
1902 return std.mem.bytesAsSlice(T, region);
1903 }
1904
1905 fn blockInfoAddressLessThan(_: void, lhs: RegionControlFlow.BlockInfo, rhs: RegionControlFlow.BlockInfo) bool {
1906 return @intFromPtr(lhs.block) < @intFromPtr(rhs.block);
1907 }
1908
1909 fn blockInfosOrdered(blocks: []const RegionControlFlow.BlockInfo) bool {
1910 if (blocks.len < 2) return true;
1911 for (blocks[1..], blocks[0 .. blocks.len - 1]) |current, previous| {
1912 if (@intFromPtr(previous.block) >= @intFromPtr(current.block)) return false;
1913 }
1914 return true;
1915 }
1916
1917 fn blocksOrdered(blocks: []const *ir.Block) bool {
1918 if (blocks.len < 2) return true;
1919 for (blocks[1..], blocks[0 .. blocks.len - 1]) |current, previous| {
1920 if (@intFromPtr(previous) >= @intFromPtr(current)) return false;
1921 }
1922 return true;
1923 }
1924
1925 fn indexOfBlockInfo(blocks: []const RegionControlFlow.BlockInfo, block: *ir.Block) ?usize {
1926 var low: usize = 0;
1927 var high = blocks.len;
1928 const address = @intFromPtr(block);
1929 while (low < high) {
1930 std.debug.assert(high <= blocks.len);
1931 const middle = low + (high - low) / 2;
1932 std.debug.assert(middle < blocks.len);
1933 const middle_address = @intFromPtr(blocks[middle].block);
1934 if (middle_address == address) return middle;
1935 if (middle_address < address) {
1936 low = middle + 1;
1937 } else {
1938 high = middle;
1939 }
1940 }
1941 return null;
1942 }
1943
1944 fn indexOfBlock(blocks: []const *ir.Block, block: *ir.Block) ?usize {
1945 var low: usize = 0;
1946 var high = blocks.len;
1947 const address = @intFromPtr(block);
1948 while (low < high) {
1949 std.debug.assert(high <= blocks.len);
1950 const middle = low + (high - low) / 2;
1951 std.debug.assert(middle < blocks.len);
1952 const middle_address = @intFromPtr(blocks[middle]);
1953 if (middle_address == address) return middle;
1954 if (middle_address < address) {
1955 low = middle + 1;
1956 } else {
1957 high = middle;
1958 }
1959 }
1960 return null;
1961 }
1962
1963 fn relationIndex(block_count: usize, block_index: usize, dominator_index: usize) usize {
1964 return block_index * block_count + dominator_index;
1965 }
1966
1967 fn computeRelations(
1968 cfg: *const RegionControlFlow,
1969 kind: DominanceKind,
1970 relations: []bool,
1971 roots: []bool,
1972 scratch: []bool,
1973 ) void {
1974 const blocks = cfg.blockInfos();
1975 const block_count = blocks.len;
1976 if (block_count == 0) return;
1977 const relation_count = std.math.mul(
1978 usize,
1979 block_count,
1980 block_count,
1981 ) catch unreachable;
1982 std.debug.assert(relations.len == relation_count);
1983 std.debug.assert(roots.len == block_count);
1984 std.debug.assert(scratch.len == block_count);
1985
1986 computeRoots(cfg, kind, roots);
1987
1988 for (0..block_count) |block_index| {
1989 const row = relations[block_index * block_count ..][0..block_count];
1990 if (roots[block_index]) {
1991 @memset(row, false);
1992 row[block_index] = true;
1993 } else {
1994 @memset(row, true);
1995 }
1996 }
1997
1998 var changed = true;
1999 while (changed) {
2000 changed = false;
2001 for (0..block_count) |block_index| {
2002 if (roots[block_index]) continue;
2003
2004 const inputs = switch (kind) {
2005 .forward => blocks[block_index].predecessors,
2006 .reverse => blocks[block_index].successors,
2007 };
2008
2009 @memset(scratch, true);
2010 for (inputs) |input| {
2011 const input_index = cfg.indexOf(input) orelse continue;
2012 const input_row = relations[input_index * block_count ..][0..block_count];
2013 for (scratch, input_row) |*slot, input_bit| {
2014 slot.* = slot.* and input_bit;
2015 }
2016 }
2017 scratch[block_index] = true;
2018
2019 const row = relations[block_index * block_count ..][0..block_count];
2020 if (!std.mem.eql(bool, row, scratch)) {
2021 @memcpy(row, scratch);
2022 changed = true;
2023 }
2024 }
2025 }
2026 }
2027
2028 fn computeRoots(cfg: *const RegionControlFlow, kind: DominanceKind, roots: []bool) void {
2029 const blocks = cfg.blockInfos();
2030 std.debug.assert(roots.len == blocks.len);
2031 @memset(roots, false);
2032
2033 switch (kind) {
2034 .forward => {
2035 if (cfg.entryBlock()) |entry| {
2036 if (cfg.indexOf(entry)) |entry_index| roots[entry_index] = true;
2037 }
2038 for (blocks, 0..) |info, index| {
2039 if (info.predecessors.len == 0) roots[index] = true;
2040 }
2041 },
2042 .reverse => {
2043 var has_exit = false;
2044 for (blocks, 0..) |info, index| {
2045 if (info.successors.len == 0) {
2046 roots[index] = true;
2047 has_exit = true;
2048 }
2049 }
2050 if (!has_exit) {
2051 @memset(roots, true);
2052 }
2053 },
2054 }
2055 }
2056
2057 fn operationPrecedesOrSame(first: *ir.Operation, second: *ir.Operation) bool {
2058 return first == second or first.isBeforeInBlock(second);
2059 }
2060
2061 fn buildDiamond(ctx: *ir.Context) !struct {
2062 module: @import("../dialects/fixture/root.zig").TestDialect.ModuleOp,
2063 entry: *ir.Block,
2064 then_block: *ir.Block,
2065 else_block: *ir.Block,
2066 merge: *ir.Block,
2067 unreachable_block: *ir.Block,
2068 entry_term: *ir.Operation,
2069 then_value: *ir.Operation,
2070 then_term: *ir.Operation,
2071 else_term: *ir.Operation,
2072 } {
2073 const test_dialect = @import("../dialects/fixture/root.zig");
2074
2075 try test_dialect.registerTestDialect(ctx);
2076 _ = try ctx.registerOperation("test.cond_br", .{});
2077 _ = try ctx.registerOperation("test.value", .{});
2078 _ = try ctx.registerOperation("test.return", .{});
2079
2080 const loc = ir.Location.getUnknown();
2081 const module = try test_dialect.TestDialect.ModuleOp.create(ctx, loc);
2082 const region = module.getBody();
2083 const entry = module.getBodyBlock();
2084 const then_block = try region.addBlock();
2085 const else_block = try region.addBlock();
2086 const merge = try region.addBlock();
2087 const unreachable_block = try region.addBlock();
2088
2089 var builder = ir.OperationBuilder.init(ctx);
2090
2091 var entry_state = ir.Operation.State.init("test.cond_br", loc);
2092 entry_state.addSuccessors(&.{ then_block, else_block });
2093 const entry_term = try builder.create(entry_state);
2094 try entry.addOperation(entry_term);
2095
2096 const i64_type = try test_dialect.TestDialect.getI64Type(ctx);
2097 var then_value_state = ir.Operation.State.init("test.value", loc);
2098 then_value_state.addTypes(&.{i64_type});
2099 const then_value = try builder.create(then_value_state);
2100 try then_block.addOperation(then_value);
2101
2102 var then_state = ir.Operation.State.init(test_dialect.TestDialect.BranchOp.operation_name, loc);
2103 then_state.addSuccessors(&.{merge});
2104 const then_term = try builder.create(then_state);
2105 try then_block.addOperation(then_term);
2106
2107 var else_state = ir.Operation.State.init(test_dialect.TestDialect.BranchOp.operation_name, loc);
2108 else_state.addSuccessors(&.{merge});
2109 const else_term = try builder.create(else_state);
2110 try else_block.addOperation(else_term);
2111
2112 const merge_term = try builder.create(ir.Operation.State.init("test.return", loc));
2113 try merge.addOperation(merge_term);
2114
2115 const unreachable_term = try builder.create(ir.Operation.State.init("test.return", loc));
2116 try unreachable_block.addOperation(unreachable_term);
2117
2118 return .{
2119 .module = module,
2120 .entry = entry,
2121 .then_block = then_block,
2122 .else_block = else_block,
2123 .merge = merge,
2124 .unreachable_block = unreachable_block,
2125 .entry_term = entry_term,
2126 .then_value = then_value,
2127 .then_term = then_term,
2128 .else_term = else_term,
2129 };
2130 }
2131
2132 const NestedControlFixture = struct {
2133 root: @import("../dialects/fixture/root.zig").TestDialect.ModuleOp,
2134 first: @import("../dialects/fixture/root.zig").TestDialect.ModuleOp,
2135 second: @import("../dialects/fixture/root.zig").TestDialect.ModuleOp,
2136 first_branch: *ir.Operation,
2137 };
2138
2139 fn buildNestedControlFixture(ctx: *ir.Context) !NestedControlFixture {
2140 const test_dialect = @import("../dialects/fixture/root.zig");
2141 const loc = ir.Location.getUnknown();
2142 const root = try test_dialect.TestDialect.ModuleOp.create(ctx, loc);
2143 const lhs = try test_dialect.TestDialect.ModuleOp.create(ctx, loc);
2144 const rhs = try test_dialect.TestDialect.ModuleOp.create(ctx, loc);
2145 const first = if (@intFromPtr(lhs.getBody()) > @intFromPtr(rhs.getBody()))
2146 lhs
2147 else
2148 rhs;
2149 const second = if (first.op == lhs.op) rhs else lhs;
2150 try root.getBodyBlock().addOperation(first.op);
2151 try root.getBodyBlock().addOperation(second.op);
2152
2153 var builder = ir.OperationBuilder.init(ctx);
2154 var first_state = ir.Operation.State.init(
2155 test_dialect.TestDialect.BranchOp.operation_name,
2156 loc,
2157 );
2158 first_state.addSuccessors(&.{first.getBodyBlock()});
2159 const first_branch = try builder.create(first_state);
2160 try first.getBodyBlock().addOperation(first_branch);
2161
2162 var second_state = ir.Operation.State.init(
2163 test_dialect.TestDialect.BranchOp.operation_name,
2164 loc,
2165 );
2166 second_state.addSuccessors(&.{second.getBodyBlock()});
2167 const second_branch = try builder.create(second_state);
2168 try second.getBodyBlock().addOperation(second_branch);
2169
2170 return .{
2171 .root = root,
2172 .first = first,
2173 .second = second,
2174 .first_branch = first_branch,
2175 };
2176 }
2177
2178 test "ControlFlowGraphAnalysis records region edges" {
2179 const testing = std.testing;
2180 const allocator = testing.allocator;
2181
2182 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2183 defer ctx.deinit(allocator);
2184 const fixture = try buildDiamond(&ctx);
2185
2186 var cache = pass.AnalysisCache.init(allocator, null);
2187 defer cache.deinit();
2188
2189 var pass_ctx = pass.PassContext.init(fixture.module.op, &ctx, allocator, &cache);
2190 defer pass_ctx.deinit();
2191
2192 const cfg = try getControlFlowGraphAnalysis(&pass_ctx, fixture.module.op);
2193 const region_cfg = cfg.getRegion(fixture.module.getBody()) orelse return error.TestExpectedRegionCfg;
2194
2195 try testing.expectEqual(@as(usize, 5), region_cfg.blockCount());
2196 try testing.expect(region_cfg.hasEdge(fixture.entry, fixture.then_block));
2197 try testing.expect(region_cfg.hasEdge(fixture.entry, fixture.else_block));
2198 try testing.expect(region_cfg.hasEdge(fixture.then_block, fixture.merge));
2199 try testing.expect(region_cfg.hasEdge(fixture.else_block, fixture.merge));
2200 try testing.expect(!region_cfg.hasEdge(fixture.merge, fixture.unreachable_block));
2201
2202 const entry_succs = region_cfg.successors(fixture.entry) orelse return error.TestExpectedSuccessors;
2203 try testing.expectEqual(@as(usize, 2), entry_succs.len);
2204 try testing.expect(entry_succs[0] == fixture.then_block);
2205 try testing.expect(entry_succs[1] == fixture.else_block);
2206
2207 const merge_preds = region_cfg.predecessors(fixture.merge) orelse return error.TestExpectedPredecessors;
2208 try testing.expectEqual(@as(usize, 2), merge_preds.len);
2209 try testing.expect(merge_preds[0] == fixture.then_block);
2210 try testing.expect(merge_preds[1] == fixture.else_block);
2211 }
2212
2213 test "control-flow graph analysis derives exact region owner capacity" {
2214 comptime {
2215 @stardustClaim(
2216 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_capacity_capacity_model"),
2217 null,
2218 null,
2219 null,
2220 null,
2221 null,
2222 null,
2223 );
2224 }
2225 comptime {
2226 @stardustClaim(
2227 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_capacity_overload"),
2228 null,
2229 null,
2230 null,
2231 null,
2232 null,
2233 null,
2234 );
2235 }
2236
2237 const testing = std.testing;
2238 const allocator = testing.allocator;
2239
2240 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2241 defer ctx.deinit(allocator);
2242 const fixture = try buildNestedControlFixture(&ctx);
2243 const limits = try ControlFlowGraphAnalysis.Limits.inspect(fixture.root.op);
2244 try testing.expectEqual(@as(usize, 3), limits.region_count);
2245 const capacity = try ControlFlowGraphAnalysis.Capacity.derive(limits);
2246 try testing.expectEqual(@as(usize, 3), capacity.region_count);
2247 try testing.expectEqual(
2248 3 * @sizeOf(RegionControlFlow),
2249 capacity.storage_bytes,
2250 );
2251
2252 var overflowing = limits;
2253 overflowing.region_count = std.math.maxInt(usize);
2254 try testing.expectError(
2255 error.CapacityOverflow,
2256 ControlFlowGraphAnalysis.Capacity.derive(overflowing),
2257 );
2258
2259 const stale_root = try @import("../dialects/fixture/root.zig").TestDialect.ModuleOp.create(
2260 &ctx,
2261 ir.Location.getUnknown(),
2262 );
2263 const stale_limits = try ControlFlowGraphAnalysis.Limits.inspect(
2264 stale_root.op,
2265 );
2266 const nested = try @import("../dialects/fixture/root.zig").TestDialect.ModuleOp.create(
2267 &ctx,
2268 ir.Location.getUnknown(),
2269 );
2270 try stale_root.getBodyBlock().addOperation(nested.op);
2271 try testing.expectError(
2272 error.OperationChanged,
2273 ControlFlowGraphAnalysis.init(allocator, stale_limits),
2274 );
2275 }
2276
2277 test "control-flow graph analysis acquires one exact region owner array" {
2278 comptime {
2279 @stardustClaim(
2280 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_acquisition"),
2281 null,
2282 null,
2283 null,
2284 null,
2285 null,
2286 null,
2287 );
2288 }
2289
2290 const testing = std.testing;
2291 const allocator = testing.allocator;
2292
2293 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2294 defer ctx.deinit(allocator);
2295 const fixture = try buildNestedControlFixture(&ctx);
2296 const limits = try ControlFlowGraphAnalysis.Limits.inspect(fixture.root.op);
2297 const capacity = try ControlFlowGraphAnalysis.Capacity.derive(limits);
2298 var counting = std.testing.FailingAllocator.init(allocator, .{});
2299 var cfg = try ControlFlowGraphAnalysis.initForOperation(
2300 counting.allocator(),
2301 fixture.root.op,
2302 );
2303 defer cfg.deinit(counting.allocator());
2304 try testing.expectEqual(@as(usize, 1), counting.alloc_index);
2305 try testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);
2306 try cfg.activate();
2307 try testing.expectEqual(@as(usize, 3), cfg.regionCount());
2308 try testing.expect(regionControlFlowsOrdered(cfg.regionSlice()));
2309 try testing.expect(cfg.getRegion(fixture.root.getBody()) != null);
2310 try testing.expect(cfg.getRegion(fixture.first.getBody()) != null);
2311 try testing.expect(cfg.getRegion(fixture.second.getBody()) != null);
2312 try testing.expectEqual(
2313 @as(usize, 1),
2314 cfg.successors(fixture.first.getBodyBlock()).?.len,
2315 );
2316 try testing.expect(
2317 cfg.successors(fixture.first.getBodyBlock()).?[0] ==
2318 fixture.first.getBodyBlock(),
2319 );
2320
2321 var empty_counting = std.testing.FailingAllocator.init(allocator, .{});
2322 var empty_cfg = try ControlFlowGraphAnalysis.initForOperation(
2323 empty_counting.allocator(),
2324 fixture.first_branch,
2325 );
2326 defer empty_cfg.deinit(empty_counting.allocator());
2327 try testing.expectEqual(@as(usize, 0), empty_counting.alloc_index);
2328 try empty_cfg.activate();
2329 try testing.expectEqual(@as(usize, 0), empty_cfg.regionCount());
2330
2331 const test_dialect = @import("../dialects/fixture/root.zig");
2332 const large_root = try test_dialect.TestDialect.ModuleOp.create(
2333 &ctx,
2334 ir.Location.getUnknown(),
2335 );
2336 var large_children: [control_flow_graph_gather_capacity]*ir.Operation =
2337 undefined;
2338 var child_count: usize = 0;
2339 for (0..control_flow_graph_gather_capacity) |_| {
2340 const child = try test_dialect.TestDialect.ModuleOp.create(
2341 &ctx,
2342 ir.Location.getUnknown(),
2343 );
2344 var insert = child_count;
2345 while (insert > 0) {
2346 const previous = &large_children[insert - 1].regions.items[0];
2347 if (@intFromPtr(previous) > @intFromPtr(child.getBody())) break;
2348 large_children[insert] = large_children[insert - 1];
2349 insert -= 1;
2350 }
2351 large_children[insert] = child.op;
2352 child_count += 1;
2353 }
2354 for (large_children) |child| {
2355 try large_root.getBodyBlock().addOperation(child);
2356 }
2357 var large_counting = std.testing.FailingAllocator.init(allocator, .{});
2358 var large_cfg = try ControlFlowGraphAnalysis.initForOperation(
2359 large_counting.allocator(),
2360 large_root.op,
2361 );
2362 defer large_cfg.deinit(large_counting.allocator());
2363 try testing.expectEqual(@as(usize, 1), large_counting.alloc_index);
2364 try large_cfg.activate();
2365 try testing.expectEqual(
2366 control_flow_graph_gather_capacity + 1,
2367 large_cfg.regionCount(),
2368 );
2369 }
2370
2371 test "control-flow graph analysis queries remain allocation free after sealing" {
2372 comptime {
2373 @stardustClaim(
2374 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_sealed_transitive_risk"),
2375 null,
2376 null,
2377 null,
2378 null,
2379 null,
2380 null,
2381 );
2382 }
2383 comptime {
2384 @stardustClaim(
2385 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_sealed_foreign_risk"),
2386 null,
2387 null,
2388 null,
2389 null,
2390 null,
2391 null,
2392 );
2393 }
2394
2395 const testing = std.testing;
2396 const allocator = testing.allocator;
2397
2398 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2399 defer ctx.deinit(allocator);
2400 const fixture = try buildNestedControlFixture(&ctx);
2401 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
2402 var maybe_cfg: ?ControlFlowGraphAnalysis = null;
2403 defer {
2404 if (phase_allocator.phase() == .initialization) {
2405 phase_allocator.abortInitialization();
2406 }
2407 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
2408 if (maybe_cfg) |*cfg| {
2409 if (cfg.phase != .teardown) {
2410 cfg.deinit(phase_allocator.teardownAllocator());
2411 }
2412 }
2413 phase_allocator.deinit();
2414 }
2415 maybe_cfg = try ControlFlowGraphAnalysis.initForOperation(
2416 phase_allocator.initializationAllocator(),
2417 fixture.root.op,
2418 );
2419 const cfg = &maybe_cfg.?;
2420 phase_allocator.seal();
2421 try cfg.activate();
2422
2423 try testing.expectEqual(@as(usize, 3), cfg.regionCount());
2424 try testing.expect(cfg.getRegion(fixture.first.getBody()) != null);
2425 try testing.expectEqual(
2426 @as(usize, 1),
2427 cfg.predecessors(fixture.first.getBodyBlock()).?.len,
2428 );
2429 try testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
2430 }
2431
2432 const ControlFlowGraphAnalysisFailureHarness = struct {
2433 fn run(allocator: std.mem.Allocator, root: *ir.Operation) !void {
2434 var cfg = try ControlFlowGraphAnalysis.initForOperation(
2435 allocator,
2436 root,
2437 );
2438 defer cfg.deinit(allocator);
2439 try cfg.activate();
2440 try std.testing.expectEqual(@as(usize, 3), cfg.regionCount());
2441 }
2442 };
2443
2444 test "ControlFlowGraphAnalysis build retries every allocation failure" {
2445 comptime {
2446 @stardustClaim(
2447 @import("alloc_phase").capacity.witness(ControlFlowGraphAnalysis, "choir_cfg_analysis_oom"),
2448 null,
2449 null,
2450 null,
2451 null,
2452 null,
2453 null,
2454 );
2455 }
2456
2457 const testing = std.testing;
2458 const allocator = testing.allocator;
2459
2460 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2461 defer ctx.deinit(allocator);
2462 const fixture = try buildNestedControlFixture(&ctx);
2463 try testing.checkAllAllocationFailures(
2464 allocator,
2465 ControlFlowGraphAnalysisFailureHarness.run,
2466 .{fixture.root.op},
2467 );
2468 try ControlFlowGraphAnalysisFailureHarness.run(
2469 allocator,
2470 fixture.root.op,
2471 );
2472 }
2473
2474 test "RegionControlFlow orders exact block lookup" {
2475 const testing = std.testing;
2476 const allocator = testing.allocator;
2477
2478 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2479 defer ctx.deinit(allocator);
2480 const fixture = try buildDiamond(&ctx);
2481
2482 var region_cfg = try RegionControlFlow.initForRegion(
2483 allocator,
2484 fixture.module.getBody(),
2485 );
2486 defer region_cfg.deinit(allocator);
2487 try region_cfg.activate();
2488
2489 const blocks = region_cfg.blockInfos();
2490 try testing.expectEqual(@as(usize, 5), blocks.len);
2491 for (blocks, 0..) |info, index| {
2492 try testing.expectEqual(index, region_cfg.indexOf(info.block).?);
2493 if (index > 0) {
2494 try testing.expect(@intFromPtr(blocks[index - 1].block) < @intFromPtr(info.block));
2495 }
2496 }
2497
2498 const test_dialect = @import("../dialects/fixture/root.zig");
2499 const foreign = try test_dialect.TestDialect.ModuleOp.create(&ctx, ir.Location.getUnknown());
2500 try testing.expect(region_cfg.indexOf(foreign.getBodyBlock()) == null);
2501 }
2502
2503 test "region control-flow capacity matches an independent aligned byte model" {
2504 comptime {
2505 @stardustClaim(
2506 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_capacity_capacity_model"),
2507 null,
2508 null,
2509 null,
2510 null,
2511 null,
2512 null,
2513 );
2514 }
2515 comptime {
2516 @stardustClaim(
2517 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_capacity_overload"),
2518 null,
2519 null,
2520 null,
2521 null,
2522 null,
2523 null,
2524 );
2525 }
2526
2527 const testing = std.testing;
2528 const allocator = testing.allocator;
2529
2530 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2531 defer ctx.deinit(allocator);
2532 const fixture = try buildDiamond(&ctx);
2533 const limits = try RegionControlFlow.Limits.inspect(fixture.module.getBody());
2534 try testing.expectEqual(@as(usize, 5), limits.facts.block_count);
2535 try testing.expectEqual(@as(usize, 4), limits.facts.edge_count);
2536
2537 const capacity = try RegionControlFlow.Capacity.derive(limits);
2538 var expected: usize = 0;
2539 expected = std.mem.alignForward(
2540 usize,
2541 expected,
2542 @alignOf(RegionControlFlow.BlockInfo),
2543 );
2544 expected = try std.math.add(
2545 usize,
2546 expected,
2547 try std.math.mul(usize, 5, @sizeOf(RegionControlFlow.BlockInfo)),
2548 );
2549 inline for (.{ *ir.Block, *ir.Block, usize }, .{ 4, 4, 5 }) |T, count| {
2550 expected = std.mem.alignForward(usize, expected, @alignOf(T));
2551 expected = try std.math.add(
2552 usize,
2553 expected,
2554 try std.math.mul(usize, count, @sizeOf(T)),
2555 );
2556 }
2557 try testing.expectEqual(expected, capacity.working_bytes);
2558
2559 var singleton = limits;
2560 singleton.facts = .{ .block_count = 1, .edge_count = 1 };
2561 try testing.expectEqual(
2562 @as(usize, 0),
2563 (try RegionControlFlow.Capacity.derive(singleton)).working_bytes,
2564 );
2565 var overflowing = limits;
2566 overflowing.facts.edge_count = std.math.maxInt(usize);
2567 try testing.expectError(
2568 error.CapacityOverflow,
2569 RegionControlFlow.Capacity.derive(overflowing),
2570 );
2571 }
2572
2573 test "region control-flow acquires at most one exact backing region" {
2574 comptime {
2575 @stardustClaim(
2576 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_acquisition"),
2577 null,
2578 null,
2579 null,
2580 null,
2581 null,
2582 null,
2583 );
2584 }
2585
2586 const testing = std.testing;
2587 const allocator = testing.allocator;
2588
2589 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2590 defer ctx.deinit(allocator);
2591 const fixture = try buildDiamond(&ctx);
2592 const limits = try RegionControlFlow.Limits.inspect(fixture.module.getBody());
2593 const capacity = try RegionControlFlow.Capacity.derive(limits);
2594 var counting = std.testing.FailingAllocator.init(allocator, .{});
2595 var region_cfg = try RegionControlFlow.init(counting.allocator(), limits);
2596 defer region_cfg.deinit(counting.allocator());
2597 try testing.expectEqual(@as(usize, 1), counting.alloc_index);
2598 try testing.expectEqual(capacity.working_bytes, counting.allocated_bytes);
2599 try region_cfg.activate();
2600 try testing.expectEqual(@as(usize, 5), region_cfg.blockCount());
2601
2602 var empty_region = ir.Region.init(allocator);
2603 defer empty_region.deinit();
2604 const empty_limits = try RegionControlFlow.Limits.inspect(&empty_region);
2605 var empty_counting = std.testing.FailingAllocator.init(allocator, .{});
2606 var empty_cfg = try RegionControlFlow.init(
2607 empty_counting.allocator(),
2608 empty_limits,
2609 );
2610 defer empty_cfg.deinit(empty_counting.allocator());
2611 try testing.expectEqual(@as(usize, 0), empty_counting.alloc_index);
2612 try empty_cfg.activate();
2613 try testing.expectEqual(@as(usize, 0), empty_cfg.blockCount());
2614
2615 var changed_region = ir.Region.init(allocator);
2616 defer changed_region.deinit();
2617 const stale_limits = try RegionControlFlow.Limits.inspect(&changed_region);
2618 _ = try changed_region.addBlock();
2619 try testing.expectError(
2620 error.RegionChanged,
2621 RegionControlFlow.init(allocator, stale_limits),
2622 );
2623
2624 const test_dialect = @import("../dialects/fixture/root.zig");
2625 const single_module = try test_dialect.TestDialect.ModuleOp.create(
2626 &ctx,
2627 ir.Location.getUnknown(),
2628 );
2629 const single_block = single_module.getBodyBlock();
2630 var builder = ir.OperationBuilder.init(&ctx);
2631 var branch_state = ir.Operation.State.init(
2632 test_dialect.TestDialect.BranchOp.operation_name,
2633 ir.Location.getUnknown(),
2634 );
2635 branch_state.addSuccessors(&.{single_block});
2636 const branch = try builder.create(branch_state);
2637 try single_block.addOperation(branch);
2638 const single_limits = try RegionControlFlow.Limits.inspect(
2639 single_module.getBody(),
2640 );
2641 var single_counting = std.testing.FailingAllocator.init(allocator, .{});
2642 var single_cfg = try RegionControlFlow.init(
2643 single_counting.allocator(),
2644 single_limits,
2645 );
2646 defer single_cfg.deinit(single_counting.allocator());
2647 try testing.expectEqual(@as(usize, 0), single_counting.alloc_index);
2648 try single_cfg.activate();
2649 try testing.expectEqual(@as(usize, 1), single_cfg.blockCount());
2650 try testing.expect(single_cfg.successors(single_block).?[0] == single_block);
2651 try testing.expect(single_cfg.predecessors(single_block).?[0] == single_block);
2652 }
2653
2654 test "region control-flow queries remain allocation free after sealing" {
2655 comptime {
2656 @stardustClaim(
2657 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_sealed_transitive_risk"),
2658 null,
2659 null,
2660 null,
2661 null,
2662 null,
2663 null,
2664 );
2665 }
2666 comptime {
2667 @stardustClaim(
2668 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_sealed_foreign_risk"),
2669 null,
2670 null,
2671 null,
2672 null,
2673 null,
2674 null,
2675 );
2676 }
2677
2678 const testing = std.testing;
2679 const allocator = testing.allocator;
2680
2681 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2682 defer ctx.deinit(allocator);
2683 const fixture = try buildDiamond(&ctx);
2684 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
2685 var maybe_cfg: ?RegionControlFlow = null;
2686 defer {
2687 if (phase_allocator.phase() == .initialization) {
2688 phase_allocator.abortInitialization();
2689 }
2690 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
2691 if (maybe_cfg) |*region_cfg| {
2692 if (region_cfg.phase != .teardown) {
2693 region_cfg.deinit(phase_allocator.teardownAllocator());
2694 }
2695 }
2696 phase_allocator.deinit();
2697 }
2698 maybe_cfg = try RegionControlFlow.initForRegion(
2699 phase_allocator.initializationAllocator(),
2700 fixture.module.getBody(),
2701 );
2702 const region_cfg = &maybe_cfg.?;
2703 phase_allocator.seal();
2704 try region_cfg.activate();
2705
2706 try testing.expectEqual(@as(usize, 5), region_cfg.blockCount());
2707 try testing.expect(region_cfg.entryBlock() == fixture.entry);
2708 try testing.expect(region_cfg.hasEdge(fixture.entry, fixture.then_block));
2709 try testing.expect(region_cfg.hasEdge(fixture.else_block, fixture.merge));
2710 try testing.expectEqual(@as(usize, 2), region_cfg.predecessors(fixture.merge).?.len);
2711 try testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
2712 }
2713
2714 const RegionControlFlowFailureHarness = struct {
2715 fn run(allocator: std.mem.Allocator, region: *ir.Region) !void {
2716 var region_cfg = try RegionControlFlow.initForRegion(allocator, region);
2717 defer region_cfg.deinit(allocator);
2718 try region_cfg.activate();
2719 try std.testing.expectEqual(@as(usize, 5), region_cfg.blockCount());
2720 }
2721 };
2722
2723 test "RegionControlFlow build retries every allocation failure" {
2724 comptime {
2725 @stardustClaim(
2726 @import("alloc_phase").capacity.witness(RegionControlFlow, "choir_region_cfg_oom"),
2727 null,
2728 null,
2729 null,
2730 null,
2731 null,
2732 null,
2733 );
2734 }
2735
2736 const testing = std.testing;
2737 const allocator = testing.allocator;
2738
2739 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2740 defer ctx.deinit(allocator);
2741 const fixture = try buildDiamond(&ctx);
2742 const region = fixture.module.getBody();
2743
2744 try testing.checkAllAllocationFailures(allocator, RegionControlFlowFailureHarness.run, .{region});
2745 try RegionControlFlowFailureHarness.run(allocator, region);
2746 }
2747
2748 test "DominanceAnalysis handles diamond and isolated roots" {
2749 const testing = std.testing;
2750 const allocator = testing.allocator;
2751
2752 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2753 defer ctx.deinit(allocator);
2754 const fixture = try buildDiamond(&ctx);
2755
2756 var cache = pass.AnalysisCache.init(allocator, null);
2757 defer cache.deinit();
2758
2759 var pass_ctx = pass.PassContext.init(fixture.module.op, &ctx, allocator, &cache);
2760 defer pass_ctx.deinit();
2761
2762 const dominance = try getDominanceAnalysis(&pass_ctx, fixture.module.op);
2763
2764 try testing.expect(dominance.dominatesBlock(fixture.entry, fixture.entry));
2765 try testing.expect(dominance.dominatesBlock(fixture.entry, fixture.then_block));
2766 try testing.expect(dominance.dominatesBlock(fixture.entry, fixture.else_block));
2767 try testing.expect(dominance.dominatesBlock(fixture.entry, fixture.merge));
2768 try testing.expect(!dominance.dominatesBlock(fixture.then_block, fixture.merge));
2769 try testing.expect(!dominance.dominatesBlock(fixture.else_block, fixture.merge));
2770 try testing.expect(!dominance.dominatesBlock(fixture.entry, fixture.unreachable_block));
2771
2772 try testing.expect(dominance.dominatesOperation(fixture.then_value, fixture.then_term));
2773 try testing.expect(!dominance.dominatesOperation(fixture.then_term, fixture.then_value));
2774 }
2775
2776 test "block dominance analysis derives exact aligned region capacity" {
2777 comptime {
2778 @stardustClaim(
2779 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_capacity_capacity_model"),
2780 null,
2781 null,
2782 null,
2783 null,
2784 null,
2785 null,
2786 );
2787 }
2788 comptime {
2789 @stardustClaim(
2790 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_capacity_overload"),
2791 null,
2792 null,
2793 null,
2794 null,
2795 null,
2796 null,
2797 );
2798 }
2799
2800 const testing = std.testing;
2801 const allocator = testing.allocator;
2802
2803 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2804 defer ctx.deinit(allocator);
2805 const fixture = try buildNestedControlFixture(&ctx);
2806 var cfg = try ControlFlowGraphAnalysis.initForOperation(
2807 allocator,
2808 fixture.root.op,
2809 );
2810 defer cfg.deinit(allocator);
2811 try cfg.activate();
2812
2813 const limits = BlockDominanceAnalysis.Limits.inspect(&cfg, .forward);
2814 try testing.expectEqual(@as(usize, 3), limits.region_count);
2815 const capacity = try BlockDominanceAnalysis.Capacity.derive(limits);
2816 try testing.expectEqual(@as(usize, 3), capacity.region_count);
2817 try testing.expectEqual(
2818 3 * @sizeOf(RegionDominance),
2819 capacity.storage_bytes,
2820 );
2821 var overflowing = limits;
2822 overflowing.region_count = std.math.maxInt(usize);
2823 try testing.expectError(
2824 error.CapacityOverflow,
2825 BlockDominanceAnalysis.Capacity.derive(overflowing),
2826 );
2827 }
2828
2829 test "block dominance analysis acquires one exact region owner array" {
2830 comptime {
2831 @stardustClaim(
2832 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_acquisition"),
2833 null,
2834 null,
2835 null,
2836 null,
2837 null,
2838 null,
2839 );
2840 }
2841
2842 const testing = std.testing;
2843 const allocator = testing.allocator;
2844
2845 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2846 defer ctx.deinit(allocator);
2847 const fixture = try buildNestedControlFixture(&ctx);
2848 var cfg = try ControlFlowGraphAnalysis.initForOperation(
2849 allocator,
2850 fixture.root.op,
2851 );
2852 defer cfg.deinit(allocator);
2853 try cfg.activate();
2854
2855 const limits = BlockDominanceAnalysis.Limits.inspect(&cfg, .forward);
2856 const capacity = try BlockDominanceAnalysis.Capacity.derive(limits);
2857 var counting = std.testing.FailingAllocator.init(allocator, .{});
2858 var dominance = try BlockDominanceAnalysis.init(
2859 counting.allocator(),
2860 limits,
2861 );
2862 defer dominance.deinit(counting.allocator());
2863 try testing.expectEqual(@as(usize, 1), counting.alloc_index);
2864 try testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);
2865 try dominance.activate();
2866 try testing.expect(regionDominancesOrdered(dominance.regions));
2867 for (cfg.regionSlice(), dominance.regions) |region_cfg, *region_dom| {
2868 try testing.expect(region_dom.regionPointer() == region_cfg.region);
2869 try testing.expect(
2870 dominance.getRegion(region_cfg.region) == region_dom,
2871 );
2872 const block = region_cfg.entryBlock().?;
2873 try testing.expect(region_dom.contains(block, block));
2874 }
2875 try testing.expect(!dominance.dominatesBlock(
2876 fixture.first.getBodyBlock(),
2877 fixture.second.getBodyBlock(),
2878 ));
2879
2880 var empty_cfg = try ControlFlowGraphAnalysis.initForOperation(
2881 allocator,
2882 fixture.first_branch,
2883 );
2884 defer empty_cfg.deinit(allocator);
2885 try empty_cfg.activate();
2886 const empty_limits = BlockDominanceAnalysis.Limits.inspect(
2887 &empty_cfg,
2888 .forward,
2889 );
2890 var empty_counting = std.testing.FailingAllocator.init(allocator, .{});
2891 var empty_dominance = try BlockDominanceAnalysis.init(
2892 empty_counting.allocator(),
2893 empty_limits,
2894 );
2895 defer empty_dominance.deinit(empty_counting.allocator());
2896 try testing.expectEqual(@as(usize, 0), empty_counting.alloc_index);
2897 try empty_dominance.activate();
2898 try testing.expect(
2899 empty_dominance.getRegion(fixture.first.getBody()) == null,
2900 );
2901 }
2902
2903 test "block dominance analysis queries remain allocation free after sealing" {
2904 comptime {
2905 @stardustClaim(
2906 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_sealed_transitive_risk"),
2907 null,
2908 null,
2909 null,
2910 null,
2911 null,
2912 null,
2913 );
2914 }
2915 comptime {
2916 @stardustClaim(
2917 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_sealed_foreign_risk"),
2918 null,
2919 null,
2920 null,
2921 null,
2922 null,
2923 null,
2924 );
2925 }
2926
2927 const testing = std.testing;
2928 const allocator = testing.allocator;
2929
2930 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2931 defer ctx.deinit(allocator);
2932 const fixture = try buildNestedControlFixture(&ctx);
2933 var cfg = try ControlFlowGraphAnalysis.initForOperation(
2934 allocator,
2935 fixture.root.op,
2936 );
2937 defer cfg.deinit(allocator);
2938 try cfg.activate();
2939 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
2940 var maybe_dominance: ?BlockDominanceAnalysis = null;
2941 defer {
2942 if (phase_allocator.phase() == .initialization) {
2943 phase_allocator.abortInitialization();
2944 }
2945 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
2946 if (maybe_dominance) |*dominance| {
2947 if (dominance.phase != .teardown) {
2948 dominance.deinit(phase_allocator.teardownAllocator());
2949 }
2950 }
2951 phase_allocator.deinit();
2952 }
2953 maybe_dominance = try BlockDominanceAnalysis.init(
2954 phase_allocator.initializationAllocator(),
2955 BlockDominanceAnalysis.Limits.inspect(&cfg, .forward),
2956 );
2957 const dominance = &maybe_dominance.?;
2958 phase_allocator.seal();
2959 try dominance.activate();
2960
2961 try testing.expect(dominance.dominatesBlock(
2962 fixture.first.getBodyBlock(),
2963 fixture.first.getBodyBlock(),
2964 ));
2965 try testing.expect(
2966 dominance.getRegion(fixture.second.getBody()) != null,
2967 );
2968 try testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
2969 }
2970
2971 test "block dominance analysis survives independent CFG invalidation" {
2972 comptime {
2973 @stardustClaim(
2974 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_independent"),
2975 null,
2976 null,
2977 null,
2978 null,
2979 null,
2980 null,
2981 );
2982 }
2983
2984 const testing = std.testing;
2985 const allocator = testing.allocator;
2986
2987 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
2988 defer ctx.deinit(allocator);
2989 const fixture = try buildNestedControlFixture(&ctx);
2990 var cache = pass.AnalysisCache.init(allocator, null);
2991 defer cache.deinit();
2992 var pass_ctx = pass.PassContext.init(
2993 fixture.root.op,
2994 &ctx,
2995 allocator,
2996 &cache,
2997 );
2998 defer pass_ctx.deinit();
2999
3000 const dominance = try getDominanceAnalysis(
3001 &pass_ctx,
3002 fixture.root.op,
3003 );
3004 try pass_ctx.preserveAnalysis(dominance_analysis_descriptor.id);
3005 cache.invalidate(&pass_ctx.preserved);
3006
3007 try testing.expect(dominance.dominatesBlock(
3008 fixture.first.getBodyBlock(),
3009 fixture.first.getBodyBlock(),
3010 ));
3011 const cfg = try getControlFlowGraphAnalysis(
3012 &pass_ctx,
3013 fixture.root.op,
3014 );
3015 try testing.expect(cfg.getRegion(fixture.first.getBody()) != null);
3016 try testing.expect(
3017 dominance.getRegion(fixture.first.getBody()) != null,
3018 );
3019 }
3020
3021 const BlockDominanceAnalysisFailureHarness = struct {
3022 fn run(
3023 allocator: std.mem.Allocator,
3024 cfg: *const ControlFlowGraphAnalysis,
3025 ) !void {
3026 var dominance = try BlockDominanceAnalysis.init(
3027 allocator,
3028 BlockDominanceAnalysis.Limits.inspect(cfg, .forward),
3029 );
3030 defer dominance.deinit(allocator);
3031 try dominance.activate();
3032 try std.testing.expectEqual(cfg.regionCount(), dominance.regions.len);
3033 }
3034 };
3035
3036 test "BlockDominanceAnalysis build retries every allocation failure" {
3037 comptime {
3038 @stardustClaim(
3039 @import("alloc_phase").capacity.witness(BlockDominanceAnalysis, "choir_block_dominance_analysis_oom"),
3040 null,
3041 null,
3042 null,
3043 null,
3044 null,
3045 null,
3046 );
3047 }
3048
3049 const testing = std.testing;
3050 const allocator = testing.allocator;
3051
3052 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3053 defer ctx.deinit(allocator);
3054 const fixture = try buildNestedControlFixture(&ctx);
3055 var cfg = try ControlFlowGraphAnalysis.initForOperation(
3056 allocator,
3057 fixture.root.op,
3058 );
3059 defer cfg.deinit(allocator);
3060 try cfg.activate();
3061 try testing.checkAllAllocationFailures(
3062 allocator,
3063 BlockDominanceAnalysisFailureHarness.run,
3064 .{&cfg},
3065 );
3066 try BlockDominanceAnalysisFailureHarness.run(allocator, &cfg);
3067 }
3068
3069 test "region dominance capacity matches an independent aligned byte model" {
3070 comptime {
3071 @stardustClaim(
3072 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_capacity_capacity_model"),
3073 null,
3074 null,
3075 null,
3076 null,
3077 null,
3078 null,
3079 );
3080 }
3081 comptime {
3082 @stardustClaim(
3083 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_capacity_overload"),
3084 null,
3085 null,
3086 null,
3087 null,
3088 null,
3089 null,
3090 );
3091 }
3092
3093 const testing = std.testing;
3094 const allocator = testing.allocator;
3095
3096 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3097 defer ctx.deinit(allocator);
3098 const fixture = try buildDiamond(&ctx);
3099 var region_cfg = try RegionControlFlow.initForRegion(
3100 allocator,
3101 fixture.module.getBody(),
3102 );
3103 defer region_cfg.deinit(allocator);
3104 try region_cfg.activate();
3105 const limits = RegionDominance.Limits.inspect(®ion_cfg, .forward);
3106 try testing.expectEqual(@as(usize, 5), limits.block_count);
3107
3108 const capacity = try RegionDominance.Capacity.derive(limits);
3109 var expected: usize = 0;
3110 inline for (.{ *ir.Block, bool, bool, bool }, .{ 5, 25, 5, 5 }) |T, count| {
3111 expected = std.mem.alignForward(usize, expected, @alignOf(T));
3112 expected = try std.math.add(
3113 usize,
3114 expected,
3115 try std.math.mul(usize, count, @sizeOf(T)),
3116 );
3117 }
3118 try testing.expectEqual(expected, capacity.working_bytes);
3119 try testing.expectEqual(@as(usize, 5), capacity.block_count);
3120
3121 var singleton = limits;
3122 singleton.block_count = 1;
3123 try testing.expectEqual(
3124 @as(usize, 0),
3125 (try RegionDominance.Capacity.derive(singleton)).working_bytes,
3126 );
3127 var overflowing = limits;
3128 overflowing.block_count = std.math.maxInt(usize);
3129 try testing.expectError(
3130 error.CapacityOverflow,
3131 RegionDominance.Capacity.derive(overflowing),
3132 );
3133 }
3134
3135 test "region dominance acquires at most one exact backing region" {
3136 comptime {
3137 @stardustClaim(
3138 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_acquisition"),
3139 null,
3140 null,
3141 null,
3142 null,
3143 null,
3144 null,
3145 );
3146 }
3147
3148 const testing = std.testing;
3149 const allocator = testing.allocator;
3150
3151 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3152 defer ctx.deinit(allocator);
3153 const fixture = try buildDiamond(&ctx);
3154 var region_cfg = try RegionControlFlow.initForRegion(
3155 allocator,
3156 fixture.module.getBody(),
3157 );
3158 defer region_cfg.deinit(allocator);
3159 try region_cfg.activate();
3160 const limits = RegionDominance.Limits.inspect(®ion_cfg, .forward);
3161 const capacity = try RegionDominance.Capacity.derive(limits);
3162 var incompatible_limits = limits;
3163 incompatible_limits.block_count = 4;
3164 try testing.expectError(
3165 error.RegionChanged,
3166 RegionDominance.init(allocator, incompatible_limits),
3167 );
3168 var counting = std.testing.FailingAllocator.init(allocator, .{});
3169 var dominance = try RegionDominance.init(counting.allocator(), limits);
3170 defer dominance.deinit(counting.allocator());
3171 try testing.expectEqual(@as(usize, 1), counting.alloc_index);
3172 try testing.expectEqual(capacity.working_bytes, counting.allocated_bytes);
3173 try dominance.activate();
3174 try testing.expect(dominance.contains(fixture.entry, fixture.merge));
3175
3176 var empty_region = ir.Region.init(allocator);
3177 defer empty_region.deinit();
3178 var empty_cfg = try RegionControlFlow.initForRegion(allocator, &empty_region);
3179 defer empty_cfg.deinit(allocator);
3180 try empty_cfg.activate();
3181 const empty_limits = RegionDominance.Limits.inspect(&empty_cfg, .forward);
3182 var empty_counting = std.testing.FailingAllocator.init(allocator, .{});
3183 var empty_dominance = try RegionDominance.init(
3184 empty_counting.allocator(),
3185 empty_limits,
3186 );
3187 defer empty_dominance.deinit(empty_counting.allocator());
3188 try testing.expectEqual(@as(usize, 0), empty_counting.alloc_index);
3189 try empty_dominance.activate();
3190 try testing.expect(!empty_dominance.contains(fixture.entry, fixture.entry));
3191
3192 const test_dialect = @import("../dialects/fixture/root.zig");
3193 const single_module = try test_dialect.TestDialect.ModuleOp.create(
3194 &ctx,
3195 ir.Location.getUnknown(),
3196 );
3197 var single_cfg = try RegionControlFlow.initForRegion(
3198 allocator,
3199 single_module.getBody(),
3200 );
3201 defer single_cfg.deinit(allocator);
3202 try single_cfg.activate();
3203 const single_limits = RegionDominance.Limits.inspect(&single_cfg, .forward);
3204 var single_counting = std.testing.FailingAllocator.init(allocator, .{});
3205 var single_dominance = try RegionDominance.init(
3206 single_counting.allocator(),
3207 single_limits,
3208 );
3209 defer single_dominance.deinit(single_counting.allocator());
3210 try testing.expectEqual(@as(usize, 0), single_counting.alloc_index);
3211 try single_dominance.activate();
3212 const block = single_module.getBodyBlock();
3213 try testing.expect(single_dominance.contains(block, block));
3214 }
3215
3216 test "region dominance queries remain allocation free after sealing" {
3217 comptime {
3218 @stardustClaim(
3219 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_sealed_transitive_risk"),
3220 null,
3221 null,
3222 null,
3223 null,
3224 null,
3225 null,
3226 );
3227 }
3228 comptime {
3229 @stardustClaim(
3230 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_sealed_foreign_risk"),
3231 null,
3232 null,
3233 null,
3234 null,
3235 null,
3236 null,
3237 );
3238 }
3239
3240 const testing = std.testing;
3241 const allocator = testing.allocator;
3242
3243 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3244 defer ctx.deinit(allocator);
3245 const fixture = try buildDiamond(&ctx);
3246 var region_cfg = try RegionControlFlow.initForRegion(
3247 allocator,
3248 fixture.module.getBody(),
3249 );
3250 defer region_cfg.deinit(allocator);
3251 try region_cfg.activate();
3252 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
3253 var maybe_dominance: ?RegionDominance = null;
3254 defer {
3255 if (phase_allocator.phase() == .initialization) {
3256 phase_allocator.abortInitialization();
3257 }
3258 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
3259 if (maybe_dominance) |*dominance| {
3260 if (dominance.phase != .teardown) {
3261 dominance.deinit(phase_allocator.teardownAllocator());
3262 }
3263 }
3264 phase_allocator.deinit();
3265 }
3266 maybe_dominance = try RegionDominance.initForRegion(
3267 phase_allocator.initializationAllocator(),
3268 ®ion_cfg,
3269 .forward,
3270 );
3271 const dominance = &maybe_dominance.?;
3272 phase_allocator.seal();
3273 try dominance.activate();
3274
3275 try testing.expect(dominance.contains(fixture.entry, fixture.merge));
3276 try testing.expect(!dominance.contains(fixture.then_block, fixture.merge));
3277 for (dominance.blockSlice()) |block| {
3278 try testing.expect(dominance.contains(block, block));
3279 }
3280 try testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
3281 }
3282
3283 const RegionDominanceFailureHarness = struct {
3284 fn run(allocator: std.mem.Allocator, cfg: *const RegionControlFlow) !void {
3285 var dominance = try RegionDominance.initForRegion(
3286 allocator,
3287 cfg,
3288 .forward,
3289 );
3290 defer dominance.deinit(allocator);
3291 try dominance.activate();
3292 for (dominance.blockSlice()) |block| {
3293 try std.testing.expect(dominance.contains(block, block));
3294 }
3295 }
3296 };
3297
3298 test "RegionDominance build retries every allocation failure" {
3299 comptime {
3300 @stardustClaim(
3301 @import("alloc_phase").capacity.witness(RegionDominance, "choir_region_dominance_oom"),
3302 null,
3303 null,
3304 null,
3305 null,
3306 null,
3307 null,
3308 );
3309 }
3310
3311 const testing = std.testing;
3312 const allocator = testing.allocator;
3313
3314 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3315 defer ctx.deinit(allocator);
3316 const fixture = try buildDiamond(&ctx);
3317
3318 var region_cfg = try RegionControlFlow.initForRegion(
3319 allocator,
3320 fixture.module.getBody(),
3321 );
3322 defer region_cfg.deinit(allocator);
3323 try region_cfg.activate();
3324
3325 try testing.checkAllAllocationFailures(allocator, RegionDominanceFailureHarness.run, .{®ion_cfg});
3326 try RegionDominanceFailureHarness.run(allocator, ®ion_cfg);
3327 }
3328
3329 test "PostDominanceAnalysis handles diamond exits" {
3330 const testing = std.testing;
3331 const allocator = testing.allocator;
3332
3333 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
3334 defer ctx.deinit(allocator);
3335 const fixture = try buildDiamond(&ctx);
3336
3337 var cache = pass.AnalysisCache.init(allocator, null);
3338 defer cache.deinit();
3339
3340 var pass_ctx = pass.PassContext.init(fixture.module.op, &ctx, allocator, &cache);
3341 defer pass_ctx.deinit();
3342
3343 const post_dominance = try getPostDominanceAnalysis(&pass_ctx, fixture.module.op);
3344
3345 try testing.expect(post_dominance.postDominatesBlock(fixture.merge, fixture.then_block));
3346 try testing.expect(post_dominance.postDominatesBlock(fixture.merge, fixture.else_block));
3347 try testing.expect(post_dominance.postDominatesBlock(fixture.merge, fixture.entry));
3348 try testing.expect(!post_dominance.postDominatesBlock(fixture.then_block, fixture.entry));
3349 try testing.expect(!post_dominance.postDominatesBlock(fixture.unreachable_block, fixture.entry));
3350
3351 try testing.expect(post_dominance.postDominatesOperation(fixture.then_term, fixture.then_value));
3352 try testing.expect(!post_dominance.postDominatesOperation(fixture.then_value, fixture.then_term));
3353 }
3354
3355 test "U0 control analysis refuses its declared work before building the graph" {
3356 const revision = @import("../product/revision/root.zig");
3357 const allocator = std.testing.allocator;
3358 var context = try ir.Context.init(allocator, ir.Context.Limits.testing);
3359 defer context.deinit(allocator);
3360 const fixture = try buildDiamond(&context);
3361 const ledger = try revision.AccountingV1.create(allocator, .{
3362 .allowance = .{ .allocation_capacity = 1 << 20 },
3363 .workspace = 1 << 20,
3364 .events = 8,
3365 }, &.{});
3366 defer ledger.destroy();
3367 var observed = std.testing.FailingAllocator.init(allocator, .{});
3368 var stats: pass.PassManagerStats = .{};
3369 var cache = try pass.AnalysisCache.initAccounted(
3370 observed.allocator(),
3371 &stats,
3372 ledger,
3373 .{},
3374 4,
3375 );
3376 defer cache.deinit();
3377 const before = observed.allocated_bytes;
3378 var ctx = pass.PassContext.init(fixture.module.op, &context, observed.allocator(), &cache);
3379 defer ctx.deinit();
3380 try std.testing.expectError(
3381 error.WorkExhausted,
3382 getControlFlowGraphAnalysis(&ctx, fixture.module.op),
3383 );
3384 try std.testing.expectEqual(before, observed.allocated_bytes);
3385 try std.testing.expectEqual(0, stats.analysis_misses);
3386 try std.testing.expectEqual(.exhausted, ledger.view().outcome);
3387 try std.testing.expectEqual(1, ledger.view().charged.analysis_computations);
3388 }
3389
3390 const ControlComputation = enum {
3391 cfg,
3392 dominance,
3393 postdominance,
3394
3395 fn get(self: ControlComputation, ctx: *pass.PassContext, op: *ir.Operation) !*anyopaque {
3396 return switch (self) {
3397 .cfg => @ptrCast(try getControlFlowGraphAnalysis(ctx, op)),
3398 .dominance => @ptrCast(try getDominanceAnalysis(ctx, op)),
3399 .postdominance => @ptrCast(try getPostDominanceAnalysis(ctx, op)),
3400 };
3401 }
3402 };
3403
3404 test "U0 control accounting records nested CFG work and bounds observed allocations" {
3405 const revision = @import("../product/revision/root.zig");
3406 const allocator = std.testing.allocator;
3407 var context = try ir.Context.init(allocator, ir.Context.Limits.testing);
3408 defer context.deinit(allocator);
3409 const fixture = try buildDiamond(&context);
3410 for (std.enums.values(ControlComputation)) |which| {
3411 const ledger = try revision.AccountingV1.create(allocator, .{
3412 .allowance = revision.WorkVector.uniform(1 << 20),
3413 .workspace = 1 << 20,
3414 .events = 8,
3415 }, &.{});
3416 defer ledger.destroy();
3417 var observed = std.testing.FailingAllocator.init(allocator, .{});
3418 var stats: pass.PassManagerStats = .{};
3419 var cache = try pass.AnalysisCache.initAccounted(
3420 observed.allocator(),
3421 &stats,
3422 ledger,
3423 .{},
3424 4,
3425 );
3426 defer cache.deinit();
3427 const before_bytes = observed.allocated_bytes;
3428 const before_charge = ledger.view().charged.allocation_capacity;
3429 var ctx = pass.PassContext.init(fixture.module.op, &context, observed.allocator(), &cache);
3430 defer ctx.deinit();
3431 const first = try which.get(&ctx, fixture.module.op);
3432 const receipt = ledger.view();
3433 try std.testing.expect(!receipt.missing_work_contract);
3434 const computations: u64 = if (which == .cfg) 1 else 2;
3435 try std.testing.expectEqual(computations, receipt.charged.analysis_computations);
3436 try std.testing.expectEqual(computations, stats.analysis_misses);
3437 try std.testing.expectEqual(computations, receipt.executed.work.analysis_computations);
3438 try std.testing.expectEqual(.analysis, receipt.events[1].phase);
3439 if (which != .cfg) try std.testing.expectEqual(1, receipt.events[2].parent.?);
3440 const allocated = observed.allocated_bytes - before_bytes;
3441 try std.testing.expect(allocated <= receipt.charged.allocation_capacity - before_charge);
3442 try std.testing.expect(receipt.maximum_live_storage >= observed.allocated_bytes);
3443 const allocations = observed.allocations;
3444 try std.testing.expectEqual(first, try which.get(&ctx, fixture.module.op));
3445 try std.testing.expectEqual(allocations, observed.allocations);
3446 try std.testing.expectEqualDeep(receipt.charged, ledger.view().charged);
3447 try std.testing.expectEqual(1, stats.analysis_hits);
3448 try ledger.producersComplete();
3449 }
3450 }