| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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>
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* 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
|
| |
|
|
|
|
|
|
|
| |
* Trim trailing whitespace
* Ensure final new lines
* Convert line endings from CRLF to LF
* Replace tabs with spaces
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* chapter9
* merge fixes to chapter8
* Ch 9 notes
* Ch 9 work
Add a Iterate phase, after parsing.
Add a Worklist with fast dup removal & rand pull.
Add a Node.iter() call which returns progress or null. Peephole calls it. Iter() also asserts that Types make monotonic progress.
Intern all types, so we can do a cheap/easy "isa" test.
* GVN
* rename temporarily
* Apply Cliff's worklist changes
* Apply Cliff's GVN changes
* Revert "GVN"
This reverts commit 9dc6db1cac7e40de4a58333cbc3c9c3e7c088e6f.
* Revert "Ch 9 work"
This reverts commit df5b74e6c017a4f237a5d1a550a83b40a7928876.
* Fix 3-1+2
Was computing as 3-(1+2) == 0, not 4 as expected.
Add tests.
Unlock in swap12.
* Missed some cut-n-paste changes
* Break up the test file per-chapter
* Fix keep-alive while looping expressions
Must "hook" LHS prior to calling peepholes
* Ch9 Region optimization
Bug fix, GVN hits 2 inProgress Loops
Bug fix lifetime tracking when parsing dead code
Bug fix debug find call
GraphViz post-iterate
* Readme overhaul
Progress on Ch 9 readme
* Fix bugs hashcode
Was relying on label() hashCode for Phi, Proj; since this is debug-only cannot be relied on. Proj relies on _idx field, Phi needs a !inProgress check.
* Constant nodes print "#" before con
* Add a farther neighbor check
Peeps that check more than the nearest neighbor register a dependency on the Node that failed them. Should that Node later change, the peep root is put back on the worklist and revisited.
* Fix addDeps assert
Unwind golden test print, print smarter.
Unlock edges in subsume
* Update README
* shuffle adddeps forward one
its needed again shortly in another test, so just cover it now
* Fix fuzzer bugs
Peep x+(-y) to x-y
Handle TOP inputs; didn't think it could happen before running an optimistic pass, but fuzzer proved me wrong.
Deleting an input can recursively delete the self-node.
When checking the compute() type assert, delay setting _type so the method can just be re-run in the debugger.
Missing addDep in Phi
Parser mis-handling stacked operators like "1+-2" or "1==!=<=<>=>2"
Make Work list deterministic between tests.
* Update fuzzer to run iterate (#62)
* Update fuzzer to run iterate
* Work seed is now reset by reset
* A few more fuzzer tests
Set _type in iter() even later, better debugging.
Handle dead active scopes in visiualizer.
Region ideal honors Loop invariants; finish Region ideal for single input; inProgress check is a little tighter.
Type.isConstant is true strictly for lattice centerline constants. Clean up TypeInteger.
ideaj warning removal
* Fix all fuzzer bugs
iter() does not call peep(), instead peep() is self-recursive. This allows Iterate() to call iter(), and not get into arbitrary recursive peep() changes that do not track on the worklist.
Div, Minus, If all monotonic.
Catch a bunch of progress issues.
Robustify IRPrinter and Iterate and Region ideal
* Reducer could run into an infinite loop (#63)
* Write up how the Evaluator works (#64)
* Write up how the Evaluator works
* Some small improvements and a slightly better wrap up.
* Series of fuzzer bugs.
Fix monotonicity for all data nodes.
Generic compute intercept for data nodes, check all inputs for TOP/BOTTOM, and again for IntDataNodes.
Fix general progress bug allow high Types as constants.
Fix progress Region 1-input has obvious idom.
Make shortcut for fuzzer; renames Fuzzer to not have "Test" in the class name.
Fix invert comment in TypeInteger
* All fuzzer tests pass
Turn off expensive assert accidentally turned on
CSE needs to join types.
Add a type join.
Missing dep in Phi
* More README
* Hacking alternative way to fix the type compute
* Node is no longer IntSupplier
Renamed Work to WorkList
Renamed Iterate to IterOptim
Renamed Node.iter() to Node.peepholeOpt()
WorkList expects elements to be of Node
* Add an example of GVN
* Rename the method depsClear to moveDepsToWorklist - to better capture what it actually does.
* Add a second example of GVN benefits
* Fix typo
* Add example of worklist opt
* Prepare to allow alternative post parse worklist opt
* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple
* Alternative WorkList opt that has following differences:
1. It does not require dependencies between nodes
2. It does not require calls from inside the Node class, and therefore runs totally independently as a post parse step.
3. It is simple
* The RPO list was incomplete as it only identified the subgraph accessible from the STOP node.
* Fix iter count
* Add test suggested by Xmilia
* Fix bug where after the region is peeped the phis get consistent number of inputs
* Fix bug where after the region is peeped the phis get consistent number of inputs
* Dump out stats on how many nodes we peepd during the post parse iterative opt.
* Make it easy to switch the IterOpt
* Use deps based worklist by default
* Sharper worklist add
* Copy across Cliff's changes
* Merge changes to Iterate
* Revert failing change
* Update readme
* Add comments / update docs to explain the patterns where we call addDep().
* As before, unconditionally made dep a dependent of region.
* Fix a lot of missing dep issues
Rename IterOptim -> IterPeeps
Some grammar changes in comments & readme
* Bump up fuzzer limits, more testing
Missing dep in idom calc in IfNode.
Missed idom cache clear on Region edit.
* Remove RPO based peeps
O(n^2) behavior
* Minor updates README
* fix compile bug
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Darrick Wiebe <darrickw@untether.ai>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
* #52 Update chapter8 to align with chapter7
* #52 Update chapter8 to align with chapter7
* #52 Fix spacing
* #51 get started on break and continue
* #51 get started on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* break & continue scopes are made lazily, and merged into as discovered
Drop ContBreak.
Drop ScopeNode.addScope.
Add a simple mergeScopes.
Simplify Region.inProgress; drop from child classes, use in Region.
Add a ConstantNode.XCONTROL shortcut.
* Fix some regressions
* Error on dead code after break/continue
* A more robust dead-def check
* Fix for dead loop-back path
* Fix scope shadowing bug with continue/break
Turn on LAZY phis by default; fix minor golden test results
* Fix a case with both break & continue
* #51 more on break and continue
* #51 more on break and continue
* #51 more on break and continue
* #51 fix erroneous push of scope
* #51 fix import
* #51 update test expected results
* #51 Start Chapter8 writeup
* #51 Start Chapter8 writeup
* #51 _scope needs killing after continue
* Add graph evaluator (#56)
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 wip writeup
* #51 update code comments / add assertion
* #51 revert assertion
* #51 evaluate graph to verify test outcome
* #51 add code snippets
* #51 add examples
* Cleanup README
Comment for usefullness of true Loops.
Try to distiguish `PhiNode` as the programming construct from `phi` as the mathematically SSA notation.
Flow long lines.
Remove LAZY flag, set as `true`. Fold up true tests.
* minor comment
* #51 Check _breakScope is not null when parsing break or continue to detect use outside of loop
* #51 in parseComparison we need to move the op= version above the op version, since at this time using <= and >= does not work since they are parsed as > and < with a preceeding = which causes an error
* #51 Update main README to link to chapter 8
* Remove useless test
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
|
| |
|
|
|
|
|
| |
* #52 Update chapter8 to align with chapter7
* #52 Update chapter8 to align with chapter7
* #52 Fix spacing
|
|
|
* #44 Start on chapter 7
* #44
Temp hack on printing to not break on cycles.
Parse while statement.
* #44 Remove unnecessary method
* #44 Remove unnecessary phi map
* #44 Phi should have existing nodes from both scopes as input
* #44 We need to only insert phis once for each name that is looked up. To do so,
we need to know when a named is looked up first time inside the loop body.
The phi must have its second input added later on after the loop is fully parsed.
* #44 Add phi also when update() is called.
Only add phi if name was known at loop start
* #44 Only create phi in loop body if var binding in head != body.
During finish() lookup in body directly.
* #44 Update the print output to make it similar to that in Xmilia's fork
* #44 Disable peephole for phis & region involved in while loop
* Fix broken tests
Remove "disablePeephole" set in some tests, and remaining set for other tests, so a bulk test-all fails because disablePeephole is true for all.
Reset disablePeephole in Node.reset
Switch HashSet for BitSet (touches all).
* Restructure Node class
Group printing, group node & edge manipulations, group optimizations.
Also, fix LoopRegion idom, it does not use Region idom but uses the original
* #44 Node printing
* #44 Node printing
* #44 Fix control edges in loop region
Change label of loop region
Fix the output count in dump
* #44 Revise dump output
* #44 When a LoopRegionNode is duplicated, ensure the dupe is also a LoopRegionNode
* #44 When a LoopScopeNode is merged, we merge the names set too
* #44 When a LoopScopeNode is merged, we merge the names set too
* #44 Fix print1() on RegionNode to use label()
* #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created
* Revert "#44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created"
This reverts commit 5f729709855046c5c10904f08385fd1aec9a298a.
* #44 Fix bug caused by incorrect comparison of nodes between body and head of loop; the check must be performed before any phis are created
* #44 when we create a phi incrementally for a loop region, all scopes that are cloned from the original must get the same phi update
* #44 test case
* #44 test case
* Squashed commit of the following:
commit 15666e287e6bbc39b3fcc49939165a1e908d43b2
Author: Cliff Click <cliffc@acm.org>
Date: Mon Nov 27 09:45:40 2023 -0800
lazy/eager phis
Eager phis by default, but can flip Parser.LAZY to switch to lazy phis. Several tests golden answers change when flipping this flag due to minor node renumbering.
Phi combines same_inputs and singleUniqueInput.
Fancier basic-block-like printing. Uses isMultiHead & isMultiTail which show up in many Nodes.
Remove blanks in triple-quote strings.
commit 6ea70182a92b7db4fe5a1fdc2c4491842ef77ee5
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 11:13:22 2023 -0800
Remove dead scopes
Add a debug find
commit a52c06a47bf1e56866d8b4d043290838f053ad76
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 10:21:48 2023 -0800
No constraints on backedges
nicer loopy graphs
commit b5ab550098355f0b66bf24b40adf2e5ba4d86e4e
Author: Cliff Click <cliffc@acm.org>
Date: Sun Nov 26 10:13:22 2023 -0800
Fix regression
commit 30a7f5c734c686c02d3ca479914c9427b65cc469
Author: Cliff Click <cliffc@acm.org>
Date: Sat Nov 25 21:51:47 2023 -0800
minor cleanup
commit ad742b795ce0c93cfc82b2b11740261cfd923d02
Author: Cliff Click <cliffc@acm.org>
Date: Sat Nov 25 21:47:05 2023 -0800
Fixes lazy phi
Scope now takes a 'loop' option on dupping; the dup'ed Scope is filled with "Lazy Phi" sentinels - markers to indicate a Phi is need if this variable is ever referenced. If its never referenced, at the loop exit the "Lazy Phi" unwinds back to the original value. Lookup and update calls lazily insert concrete Phis over "Lazy Phis" at first touch.
Rename _allScopes to _xScopes its "active" not "all" scopes now.
Remove try/finally block at end, because a compiler bug throws, then attempts a GraphViz on a broken graph, then throws again, hiding the original bug.
Removed 1 extra layer of Scopes.
Scope printing now prints in edge order; added a reversemap for printing.
More touches to ascii printing.
* Remove flag to parseBlock
* Bugfix for lazy on empty loop body
Remove extra phi name-matching code
* Keep head alive until entire end_loop merging is done
* Create chapter 8 as a copy of chapter 7
* #44 Chapter 7 is now eager phis only (#46)
* #44 Chapter 7 is now eager phis only
* MOVE IR Printing to dedicated class to declutter Node. Remove Ary (#49)
* #44 Move IR printing to dedicated class to declutter Node, and remove Ary
* #44 refactor Node.delUse() to use common del()
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* Revert "#44 Some cleanups"
This reverts commit 2702c338c8bdaa5ef2128000e26f1a8496baf34a.
* #44 Some cleanups
* #44 Some cleanups
* #44 Some cleanups
* #44 Fix typo
* #44 Fix markdown formatting
* #44 Remove line numbers from code snippets
---------
Co-authored-by: Cliff Click <cliffc@acm.org>
|
