From 34e7282dd7c58b49702c7ecd9f80a46398efd0c1 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 7 Feb 2025 08:58:36 -0800 Subject: Ch19 (#155) MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit * Initial push Major CodeGen cleanup; most static globals move into the CodeGen object. * Minor progress bug with mutual recursion * Add test from pr#148 * First cut x86 "port" Only "return 0;", no registers, no encoding, but yah gotta start somewhere * Update README.md * Update README.md * Update ListScheduler.java * command line launcher for simple Parser bug fref in args Some new test cases. * Add basic RegMask for more than 64 bits of register mask. Add calling convention basics to X86; con+ret RegMasks. GCM computes CFG for all users. Drop unused MultiUse. Pick up reg-pressure aware ListScheduler. Re-layout CodeGen file to get code & data chunks nearer each other. minor Ary extension * ASM Printer InstSel handles folding 2+ ideal ops into 1 machine op * handle instSel for some control flow Bool,If,CProj,Region,Phi Handle 2-op expansions Shuffle instSel graph walk back again. * Basic if-block inst selects and asm prints * Add mul-by-coinstant to shift * left shift codegen basic * exclude RSP from *write* mask * 2-arg add (not immediate) mul-by-small constant opt. Some utilities. * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * inst select for new struct allocation * Float, bitwise and arithmetic operands codegen x86-64 (#150) * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * Handle first loop Change inst sel walk again to pre-order, to set an early visit bit to stop cycles. CFGNode copies dom/loop info. Cmp not-immediate form. Ret/Fun lazy updates * float ops without imm values * merge * merge * inst select for new struct allocation * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * Remove non-exsting FP+imm ops * left shift codegen basic * sar codegen basic * merge * some basic ops * addf * divf, subf, mulf * rsp allowed in bitwise input, not output * formatting * float ops without imm values * merge * merge * Rebased on ch 19 * Update tests --------- Co-authored-by: Cliff Click * cleanup after merge alpha-sort helper fcns implicit test vs zero/null * Add LEA op asm print works on ideal nodes for all tests * Minor cleanup lea * x86 addressing modes during inst select Drop New taking inits; just follow with initializing stores. Simplifies inst selelection which otherwise needs to undo this optimization and emit following init stores. Basic load/store for now, op-to-mem comes later add same becomes Shl by 1. Drop DivF-immiedate * extended ch13, 14,15,16 (#153) * merge2 * merge3 * Fix a few minor fuzzer bugs * Force array layout ld/st get size (but not signed/unsigned) Add unsigned LT for later range checks. * Fix a bunch of float issues was deleting required inputs * simpler invariant defensive copy inputs for simpler invariant in complex sharing patterns inc/dec form (just the opcode now). * Call & CallR X86 instructions * Add-from-memory op Remove FP immediate forms. * Remove name from TFP Never shoulda been there (but was convenient for awhile). Moved into FunNode, found by checking the linker table with a TFP. * New (#154) * merge2 * merge3 * GCM for float ops fixed, other cleanup - small extensions * call setup * merge2 * remove debug prints add check for bad call convention fix 3 tests (bad merge?) * cleanup call convention abi Needs more love at some point... * one more cleanup ABI --------- Co-authored-by: Cliff Click * Add CmpMem form Common addressing mode print LEA can skip a base * Add a AddFMemX86 A bunch of mem op patterns are missing, hopefully they are just cut-n-paste from the existing patterns. * Docs * XMM reg mask fix Minor README updates * Allow inverted cmp/mem narrowing stores can bypass an AndMask Array length loads do not need control Some missing print info * Support "*ptr op= val" at least for MemAdd * missed golden rule update * Array len is u32 load-after-store zero/sign-extends if the store is truncating * One more missed case --------- Co-authored-by: hadha Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- chapter13/README.md | 231 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 222 insertions(+), 9 deletions(-) (limited to 'chapter13/README.md') diff --git a/chapter13/README.md b/chapter13/README.md index 5d3979ad..7feaba53 100644 --- a/chapter13/README.md +++ b/chapter13/README.md @@ -1,5 +1,13 @@ # Chapter 13: References +# 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. 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. @@ -9,22 +17,171 @@ You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linea 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. + + +Consider the following code: ```java struct Person { - String name; // No string type, yet +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. +```java +Type t = TYPES.get(tname); + // Assume a forward-reference type + if( t == null ) { + int old2 = _lexer._position; + String id = _lexer.matchId(); + if( id==null ) { + _lexer._position = old; + return null; + } + TYPES.put(tname,t = TypeStruct.make(tname)); // Assume forward ref + _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?; // A family tree, or not + FamilyTree? tree; +} +Person p = new Person; +p.tree.la = null; // Accessing unknown field 'la' from 'null' + +``` + +It turns out `p.tree` is `null`, so we can't access the field `la` from it. +```java +// name = "tree" +// memAlias(alias) = StoreNode +// in(3) = {ConstantNode@1651} "null" +return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole()); +``` +`LoadNode::idealize` +In LoadNode idealize we return st.val(). +```java + // Simple Load-after-Store on same address. + if( mem() instanceof StoreNode st && + ptr() == st.ptr() ) { // Must check same object + assert _name.equals(st._name); // Equiv class aliasing is perfect + return st.val(); // // <<-- {ConstantNode@1651} "null" + } +``` +`mem(): ` refers to `memAlias(alias)`. Therefore, in the next iteration, we will end up with: + +```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!!! } -struct FamilyTree { - Person father?; // FamilyTree can reference Person - Person mother?; - Person []kids?; +``` +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(); + int alias = START._aliasStarts.get(obj._name); + for( Field field : obj._fields ) { + memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); + alias++; + } + return n.unkeep(); } ``` +Zooming in.... + +```java +// parsing = FamilyTree? tree; +for( Field field : obj._fields ) { + // field._type = *FamilyTree? + // REMEMBER: + // @Override public TypeMemPtr makeInit() { return NULLPTR; } + memAlias(..., new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); + alias++; +} +``` +In a case of a reference `field._type.makeInit()` will return a `NULLPTR`, later this is what the peephole turns into when loading +the field. `p.tree` + +--- + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // Value reports as null, despite field typed as not-null +``` + +As shown above, we explicitly allow not-null fields to be null initialized. +(as of chapter13) +We can't allow null to be stored into a not-null field, but we can allow a not-null field to be null(initially). + + +### Self-referential references +Self-cyclic or self-referential types are types that include a reference to themsleves as part of their defintion. + +Consider the following code: +```java +struct N { N next; int i; } +N n = new N; +n.next = null; // <<-- Compile error, cannot store null into not-null field +return n.next; +``` +The field `next` is of type `N`, which is the same type as the structure `N` itself. +This creates a circular reference. To resolve this, we auto deepen the forward ref type. + + +#### 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)); +} +``` + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while( arg ) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.i; +``` + +--- Normal field syntax works: -e.g. `person.tree.father = new Person;` or - `person.tree.father.name = "Dad";`. +e.g. `person.tree.father = new Person;` or +`person.tree.father.name = "Dad";`. Reference fields all start out null, and can be tested as such. However, a non-null reference field can only be stored with a non-null ref. @@ -32,7 +189,7 @@ non-null reference field can only be stored with a non-null ref. ```java struct N { N next; int i; } N n = new N; -return n.next; // Value reports as null, despite field typed as not-null +return n.next.i; // Value reports as null, despite field typed as not-null ``` And: @@ -43,3 +200,59 @@ N n = new N; n.next = null; // <<-- Compile 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) +``` +The control nodes are already set so the early schedule is useless. +All the nodes involed: Return, Constant, NewNode specific their control input explicitly so there is nothing to do. + +#### 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); +``` \ No newline at end of file -- cgit v1.2.3