ZJIT: Create HIR effect system (#15359)

**Progress**
I've added a new directory, `zjit/src/hir_effect`. It follows the same structure as `zjit/src/hir_type` and includes:
- a ruby script to generate a rust file containing a bitset of effects we want to track
- a modified `hir.rs` to include an `effects_of` function that catalogs effects for each HIR instruction, similar to `infer_type`. Right now these effects are not specialized, all instructions currently return the top of the lattice (any effect)
- a module file for effects at `zjit/src/hir_effect/mod.rs` that again, mirrors `zjit/src/hir_type/mod.rs`. This contains a lot of helper functions and lattice operations like union and intersection

**Design Idea**
The effect system is bitset-based rather than range-based. This is the first kind of effect system described in [Max's blog post](https://bernsteinbear.com/blog/compiler-effects/).
Practically, having effects defined for each HIR instruction should allow us to have better generalization than the implicit effect system we have for c functions that we annotation as elidable, leaf, etc. Additionally, this could allow us to reason about the effects of multiple HIR instructions unioned together, something I don't believe currently exists.

**Practical Goals**
This PR replaces `has_effects` with a new effects-based `is_elidable` function. This has no behavior change to the JIT, but will make it easier to reason about effects of basic blocks and CCalls with the new design. We may be able to accomplish other quality of life improvements, such as consolidation of `nogc`, `leaf`, and other annotations.

5 files changed, 758 insertions, 57 deletions

diff --git a/zjit/src/hir.rs b/zjit/src/hir.rs
index 97a0097073..29c34694b7 100644
--- a/zjit/src/hir.rs
+++ b/zjit/src/hir.rs
@@ -13,6 +13,7 @@ use std::{
     cell::RefCell, collections::{BTreeSet, HashMap, HashSet, VecDeque}, ffi::{c_void, c_uint, c_int, CStr}, fmt::Display, mem::{align_of, size_of}, ptr, slice::Iter
 };
 use crate::hir_type::{Type, types};
+use crate::hir_effect::{Effect, abstract_heaps, effects};
 use crate::bitset::BitSet;
 use crate::profile::{TypeDistributionSummary, ProfiledType};
 use crate::stats::Counter;
@@ -1053,61 +1054,167 @@ impl Insn {
         InsnPrinter { inner: self.clone(), ptr_map, iseq }
     }
 
-    /// Return true if the instruction needs to be kept around. For example, if the instruction
-    /// might have a side effect, or if the instruction may raise an exception.
-    fn has_effects(&self) -> bool {
-        match self {
-            Insn::Const { .. } => false,
-            Insn::Param => false,
-            Insn::StringCopy { .. } => false,
-            Insn::NewArray { .. } => false,
-            // NewHash's operands may be hashed and compared for equality, which could have
-            // side-effects.
-            Insn::NewHash { elements, .. } => !elements.is_empty(),
-            Insn::ArrayLength { .. } => false,
-            Insn::ArrayDup { .. } => false,
-            Insn::HashDup { .. } => false,
-            Insn::Test { .. } => false,
-            Insn::Snapshot { .. } => false,
-            Insn::FixnumAdd  { .. } => false,
-            Insn::FixnumSub  { .. } => false,
-            Insn::FixnumMult { .. } => false,
-            // TODO(max): Consider adding a Guard that the rhs is non-zero before Div and Mod
-            // Div *is* critical unless we can prove the right hand side != 0
-            // Mod *is* critical unless we can prove the right hand side != 0
-            Insn::FixnumEq   { .. } => false,
-            Insn::FixnumNeq  { .. } => false,
-            Insn::FixnumLt   { .. } => false,
-            Insn::FixnumLe   { .. } => false,
-            Insn::FixnumGt   { .. } => false,
-            Insn::FixnumGe   { .. } => false,
-            Insn::FixnumAnd  { .. } => false,
-            Insn::FixnumOr   { .. } => false,
-            Insn::FixnumXor  { .. } => false,
-            Insn::FixnumLShift { .. } => false,
-            Insn::FixnumRShift { .. } => false,
-            Insn::FixnumAref { .. } => false,
-            Insn::GetLocal   { .. } => false,
-            Insn::IsNil      { .. } => false,
-            Insn::LoadPC => false,
-            Insn::LoadEC => false,
-            Insn::LoadSelf => false,
-            Insn::LoadField { .. } => false,
-            Insn::CCall { elidable, .. } => !elidable,
-            Insn::CCallWithFrame { elidable, .. } => !elidable,
-            Insn::ObjectAllocClass { .. } => false,
-            // TODO: NewRange is effects free if we can prove the two ends to be Fixnum,
-            // but we don't have type information here in `impl Insn`. See rb_range_new().
-            Insn::NewRange { .. } => true,
-            Insn::NewRangeFixnum { .. } => false,
-            Insn::StringGetbyte { .. } => false,
-            Insn::IsBlockGiven => false,
-            Insn::BoxFixnum { .. } => false,
-            Insn::BoxBool { .. } => false,
-            Insn::IsBitEqual { .. } => false,
-            Insn::IsA { .. } => false,
-            _ => true,
-        }
+    // TODO(Jacob): Model SP. ie, all allocations modify stack size but using the effect for stack modification feels excessive
+    // TODO(Jacob): Add sideeffect failure bit
+    fn effects_of(&self) -> Effect {
+        const allocates: Effect = Effect::read_write(abstract_heaps::PC.union(abstract_heaps::Allocator), abstract_heaps::Allocator);
+        match &self {
+            Insn::Const { .. } => effects::Empty,
+            Insn::Param { .. } => effects::Empty,
+            Insn::StringCopy { .. } => allocates,
+            Insn::StringIntern { .. } => effects::Any,
+            Insn::StringConcat { .. } => effects::Any,
+            Insn::StringGetbyte { .. } => Effect::read_write(abstract_heaps::Other, abstract_heaps::Empty),
+            Insn::StringSetbyteFixnum { .. } => effects::Any,
+            Insn::StringAppend { .. } => effects::Any,
+            Insn::StringAppendCodepoint { .. } => effects::Any,
+            Insn::ToRegexp { .. } => effects::Any,
+            Insn::PutSpecialObject { .. } => effects::Any,
+            Insn::ToArray { .. } => effects::Any,
+            Insn::ToNewArray { .. } => effects::Any,
+            Insn::NewArray { .. } => allocates,
+            Insn::NewHash { elements, .. } => {
+                // NewHash's operands may be hashed and compared for equality, which could have
+                // side-effects. Empty hashes are definitely elidable.
+                if elements.is_empty() {
+                    Effect::write(abstract_heaps::Allocator)
+                }
+                else {
+                    effects::Any
+                }
+            },
+            Insn::NewRange { .. } => effects::Any,
+            Insn::NewRangeFixnum { .. } => allocates,
+            Insn::ArrayDup { .. } => allocates,
+            Insn::ArrayHash { .. } => effects::Any,
+            Insn::ArrayMax { .. } => effects::Any,
+            Insn::ArrayInclude { .. } => effects::Any,
+            Insn::ArrayPackBuffer { .. } => effects::Any,
+            Insn::DupArrayInclude { .. } => effects::Any,
+            Insn::ArrayExtend { .. } => effects::Any,
+            Insn::ArrayPush { .. } => effects::Any,
+            Insn::ArrayAref { ..  } => effects::Any,
+            Insn::ArrayAset { .. } => effects::Any,
+            Insn::ArrayPop { ..  } => effects::Any,
+            Insn::ArrayLength { .. } => Effect::write(abstract_heaps::Empty),
+            Insn::HashAref { .. } => effects::Any,
+            Insn::HashAset { .. } => effects::Any,
+            Insn::HashDup { .. } => allocates,
+            Insn::ObjectAlloc { .. } => effects::Any,
+            Insn::ObjectAllocClass { .. } => allocates,
+            Insn::Test { .. } => effects::Empty,
+            Insn::IsNil { .. } => effects::Empty,
+            Insn::IsMethodCfunc { .. } => effects::Any,
+            Insn::IsBitEqual { .. } => effects::Empty,
+            Insn::IsBitNotEqual { .. } => effects::Any,
+            Insn::BoxBool { .. } => effects::Empty,
+            Insn::BoxFixnum { .. } => effects::Empty,
+            Insn::UnboxFixnum { .. } => effects::Any,
+            Insn::FixnumAref { .. } => effects::Empty,
+            Insn::Defined { .. } => effects::Any,
+            Insn::GetConstantPath { .. } => effects::Any,
+            Insn::IsBlockGiven { .. } => Effect::read_write(abstract_heaps::Other, abstract_heaps::Empty),
+            Insn::FixnumBitCheck { .. } => effects::Any,
+            Insn::IsA { .. } => effects::Empty,
+            Insn::GetGlobal { .. } => effects::Any,
+            Insn::SetGlobal { .. } => effects::Any,
+            Insn::GetIvar { .. } => effects::Any,
+            Insn::SetIvar { .. } => effects::Any,
+            Insn::DefinedIvar { .. } => effects::Any,
+            Insn::LoadPC { .. } => Effect::read_write(abstract_heaps::PC, abstract_heaps::Empty),
+            Insn::LoadEC { .. } => effects::Empty,
+            Insn::LoadSelf { .. } => Effect::read_write(abstract_heaps::Frame, abstract_heaps::Empty),
+            Insn::LoadField { .. } => Effect::read_write(abstract_heaps::Other, abstract_heaps::Empty),
+            Insn::StoreField { .. } => effects::Any,
+            Insn::WriteBarrier { .. } => effects::Any,
+            Insn::GetLocal   { .. } => Effect::read_write(abstract_heaps::Locals, abstract_heaps::Empty),
+            Insn::SetLocal { .. } => effects::Any,
+            Insn::GetSpecialSymbol { .. } => effects::Any,
+            Insn::GetSpecialNumber { .. } => effects::Any,
+            Insn::GetClassVar { .. } => effects::Any,
+            Insn::SetClassVar { .. } => effects::Any,
+            Insn::Snapshot { .. } => effects::Empty,
+            Insn::Jump(_) => effects::Any,
+            Insn::IfTrue { .. } => effects::Any,
+            Insn::IfFalse { .. } => effects::Any,
+            Insn::CCall { elidable, .. } => {
+                if *elidable {
+                    Effect::write(abstract_heaps::Allocator)
+                }
+                else {
+                    effects::Any
+                }
+            },
+            Insn::CCallWithFrame { elidable, .. } => {
+                if *elidable {
+                    Effect::write(abstract_heaps::Allocator)
+                }
+                else {
+                    effects::Any
+                }
+            },
+            Insn::CCallVariadic { .. } => effects::Any,
+            Insn::SendWithoutBlock { .. } => effects::Any,
+            Insn::Send { .. } => effects::Any,
+            Insn::SendForward { .. } => effects::Any,
+            Insn::InvokeSuper { .. } => effects::Any,
+            Insn::InvokeBlock { .. } => effects::Any,
+            Insn::SendWithoutBlockDirect { .. } => effects::Any,
+            Insn::InvokeBuiltin { .. } => effects::Any,
+            Insn::EntryPoint { .. } => effects::Any,
+            Insn::Return { .. } => effects::Any,
+            Insn::Throw { .. } => effects::Any,
+            Insn::FixnumAdd { .. } => effects::Empty,
+            Insn::FixnumSub { .. } => effects::Empty,
+            Insn::FixnumMult { .. } => effects::Empty,
+            Insn::FixnumDiv { .. } => effects::Any,
+            Insn::FixnumMod { .. } => effects::Any,
+            Insn::FixnumEq { .. } => effects::Empty,
+            Insn::FixnumNeq { .. } => effects::Empty,
+            Insn::FixnumLt { .. } => effects::Empty,
+            Insn::FixnumLe { .. } => effects::Empty,
+            Insn::FixnumGt { .. } => effects::Empty,
+            Insn::FixnumGe { .. } => effects::Empty,
+            Insn::FixnumAnd { .. } => effects::Empty,
+            Insn::FixnumOr { .. } => effects::Empty,
+            Insn::FixnumXor { .. } => effects::Empty,
+            Insn::FixnumLShift { .. } => effects::Empty,
+            Insn::FixnumRShift { .. } => effects::Empty,
+            Insn::ObjToString { .. } => effects::Any,
+            Insn::AnyToString { .. } => effects::Any,
+            Insn::GuardType { .. } => effects::Any,
+            Insn::GuardTypeNot { .. } => effects::Any,
+            Insn::GuardBitEquals { .. } => effects::Any,
+            Insn::GuardShape { .. } => effects::Any,
+            Insn::GuardBlockParamProxy { .. } => effects::Any,
+            Insn::GuardNotFrozen { .. } => effects::Any,
+            Insn::GuardNotShared { .. } => effects::Any,
+            Insn::GuardGreaterEq { .. } => effects::Any,
+            Insn::GuardSuperMethodEntry { .. } => effects::Any,
+            Insn::GetBlockHandler { .. } => effects::Any,
+            Insn::GuardLess { .. } => effects::Any,
+            Insn::PatchPoint { .. } => effects::Any,
+            Insn::SideExit { .. } => effects::Any,
+            Insn::IncrCounter(_) => effects::Any,
+            Insn::IncrCounterPtr { .. } => effects::Any,
+            Insn::CheckInterrupts { .. } => effects::Any,
+        }
+    }
+
+    /// Return true if we can safely omit the instruction. This occurs when one of the following
+    /// conditions are met.
+    /// 1. The instruction does not write anything.
+    /// 2. The instruction only allocates and writes nothing else.
+    /// Calling the effects of our instruction `insn_effects`, we need:
+    /// `effects::Empty` to include `insn_effects.write` or `effects::Allocator` to include
+    /// `insn_effects.write`.
+    /// We can simplify this to `effects::Empty.union(effects::Allocator).includes(insn_effects.write)`.
+    /// But the union of `Allocator` and `Empty` is simply `Allocator`, so our entire function
+    /// collapses to `effects::Allocator.includes(insn_effects.write)`.
+    /// Note: These are restrictions on the `write` `EffectSet` only. Even instructions with
+    /// `read: effects::Any` could potentially be omitted.
+    fn is_elidable(&self) -> bool {
+        abstract_heaps::Allocator.includes(self.effects_of().write_bits())
     }
 }
 
@@ -4388,8 +4495,7 @@ impl Function {
         // otherwise necessary to keep around
         for block_id in &rpo {
             for insn_id in &self.blocks[block_id.0].insns {
-                let insn = &self.insns[insn_id.0];
-                if insn.has_effects() {
+                if !&self.insns[insn_id.0].is_elidable() {
                     worklist.push_back(*insn_id);
                 }
             }
diff --git a/zjit/src/hir_effect/gen_hir_effect.rb b/zjit/src/hir_effect/gen_hir_effect.rb
new file mode 100644
index 0000000000..51cc712feb
--- /dev/null
+++ b/zjit/src/hir_effect/gen_hir_effect.rb
@@ -0,0 +1,119 @@
+# Generate hir_effect.inc.rs. To do this, we build up a DAG that
+# represents the ZJIT effect hierarchy.
+
+require 'set'
+
+# Effect represents not just a Ruby class but a named union of other effects.
+class Effect
+  attr_accessor :name, :subeffects
+
+  def initialize name, subeffects=nil
+    @name = name
+    @subeffects = subeffects || []
+  end
+
+  def all_subeffects
+    subeffects.flat_map { |subeffect| subeffect.all_subeffects } + subeffects
+  end
+
+  def subeffect name
+    result = Effect.new name
+    @subeffects << result
+    result
+  end
+end
+
+# Helper to generate graphviz.
+def to_graphviz_rec effect
+  effect.subeffects.each {|subeffect|
+    puts effect.name + "->" + subeffect.name + ";"
+  }
+  effect.subeffect.each {|subeffect|
+    to_graphviz_rec subeffect
+  }
+end
+
+# Generate graphviz.
+def to_graphviz effect
+  puts "digraph G {"
+  to_graphviz_rec effect
+  puts "}"
+end
+
+# ===== Start generating the effect DAG =====
+
+# Start at Any. All effects are subeffects of Any.
+any = Effect.new 'Any'
+# Build the effect universe.
+allocator = any.subeffect 'Allocator'
+control = any.subeffect 'Control'
+memory = any.subeffect 'Memory'
+other = memory.subeffect 'Other'
+frame = memory.subeffect 'Frame'
+pc = frame.subeffect 'PC'
+locals = frame.subeffect 'Locals'
+stack = frame.subeffect 'Stack'
+
+# Use the smallest unsigned value needed to describe all effect bits
+# If it becomes an issue, this can be generated but for now we do it manually
+$int_label = 'u8'
+
+# Assign individual bits to effect leaves and union bit patterns to nodes with subeffects
+num_bits = 0
+$bits = {"Empty" => ["0#{$int_label}"]}
+$numeric_bits = {"Empty" => 0}
+Set[any, *any.all_subeffects].sort_by(&:name).each {|effect|
+  subeffects = effect.subeffects
+  if subeffects.empty?
+    # Assign bits for leaves
+    $bits[effect.name] = ["1#{$int_label} << #{num_bits}"]
+    $numeric_bits[effect.name] = 1 << num_bits
+    num_bits += 1
+  else
+    # Assign bits for unions
+    $bits[effect.name] = subeffects.map(&:name).sort
+  end
+}
+[*any.all_subeffects, any].each {|effect|
+  subeffects = effect.subeffects
+  unless subeffects.empty?
+    $numeric_bits[effect.name] = subeffects.map {|ty| $numeric_bits[ty.name]}.reduce(&:|)
+  end
+}
+
+# ===== Finished generating the DAG; write Rust code =====
+
+puts "// This file is @generated by src/hir/gen_hir_effect.rb."
+puts "mod bits {"
+$bits.keys.sort.map {|effect_name|
+  subeffects = $bits[effect_name].join(" | ")
+  puts "  pub const #{effect_name}: #{$int_label} = #{subeffects};"
+}
+puts "  pub const AllBitPatterns: [(&str, #{$int_label}); #{$bits.size}] = ["
+# Sort the bit patterns by decreasing value so that we can print the densest
+# possible to-string representation of an Effect. For example, Frame instead of
+# PC|Stack|Locals
+$numeric_bits.sort_by {|key, val| -val}.each {|effect_name, _|
+  puts "    (\"#{effect_name}\", #{effect_name}),"
+}
+puts "  ];"
+puts "  pub const NumEffectBits: #{$int_label} = #{num_bits};
+}"
+
+puts "pub mod effect_types {"
+puts "  pub type EffectBits = #{$int_label};"
+puts "}"
+
+puts "pub mod abstract_heaps {
+  use super::*;"
+$bits.keys.sort.map {|effect_name|
+    puts "  pub const #{effect_name}: AbstractHeap = AbstractHeap::from_bits(bits::#{effect_name});"
+}
+puts "}"
+
+puts "pub mod effects {
+  use super::*;"
+$bits.keys.sort.map {|effect_name|
+    puts "  pub const #{effect_name}: Effect = Effect::promote(abstract_heaps::#{effect_name});"
+}
+puts "}"
diff --git a/zjit/src/hir_effect/hir_effect.inc.rs b/zjit/src/hir_effect/hir_effect.inc.rs
new file mode 100644
index 0000000000..d9566b3eaa
--- /dev/null
+++ b/zjit/src/hir_effect/hir_effect.inc.rs
@@ -0,0 +1,55 @@
+// This file is @generated by src/hir/gen_hir_effect.rb.
+mod bits {
+  pub const Allocator: u8 = 1u8 << 0;
+  pub const Any: u8 = Allocator | Control | Memory;
+  pub const Control: u8 = 1u8 << 1;
+  pub const Empty: u8 = 0u8;
+  pub const Frame: u8 = Locals | PC | Stack;
+  pub const Locals: u8 = 1u8 << 2;
+  pub const Memory: u8 = Frame | Other;
+  pub const Other: u8 = 1u8 << 3;
+  pub const PC: u8 = 1u8 << 4;
+  pub const Stack: u8 = 1u8 << 5;
+  pub const AllBitPatterns: [(&str, u8); 10] = [
+    ("Any", Any),
+    ("Memory", Memory),
+    ("Frame", Frame),
+    ("Stack", Stack),
+    ("PC", PC),
+    ("Other", Other),
+    ("Locals", Locals),
+    ("Control", Control),
+    ("Allocator", Allocator),
+    ("Empty", Empty),
+  ];
+  pub const NumEffectBits: u8 = 6;
+}
+pub mod effect_types {
+  pub type EffectBits = u8;
+}
+pub mod abstract_heaps {
+  use super::*;
+  pub const Allocator: AbstractHeap = AbstractHeap::from_bits(bits::Allocator);
+  pub const Any: AbstractHeap = AbstractHeap::from_bits(bits::Any);
+  pub const Control: AbstractHeap = AbstractHeap::from_bits(bits::Control);
+  pub const Empty: AbstractHeap = AbstractHeap::from_bits(bits::Empty);
+  pub const Frame: AbstractHeap = AbstractHeap::from_bits(bits::Frame);
+  pub const Locals: AbstractHeap = AbstractHeap::from_bits(bits::Locals);
+  pub const Memory: AbstractHeap = AbstractHeap::from_bits(bits::Memory);
+  pub const Other: AbstractHeap = AbstractHeap::from_bits(bits::Other);
+  pub const PC: AbstractHeap = AbstractHeap::from_bits(bits::PC);
+  pub const Stack: AbstractHeap = AbstractHeap::from_bits(bits::Stack);
+}
+pub mod effects {
+  use super::*;
+  pub const Allocator: Effect = Effect::promote(abstract_heaps::Allocator);
+  pub const Any: Effect = Effect::promote(abstract_heaps::Any);
+  pub const Control: Effect = Effect::promote(abstract_heaps::Control);
+  pub const Empty: Effect = Effect::promote(abstract_heaps::Empty);
+  pub const Frame: Effect = Effect::promote(abstract_heaps::Frame);
+  pub const Locals: Effect = Effect::promote(abstract_heaps::Locals);
+  pub const Memory: Effect = Effect::promote(abstract_heaps::Memory);
+  pub const Other: Effect = Effect::promote(abstract_heaps::Other);
+  pub const PC: Effect = Effect::promote(abstract_heaps::PC);
+  pub const Stack: Effect = Effect::promote(abstract_heaps::Stack);
+}
diff --git a/zjit/src/hir_effect/mod.rs b/zjit/src/hir_effect/mod.rs
new file mode 100644
index 0000000000..b1d7b27411
--- /dev/null
+++ b/zjit/src/hir_effect/mod.rs
@@ -0,0 +1,420 @@
+//! High-level intermediate representation effects.
+
+#![allow(non_upper_case_globals)]
+use crate::hir::{PtrPrintMap};
+include!("hir_effect.inc.rs");
+
+// NOTE: Effect very intentionally does not support Eq or PartialEq; we almost never want to check
+// bit equality of types in the compiler but instead check subtyping, intersection, union, etc.
+/// The AbstractHeap struct is the main work horse of effect inference and specialization. The main interfaces
+/// will look like:
+///
+/// * is AbstractHeap A a subset of AbstractHeap B
+/// * union/meet AbstractHeap A and AbstractHeap B
+///
+/// or
+///
+/// * is Effect A a subset of Effect B
+/// * union/meet Effect A and Effect B
+///
+/// The AbstractHeap is the work horse because Effect is simply 2 AbstractHeaps; one for read, and one for write.
+/// Currently, the abstract heap is implemented as a bitset. As we enrich our effect system, this will be updated
+/// to match the name and use a heap implementation, roughly aligned with
+/// <https://gist.github.com/pizlonator/cf1e72b8600b1437dda8153ea3fdb963>.
+///
+/// Most questions can be rewritten in terms of these operations.
+///
+/// Lattice Top corresponds to the "Any" effect. All bits are set and any effect is possible.
+/// Lattice Bottom corresponds to the "None" effect. No bits are set and no effects are possible.
+/// Elements between abstract_heaps have effects corresponding to the bits that are set.
+/// This enables more complex analyses compared to prior ZJIT implementations such as "has_effect",
+/// a function that returns a boolean value. Such functions impose an implicit single bit effect
+/// system. This explicit design with a lattice allows us many bits for effects.
+#[derive(Clone, Copy, Debug)]
+pub struct AbstractHeap {
+    bits: effect_types::EffectBits
+}
+
+#[derive(Clone, Copy, Debug)]
+pub struct Effect {
+    /// Unlike ZJIT's type system, effects do not have a notion of subclasses.
+    /// Instead of specializations, the Effect struct contains two AbstractHeaps.
+    /// We distinguish between read effects and write effects.
+    /// Both use the same effects lattice, but splitting into two heaps allows
+    /// for finer grained optimization.
+    ///
+    /// For instance:
+    /// We can elide HIR instructions with no write effects, but the read effects are necessary for instruction
+    /// reordering optimizations.
+    ///
+    /// These fields should not be directly read or written except by internal `Effect` APIs.
+    read: AbstractHeap,
+    write: AbstractHeap
+}
+
+/// Print adaptor for [`AbstractHeap`]. See [`PtrPrintMap`].
+pub struct AbstractHeapPrinter<'a> {
+    inner: AbstractHeap,
+    ptr_map: &'a PtrPrintMap,
+}
+
+impl<'a> std::fmt::Display for AbstractHeapPrinter<'a> {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        let effect = self.inner;
+        let mut bits = effect.bits;
+        let mut sep = "";
+        // First, make sure patterns are sorted from higher order bits to lower order.
+        // For each match where `bits` contains the pattern, we mask off the matched bits
+        // and continue searching for matches until bits == 0.
+        // Our first match could be exact and may not require a separator, but all subsequent
+        // matches do.
+        debug_assert!(bits::AllBitPatterns.is_sorted_by(|(_, left), (_, right)| left > right));
+        for (name, pattern) in bits::AllBitPatterns {
+            if (bits & pattern) == pattern {
+                write!(f, "{sep}{name}")?;
+                sep = "|";
+                bits &= !pattern;
+            }
+            // The `sep != ""` check allows us to handle the effects::None case gracefully.
+            if (bits == 0) & (sep != "") { break; }
+        }
+        debug_assert_eq!(bits, 0, "Should have eliminated all bits by iterating over all patterns");
+        Ok(())
+    }
+}
+
+impl std::fmt::Display for AbstractHeap {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        self.print(&PtrPrintMap::identity()).fmt(f)
+    }
+}
+
+/// Print adaptor for [`Effect`]. See [`PtrPrintMap`].
+pub struct EffectPrinter<'a> {
+    inner: Effect,
+    ptr_map: &'a PtrPrintMap,
+}
+
+impl<'a> std::fmt::Display for EffectPrinter<'a> {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        write!(f, "{}, {}", self.inner.read, self.inner.write)
+    }
+}
+
+impl std::fmt::Display for Effect {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
+        self.print(&PtrPrintMap::identity()).fmt(f)
+    }
+}
+
+impl AbstractHeap {
+    const fn from_bits(bits: effect_types::EffectBits) -> Self {
+        Self { bits }
+    }
+
+    pub const fn union(&self, other: Self) -> Self {
+        Self::from_bits(self.bits | other.bits)
+    }
+
+    pub const fn intersect(&self, other: Self) -> Self {
+        Self::from_bits(self.bits & other.bits)
+    }
+
+    pub const fn exclude(&self, other: Self) -> Self {
+        Self::from_bits(self.bits - (self.bits & other.bits))
+    }
+
+    /// Check bit equality of two `Effect`s. Do not use! You are probably looking for [`Effect::includes`].
+    /// This function is intentionally made private.
+    const fn bit_equal(&self, other: Self) -> bool {
+        self.bits == other.bits
+    }
+
+    pub const fn includes(&self, other: Self) -> bool {
+        self.bit_equal(
+            self.union(other)
+        )
+    }
+
+    pub const fn overlaps(&self, other: Self) -> bool {
+        !abstract_heaps::Empty.includes(
+            self.intersect(other)
+        )
+    }
+
+    pub const fn print(self, ptr_map: &PtrPrintMap) -> AbstractHeapPrinter<'_> {
+        AbstractHeapPrinter { inner: self, ptr_map }
+    }
+}
+
+impl Effect {
+    pub const fn read_write(read: AbstractHeap, write: AbstractHeap) -> Effect {
+        Effect { read, write }
+    }
+
+    /// This function addresses the special case where the read and write heaps are the same
+    pub const fn promote(heap: AbstractHeap) -> Effect {
+        Effect {read: heap, write: heap }
+    }
+
+    /// This function accepts write and heaps read to Any
+    pub const fn write(write: AbstractHeap) -> Effect {
+        Effect { read: abstract_heaps::Any, write }
+    }
+
+    /// This function accepts read and heaps read to Any
+    pub const fn read(read: AbstractHeap) -> Effect {
+        Effect { read, write: abstract_heaps::Any }
+    }
+
+    /// Method to access the private read field
+    pub const fn read_bits(&self) -> AbstractHeap {
+        self.read
+    }
+
+    /// Method to access the private write field
+    pub const fn write_bits(&self) -> AbstractHeap {
+        self.write
+    }
+
+    pub const fn union(&self, other: Effect) -> Effect {
+        Effect::read_write(
+            self.read.union(other.read),
+            self.write.union(other.write)
+        )
+    }
+
+    pub const fn intersect(&self, other: Effect) -> Effect {
+        Effect::read_write(
+            self.read.intersect(other.read),
+            self.write.intersect(other.write)
+        )
+    }
+
+    pub const fn exclude(&self, other: Effect) -> Effect {
+        Effect::read_write(
+            self.read.exclude(other.read),
+            self.write.exclude(other.write)
+        )
+    }
+
+    /// Check bit equality of two `Effect`s. Do not use! You are probably looking for [`Effect::includes`].
+    /// This function is intentionally made private.
+    const fn bit_equal(&self, other: Effect) -> bool {
+        self.read.bit_equal(other.read) & self.write.bit_equal(other.write)
+    }
+
+    pub const fn includes(&self, other: Effect) -> bool {
+        self.bit_equal(Effect::union(self, other))
+    }
+
+    pub const fn overlaps(&self, other: Effect) -> bool {
+        Effect::promote(abstract_heaps::Empty).includes(
+            self.intersect(other)
+        )
+    }
+
+    pub const fn print(self, ptr_map: &PtrPrintMap) -> EffectPrinter<'_> {
+        EffectPrinter { inner: self, ptr_map }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[track_caller]
+    fn assert_heap_bit_equal(left: AbstractHeap, right: AbstractHeap) {
+        assert!(left.bit_equal(right), "{left} bits are not equal to {right} bits");
+    }
+
+    #[track_caller]
+    fn assert_subeffect_heap(left: AbstractHeap, right: AbstractHeap) {
+        assert!(right.includes(left), "{left} is not a subeffect heap of {right}");
+    }
+
+    #[track_caller]
+    fn assert_not_subeffect_heap(left: AbstractHeap, right: AbstractHeap) {
+        assert!(!right.includes(left), "{left} is a subeffect heap of {right}");
+    }
+
+    #[track_caller]
+    fn assert_bit_equal(left: Effect, right: Effect) {
+        assert!(left.bit_equal(right), "{left} bits are not equal to {right} bits");
+    }
+
+    #[track_caller]
+    fn assert_subeffect(left: Effect, right: Effect) {
+        assert!(right.includes(left), "{left} is not a subeffect of {right}");
+    }
+
+    #[track_caller]
+    fn assert_not_subeffect(left: Effect, right: Effect) {
+        assert!(!right.includes(left), "{left} is a subeffect of {right}");
+    }
+
+    #[test]
+    fn effect_heap_none_is_subeffect_of_everything() {
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Empty);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Control);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Frame);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Stack);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Locals);
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Allocator);
+    }
+
+    #[test]
+    fn effect_heap_everything_is_subeffect_of_any() {
+        assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Any, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Control, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Frame, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Memory, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Locals, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::PC, abstract_heaps::Any);
+    }
+
+    #[test]
+    fn effect_heap_union_never_shrinks() {
+        // iterate over all effect entries from bottom to top
+        for i in [0, 1, 4, 6, 10, 15] {
+            let e = AbstractHeap::from_bits(i);
+            // Testing on bottom, top, and some arbitrary element in the middle
+            assert_subeffect_heap(abstract_heaps::Empty, abstract_heaps::Empty.union(e));
+            assert_subeffect_heap(abstract_heaps::Any, abstract_heaps::Any.union(e));
+            assert_subeffect_heap(abstract_heaps::Frame, abstract_heaps::Frame.union(e));
+        }
+    }
+
+    #[test]
+    fn effect_heap_intersect_never_grows() {
+        // Randomly selected values from bottom to top
+        for i in [0, 3, 6, 8, 15] {
+            let e = AbstractHeap::from_bits(i);
+            // Testing on bottom, top, and some arbitrary element in the middle
+            assert_subeffect_heap(abstract_heaps::Empty.intersect(e), abstract_heaps::Empty);
+            assert_subeffect_heap(abstract_heaps::Any.intersect(e), abstract_heaps::Any);
+            assert_subeffect_heap(abstract_heaps::Frame.intersect(e), abstract_heaps::Frame);
+        }
+    }
+
+    #[test]
+    fn effect_heap_self_is_included() {
+        assert!(abstract_heaps::Stack.includes(abstract_heaps::Stack));
+        assert!(abstract_heaps::Any.includes(abstract_heaps::Any));
+        assert!(abstract_heaps::Empty.includes(abstract_heaps::Empty));
+    }
+
+    #[test]
+    fn effect_heap_frame_includes_stack_locals_and_pc() {
+        assert_subeffect_heap(abstract_heaps::Stack, abstract_heaps::Frame);
+        assert_subeffect_heap(abstract_heaps::Locals, abstract_heaps::Frame);
+        assert_subeffect_heap(abstract_heaps::PC, abstract_heaps::Frame);
+    }
+
+    #[test]
+    fn effect_heap_frame_is_stack_locals_and_pc() {
+        let union = abstract_heaps::Stack.union(abstract_heaps::Locals.union(abstract_heaps::PC));
+        assert_heap_bit_equal(abstract_heaps::Frame, union);
+    }
+
+    #[test]
+    fn effect_heap_any_includes_some_subeffects() {
+        assert_subeffect_heap(abstract_heaps::Allocator, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Frame, abstract_heaps::Any);
+        assert_subeffect_heap(abstract_heaps::Memory, abstract_heaps::Any);
+    }
+
+    #[test]
+    fn effect_heap_display_exact_bits_match() {
+        assert_eq!(format!("{}", abstract_heaps::Empty), "Empty");
+        assert_eq!(format!("{}", abstract_heaps::PC), "PC");
+        assert_eq!(format!("{}", abstract_heaps::Any), "Any");
+        assert_eq!(format!("{}", abstract_heaps::Frame), "Frame");
+        assert_eq!(format!("{}", abstract_heaps::Stack.union(abstract_heaps::Locals.union(abstract_heaps::PC))), "Frame");
+    }
+
+    #[test]
+    fn effect_heap_display_multiple_bits() {
+        assert_eq!(format!("{}", abstract_heaps::Stack.union(abstract_heaps::Locals.union(abstract_heaps::PC))), "Frame");
+        assert_eq!(format!("{}", abstract_heaps::Stack.union(abstract_heaps::Locals)), "Stack|Locals");
+        assert_eq!(format!("{}", abstract_heaps::PC.union(abstract_heaps::Allocator)), "PC|Allocator");
+    }
+
+    #[test]
+    fn effect_any_includes_everything() {
+        assert_subeffect(effects::Allocator, effects::Any);
+        assert_subeffect(effects::Frame, effects::Any);
+        assert_subeffect(effects::Memory, effects::Any);
+        // Let's do a less standard effect too
+        assert_subeffect(
+            Effect::read_write(abstract_heaps::Control, abstract_heaps::Any),
+            effects::Any
+        );
+    }
+
+    #[test]
+    fn effect_union_is_idempotent() {
+        assert_bit_equal(
+            Effect::read(abstract_heaps::Any)
+                .union(Effect::write(abstract_heaps::Any)),
+            effects::Any
+        );
+        assert_bit_equal(
+            effects::Empty.union(effects::Empty),
+            effects::Empty
+        );
+    }
+
+    #[test]
+    fn effect_union_contains_and_excludes() {
+        assert_subeffect(
+            effects::Control.union(effects::Frame),
+            effects::Any
+        );
+        assert_not_subeffect(
+            effects::Frame.union(effects::Locals),
+            effects::PC
+        );
+    }
+
+    #[test]
+    fn effect_intersect_is_empty() {
+        assert_subeffect(effects::Memory.intersect(effects::Control), effects::Empty);
+        assert_subeffect(
+            Effect::read_write(abstract_heaps::Allocator, abstract_heaps::Other)
+                .intersect(Effect::read_write(abstract_heaps::Stack, abstract_heaps::PC)),
+            effects::Empty
+        )
+    }
+
+    #[test]
+    fn effect_intersect_exact_match() {
+        assert_subeffect(effects::Frame.intersect(effects::PC), effects::PC);
+        assert_subeffect(effects::Allocator.intersect(effects::Allocator), effects::Allocator);
+    }
+
+    #[test]
+    fn effect_display_exact_bits_match() {
+        assert_eq!(format!("{}", effects::Empty), "Empty, Empty");
+        assert_eq!(format!("{}", effects::PC), "PC, PC");
+        assert_eq!(format!("{}", effects::Any), "Any, Any");
+        assert_eq!(format!("{}", effects::Frame), "Frame, Frame");
+        assert_eq!(format!("{}", effects::Stack.union(effects::Locals.union(effects::PC))), "Frame, Frame");
+        assert_eq!(format!("{}", Effect::write(abstract_heaps::Control)), "Any, Control");
+        assert_eq!(format!("{}", Effect::read_write(abstract_heaps::Allocator, abstract_heaps::Memory)), "Allocator, Memory");
+    }
+
+    #[test]
+    fn effect_display_multiple_bits() {
+        assert_eq!(format!("{}", effects::Stack.union(effects::Locals.union(effects::PC))), "Frame, Frame");
+        assert_eq!(format!("{}", effects::Stack.union(effects::Locals)), "Stack|Locals, Stack|Locals");
+        assert_eq!(format!("{}", effects::PC.union(effects::Allocator)), "PC|Allocator, PC|Allocator");
+        assert_eq!(format!("{}", Effect::read_write(abstract_heaps::Other, abstract_heaps::PC)
+            .union(Effect::read_write(abstract_heaps::Memory, abstract_heaps::Stack))),
+            "Memory, Stack|PC"
+        );
+    }
+
+}
diff --git a/zjit/src/lib.rs b/zjit/src/lib.rs
index e7420c16dd..a79989c912 100644
--- a/zjit/src/lib.rs
+++ b/zjit/src/lib.rs
@@ -15,6 +15,7 @@ mod cruby;
 mod cruby_methods;
 mod hir;
 mod hir_type;
+mod hir_effect;
 mod codegen;
 mod stats;
 mod cast;