summaryrefslogtreecommitdiff
path: root/chapter05
Commit message (Collapse)AuthorAgeFilesLines
* Get makefiles and fuzzer testing uniform across chaptersCliff Click2026-09-171-0/+1
|
* Docs: Proj is not always a data node (#250)Symious2026-09-091-1/+5
| | | | | | | | | | | | | | | | | | | 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-2/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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
|
* Start to fix maven failsCliff Click2025-01-151-1/+1
|
* Test for "arg--2"Cliff Click2025-01-151-0/+6
| | | | Parse as "arg - -2" and not "arg-- 2" which is a syntax error
* Link to linear history and tag chaptersThalia Archibald2024-10-231-0/+2
|
* Cleanup on ch5 READMECliff Click2024-09-291-100/+116
|
* c will die when the scope dies.Tamas Hadhazy2024-09-291-1/+3
|
* add graph and explanationTamas Hadhazy2024-09-292-4/+246
|
* add missing ToStringTamas Hadhazy2024-09-261-0/+4
|
* move x-x check up frontCliff Click2024-09-131-3/+4
|
* x-x==0Cliff Click2024-09-132-5/+9
| | | | | | Move x-x==0 to compute. Add x/1 ==> x All chapters
* Backport empty statement fixCliff Click2024-09-071-0/+1
| | | | | Split Ch13 tests from Chapter12Test.java Handle forward refs never defined.
* 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-329/+407
| | | | | | | | | | | | | | | | | * 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-2132-133/+133
| | | | | | | | | * 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-2/+2
| | | | | | | | | | | | | | | | | | * 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
* fix small typo in chapter 5 (#73)David Rubin2024-04-231-2/+2
|
* Sync changes to previous chapters (#57)Dibyendu Majumdar2024-01-153-17/+11
| | | Also fix broken links in README
* Backport some of the code refactoring to previous chapters (#50)Dibyendu Majumdar2023-12-0722-224/+357
| | | | | | | | | | | * #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-1121-69/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * #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>
* Link to parseIf. (#36)Dibyendu Majumdar2023-11-051-138/+18
| | | | | | | * Link to parseIf. Reorder the table of nodes. Fix example. * Replace code with links
* Backport changes in Chapter 5 to previous chapters and update Chapter5 ↵Dibyendu Majumdar2023-11-0320-217/+2184
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* Cleanup PR#28.Cliff Click2023-11-012-15/+14
| | | | Remove parseBlock flag, and just require the missing `}`
* Bail out unclosed block (#25)Yichen Yan2023-11-012-5/+23
| | | | | | | | | * Report unclosed block in parsing * Fix tests * Resolve comments and rebase onto chapter5 * Test `isEOF` after consume whitespaces
* Test expecting an excpetion is missing an fail (#29)XmiliaH2023-11-011-0/+1
|
* Update visualdibyendumajumdar2023-11-016-196/+225
|
* Revert "Report unclosed block in parsing (#28)"dibyendumajumdar2023-11-012-13/+1
| | | | This reverts commit e3c412bbbdd6f6eefe2ac889f6d59aeaef71beb1.
* Report unclosed block in parsing (#28)XmiliaH2023-11-012-1/+13
|
* Fix list of keywords and node index of merge (#27)XmiliaH2023-11-013-3/+3
| | | | | | | * Wrong input index used * Then is currently not a keyword * Some phis are now not created and ids shifted
* Try another graphicsCliff Click2023-11-011-13/+35
|
* Bugfix RegionCliff Click2023-11-011-1/+1
| | | | Region edges need to align with Phi edges; missing leading null
* Small doc cleanup (#24)XmiliaH2023-11-011-59/+54
|
* Add copy method to bool nodes (#23)XmiliaH2023-11-012-6/+13
|
* Update visualdibyendumajumdar2023-11-011-0/+200
|
* Update visualdibyendumajumdar2023-11-012-0/+72
|
* Update visualdibyendumajumdar2023-11-013-119/+149
|
* Update the description of Region nodedibyendumajumdar2023-11-015-403/+389
| | | | | Update visuals Update chapter list
* Remove most TODO'sCliff Click2023-11-016-6/+9
| | | | Make an official TODO which can't be hit in the current Chapter, but future binary ops might hit it.
* Some improvements for chapter5 (#22)XmiliaH2023-11-015-13/+22
| | | | | | | | | | | * Return null when the node cannot be copied * Make add_def package private again * Phi node can have more then two data inputs in theory * Use swap12 * Use addUse
* Cleanup doc example graphCliff Click2023-11-011-2/+1
|
* Lots of improvements to graphvizCliff Click2023-11-0114-60/+79
| | | | | | | | Merging common edges. Phis of same Region align. Phis use greek phi, and have a debug name. Scope carries the debug name. Phis are lightly colored. Common math names for math prims. Parse can optionally show the graph after closing the last scope.
* Bug fix last peepholeCliff Click2023-11-013-8/+10
|
* Rethink & cleanup Add peepsCliff Click2023-11-014-30/+135
| | | | More rigorously head for a left-spline sum-of-products format.
* Fix div-by-0, some javadocCliff Click2023-11-014-16/+17
| | | | | 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
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 09:10:56 +0000