summaryrefslogtreecommitdiff
path: root/chapter04
Commit message (Collapse)AuthorAgeFilesLines
* Get makefiles and fuzzer testing uniform across chaptersCliff Click2026-09-171-0/+3
|
* Docs: Proj is not always a data node (#250)Symious2026-09-091-1/+4
| | | | | | | | | | | | | | | | | | | The node recap tables in chapters 4 and 5 classify `Proj` as "Data", but `ProjNode.isCFG()` has returned true for control projections since chapter 4: ch4: return _idx==0; ch5+: return _idx==0 || ctrl() instanceof IfNode; So `Proj#0` off `Start` is a control node, and from chapter 5 both projections off an `If` are too -- which is exactly why the dominator walk in `IfNode.compute()` can step through them. Change the Type column to "Data / Control" and add a note under each table pointing at `isCFG()`. Table alignment is unchanged: "Data / Control" is the same width as "Abstract class". Docs-only change. Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
* Fix typo: spline -> spine in AddNode (chapters 4-8) (#248)Symious2026-09-091-5/+5
| | | | | | | | | | | | | | | The add canonicalization builds a left-leaning chain of AddNodes -- the "spine" -- with off-spine operands hanging off each in(2). The comparator and its comments were spelled "spline" (a curve / mechanical part), which was already inconsistent with the goal comment in the same method: // Goal: a left-spine set of adds, with constants on the rhs Chapters 9 and later already use "spine" / "spine_cmp"; this brings the earlier chapters in line. Comment and private-method-name only, no behavior change. Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
* Backport renaming of `Type::_print()` in Chapter13 to earlier chapters (#244)Hsiang-Ying Fu2026-07-034-6/+6
|
* Move `addUse()` return statement to `keep()` (#243)Hsiang-Ying Fu2026-07-031-2/+2
|
* Cleanup (#162)RobertObkircher2025-02-161-1/+1
| | | | | | | | | * remove unused method lazyFRef * remove unused method copyF(Node, Node) * make TypeMemPtr constants final * make ConstantNode value final
* Ch19 (#155)Cliff Click2025-02-071-1/+19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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 <cliffc@acm.org> * 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 <cliffc@acm.org> * 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 <helsgithub15@gmail.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
* Add testRedeclareVar in all later chapterstannal2025-01-191-0/+10
|
* Test for "arg--2"Cliff Click2025-01-151-0/+6
| | | | Parse as "arg - -2" and not "arg-- 2" which is a syntax error
* More lattice docs reworksCliff Click2025-01-153-112/+270
|
* Upgrades to the Type lattice diagramsCliff Click2025-01-152-209/+210
|
* Link to linear history and tag chaptersThalia Archibald2024-10-231-0/+2
|
* Update DCE commentsCliff Click2024-10-061-5/+10
|
* add appendix section, dceTamas Hadhazy2024-10-062-139/+171
|
* add example 2Tamas Hadhazy2024-10-061-1/+15
|
* fix typos, better graph positionTamas Hadhazy2024-10-061-2/+3
|
* ch4 extend DCETamas Hadhazy2024-10-063-4/+265
|
* dce initHels152024-10-062-0/+143
|
* A bunch of rewording to get better flowCliff Click2024-09-291-89/+92
| | | | Fix a bunch of indent bugs.
* update readmeHels152024-09-251-15/+17
|
* replace constant fold version to argHels152024-09-251-6/+6
|
* extend opt and projnode docsHels152024-09-253-1/+286
|
* move x-x check up frontCliff Click2024-09-131-4/+4
|
* x-x==0Cliff Click2024-09-131-1/+6
| | | | | | Move x-x==0 to compute. Add x/1 ==> x All chapters
* Updates READMECliff Click2024-09-071-9/+10
| | | | More on Types, pushed out Arrays one more chapter
* Backport empty statement fixCliff Click2024-09-071-0/+1
| | | | | Split Ch13 tests from Chapter12Test.java Handle forward refs never defined.
* handle all unsigned int variantsCliff Click2024-09-071-0/+98
| | | | and-masking and typenames for all!
* Fix grammar and forward-port minor changes (#91)Thalia Archibald2024-07-011-2/+1
| | | | | | | | | | | | | | | * Backport test exception handling to chapter 1 * Add unary ! to chapter 10 and 11 grammars * Lex { } ! as punctuation * Forward-port format whitespace * Forward-port test organization * Forward-port replace build-graphs.sh with Makefile * Add chapter title to chapter 11
* Backport tests (#87)Thalia Archibald2024-06-218-216/+269
| | | | | | | | | | | | | | | | | * Fix unexpected number parse errors * Add chapter titles * Split test files by chapter * Backport rename Fuzzer08Test to FuzzerWrap * Replace graph build scripts with Makefile * Backport Chapter05Test.testRegress1 * Backport require space after 'return' * Backport check EOF after return statement
* Format whitespace (#86)Thalia Archibald2024-06-2128-93/+92
| | | | | | | | | * Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces
* Documentation updates (#76)Dibyendu Majumdar2024-05-024-36/+293
| | | | | | | | | | | | | | | | | | * More clearly explain why we do not have an AST in the implementation * Improve the description of type lattice. Cross reference to future chapters. * Minor update * Add lattice visual Revise the text describing meet. * minor update * Add a lattice visual to the text * Update the lattice visual. Add description of the new edges in the SoN graph
* Sync changes to previous chapters (#57)Dibyendu Majumdar2024-01-153-12/+7
| | | Also fix broken links in README
* Backport some of the code refactoring to previous chapters (#50)Dibyendu Majumdar2023-12-0714-183/+308
| | | | | | | | | | | * #44 Revise docs and comments * #44 Add starting scope to xScopes * #44 back some of the code refactoring port to previous chapters * #44 add_def should not be public * #44 add_def should not be public. Rename method names so that they are camelcase
* Chapter 6 (#38)Dibyendu Majumdar2023-11-1116-64/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #37 Create chapter 6 skeleton * #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too. We have a _type field that is like an enum. * #37 Revise Type.meet() - this is now final. Subclasses can override xmeet() which is protected but now handles simple types in Type itself. * #37 Basic test for peephole of CFG * #37 Revise compute of if * #37 Revise compute of if * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP peephole of If * #37 WIP fix the chars inserted by IntelliJ * #37 WIP Fix compute type in IfNode * #37 WIP Null check region inputs * #37 WIP Fix where we choose great grand parent instead of grand parent Add new test * #37 WIP More fixes and tests * #37 WIP Some minor adjustments * Cleanup folding dead IF tests Remove isDeadCtrl & just test for the constant. Remove DEAD_CTRL, doesn't properly reset between tests. Move keep/unkeep to Node. PhiNode has a proper compute() call. ProjNode ideal is a lot simpler. Region doesn't ever get a null. Move the mergeScopes Region peep till after all Phis are added. Type TOP and XCONTROL count as constants. TypeTuple gets a toString * #37 WIP Upate README * #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed * #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed * #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes * Region removes dead input paths Remove region-folding in Return, If. Add a Makefile. Reformat triple-quote lines to be emacs-friendly. * StopNode idealize Return type sharpens to include control input. * Remove !=, >=, >; use Not and <, <=, == Fix bug mixing rotating different ops. Generalize Add fold constants; apply to Mul, EQ. Fix Div.copy * Fix bug rotating e.g. < or <= Peep is only valid for associative ops * #37 WIP Doc updates * Work over the Ch6 Readme Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis. When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input. * Update chapter06/README.md Co-authored-by: Yichen Yan <oraluben@outlook.com> * Update chapter06/README.md Co-authored-by: Yichen Yan <oraluben@outlook.com> * #37 Backport type system changes to chapter 2 * #37 Backport type system changes to chapter 3 * #37 Backport type system changes to chapter 4 * #37 Backport type system changes to chapter 5 * #37 Merge chapter 5 updates from main. Remove language grammar module as we describe the grammar incrementally in each chapter. * #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole * #37 Sync some updates to chapter 2 * #37 Sync some updates to chapter 3 * #37 Sync some updates to chapter 4 --------- Co-authored-by: Cliff Click <cliffc@acm.org> Co-authored-by: Yichen Yan <oraluben@outlook.com>
* Backport changes in Chapter 5 to previous chapters and update Chapter5 ↵Dibyendu Majumdar2023-11-0323-367/+485
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | documentation (#34) * Backport changes from chapter 5 to older chapters (#30) * Fix wrong indent * Backport to chapter 4 * Backport to chapter 3 * Backport to chapter 2 * Backport to chapter 1 * Add if statement to comment (#32) * Update visuals for chapters 1,2 & 3. Reenable drawing of edges from constants to Start for these chapters. * Update visuals for chapters 4. Revise text to explain the labeling of edges in graphs and that we omit edge from Constant to Start nodes from chapter 4. * Add code snippets for if statement parsing and the duplication and merging of ScopeNodes. Explain how scopeNodes are duplicated and merged. * Add constant check to minus node (#31) * Fix closing root block with } (#33) * Backport fix closing root block with } to chapter 4 and 3 (#35) * Show use-def edge from Phi to Region as dotted edge. Add example of Phi peephole. Update visuals. Add more examples. * Fix visuals in chapter 1 and README in chapter 4. * Remove subheading * Adjust spaces --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
* Bail out unclosed block (#25)Yichen Yan2023-11-012-5/+20
| | | | | | | | | * Report unclosed block in parsing * Fix tests * Resolve comments and rebase onto chapter5 * Test `isEOF` after consume whitespaces
* Fix div-by-0, some javadocCliff Click2023-11-012-5/+5
| | | | | higher level parsers can return null, but their return is ignored anycase. div-by-0 is defined to be 0, backported to ch2,3,4,5
* Add descriptions of the new node types in Chapter 5.dibyendumajumdar2023-11-011-1/+6
| | | | Add references to Cliff's thesis.
* set_def might kill new_def in kill recursion caused by old_def being killed ↵XmiliaH2023-10-282-3/+12
| | | | (#18)
* Remove true and false from grammar as the parser does not recognise them (#17)XmiliaH2023-10-281-2/+0
|
* Applied fix for #12 to chapter 3 (#15)Dibyendu Majumdar2023-10-272-1/+4
| | | | ScopeNode added to chapter 3 Revised the description for Chapter 3 and 4 to include ScopeNode.
* Replace Parser scopes with ScopeNode (#14)Cliff Click2023-10-267-73/+191
| | | | | | | | | | | | | | | Fixes #12 * Replace Parser scopes with ScopeNode Basically move the Stack of HashMaps to a ScopeNode, with wrappers. The HashMap maps String names to Integer indices; inputs to the ScopeNode. This way, the ScopeNode keeps alive Nodes that are only alive because they are alive in the HashMap. Fix bug isDead -> isUnused in deadCodeElim. Support routines for adding/removing edges in ScopeNode. Set $ctrl to null after a Return; there is no control. Regression tests. * One more test case
* Add a description of proj nodes (#11)Dibyendu Majumdar2023-10-262-0/+13
| | | | | * Add a description of proj nodes * Add a description of proj nodes
* Revision of docs (#10)Dibyendu Majumdar2023-10-211-4/+4
| | | | | | | | | * Port updates back to chapter 2 * Update older visuals to match new format * Update older visuals to match new format * update docs
* Add the second diagram that got lost. (#9)Dibyendu Majumdar2023-10-201-0/+4
|
* Chapter4 (#8)Cliff Click2023-10-2028-0/+2458
* Initial work on chapter 4. Updated language grammar for chapter 4 Enhanced Parser to implement comparison operators Parser now allows setting 'arg' as input parameter to program The StartNode now has a tuple as result with two values. We set up two projection nodes as output of Start - the first is bound to scope as '$ctrl' and second as 'arg'. Return node now obtains the ctrl input by looking up '$ctrl' in scope; thus it gets the projection node. Added TypeTuple - represents a tuple of values. This is the type of Start. Added BoolNode - for comparison operators. Added MultiNode - interface for nodes that generate tuple results. Start implements this interface. Added ProjNode - projections to extract values from Start node. Each projection takes a MultiNode and an index value. Initial writeup of chapter 4 in README. GraphVisualizer now searches node outputs as well to locate all nodes * Add TypeControl. The first member of Start's tuple is of TypeControl. Correct the projType() method * Quote port names in edges as unquoted $ctrl is not valid. Revise how we decide an edge is a control edge so that it works correctly for projections. * We used to compute initial type in Node but this is problematic for new node types such as ProjNode and BoolNode as the construction is not yet complete when Node calls compute(). So we have to move compute() call down to the sub type's constructor. Add some tests for comparison ops. * Describe the $ctrl name binding and how it represents the Ptri net model. Add a diagram to show why we need algebraic manipulation of expressions. * Implement a simplification for expressions such as (con1 + arg) + con2 -> arg + con3 con1 + (arg + con2) -> arg + con3 * Add diagram to show what the graph looks like post peephole * Explain projection nodes * Cleanup Chapter 4, add peepholes. Add like 6 peepholes. Replace the 2 prior ones with 1-liners. BoolNode: replace the switch with 6 1-line classes. Giant comment discussion on idealize() calling convention. TypeInteger shorten isTop and isBot, and use them instead of calling "equals()". * 2 more peeps, no tests yet * Cleanup Chapter 4 `peephole()` kills nodes killed by `idealize()` calls... and works recursively. This requires keeping "mid-peephole" nodes alive. The edge-swap code in Add and Mul now keeps their inputs alive mid-swap. MultiNode is a class, not an interface. Move the initial 'compute()' to peephole, instead of requiring each constructor to do it. Start and Constant remember their original types, even if the `_type` field changes. `kill()` flags nodes as DEAD. Print DEAD nodes with "DEAD". Change recursive `_print()` to a tik-tok style, so each individual print does not need to handle DEAD printing. This printing will soon need a "visit" bit to avoid infinite recursion. Projs pick up a debugging name. GraphViz: combine Multis and their Projs. Drop Constant inputs from Start. Fix coloring Control edges red. * minor WS cleanup * Cleaned up Node.peephole Use a smart DCE call after peephole. More comments. Tidy interfaces. * minor comment cleanup * But the proj nodes inside a table * No need to set column span on multi node as we put the proj nodes in a table * Update the dot diagrams * Rename method to make it more obvious to the reader * Start to add a description of peephole * Rename del() to delUse() and make it an instance method as it reads better that way. Add new method addUse() again to improve readability. Adjust removeDeadCode() to make the intention clear. * Update docs explaining how peephole works Update the diagrams * Fix errors * Add diagram to show what the graph looks like post peephole * 2 more peeps, no tests yet * Cleanup Chapter 4 `peephole()` kills nodes killed by `idealize()` calls... and works recursively. This requires keeping "mid-peephole" nodes alive. The edge-swap code in Add and Mul now keeps their inputs alive mid-swap. MultiNode is a class, not an interface. Move the initial 'compute()' to peephole, instead of requiring each constructor to do it. Start and Constant remember their original types, even if the `_type` field changes. `kill()` flags nodes as DEAD. Print DEAD nodes with "DEAD". Change recursive `_print()` to a tik-tok style, so each individual print does not need to handle DEAD printing. This printing will soon need a "visit" bit to avoid infinite recursion. Projs pick up a debugging name. GraphViz: combine Multis and their Projs. Drop Constant inputs from Start. Fix coloring Control edges red. * minor WS cleanup * Cleaned up Node.peephole Use a smart DCE call after peephole. More comments. Tidy interfaces. * minor comment cleanup * But the proj nodes inside a table * No need to set column span on multi node as we put the proj nodes in a table * Update the dot diagrams * Rename method to make it more obvious to the reader * Start to add a description of peephole * Rename del() to delUse() and make it an instance method as it reads better that way. Add new method addUse() again to improve readability. Adjust removeDeadCode() to make the intention clear. * Update docs explaining how peephole works Update the diagrams * Minor cleanups Split isUnused from isDead, with comments. Rename removeDeadCode back to deadCodeElim after discussion; matches the historical compiler wording. Fixup large javadoc example with a table. * match doc and code * Fix name of method * Fix name of method --------- Co-authored-by: dibyendumajumdar <mobile@majumdar.org.uk>
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 09:10:55 +0000