From c3958e34c0de21df52e57e47e4f47ffe6464f138 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 09:29:42 -0700 Subject: Graph updates; readme updates --- chapter13/README.md | 180 ++++++++++++++++++---------------------------------- 1 file changed, 62 insertions(+), 118 deletions(-) (limited to 'chapter13/README.md') diff --git a/chapter13/README.md b/chapter13/README.md index 38b512cc..ae1d378b 100644 --- a/chapter13/README.md +++ b/chapter13/README.md @@ -3,45 +3,41 @@ [Previous: Chapter 12](../chapter12/README.md) | [Next: Chapter 14](../chapter14/README.md) -Memory retains one `$mem` binding and lazy partitions. Typed initialization -stores now include each field's declared type and initialization flag, while -`MemMerge` preserves the other fields. Start and Return keep control in slot 0 -and memory in slot 1. - # Table of Contents 1. [References](#references) - [Forward References](#forward-references) - [Self-referential references](#self-referential-references) - [Auto deepen forward ref types](#auto-deepen-forward-ref-types) -2. [Global Code Motion Example](#global-code-motion-walkthrough) -In this chapter, we add references and structs. +In this chapter, we extend structs to allow for forward and cyclic references. You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter13) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter12...linear-chapter13) it to the previous chapter. -## References - -Structs can reference other structs; references can be mutually recursive. -Any reference field can allow null or not, same as a normal variable. - -### Forward References -A forward reference occurs when a type or identifier is used before its full definition is -encountered by the compiler. (incomplete types, mutual references). -When forward-reference types are encountered, the compiler may initially treat them as placeholders or "shallow" representations. +## Forward References +A forward reference occurs when a type or identifier is used before its full +definition is encountered by the compiler. (incomplete types, mutual +references). When forward-reference types are encountered, the compiler may +initially treat them as placeholders or "shallow" representations. -Consider the following code: ```java struct Person { -String name; // No string type, yet -int age; -FamilyTree? tree; // A family tree, or not + String name; // No string type, yet + int age; + FamilyTree? tree; // A family tree, or not } -... ``` -At the time of the `Person` struct definition, the `FamilyTree` struct is not yet defined. This is a forward reference. To handle this, we assume the struct will be defined later. + +[edit: Show the TypeStruct mapping] + +At the time of the `Person` struct definition, the `FamilyTree` struct is not +yet defined. This is a forward reference. To handle this, we assume the struct +will be defined later. + +[edit: swap to code reference] + ```java Type t = TYPES.get(tname); // Assume a forward-reference type @@ -56,55 +52,25 @@ Type t = TYPES.get(tname); _lexer._position = old2; } ``` + Reference fields start out as null, doing anything with them will result in a compile time error. ```java struct Person { - String name; - int age; - FamilyTree? tree; + String name; + int age; + FamilyTree? tree; } Person p = new Person; -p.tree.la = null; // Accessing unknown field 'la' from 'null' - +p.tree.left = null; // Accessing unknown field 'left' from 'null' ``` -It turns out `p.tree` is `null`, so we can't access the field `la` from it. -```java -// name = "tree" -// mem() is the current aggregate; its tree alias selects the initializing Store. -// in(3) = {ConstantNode@1651} "null" -return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); -``` -`LoadNode::idealize` -LoadNode first selects its alias through any MemMerge, then returns `st.val()` -when it finds a matching Store to the same object. -```java - // Simple Load-after-Store on same address. - if( mem() instanceof StoreNode st && - ptr() == st.ptr() && _alias == st._alias ) { // Same object and field - assert _name.equals(st._name); // Equiv class aliasing is perfect - return st.val(); // // <<-- {ConstantNode@1651} "null" - } -``` -After alias selection, the Load's `mem()` refers to that initializing Store. -In the next iteration, we will end up with: +It turns out `p.tree` is `null`, so we can't access the field `left` from it. -```java -... -// expr {ConstantNode@1651} "null" -// ptr = expr._type -// ptr = TypeMemPtr@1510 "null" -// ptr._obj._name = $TOP -TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); -int idx = base==null ? -1 : base.find(name); // <<-- null -if( idx == -1 ) { - throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); // throws here!!! -} -``` When we are creating the struct, we set up the initial value to Null: `newStruct`: + ```java private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); @@ -160,17 +126,9 @@ This creates a circular reference. To resolve this, we auto deepen the forward r #### Auto deepen forward ref types -Auto deepening refers to the process where the compiler expands the forward reference into its complete definition. -When `a.next` is encountered, we auto deepen the type so its fields are going to be set. - -This is needed to resolve the stale type that the loop brings around. - -```java -if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) { - e = tmp.make_from((TypeStruct) TYPES.get(tmp._obj._name)); -} -``` +Auto deepening refers to the process where the compiler expands the forward reference into its complete definition. +Here we have a simple linked list implementation, with the payload being a `int`. ```java struct LLI { LLI? next; int i; } @@ -182,12 +140,23 @@ while( arg ) { head = x; arg = arg-1; } -if( !head ) return 0; +if( !head ) return 0; LLI? next = head.next; if( next==null ) return 1; return next.i; ``` +When `a.next` is encountered, we auto deepen the type so its fields are going to be set. + +This is needed to resolve the stale type that the loop brings around. + +```java +if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) { + e = tmp.make_from((TypeStruct) TYPES.get(tmp._obj._name)); +} +``` + + --- Normal field syntax works: @@ -208,62 +177,37 @@ And: ```java struct N { N next; int i; } N n = new N; -n.next = null; // <<-- Compile error, cannot store null into not-null field +n.next = null; // Error, cannot store null into not-null field return n.next; ``` Forward references must be specified later and field access is later checked. -## Global Code Motion walkthrough -Now that we have all these new features covered consider the following example: -```java -struct Person { - String name; - int age; - FamilyTree? tree; -} -Person p = new Person; -p.age =1; -return p.age; -``` -Reverse post order: Traverse nodes before their children. (Opposite of post order). -Loop through the post order list from the end to the beginning. -RPO = `[StartNode, CProjNode("ctrl"), ReturnNode("return 1"), StopNode("return 1"), XctrlNode("Xctrl")]` -> all the control nodes. - -Remember, with constants we want to schedule them to the deepest basic block. -For example a constant node will have StartNode as its in(0) but we can find a better replacement. -Early schedule: - -Does not change anything here: - -#### Early schedule: -``` -From: Start to: Start|#1(18) -From: Start to: Start|#null(12) -From: $ctrl to: $ctrl|.name=(13) -From: $ctrl to: $ctrl|.age=(19) -From: $ctrl to: $ctrl|.tree=(17) +## `LoadNode::idealize` +LoadNode first selects its alias through any MemMerge, then returns `st.val()` +when it finds a matching Store to the same object. +```java + // Simple Load-after-Store on same address. + if( mem() instanceof StoreNode st && + ptr() == st.ptr() && _alias == st._alias ) { // Same object and field + assert _name.equals(st._name); // Equiv class aliasing is perfect + return st.val(); // // <<-- {ConstantNode@1651} "null" + } ``` -The control nodes are already set so the early schedule is useless. -All the nodes involved: Return, Constant, NewNode specify their control input explicitly so there is nothing to do. +After alias selection, the Load's `mem()` refers to that initializing Store. +In the next iteration, we will end up with: -#### Late schedule: -``` -From: Start to: $ctrl(12) -From: Start to: $ctrl(18) -``` -We see that the late schedule actually changes the control input of the StartNode to the $ctrl node in 2 cases. -The algo that does this is: ```java - // Walk up from the LCA to the early, looking for best place. This is -// the lowest execution frequency, approximated by least loop depth and -// deepest control flow. -CFGNode best = lca; -lca = lca.idom(); // Already found best for starting LCA -for( ; lca != early.idom(); lca = lca.idom() ) - if( better(lca,best) ) - best = lca; -assert !(best instanceof IfNode); +... +// expr {ConstantNode@1651} "null" +// ptr = expr._type +// ptr = TypeMemPtr@1510 "null" +// ptr._obj._name = $TOP +TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); +int idx = base==null ? -1 : base.find(name); // <<-- null +if( idx == -1 ) { + throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); // throws here!!! +} ``` -- cgit v1.2.3