lib/choir/src/passes/effects.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const ir = @import("../core/root.zig");
4
5 const facts = ir.interfaces.effects;
6
7 const Dependency = struct {
8 op: *ir.Operation,
9 revision: []u8,
10 declaration: facts.Declaration,
11 executes: bool,
12 instantiate_body: bool,
13 };
14
15 /// A graph of ordered local declarations bound to exact IR and callee inputs.
16 /// Nodes retain their local subjects: operand zero in a callee is not operand
17 /// zero in its caller. Unproved bindings therefore never authorize an action.
18 pub const EffectSummary = struct {
19 allocator: std.mem.Allocator,
20 storage: alloc_arena.Arena,
21 context: *ir.Context,
22 creation_boundary: u31,
23 nodes: []Dependency,
24 used: usize = 0,
25 complete: bool = true,
26 /// Room to rewrite one node's revision for comparison, taken once from
27 /// this summary's own arena and as wide as the widest revision it holds.
28 /// `isCurrent` borrows it so that asking whether a summary is still
29 /// current costs no allocation and cannot fail for want of one.
30 scratch: []u8 = &.{},
31
32 pub fn init(allocator: std.mem.Allocator, op: *ir.Operation) !EffectSummary {
33 var storage = alloc_arena.Arena.init(allocator);
34 errdefer storage.deinit();
35 const scratch = storage.allocator();
36 const leaf = op.getNumRegions() == 0 and !op.hasInterface(ir.interfaces.CallOpInterface);
37 const node_count = if (leaf) 1 else op.getContext().operationCount();
38 var self = EffectSummary{
39 .allocator = scratch,
40 .storage = undefined,
41 .context = op.getContext(),
42 .creation_boundary = op.getContext().operationCreationBoundary(),
43 .nodes = try scratch.alloc(Dependency, node_count),
44 };
45 try self.append(op, true, false);
46 var index: usize = 0;
47 while (index < self.used) : (index += 1) try self.expand(index);
48 std.debug.assert(self.used <= self.nodes.len);
49 var widest: usize = 0;
50 for (self.nodes[0..self.used]) |node| widest = @max(widest, node.revision.len);
51 self.scratch = try scratch.alloc(u8, widest);
52 self.allocator = allocator;
53 self.storage = storage;
54 return self;
55 }
56
57 pub fn deinit(self: *EffectSummary) void {
58 self.storage.deinit();
59 self.* = undefined;
60 }
61
62 fn append(self: *EffectSummary, op: *ir.Operation, executes: bool, body: bool) !void {
63 for (self.nodes[0..self.used]) |node| {
64 if (node.op == op) {
65 self.complete = false;
66 return;
67 }
68 }
69 if (self.used == self.nodes.len) {
70 self.complete = false;
71 return;
72 }
73 var declaration = try facts.inspect(self.allocator, op);
74 errdefer declaration.deinit(self.allocator);
75 const revision = try revisionAlloc(self.allocator, op);
76 self.nodes[self.used] = .{
77 .op = op,
78 .revision = revision,
79 .declaration = declaration,
80 .executes = executes,
81 .instantiate_body = body,
82 };
83 self.used += 1;
84 if (executes and !declaration.facts.complete) self.complete = false;
85 }
86
87 fn expand(self: *EffectSummary, index: usize) !void {
88 const node = self.nodes[index];
89 for (node.op.regions.items, 0..) |*region, region_index| {
90 const mode = regionExecution(node.declaration.facts, region_index);
91 if (node.executes and mode == .unknown) self.complete = false;
92 const executes = node.executes and (mode != .latent or node.instantiate_body);
93 var blocks = region.getBlocks();
94 while (blocks.next()) |block| {
95 var operations = block.getOperations();
96 while (operations.next()) |child| try self.append(child, executes, false);
97 }
98 }
99 if (node.op.hasInterface(ir.interfaces.CallOpInterface)) {
100 if (resolveCallee(node.op)) |callee| {
101 try self.append(callee, node.executes, true);
102 } else if (node.executes) self.complete = false;
103 }
104 }
105
106 pub fn isCurrent(self: *const EffectSummary) bool {
107 for (self.nodes[0..self.used]) |node| {
108 if (!self.context.containsOperation(node.op)) return false;
109 if (!node.op.createdBefore(self.creation_boundary)) return false;
110 if (!revisionMatches(self.scratch, node.op, node.revision)) return false;
111 }
112 return true;
113 }
114
115 pub fn discard(self: *const EffectSummary) bool {
116 return self.all(.discard);
117 }
118
119 pub fn repeatableExpression(self: *const EffectSummary) bool {
120 return self.all(.repeatable);
121 }
122
123 pub fn duplicate(self: *const EffectSummary, stability: facts.Stability) bool {
124 if (!self.discard()) return false;
125 for (self.nodes[0..self.used]) |node| {
126 if (node.executes and !facts.duplicate(node.declaration.facts, stability)) return false;
127 }
128 return true;
129 }
130
131 pub fn speculate(self: *const EffectSummary, operands_available: bool) bool {
132 if (!self.discard()) return false;
133 for (self.nodes[0..self.used]) |node| {
134 if (node.executes and !facts.speculate(node.declaration.facts, operands_available)) {
135 return false;
136 }
137 }
138 return true;
139 }
140
141 pub fn reorder(self: *const EffectSummary, other: *const EffectSummary) bool {
142 if (!self.complete or !other.complete) return false;
143 if (!self.isCurrent() or !other.isCurrent()) return false;
144 for (self.nodes[0..self.used]) |left| {
145 if (!left.executes) continue;
146 for (other.nodes[0..other.used]) |right| {
147 if (!right.executes) continue;
148 if (dependsOn(left.op, right.op) or dependsOn(right.op, left.op)) return false;
149 if (!facts.reorder(left.declaration.facts, right.declaration.facts, .{
150 .no_dependencies = true,
151 })) return false;
152 }
153 }
154 return true;
155 }
156
157 pub fn invalidatesStores(self: *const EffectSummary) bool {
158 return !self.all(.read_only);
159 }
160
161 pub fn observesStores(self: *const EffectSummary) bool {
162 return !self.repeatableExpression();
163 }
164
165 fn all(
166 self: *const EffectSummary,
167 comptime action: enum { discard, repeatable, read_only },
168 ) bool {
169 if (!self.complete or !self.isCurrent()) return false;
170 for (self.nodes[0..self.used]) |node| {
171 if (!node.executes) continue;
172 const allowed = switch (action) {
173 .discard, .read_only => facts.discard(node.declaration.facts),
174 .repeatable => facts.repeatableExpression(node.declaration.facts),
175 };
176 if (!allowed) return false;
177 }
178 return true;
179 }
180 };
181
182 fn regionExecution(declaration: facts.Facts, index: usize) facts.Execution {
183 for (declaration.records) |record| switch (record) {
184 .region => |region| if (region.index == index) return region.execution,
185 else => {},
186 };
187 return .unknown;
188 }
189
190 fn resolveCallee(op: *ir.Operation) ?*ir.Operation {
191 const call = op.interface(ir.interfaces.CallOpInterface) orelse return null;
192 const name = call.call(.getCalleeSymbol, .{}) orelse return null;
193 return ir.SymbolTable.lookupNearestSymbolFrom(op, name);
194 }
195
196 fn dependsOn(user: *ir.Operation, definition: *ir.Operation) bool {
197 if (user == definition) return true;
198 if (user.isAncestor(definition) or definition.isAncestor(user)) return true;
199 for (user.operands.items) |operand| {
200 if (operand.value.getDefiningOp() == @as(*anyopaque, @ptrCast(definition))) return true;
201 }
202 return false;
203 }
204
205 /// Identity-based, exact records use immutable interned attributes and types.
206 /// The bytes include placement, operand identities, result types, properties,
207 /// child rosters, block arguments, interface contracts and resolved callees.
208 /// Whether `op` still spells the revision `expected`, written into `room`
209 /// rather than into memory this has to ask for.
210 ///
211 /// WHY THE STORED LENGTH IS THE EXACT BOUND. `room` is as wide as the widest
212 /// revision the summary holds, so a revision that does not fit in
213 /// `expected.len` bytes is longer than the one recorded and is therefore a
214 /// different revision. Overflow and mismatch are the same answer, and both are
215 /// facts about the operation rather than about the memory left, which is the
216 /// whole point: a summary that could not be checked used to read as a summary
217 /// that was stale, and three separate permissions turned on that reading.
218 fn revisionMatches(room: []u8, op: *ir.Operation, expected: []const u8) bool {
219 if (expected.len > room.len) return false;
220 var writer = std.Io.Writer.fixed(room[0..expected.len]);
221 revisionInto(&writer, op) catch return false;
222 return writer.end == expected.len and std.mem.eql(u8, room[0..expected.len], expected);
223 }
224
225 fn revisionAlloc(allocator: std.mem.Allocator, op: *ir.Operation) ![]u8 {
226 return revisionBytesAlloc(allocator, op) catch |err| switch (err) {
227 error.WriteFailed => error.OutOfMemory,
228 else => err,
229 };
230 }
231
232 fn revisionBytesAlloc(allocator: std.mem.Allocator, op: *ir.Operation) ![]u8 {
233 var output = std.Io.Writer.Allocating.init(allocator);
234 defer output.deinit();
235 try revisionInto(&output.writer, op);
236 return output.toOwnedSlice();
237 }
238
239 /// Spells `op`'s revision into `writer`. One spelling serves the summary that
240 /// records a revision and the check that compares one, so the two cannot drift
241 /// apart and answer differently about the same operation.
242 fn revisionInto(writer: *std.Io.Writer, op: *ir.Operation) !void {
243 try writer.print("{d}:{s};{x};{x};{x};{x};{x};{x};{f};", .{
244 op.name.name.len,
245 op.name.name,
246 pointer(op.getBlock()),
247 pointer(op.prev_op),
248 pointer(op.next_op),
249 pointer(op.getInterface(facts.EffectOpInterface)),
250 pointer(op.getInterface(ir.interfaces.CallOpInterface)),
251 pointer(resolveCallee(op)),
252 op.getLoc(),
253 });
254 const arithmetic = op.getContext().arithmetic_policy;
255 try writer.print("fp{any}:{any}:{any};", .{
256 arithmetic.exceptions_masked,
257 arithmetic.default_rounding,
258 arithmetic.environment_observable,
259 });
260 const properties = try op.getPropertiesAsAttr();
261 try writer.print("p{x};", .{if (properties) |attr| @intFromPtr(attr.impl) else 0});
262 var attrs = op.getAttrs();
263 while (attrs.next()) |attr| {
264 try writer.print(
265 "a{d}:{s}:{x};",
266 .{ attr.name.len, attr.name, @intFromPtr(attr.value.impl) },
267 );
268 }
269 for (op.operands.items) |operand| try writeValue(writer, operand.value);
270 try writer.writeAll("results;");
271 for (op.results.items) |*result| try writeValue(writer, result);
272 for (op.successors.items) |successor| try writer.print("s{x};", .{@intFromPtr(successor)});
273 for (op.regions.items) |*region| {
274 try writer.print("r{x};", .{@intFromPtr(region)});
275 var blocks = region.getBlocks();
276 while (blocks.next()) |block| {
277 try writer.print("b{x};", .{@intFromPtr(block)});
278 for (block.arguments.items) |argument| try writeValue(writer, argument);
279 var children = block.getOperations();
280 while (children.next()) |child| try writer.print("c{x};", .{@intFromPtr(child)});
281 }
282 }
283 }
284
285 fn writeValue(writer: *std.Io.Writer, value: *ir.Value) !void {
286 try writer.print("v{x}:{x};", .{ @intFromPtr(value), @intFromPtr(value.type.impl) });
287 }
288
289 fn pointer(value: anytype) usize {
290 return if (value) |ptr| @intFromPtr(ptr) else 0;
291 }
292
293 /// What an effect question answered, for a question whose answer costs
294 /// memory to find.
295 ///
296 /// WHY THREE AND NOT TWO. Deciding what an operation permits means reading
297 /// its declared facts, and reading them allocates from the same context the
298 /// module lives in. A caller that receives `false` for both "this operation
299 /// forbids it" and "I could not afford to look" cannot tell a fact about the
300 /// program from a shortfall in the compiler, and will go on to emit a
301 /// different program under a smaller budget while reporting nothing. The two
302 /// are different answers and this names them differently.
303 pub const Permission = enum {
304 /// The operation permits it, read from its complete declared facts.
305 yes,
306 /// The operation does not permit it. This is a fact about the operation
307 /// and holds at every budget.
308 no,
309 /// The answer was not affordable. This says nothing about the operation.
310 /// A caller turns it into a refusal that names the segment and the
311 /// figure, never into `no`.
312 unaffordable,
313 };
314
315 pub fn permitsDiscard(op: *ir.Operation) bool {
316 if (!op.hasInterface(facts.EffectOpInterface)) return false;
317 var summary = EffectSummary.init(op.allocator, op) catch return false;
318 defer summary.deinit();
319 return summary.discard();
320 }
321
322 /// Whether the reads and writes of the storage `op` allocates may be discarded.
323 ///
324 /// THE PERMISSION IS DERIVED AND NOT DECLARED. Nothing states that a cell is
325 /// private, because no operation can state it: privacy is a fact about every
326 /// use of a value, which only the module holds. What the declarations state is
327 /// enough to derive it.
328 ///
329 /// The premises, each read from a complete declaration:
330 /// 1. The allocation hands back a fresh identity. Its result is not an alias
331 /// of an operand and not a name someone else already holds, so the only way
332 /// to reach the storage is through that result.
333 /// 2. The uses of an SSA result are all of them. The use list is the module's
334 /// own record, so a use nobody can see does not exist.
335 /// 3. Each use is named by its own operation's facts as the subject of an
336 /// unordered read or write. An ordered access is observable by another
337 /// thread of control, and any other event over that subject, a free, a
338 /// borrow, a move, a release or a foreign call, hands the identity on.
339 /// 4. No result of a using operation aliases that operand, so the identity
340 /// does not leave through a result either.
341 /// 5. The only premise a use still carries over that subject is `live`, and
342 /// that premise is discharged here: an SSA use is dominated by its
343 /// definition, the allocation is that definition, and premise 3 leaves no
344 /// event that could end the storage before the use.
345 ///
346 /// From 1 through 5 the storage is unreachable outside those reads and writes.
347 /// A read of a cell nobody else can reach answers the last write to it, and a
348 /// write nobody else can read changes nothing anyone can observe, so a caller
349 /// that keeps the values in SSA form may discard both.
350 ///
351 /// WHAT THIS DOES NOT SAY. It does not permit discarding the ALLOCATION. The
352 /// allocation can still fail, and a failure is an event this says nothing
353 /// about, so the allocation stays and its bytes stay charged.
354 ///
355 /// READING THE DECLARATIONS COSTS MEMORY, so this answers three ways and not
356 /// two. `unaffordable` is not a smaller `no`: a caller that treats it as one
357 /// promotes nothing, emits a different program, and reports nothing. The caller
358 /// refuses with the segment and the figure instead.
359 /// A shape error from `inspect` stays `no`, because a declaration this
360 /// operation states wrongly is a property of the operation and reads the same
361 /// at every budget.
362 pub fn permitsDiscardingLocalAccesses(op: *ir.Operation) Permission {
363 if (!op.hasInterface(facts.EffectOpInterface)) return .no;
364 var declaration = facts.inspect(op.allocator, op) catch |err| switch (err) {
365 error.OutOfMemory => return .unaffordable,
366 else => return .no,
367 };
368 defer declaration.deinit(op.allocator);
369 if (!declaration.facts.complete) return .no;
370
371 const cell = op.getResult(0) orelse return .no;
372 var allocates = false;
373 for (declaration.facts.records) |record| switch (record) {
374 .event => |event| switch (event.kind) {
375 .allocate => {
376 if (!subjectIsResult(event.resource.subject, 0)) return .no;
377 allocates = true;
378 },
379 .failure => {},
380 else => return .no,
381 },
382 .result => |result| {
383 if (result.index != 0) continue;
384 if (!result.fresh_identity) return .no;
385 if (result.alias != null) return .no;
386 },
387 .requirement => return .no,
388 .region, .binding, .premise => {},
389 };
390 if (!allocates) return .no;
391
392 var use = cell.first_use;
393 while (use) |operand| : (use = operand.next_use) {
394 const owner: *ir.Operation = @ptrCast(@alignCast(operand.owner));
395 switch (accessesOnly(owner, operand.operand_number)) {
396 .yes => {},
397 .no => return .no,
398 .unaffordable => return .unaffordable,
399 }
400 }
401 return .yes;
402 }
403
404 /// Whether `op` names its operand `index` only as the subject of its own
405 /// unordered reads and writes, with `live` as the one premise left over it.
406 ///
407 /// AN INCOMPLETE DECLARATION IS `no` AND NOT `unaffordable`. `complete` is
408 /// cleared when an operation's facts outran the capacity that operation
409 /// itself declares for them, which is a property of the operation and holds
410 /// at every budget. Measured over the nested-loop reproducer at limits
411 /// of 65536, 8192 and 4096, every `memref.load` answered complete with 3
412 /// records and every `memref.store` complete with 2, the same at all three,
413 /// and the budget that could not afford the question failed `inspect`
414 /// outright rather than returning an incomplete answer.
415 fn accessesOnly(op: *ir.Operation, index: usize) Permission {
416 if (!op.hasInterface(facts.EffectOpInterface)) return .no;
417 var declaration = facts.inspect(op.allocator, op) catch |err| switch (err) {
418 error.OutOfMemory => return .unaffordable,
419 else => return .no,
420 };
421 defer declaration.deinit(op.allocator);
422 if (!declaration.facts.complete) return .no;
423
424 var accesses = false;
425 for (declaration.facts.records) |record| switch (record) {
426 .event => |event| {
427 if (!subjectIsOperand(event.resource.subject, index)) continue;
428 if (event.ordered) return .no;
429 if (event.kind != .read and event.kind != .write) return .no;
430 accesses = true;
431 },
432 .requirement => |requirement| {
433 const names = subjectIsOperand(requirement.subject, index) or
434 (requirement.related != null and
435 subjectIsOperand(requirement.related.?, index));
436 if (!names) continue;
437 if (requirement.kind != .live) return .no;
438 },
439 .result => |result| {
440 const alias = result.alias orelse continue;
441 if (subjectIsOperand(alias, index)) return .no;
442 },
443 .region, .binding, .premise => {},
444 };
445 return if (accesses) .yes else .no;
446 }
447
448 fn subjectIsOperand(subject: facts.Subject, index: usize) bool {
449 return subject == .operand and subject.operand == index;
450 }
451
452 fn subjectIsResult(subject: facts.Subject, index: usize) bool {
453 return subject == .result and subject.result == index;
454 }
455
456 pub fn permitsRepeatableExpression(op: *ir.Operation) bool {
457 if (!op.hasInterface(facts.EffectOpInterface)) return false;
458 var summary = EffectSummary.init(op.allocator, op) catch return false;
459 defer summary.deinit();
460 return summary.repeatableExpression();
461 }
462
463 const pass = @import("pass/root.zig");
464 const CachedSummary = pass.Analysis(
465 EffectSummary,
466 "choir.effects",
467 &.{},
468 computeSummary,
469 destroySummary,
470 null,
471 );
472
473 /// Preserving the cache entry never preserves permission across changed inputs.
474 pub fn analysis(ctx: *pass.PassContext, op: *ir.Operation) !*EffectSummary {
475 const cached = try CachedSummary.get(ctx, op);
476 if (!cached.isCurrent()) {
477 try ctx.refreshAnalysis(op, &CachedSummary.descriptor, refreshSummary);
478 }
479 return cached;
480 }
481
482 fn refreshSummary(ctx: *pass.PassContext, op: *ir.Operation, value: *anyopaque) !void {
483 const cached: *EffectSummary = @ptrCast(@alignCast(value));
484 const replacement = try EffectSummary.init(ctx.allocator, op);
485 cached.deinit();
486 cached.* = replacement;
487 }
488
489 fn computeSummary(ctx: *pass.PassContext, op: *ir.Operation) !*EffectSummary {
490 const result = try ctx.allocator.create(EffectSummary);
491 errdefer ctx.allocator.destroy(result);
492 result.* = try EffectSummary.init(ctx.allocator, op);
493 return result;
494 }
495
496 fn destroySummary(summary: *EffectSummary, allocator: std.mem.Allocator) void {
497 summary.deinit();
498 allocator.destroy(summary);
499 }
500
501 test "effect summary rejects stale operands attributes placement and erased identity" {
502 const arith = @import("../dialects/arith/root.zig").ArithDialect;
503 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
504 defer ctx.deinit(std.testing.allocator);
505 try ir.dialects.loadDialectSpec(&ctx, @import("../dialects/arith/root.zig").spec);
506 const ty = try arith.getScalarType(&ctx, .i32);
507 var one = try arith.ConstantOp.createInt(&ctx, .unknown, ty, 1);
508 var two = try arith.ConstantOp.createInt(&ctx, .unknown, ty, 2);
509 var add = try arith.AddOp.create(&ctx, .unknown, one.getResult(), one.getResult());
510 var summary = try EffectSummary.init(std.testing.allocator, add.op);
511 defer summary.deinit();
512 try std.testing.expect(summary.repeatableExpression());
513 add.op.setOperandValue(1, two.getResult());
514 try std.testing.expect(!summary.isCurrent());
515 try std.testing.expect(!summary.discard());
516 add.op.setOperandValue(1, one.getResult());
517 try std.testing.expect(summary.isCurrent());
518 try add.op.setAttr("contract", try ctx.getI64Attr(1));
519 try std.testing.expect(!summary.speculate(true));
520 _ = add.op.removeAttr("contract");
521 const block = try std.testing.allocator.create(ir.Block);
522 block.* = ir.Block.init(std.testing.allocator);
523 defer {
524 block.deinit();
525 std.testing.allocator.destroy(block);
526 }
527 try block.addOperation(add.op);
528 try std.testing.expect(!summary.duplicate(.{}));
529 add.op.erase();
530 try std.testing.expect(!summary.isCurrent());
531 }
532
533 test "effect summary preserves local event order and latent dependency revisions" {
534 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
535 defer ctx.deinit(std.testing.allocator);
536 try ctx.allowUnregistered();
537 try ctx.registerOperationInterface("test.effects_body", facts.EffectOpInterface.entryFor(.{
538 .complete = true,
539 .facts = &.{.{ .region = .{
540 .index = 0,
541 .execution = .latent,
542 .may_diverge = false,
543 .captures = false,
544 } }},
545 }));
546 try ctx.registerOperationInterface("test.write_fail", facts.EffectOpInterface.entryFor(.{
547 .complete = true,
548 .facts = &.{
549 .{ .event = .{ .kind = .write, .resource = .{ .subject = .{ .global = "log" } } } },
550 .{ .event = .{ .kind = .failure, .failure_name = "CheckedFailure" } },
551 },
552 }));
553 var state = ir.Operation.State.init("test.effects_body", .unknown);
554 state.addRegion();
555 const definition = try ctx.createOperation(state);
556 const block = try definition.regions.items[0].addBlock();
557 const child = try ctx.createOperation(ir.Operation.State.init("test.write_fail", .unknown));
558 try block.addOperation(child);
559 var summary = try EffectSummary.init(std.testing.allocator, definition);
560 defer summary.deinit();
561 try std.testing.expect(summary.complete);
562 try std.testing.expect(summary.discard());
563 try std.testing.expectEqual(@as(usize, 2), summary.used);
564 const events = summary.nodes[1].declaration.facts.records;
565 try std.testing.expectEqual(facts.EventKind.write, events[0].event.kind);
566 try std.testing.expectEqual(facts.EventKind.failure, events[1].event.kind);
567 try child.setAttr("mode", try ctx.getI64Attr(1));
568 try std.testing.expect(!summary.isCurrent());
569 }
570
571 test "effect summary cache refreshes unreported mutations without preserving permission" {
572 const arith = @import("../dialects/arith/root.zig").ArithDialect;
573 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
574 defer ctx.deinit(std.testing.allocator);
575 try ir.dialects.loadDialectSpec(&ctx, @import("../dialects/arith/root.zig").spec);
576 const ty = try arith.getScalarType(&ctx, .i32);
577 var constant = try arith.ConstantOp.createInt(&ctx, .unknown, ty, 1);
578 var cache = pass.AnalysisCache.init(std.testing.allocator, null);
579 defer cache.deinit();
580 var context = pass.PassContext.init(constant.op, &ctx, std.testing.allocator, &cache);
581 defer context.deinit();
582 const first = try analysis(&context, constant.op);
583 try std.testing.expect(first.discard());
584 try constant.op.setAttr("value", try ctx.getStringAttr("not an integer"));
585 try std.testing.expect(!first.discard());
586 const next = try analysis(&context, constant.op);
587 try std.testing.expect(first == next);
588 try std.testing.expect(next.isCurrent());
589 try std.testing.expect(!next.discard());
590 }
591
592 test "effect summary traverses conditional repeated and unresolved call dependencies" {
593 const dialects = @import("../dialects/root.zig");
594 const fixture = @import("../dialects/fixture/root.zig");
595 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
596 defer ctx.deinit(std.testing.allocator);
597 try dialects.registerAllDialects(&ctx);
598 const module = try fixture.TestDialect.ModuleOp.create(&ctx, .unknown);
599 const block = module.getBodyBlock();
600 var condition = try dialects.ArithDialect.ConstantOp.createBool(&ctx, .unknown, true);
601 try block.addOperation(condition.op);
602 const branch = try dialects.ScfDialect.IfOp.create(&ctx, .unknown, condition.getResult(), &.{});
603 try block.addOperation(branch.op);
604 const unknown = try dialects.FuncDialect.CallOp.create(&ctx, .unknown, "missing", &.{}, &.{});
605 try branch.getThenBlock().addOperation(unknown.op);
606 var summary = try EffectSummary.init(std.testing.allocator, branch.op);
607 defer summary.deinit();
608 try std.testing.expect(!summary.complete);
609 try std.testing.expectEqual(@as(usize, 2), summary.used);
610 try std.testing.expect(!summary.discard());
611 try std.testing.expect(!summary.speculate(true));
612 const ty = try dialects.ArithDialect.getIndexType(&ctx);
613 var zero = try dialects.ArithDialect.ConstantOp.createInt(&ctx, .unknown, ty, 0);
614 var one = try dialects.ArithDialect.ConstantOp.createInt(&ctx, .unknown, ty, 1);
615 const loop = try dialects.ScfDialect.ForOp.create(
616 &ctx,
617 .unknown,
618 zero.getResult(),
619 zero.getResult(),
620 one.getResult(),
621 &.{},
622 &.{},
623 );
624 var repeated = try EffectSummary.init(std.testing.allocator, loop.op);
625 defer repeated.deinit();
626 try std.testing.expect(!repeated.discard());
627 try std.testing.expectEqual(
628 facts.Execution.repeated,
629 regionExecution(repeated.nodes[0].declaration.facts, 0),
630 );
631 }
632
633 fn checkSummaryAllocationFailure(allocator: std.mem.Allocator, op: *ir.Operation) !void {
634 var summary = try EffectSummary.init(allocator, op);
635 defer summary.deinit();
636 }
637
638 test "effect summary releases partial exact revisions on allocation failure" {
639 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
640 defer ctx.deinit(std.testing.allocator);
641 try ctx.allowUnregistered();
642 try ctx.registerOperationInterface(
643 "effects.allocation_probe",
644 facts.EffectOpInterface.entryFor(.{ .complete = true }),
645 );
646 const op = try ctx.createOperation(ir.Operation.State.init(
647 "effects.allocation_probe",
648 .unknown,
649 ));
650 try std.testing.checkAllAllocationFailures(
651 std.testing.allocator,
652 checkSummaryAllocationFailure,
653 .{op},
654 );
655 }
656
657 test "effect summary releases nested scratch with a bounded backing allocator" {
658 var ctx = try ir.Context.init(std.testing.allocator, ir.Context.Limits.testing);
659 defer ctx.deinit(std.testing.allocator);
660 try ctx.allowUnregistered();
661 var state = ir.Operation.State.init("effects.parent", .unknown);
662 state.addRegion();
663 const parent = try ctx.createOperation(state);
664 const block = try parent.regions.items[0].addBlock();
665 for (0..4) |_| {
666 const child = try ctx.createOperation(ir.Operation.State.init("effects.child", .unknown));
667 try block.addOperation(child);
668 }
669 var bytes: [32 * 1024]u8 align(16) = undefined;
670 var backing = @import("alloc_fixed").FixedBuffer.init(&bytes);
671 for (0..128) |_| {
672 var summary = try EffectSummary.init(backing.allocator(), parent);
673 try std.testing.expect(summary.isCurrent());
674 summary.deinit();
675 try std.testing.expectEqual(@as(usize, 0), @import("alloc_fixed").used(&backing));
676 }
677 }