summaryrefslogtreecommitdiff
path: root/chapter04/README.md
Commit message (Collapse)AuthorAgeFilesLines
* Remove -disablePeepholeCliff Click2026-09-271-3/+0
|
* Extend and backport SubNode peephole (#254)Hsiang-Ying Fu2026-09-251-0/+4
| | | | | | | | | | | | | | | * Extend and backport SubNode peephole * Add tests * Restrict subtraction zero peepholes to integer operands Require resolved integer mode in chapter 25 so zero subtraction preserves floating-point signed zero. Keep nonnumeric operands in the graph for subtraction diagnostics. Add signed-zero coverage from chapter 12 and null-subtraction diagnostics from chapter 22. Confirmed the regressions fail on the original PR. Full Make suites pass in chapters 4-25 (5462 tests), including fresh chapter 25 sys.o compilation. --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Add shared graph viewer to all chaptersCliff Click2026-09-221-2/+2
|
* 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>
* 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>
* More lattice docs reworksCliff Click2025-01-151-13/+28
|
* 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-061-139/+5
|
* add example 2Tamas Hadhazy2024-10-061-1/+15
|
* fix typos, better graph positionTamas Hadhazy2024-10-061-2/+3
|
* ch4 extend DCETamas Hadhazy2024-10-061-4/+90
|
* dce initHels152024-10-061-0/+43
|
* 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-251-1/+122
|
* Updates READMECliff Click2024-09-071-9/+10
| | | | More on Types, pushed out Arrays one more chapter
* Backport tests (#87)Thalia Archibald2024-06-211-1/+1
| | | | | | | | | | | | | | | | | * 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-211-7/+7
| | | | | | | | | * Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces
* Documentation updates (#76)Dibyendu Majumdar2024-05-021-36/+33
| | | | | | | | | | | | | | | | | | * 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-151-2/+2
| | | Also fix broken links in README
* Backport some of the code refactoring to previous chapters (#50)Dibyendu Majumdar2023-12-071-10/+11
| | | | | | | | | | | * #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
* Backport changes in Chapter 5 to previous chapters and update Chapter5 ↵Dibyendu Majumdar2023-11-031-12/+15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* Add descriptions of the new node types in Chapter 5.dibyendumajumdar2023-11-011-1/+6
| | | | Add references to Cliff's thesis.
* Applied fix for #12 to chapter 3 (#15)Dibyendu Majumdar2023-10-271-1/+2
| | | | ScopeNode added to chapter 3 Revised the description for Chapter 3 and 4 to include ScopeNode.
* Add a description of proj nodes (#11)Dibyendu Majumdar2023-10-261-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-201-0/+229
* 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 22:50:36 +0000