summaryrefslogtreecommitdiff
Commit message (Collapse)AuthorAgeFilesLines
...
* 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-016-409/+395
| | | | | 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-0110-27/+36
| | | | | 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
* javadoc about null-ness returns updateCliff Click2023-11-011-2/+29
|
* Fix missing trailing expressionCliff Click2023-11-012-1/+11
|
* Fix broken error reportCliff Click2023-11-012-2/+11
|
* Fix bugs using keywords as idsCliff Click2023-11-013-19/+71
| | | | | | | | Add an exact 'matchx' for keywords. Add a list of keywords. int true=0; return true; // Expected id, found 'true' int else=arg; if(else) else=2; else else=1; return else; // Expected id, found 'else' inta=1; return a; // undefined inta
* Update READMECliff Click2023-11-013-30/+63
| | | | Add true/false
* Parser gather Returns in the StopCliff Click2023-11-019-55/+78
| | | | | | Return returns a tuple of control & result GraphViz works with multi-Scopes and Scopes do not double-print uid. Proj also does not print uid in golden test results, because every time we add a new early node, the final results change node id so fail golden test.
* Fix Scope.dup mixing up edge ordersCliff Click2023-11-014-44/+35
| | | | Fix GraphVix node edge ordering
* Dont make redundant phisCliff Click2023-11-011-1/+2
|
* Greatly simplify Merge logic; move to ScopeNode.Cliff Click2023-11-016-144/+171
| | | | | | | | | Rename CTRL_TOKEN... its not a token. _allScopes becomes a Stack, because... it behaves like a stack. Add a junk Phi peep. More general AddNode peeps Add a bunch of If tests. Rewrite how expected-exception tests work; the workflow on the old technique sucked. New one stops in the right place in the debugger.
* Emacs per-project settingCliff Click2023-11-011-0/+4
|
* Remove id as we already have it in Node.dibyendumajumdar2023-11-011-12/+1
|
* Small cleanupdibyendumajumdar2023-11-011-7/+5
|
* Add descriptions of the new node types in Chapter 5.dibyendumajumdar2023-11-012-2/+35
| | | | Add references to Cliff's thesis.
* Update the main READMEdibyendumajumdar2023-11-011-2/+2
|
* Small updatesdibyendumajumdar2023-11-011-6/+6
|
* Fix typodibyendumajumdar2023-11-011-1/+1
|
* Add writeup of if statement parsingdibyendumajumdar2023-11-016-3/+644
|
* Add writeup of if statement parsingdibyendumajumdar2023-11-011-0/+24
|
* Update visualization to show all the Scope Nodes that are active.dibyendumajumdar2023-11-014-52/+104
| | | | | | Fix test cases broken due to renaming of ProjNode label. Cleanup the way we update $ctrl token Assign an ID to each ScopeNode so that when we visualize we can assign different names
* Some initial Ch 5 cleanupCliff Click2023-11-0114-37/+42
| | | | | | Drop Control interface, not flexible enough. Use isCFG() call, overloaded in child classes. Projections have a more complex test. Missing some printouts in Bool children, If, Region, Phi. IfNode type is a tuple. Region is TypeControl.
* Added PhiNode, RegionNode, IfNode, StopNodedibyendumajumdar2023-11-0110-15/+236
| | | | | No type compute yet Initial parsing logic for If statements
* Rename test class and dot diagramsdibyendumajumdar2023-11-012-2/+2
|
* Start on Chapter 5dibyendumajumdar2023-11-011-3/+5
|
* Start on Chapter 5dibyendumajumdar2023-11-0126-0/+2063
|
* Backport fix for set_def killing new_def (#21)XmiliaH2023-10-292-6/+11
|
* 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-279-134/+287
| | | | 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-2113-338/+443
| | | | | | | | | * 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-2031-1/+2461
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * 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>
* Chapter 3 - add vars and lexical scope. (#7)Dibyendu Majumdar2023-10-0129-54/+1982
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Chapter 3 - add vars and lexical scope. * Fix typo * Overhaul graph viz Makes the scopes pointing into the graph being build more visually appealing. Constants are a printed with just the constant value. * Fix control edge color * Fix missing grouping operator parse Add a parens test. Shorten names 'Identifier' to 'Id' _lexer.match -> match require() passes a Node thru, so can be flow-coded. Uniform syntax error messages. Handy Lexer.toString for debugging. Drop Optional for null returns; less total code; less objects; less confusion. camelCase some fcns. * All parser helpers return Node, not void. Drop _ret. parseBlock and parseStatement now the same. * CLosely align chap2 and chap3 parsers Mostly whitespace aligned; dragged a few functions around to make more sense. I think the diff from Ch2 and Ch3 is down a few differences about what is a statement, plus all the symbol stuff for scopes and variables. * Add examples illustrating the symbol table creation. * Update docs and comments --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Apply changes from chapter 2 to chapter 1 (#5)Dibyendu Majumdar2023-09-295-201/+188
| | | Fix tests that check for exceptions
* Chapter 2 (#4)Dibyendu Majumdar2023-09-2634-22/+1694
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * Start on Chapter 2. * Start on Chapter 2. * Refactor * Refactor * Initial attempt at peephole opt for add operation * cleanup unused import * Start on graph visualizer * Start on graph visualizer * Rework chapter 2 Add a short discourse on the Types, and provide a Bottom type. Make a final toString; require each Node to specify its special printing via label(). Add a recursing printer called print(); toString is used by default in the debugger and so cannot be recursive. Make the peephole rules based on a proper Type and idealize calls. Big comments about the Type computations. Every node picks up a _print, compute and idealize() call. Rename long arith ops Divide, UnaryMinus, Multiply, Subtract into shorter uniform-length names. Cleans up the parser where he does the precedence op parsing. Rework Parser: - Drop Token class, its all Strings except in the one place we know a number is coming - Embed the Lexer as a field in the Parser, instead of trying to pass it around everywhere in the Parser - StartNode becomes a read-only global, so we don't have to pass it around everywhere in the Parser AND optimizer. - Lexer matches on strings and returns strings. Match and consume *at the moment* instead of carrying around a current token/string and forcing the next-token after consuming the current one. - All parse subexpressions shrink by 1/2 after these changes. * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Initial writeup of Chapter 2 * Remove range * progress Chapter 2 Drop integer ranges. Broader lattice pic. Lots of prose changes in the readme. Fixed title in gviz dot generation. Fixed bug with peephole making redundant constants. * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Implement compute for all the arithmetic node types Add a flag to switch off peephole so we can see the full graph Add post peephole graph to writeup * Fix bad path to the svg * Update pre-peephole diagram * Add dead code elimination ...and a set_def to proper update graph edges. * Update README.md * Cleanup the GraphVisualizer a bit. Update the graphs. Update the chapter list as chapter 3 deleted, and chapter 4 is now chapter 3. --------- Co-authored-by: Cliff Click <cliffc@acm.org>
* Merge pull request #3 from dibyendumajumdar/mainDibyendu Majumdar2023-09-1916-223/+687
|\ | | | | Chapter 1 implementation
generated by cgit v1.2.3 (git 2.25.1) at 2026-10-18 10:48:04 +0000