summaryrefslogtreecommitdiff
path: root/chapter06
Commit message (Collapse)AuthorAgeFilesLines
* Remove -disablePeepholeCliff Click2026-09-273-22/+2
|
* Extend and backport SubNode peephole (#254)Hsiang-Ying Fu2026-09-252-0/+47
| | | | | | | | | | | | | | | * 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>
* int fallbacks for int opsCliff Click2026-09-227-7/+7
| | | | all chapters, a little sharper for int ops
* Graph cleanupCliff Click2026-09-222-1/+2
| | | | Phis stay with regions, stop sinks to bottom,
* Tidy up scope displayCliff Click2026-09-221-1/+1
|
* Add shared graph viewer to all chaptersCliff Click2026-09-2218-295/+150
|
* Unify mixed-return checking and resultsCliff Click2026-09-193-21/+37
| | | | Unify dominator caching.
* Get makefiles and fuzzer testing uniform across chaptersCliff Click2026-09-171-0/+3
|
* Fix stale copy-pasted comment on BoolNode's phiCon call (#249)Symious2026-09-091-3/+4
| | | | | | | | | | | | | | | | | | The three comment lines above `AddNode.phiCon(this, ...)` in BoolNode were copy-pasted from MulNode and never adapted: they use `*` as the operator and describe the rotated shape `(x * (phi cons)) * con`. For BoolNode neither is right. The operator is a compare, and in chapters 6-9 `rotate` is hard-coded `false`, so the rotated shape is never matched; the shapes actually handled are `(phi cons) cmp con` and `(phi cons) cmp (phi cons)`. Reword the comment accordingly, and in chapters 6-9 add a line noting why rotate is off. Chapters 10-25 pass `this instanceof EQ`, so no such claim is made there. Comment-only change; no code is touched. 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/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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-152-115/+264
|
* Upgrades to the Type lattice diagramsCliff Click2025-01-152-222/+219
|
* Link to linear history and tag chaptersThalia Archibald2024-10-231-0/+2
|
* fix typo ch6Tamas Hadhazy2024-10-231-1/+1
|
* Turn off all printing during test runsCliff Click2024-10-125-41/+35
| | | | was making 10000 lines of ignored output
* remove peephole from ProjNode::idealize that is already handled by computeRobert Obkircher2024-09-161-6/+2
|
* 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-012-4/+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-2110-533/+612
| | | | | | | | | | | | | | | | | * 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-2135-139/+138
| | | | | | | | | * 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-13/+290
| | | | | | | | | | | | | | | | | | * 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-152-11/+7
| | | Also fix broken links in README
* Backport some of the code refactoring to previous chapters (#50)Dibyendu Majumdar2023-12-0716-241/+291
| | | | | | | | | | | * #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
* Chapter6 Part 2 - Add further peephole based on dominator calc (#42)Dibyendu Majumdar2023-11-1815-55/+364
| | | | | | | | | | | | | | | | | | | | | | * #37 Add a Utils class to hold some useful functions. (#39) Move the name '$ctrl' to the ScopeNode * Fix maven pom Missing an explicit compiler target, so IntelliJ/Maven defaulted to version 5 ??? Remove explict ver 17 from Makefile. * Add immediate dominator peephole * A little more robust & simpler idom search * #40 Revise chapter 6 writeup to include a description of dominators * #40 Revise chapter 6 writeup to include a description of dominators --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Chapter 6 (#38)Dibyendu Majumdar2023-11-1149-0/+5416
* #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>
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-15 13:25:52 +0000