diff options
120 files changed, 4371 insertions, 589 deletions
diff --git a/.gitattributes b/.gitattributes new file mode 100644 index 00000000..6313b56c --- /dev/null +++ b/.gitattributes @@ -0,0 +1 @@ +* text=auto eol=lf @@ -15,6 +15,7 @@ # run the tests # # make tests +# make test CLASS=Chapter25Test METHOD=testHelloWorldNoInline ####################################################### # @@ -63,19 +64,39 @@ TST := src/test/java CLZDIR:= build/classes main_javas := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java $(SRC)/$(SIMPLE)/node/cpus/*/*java) test_javas := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java) +simple_driver := $(TST)/$(SIMPLE)/Simple.java main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas)) include $(firstword $(wildcard ../graph/graph.mk graph/graph.mk)) include $(firstword $(wildcard ../print/print.mk print/print.mk)) include $(firstword $(wildcard ../isa/isa.mk isa/isa.mk)) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) -test_cp := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) +# These tests do not rely on the stdlib +test_alone := com.seaofnodes.simple.BrainFuckTest com.seaofnodes.simple.MergeSortTest com.seaofnodes.simple.TypeTest +test_raw_nums0 := 01 02 03 04 05 06 07 08 09 10 12 13 14Float 14 15 16 17a 17b 18 19 20 21 +test_raw_nums1 := 22 23 24 +# These tests DO rely on the stdlib +test_raw_sys := 25 + +# Convert chapter numbers to test files +test_raw0 := $(patsubst %,com.seaofnodes.simple.Chapter%Test,$(test_raw_nums0)) +test_raw1 := $(patsubst %,com.seaofnodes.simple.Chapter%Test,$(test_raw_nums1)) +test_sys := $(patsubst %,com.seaofnodes.simple.Chapter%Test,$(test_raw_sys) ) +# All the 'src/test/java' files ending in 'Test' +test_cp0 := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java)) +# Minus raw0, raw1, alone tests +test_cp1 := $(filter-out $(test_raw0) ,$(test_cp0)) +test_cp2 := $(filter-out $(test_raw1) ,$(test_cp1)) +test_cp3 := $(filter-out $(test_alone),$(test_cp2)) +test_cp4 := $(filter-out com.seaofnodes.simple.Chapter25Test,$(test_cp3)) +test_cp := $(filter-out $(test_sys) ,$(test_cp4)) +# All the classes to compile classes = $(main_classes) $(test_classes) # All the libraries libs = $(wildcard lib/*jar) jars = $(subst $(space),$(SEP),$(libs)) -default_targets := $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag +default_targets := TAGS release tests # Optionally add ctags to the default target if a reasonable one was found. ifneq ($(CTAGS),) default_targets += tags @@ -83,76 +104,129 @@ endif default: $(default_targets) -####################################################### -# Compile the chapter and shared viewer sources together +.PHONY: build +build: $(CLZDIR)/main/.mtag -$(CLZDIR)/main/.mtag: $(main_javas) Makefile +####################################################### +# Compile Java as a whole source set. javac tracks Java dependencies +# internally, so compiling only the directly out-of-date .java files can leave +# stale dependent .class files behind. +$(CLZDIR)/main/.mtag: $(main_javas) @[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main @# This crap is really just "javac", but with a beautiful error message. @# The very very long list of java files is suppressed and counted. @# The required output "Note: blah blah deprecated blah" is suppressed. - $(file >.argsM.txt,$(main_javas)) - @if [ ! -z "$(main_javas)" ] ; then \ - echo "compiling main because " $< " and " `wc -w < .argsM.txt` " more files" ; \ - if ! javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas) >& .out.txt ; then \ + $(file > .argsM.txt, $(main_javas)) + @echo "compiling main " `wc -w < .argsM.txt` " files" + @if ! javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main @.argsM.txt >& .out.txt ; then \ cat .out.txt ; \ exit 1; \ - fi ; \ - rm -rf .out.txt ; \ fi + @rm -rf .out.txt @touch $(CLZDIR)/main/.mtag @rm -f .argsM.txt -$(main_classes): $(CLZDIR)/main/.mtag - - ####################################################### -OODT := $(isa_test_javas) -$(CLZDIR)/test/.ttag: $(test_classes) $(test_javas) $(isa_test_javas) $(CLZDIR)/main/.mtag +$(CLZDIR)/test/.ttag: $(test_javas) $(isa_test_javas) $(CLZDIR)/main/.mtag @[ -d $(CLZDIR)/test ] || mkdir -p $(CLZDIR)/test - $(file >.argsT.txt,$(OODT)) - @if [ ! -z "$(OODT)" ] ; then \ - echo "compiling test because " $< " and " `wc -w < .argsT.txt` " more files" ; \ - if ! javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test $(OODT) >& .out.txt ; then \ + $(file > .argsT.txt, $(test_javas) $(isa_test_javas)) + @echo "compiling test " `wc -w < .argsT.txt` " files" + @if ! javac $(JAVAC_ARGS) -cp "$(CLZDIR)/test$(SEP)$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(TST) -d $(CLZDIR)/test @.argsT.txt >& .out.txt ; then \ cat .out.txt ; \ exit 1; \ - fi ; \ - rm -rf .out.txt ; \ fi + @rm -rf .out.txt @touch $(CLZDIR)/test/.ttag @rm -f .argsT.txt -# Collect just the out-of-date files -$(test_classes): $(CLZDIR)/test/%class: $(TST)/%java - $(eval OODT += $$<) +####################################################### + +# Default Simple .o target is build/objs which is where all the test .o's get +# dumped. The default sys search needs to NOT include all the dumped test +# files; move it down into lib/ +OBJS:= build/objs +SYS_SMPS:= $(wildcard src/main/smp/*.smp src/main/smp/*/*.smp src/main/smp/*/*/*.smp) +CPU_PORT:= x86_64_v2 +CALL_CONV:= $(if $(filter Windows_NT,$(OS)),win64,SystemV) +CPU_ABI:= $(CPU_PORT)_$(CALL_CONV) +RELEASE:= build/release +TEST_SYS:= $(OBJS)/lib_$(CPU_ABI)/sys.o +RELEASE_SYS:= $(RELEASE)/$(CPU_ABI)/sys.o +RELEASE_CRT:= $(RELEASE)/$(CPU_ABI)/simple_crt.o +C_CALL_CONV:= $(if $(filter win64,$(CALL_CONV)),ms_abi,sysv_abi) + +$(TEST_SYS): $(CLZDIR)/main/.mtag $(simple_driver) $(SYS_SMPS) | $(CLZDIR)/test/.ttag + @echo "simping " $@ + @$(JVM) com.seaofnodes.simple.Simple --cpu $(CPU_PORT) --abi $(CALL_CONV) --norun -o $@ src/main/smp/sys.smp + +$(RELEASE_SYS): $(OBJS)/lib_$(CPU_ABI)/sys.o + @echo "copying " $@ + @[ -d $(dir $@) ] || mkdir -p $(dir $@) + @cp $< $@ + +$(RELEASE_CRT): src/main/c/simple_crt.c + @echo "compiling " $@ + @[ -d $(dir $@) ] || mkdir -p $(dir $@) + @gcc -c -O2 -DCALL_CONV=$(C_CALL_CONV) -o $@ $< ####################################################### # Base launch line for JVM tests JVM=nice java -ea -cp "$(CLZDIR)/main${SEP}${jars}${SEP}$(CLZDIR)/test" - -tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag - @echo "testing " $(test_cp) - @[ -d build/objs ] || mkdir -p build/objs - @$(JVM) org.junit.runner.JUnitCore $(test_cp) - @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap +# Tests that do NOT need sys.smp +tests_raw0: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_CRT) + @echo "testing " $(test_raw0) + @[ -d $(OBJS) ] || mkdir -p $(OBJS) + @$(JVM) org.junit.runner.JUnitCore $(test_raw0) + +tests_raw1: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_CRT) + @echo "testing " $(test_raw1) + @[ -d $(OBJS) ] || mkdir -p $(OBJS) + @$(JVM) org.junit.runner.JUnitCore $(test_raw1) + +# Larger standalone tests, still JUnits, still no sys.smp +tests_alone: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(RELEASE_CRT) + @echo "testing " $(test_alone) + @[ -d $(OBJS) ] || mkdir -p $(OBJS) + @$(JVM) org.junit.runner.JUnitCore $(test_alone) + +# Tests that DO need sys.smp +tests_sys: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_CRT) + @echo "testing " $(test_sys) + @[ -d $(OBJS) ] || mkdir -p $(OBJS) + @$(JVM) org.junit.runner.JUnitCore $(test_sys) + +# One test method (or the whole class when METHOD is omitted). +CLASS ?= Chapter25Test +METHOD ?= +.PHONY: test +test: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_CRT) + @$(JVM) com.seaofnodes.simple.TestRunner "$(CLASS)" "$(METHOD)" fuzzer: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag - @echo "fuzzing " $(test_cp) + @echo "fuzzing " @$(JVM) org.junit.runner.JUnitCore com.seaofnodes.simple.FuzzerWrap -# Build a Simple jar -release: build/release/simple.jar +tests: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag tests_raw0 tests_raw1 tests_alone tests_sys fuzzer + @echo "All tests" + @[ -d $(OBJS) ] || mkdir -p $(OBJS) + @$(JVM) org.junit.runner.JUnitCore $(test_cp) + + +# Build a Simple jar and release stdlib +release: build/release/Simple.jar $(RELEASE_SYS) $(RELEASE_CRT) # Build a Simple jar -build/release/simple.jar: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag +build/release/Simple.jar: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag @echo "jarring " $@ " because " $? @[ -d $(dir $@) ] || mkdir -p $(dir $@) - @jar cf build/release/simple.jar -C $(CLZDIR)/main . -C $(CLZDIR)/test . -C $(SRC)/$(SIMPLE) . -C $(TST)/$(SIMPLE) . + @printf "Main-Class: com.seaofnodes.simple.Simple\nClass-Path: ../../lib/junit-4.12.jar ../../lib/hamcrest-core-1.3.jar\n\n" > build/release/MANIFEST.MF + @jar cfm $@ build/release/MANIFEST.MF -C $(CLZDIR)/main . -C $(CLZDIR)/test . -C $(SRC)/$(SIMPLE) . -C $(TST)/$(SIMPLE) . +####################################################### .PHONY: clean clean: rm -rf build @@ -172,30 +246,15 @@ lib/hamcrest-core-1.3.jar: @(cd lib; wget https://repo1.maven.org/maven2/org/hamcrest/hamcrest-core/1.3/hamcrest-core-1.3.jar) # Build emacs tags (part of a tasty emacs ide experience) -tags: $(main_javas) $(test_javas) +.PHONY: tags +tags: TAGS + +TAGS: $(main_javas) $(test_javas) @rm -f TAGS - @$(CTAGS) -e --recurse=yes --extra=+q --fields=+fksaiS $(SRC) $(TST) + @$(CTAGS) -e --recurse=yes --fields=+fksaiS $(SRC) $(TST) -spill-stats: $(CLZDIR)/main/.mtag $(CLZDIR)/test/.ttag - @[ -d build/objs ] || mkdir -p build/objs +# Frozen earlier allocation cohorts, followed by Chapter 25's native tests. +spill-stats: $(CLZDIR)/test/.ttag $(TEST_SYS) $(RELEASE_SYS) $(RELEASE_CRT) @$(JVM) com.seaofnodes.simple.SpillStats .PHONY: spill-stats - -.PHONY: build -build: $(CLZDIR)/main/.mtag - -# The ABI shim gives standalone native tests the same entry contract as clients. -CPU_PORT := x86_64_v2 -ifeq ($(OS),Windows_NT) -CALL_CONV := win64 -NATIVE_ABI := ms_abi -else -CALL_CONV := SystemV -NATIVE_ABI := sysv_abi -endif -runtime_obj := build/release/$(CPU_PORT)_$(CALL_CONV)/simple_crt.o -$(runtime_obj): src/main/c/simple_crt.c Makefile - @mkdir -p $(dir $@) - gcc -c -O2 -DCALL_CONV=$(NATIVE_ABI) $< -o $@ -tests: $(runtime_obj) diff --git a/README.ja.md b/README.ja.md index 37c89fe6..bad277eb 100644 --- a/README.ja.md +++ b/README.ja.md @@ -67,7 +67,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っã� * [第26章](docs/chapter26/README.ja.md):構築とプライベートメモリ * [第27章](docs/chapter27/README.ja.md):エスケープ解析と未知の呼び出し元 * [第28a章](docs/chapter28a/README.ja.md):モジュールと遅延クラス初期化 -* 第28b章:分離コンパイル +* [第28b章](docs/chapter28b/README.ja.md):分離コンパイル 付録:[ネイティブライブラリ](docs/appendices/native-libraries.md)、 [最適化とバックエンドの調整](docs/appendices/optimizer-tuning.ja.md)。 @@ -76,7 +76,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 26](docs/chapter26/README.md): Construction and Private Memory * [Chapter 27](docs/chapter27/README.md): Escape Analysis and Unknown Callers * [Chapter 28a](docs/chapter28a/README.md): Modules and Lazy Class Initialization -* Chapter 28b: Separate Compilation +* [Chapter 28b](docs/chapter28b/README.md): Separate Compilation Appendices: [Native libraries](docs/appendices/native-libraries.md), [optimizer and backend tuning](docs/appendices/optimizer-tuning.md). diff --git a/ainotes.txt b/ainotes.txt new file mode 100644 index 00000000..c0b03a4d --- /dev/null +++ b/ainotes.txt @@ -0,0 +1,34 @@ + +Historical design notes from the former combined Chapter 25, now Chapter 28b. +Current status and remaining work are in ../docs/stage-audit.md and +../docs/chapter-backports.md. The original intent below is preserved. + +Meta-info: I intend to keep extending and re-editing this "ainotes.txt" file so +I can reprompt the you (the AI) between AI restarts, As such this file will +contain a mix of high-level design decisions, goals, intents and wisdom, and +then taper down to more detailed problems and solutions - which probably keep +changing. + +AI is allowed access to all files recursively in "C:/Users/cliffc/Desktop/Simple" +directory. + +Meta-info: all the tests run with `make tests` currently run, and should again +run before we accept any changes. + + +The overall project is rooted in the `Simple/` directory, +and is a compiler tutorial broken up into chapters. +The chapters build on each other. + +Read the code in this chapter25; the goal in this chapter is to allow separate +compilation. I want to compile a "standard library", the start of which is in +`src/main/smp/sys.smp` and subdirectories and end up with either an archive or +a "fat ELF .o" file. + +Then I want to compile a 1-liner "hello world" program: + `sys.io.p("Hello World!");` +and have the symbols `sys`, `io` and `p` be found in the standard library. + +I am using a test case to represent this seperate compilation strategy in +`Chapter25Test.testModules`. There are comments there to help drive my +thinking. diff --git a/docs/chapter28b/28b-grammar.ja.md b/docs/chapter28b/28b-grammar.ja.md new file mode 100644 index 00000000..65944fe2 --- /dev/null +++ b/docs/chapter28b/28b-grammar.ja.md @@ -0,0 +1,175 @@ +# 第28b章の文法 + +[English](28b-grammar.md) | 日本語 + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +// A file is a compilation unit; its path supplies its namespace. +// Qualified names resolve nested types and other units without an import keyword. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : constructorDeclaration | methodDeclaration | statement ; + +// The constructor name must match the enclosing struct's name. +constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// Function types and expressions both receive their implicit receiver here. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol: a function, or explicit numeric native storage. Ordinary strings +// elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Allocation invokes the declared constructor; inline initializer blocks from +// earlier chapters are replaced by constructor arguments. +newExpression : 'new' type ('[' assignment ']' | callSuffix)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter28b/28b-grammar.md b/docs/chapter28b/28b-grammar.md new file mode 100644 index 00000000..c7a279fa --- /dev/null +++ b/docs/chapter28b/28b-grammar.md @@ -0,0 +1,175 @@ +# Grammar for Chapter 28b + +English | [日本語](28b-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +// A file is a compilation unit; its path supplies its namespace. +// Qualified names resolve nested types and other units without an import keyword. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : constructorDeclaration | methodDeclaration | statement ; + +// The constructor name must match the enclosing struct's name. +constructorDeclaration : 'new' IDENTIFIER '=' functionExpression ';' ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// Function types and expressions both receive their implicit receiver here. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol: a function, or explicit numeric native storage. Ordinary strings +// elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Allocation invokes the declared constructor; inline initializer blocks from +// earlier chapters are replaced by constructor arguments. +newExpression : 'new' type ('[' assignment ']' | callSuffix)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter28b/README.ja.md b/docs/chapter28b/README.ja.md new file mode 100644 index 00000000..d6274788 --- /dev/null +++ b/docs/chapter28b/README.ja.md @@ -0,0 +1,108 @@ +# 第28b章: 分離コンパイル + +[English](README.md) | 日本語 + +[Previous: Chapter 28a](../chapter28a/README.ja.md) + +前の章では、見つかったソースを一度にコンパイルしました。この章ではライブラリと +クライアントを別々にコンパイルします。クライアントにはライブラリのオブジェクト +ファイルが必要ですが、そのソースは不要です。 + +## オブジェクトに理想 IR を保存する + +通常の ELF オブジェクトには機械語、データ、シンボル、再配置情報があります。 +Simple はさらに `.simple` セクションへ型と理想 IR を保存します。クライアントは +宣言を読み込んで型を検査し、関数本体も読み込んで SCCP やインライン化に使います。 +残った呼び出しは、ネイティブリンクでライブラリの機械語につなぎます。 + +宣言型と解析中の型は別々に保存します。ある時点でフィールドの値が 0 でも、 +その宣言を定数 0 に変えてはいけません。引数の型の上限、数値演算のモード、 +Store の幅、元のソース位置も保存します。入れ子の構造体には、関数本体だけでなく +割り当て関数とコンストラクタの宣言も必要です。 + +別々のコンパイルで同じ番号になったエイリアスや関数は、同じものとは限りません。 +`GlobalBits` は定義元のファイルとファイル内の番号を保存し、インポート時にその +組み合わせを今回の番号へ写します。型とノードに同じ写像を使い、複数ファイルを +またぐ再帰型も復元します。 + +読み込みの単位は現在オブジェクトです。無関係なオブジェクトは読み込まずに済みますが、選ばれた +オブジェクトの保存済み IR は全体を復元し、記録された依存先も読み込みます。`sys.io.p` だけを +呼ぶ場合でも、`sys.o` にまとめられた十個の単位をすべて読み込み、`aryu8` と `aryi64` も含みます。 +必要なメンバーだけの読み込みは今後の目標です。IR の読み込みだけでクラスが初期化されたり、 +その本体がクライアントの出力にコピーされたりするわけではありません。元のソースの解析は省けますが、 +インポートしたグラフも新しい呼び出し元とともに最適化し、型検査します。 + +## 実行できる例 + +英語版の例は次の二つのソースルートにあります。 + +```text +src/test/smp/separate/library/Counters.smp +src/test/smp/separate/client/Main.smp +``` + +ライブラリは、ループで final フィールドを計算する `Counter` と共有カウンタを +公開します。クライアントの `run(3)` は最初に 107 を返します。同じプロセスで +続けて `run(5)` を呼ぶと 231 になります。インスタンスは別々ですが、クラスの +カウンタは共有されます。`run(0)` はライブラリを使わずに戻ります。 + +このディレクトリでライブラリをコンパイルします。 + +```sh +make lib +make build/classes/test/.ttag +java -ea -cp "build/classes/main:build/classes/test:lib/*" \ + com.seaofnodes.simple.Simple --norun -o build/separate-example/lib/ \ + src/test/smp/separate/library/Counters.smp +``` + +次にオブジェクトを使ってクライアントを評価します。 + +```sh +java -ea -cp "build/classes/main:build/classes/test:lib/*" \ + com.seaofnodes.simple.Simple --eval \ + -L build/separate-example/lib/Counters.o \ + src/test/smp/separate/client/Main.smp 3 +``` + +結果は `107` です。Windows のクラスパス区切りには `;` を使います。クライアントの +ソースルートには `Counters.smp` がありません。`SeparateCompilationTest` はさらに +二つのオブジェクトを C ドライバとリンクし、繰り返し呼び出す動作を検査します。 + +## 解析とコードの所有者 + +インポートした本体は解析に参加しても、クライアントの出力には属しません。 +`Serialize` は `Lower` がクラス初期化を展開する前に理想 IR を保存します。 +`Unlink` は機械語生成に向けてインポートした本体と解析用の呼び出し辺を切り離します。 +インライン化でクライアントへコピーされたコードは、クライアント自身の本体として +出力されます。 + +初期化規則は前の章と同じです。型のインポートだけでは初期化しません。能動的な使用は +`CLInit` を通して初期化を要求し、ライブラリが持つクラスオブジェクトとフラグを使います。 +依存関係の検査にはインポートした本体も含めます。ネイティブコードへ渡した関数の +未知の呼び出し元も保持します。 + +コンストラクタのフィールド更新はローカル値と Phi のままで、ヘルパーの出口に Store を +置きます。未完成のオブジェクトでも初期化済みフィールドは読めます。 +アンダースコアは公開インターフェースの選択に使いますが、ソースのアクセス制限は +[レビュー待ち](../chapter-backports.md)です。 + +## 検証と今後 + +リポジトリのルートから次を実行します。 + +```sh +make tests CHAPTERS=chapter28b +``` + +保存したコンストラクタ、インポートをまたぐ初期化循環、共有データ、ネイティブ関数の +サンク、ライブラリとクライアントの実行を検査します。Make はテスト用の `sys` も +オブジェクトにします。`make release` は jar と標準ライブラリを作り、`make view` は +共通のグラフビューアーを起動します。 + +保存形式は `C0DE` 以外のバージョン番号をまだ持ちません。コンパイラや形式を変えたら +オブジェクトを再構築してください。高コストの往復一致検査は無効のままで、古い増分 +ビルドの実験 `testModule0` も実行対象外です。 + +[分割計画](../chapter-split.md)の主要な七つのスナップショットはこれで揃います。 +ネイティブライブラリの構築と最適化の調整は[付録](../appendices/README.md)にまとめています。 diff --git a/docs/chapter28b/README.md b/docs/chapter28b/README.md new file mode 100644 index 00000000..da5a90a8 --- /dev/null +++ b/docs/chapter28b/README.md @@ -0,0 +1,177 @@ +# Chapter 28b: Separate Compilation + +English | [日本語](README.ja.md) + +[Previous: Chapter 28a](../chapter28a/README.md) + +The previous chapter compiled every discovered source file together. This +chapter lets a library and other code compile separately, and have full type +information. The client needs the library's *object* file, but not its source. +In spirit this is similar to Java's *class* file, with its full execution and +type semantics stored in the file; we happen to be using an ELF file for the +same reason. The ahead-of-time compiled code is *also* available for the +linking step. + +An ordinary native object contains machine code, data, symbols, and +relocations. Simple adds a `.simple` section with types and the ideal IR. +Importing `.simple` lets the client check types and optimize calls into the +library. Calls that remain out of line use the library's machine code at +native link time. + +## A library and a client + +The runnable example has two separate source roots: + +```text +src/test/smp/separate/library/Counters.smp +src/test/smp/separate/client/Main.smp +``` + +`Counters.smp` declares shared state and an instance constructor: + +```simple +int calls=0; +val next_noInline = { -> calls++; return calls; }; + +struct Counter { + val value=1; + new Counter = { int n -> + value=0; + for( int i=0; i<n; i++ ) value=value*2+1; + }; + val get = { -> value; }; +}; +``` + +`Main.smp` uses both parts of the library: + +```simple +val run = { int n -> + if( !n ) return 0; + val c = new Counters.Counter(n); + return c.get()+100*Counters.next_noInline(); +}; +return run(arg); +``` + +At runtime, `run(0)` returns without reaching or initializing `Counters`. + +For `run(3)`, `Counters` initializes, the constructor computes 7 and +`calls`==1, so we get `(7+100*1)` or 107. + +Calling `run(3)`, then `run(5)`, in one process increments the shared `calls` +twice. The first call gives `(7+100*1)`, or 107; the second gives +`(31+100*2)`, or 231. + +(The `_noInline` suffix prevents inlining, so the example exercises native +linking as well as imported IR.) + +From this chapter directory, build the compiler and compile the library: + +```sh +make lib +make build/classes/test/.ttag +java -ea -cp "build/classes/main:build/classes/test:lib/*" \ + com.seaofnodes.simple.Simple --norun -o build/separate-example/lib/ \ + src/test/smp/separate/library/Counters.smp +``` + +Then compile and evaluate the client using that object: + +```sh +java -ea -cp "build/classes/main:build/classes/test:lib/*" \ + com.seaofnodes.simple.Simple --eval \ + -L build/separate-example/lib/Counters.o \ + src/test/smp/separate/client/Main.smp 3 +``` + + +## What crosses the separate compilation boundary + +The optimized IR owned by the object is compactly encoded in the `.simple` +section and fully reconstructed when read back in. The saved state includes +canonical declarations as well as optimized flow types. E.g. `int x=7` has +declared type `int` and initial value `7`. Struct field types (both declared +and optimized), function argument types (both declared and optimized), numeric +modes, store widths, and source locations also survive serialization. + +Each loaded `.simple` section restores its units into the shared `CompUnit` +tree, mirroring the original code layout. A dependency shared by several +objects uses the same `CompUnit`. Loaded aliases and function indices are +renumbered to avoid collisions; all the dense indices end up in the same +namespace. `GlobalBits` has the mapping from the imported file indices to the +local compilation indices; this remapping extends everywhere through the loaded +code, including recursive types that span several files. Importing skips +parsing the original source, but it still analysed and type checked with its +new callers. + +`ParseAll` is the workhorse that discovers source and object dependencies. It +tracks missing symbol references, looking them up in the search path one by one, +and loading the matching files. + +The end result combines locally parsed and imported IR in one graph, while +keeping their separate `CompUnit`s. This combined compilation can take +advantage of e.g. constants in the library, or inline library code using the +normal inlining heuristics. The combined graph goes through the normal +compilation phases, including peepholes, Opto and TypeCheck. + +Dependencies between `CompUnit`s are recorded. An explicitly requested source +file is always compiled. Other source files are recompiled if their object is +missing, their source is newer, or a recorded dependency's object in the build +directory is newer. These timestamp checks are not yet a complete incremental +build system, there is some modest future work needed to finish this. + +Loading currently works at the object granularity. Unrelated objects can stay +unloaded, but selecting an object loads its entire saved graph and follows its +recorded dependencies. Future work will look at loading sub-parts more +incrementally. + + + +## Analysis, ownership, and initialization + +An imported function can participate in analysis without belonging to the +client's output. Loading the `io` library, with its `p` print function, means +that `p` is part of the analysis - but when writing out the `helloWorld` app, +`p` will not end up in the `helloWorld.o` file directly. It might be inlined +fully, or called out of line, but there won't be a stand-alone copy of it. + +After optimization, `Serialize` saves ideal IR before `Lower` expands class +initialization. `Unlink` then detaches imported bodies for machine compilation +and removes analysis call edges. The client emits its own bodies and any code +copied into them by inlining; the +remaining calls refer to symbols supplied by the library object. + +Class initialization follows the previous chapter's rules. Importing a type +does not initialize its class. Active uses retain `CLInit` checks until +lowering (unless optimization clears them out). The library supplies its +shared class object and flag. Initialization checks appear at all the active-touch +locations, whether local or remote; including source locations for error +reporting. + + +## Building and checking + +From the repository root: + +```sh +make tests CHAPTERS=chapter28b +``` + +The suite includes the preceding constructor and escape regressions, imported +constructors, initialization cycles across objects, shared static data, native +function thunks, and native library/client execution. Make also builds the +modular `sys` object used by the library tests. Clients can import that object +with `-L`; they do not need to parse the standard library's source again. +`make release` builds the launcher jar and standard library; `make view` +starts the shared graph viewer. + +The serialized format is internal and currently unversioned beyond its `C0DE` +magic. Rebuild Simple objects when the compiler or layout changes. The expensive +serialization bijection check remains disabled, and `testModule0`, the older +incremental-rebuild experiment, remains ignored. They are not validation +guarantees for this snapshot. + +This completes the seven main snapshots in the [approved split](../chapter-split.md). +See the appendices on [native libraries](../appendices/native-libraries.md) +and [optimizer/backend tuning](../appendices/optimizer-tuning.md). diff --git a/simple.bat b/simple.bat new file mode 100644 index 00000000..8308e1aa --- /dev/null +++ b/simple.bat @@ -0,0 +1,10 @@ +@echo off +setlocal + +set "HERE=%~dp0" +set "RELEASE=%HERE%build\release" +set "JAR=%RELEASE%\Simple.jar" + +if not defined SIMPLE_HOME set "SIMPLE_HOME=%RELEASE%" + +java -jar "%JAR%" %* diff --git a/simple.ps1 b/simple.ps1 new file mode 100644 index 00000000..d7ea0678 --- /dev/null +++ b/simple.ps1 @@ -0,0 +1,10 @@ +$Here = Split-Path -Parent $MyInvocation.MyCommand.Path +$Release = Join-Path $Here "build\release" +$Jar = Join-Path $Release "Simple.jar" + +if (-not $env:SIMPLE_HOME) { + $env:SIMPLE_HOME = $Release +} + +& java -jar $Jar @args +exit $LASTEXITCODE diff --git a/simple.sh b/simple.sh new file mode 100644 index 00000000..32552ecc --- /dev/null +++ b/simple.sh @@ -0,0 +1,12 @@ +#! /bin/sh +here=$(CDPATH= cd -- "$(dirname -- "$0")" && pwd) +release="$here/build/release" +jar="$release/Simple.jar" + +if command -v cygpath >/dev/null 2>&1; then + release=$(cygpath -w "$release") + jar=$(cygpath -w "$jar") +fi + +export SIMPLE_HOME="${SIMPLE_HOME:-$release}" +exec java -jar "$jar" "$@" diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index c3ad0284..87a3570a 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.node.ScopeNode.Kind; import static com.seaofnodes.simple.util.Utils.TODO; @@ -2908,6 +2909,32 @@ public class Parser { } + public static void gather(Lexer loc, HashMap<String,Integer> strs) { + if( loc==null || loc._cu==null ) return; + Serialize.gather(strs,loc._cu._cname); + String file=loc._cu.sourceFile(); + if( file!=null ) Serialize.gather(strs,file); + } + + public static void packed(Lexer loc, BAOS out, HashMap<String,Integer> strs) { + if( loc==null || loc._cu==null ) { out.packed4(0); return; } + out.packed4(loc._position+1); + out.packed4(strs.get(loc._cu._cname)); + String file=loc._cu.sourceFile(); + out.packed4(file==null ? 0 : strs.get(file)); + } + + public static Lexer unpack(BAOS in, String[] strs) { + int pos=in.packed4(); + if( pos==0 ) return null; + String owner=strs[in.packed4()]; + String file=strs[in.packed4()]; + CompUnit cu=CodeGen.CODE._compunits.get(owner.replace('.','/')); + assert cu!=null : owner; + if( !file.isEmpty() ) cu._sourceFile=file; + return new Lexer(cu,pos-1); + } + /** * Copy a lexer from a lexer */ diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index e6bace8c..8302ede6 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -29,8 +29,10 @@ public class CodeGen { IterPostOpto, // Peepholes and inlining using SCCP results FinalizeIR, // Field layout, offset cleanup, function/CU roots TypeCheck, // Last check for bad programs + Serialize, // Save ideal IR, including opaque class initialization Lower, // Expand checked class initialization to ordinary IR LoopTree, // Build a loop tree; break infinite loops + Unlink, // Unlink call sites before machine code generation Select, // Convert to target hardware nodes Schedule, // Global schedule (code motion) nodes LocalSched, // Local schedule @@ -64,7 +66,12 @@ public class CodeGen { public final String _modDir; // Module Build Root public final String _buildDir; - // Slashed path from source root to the entry file, without ".smp". + // Search path from CWD for `.o` files containing external symbols and types. + // This can contain archives, zips and other .o file containers. + public final Ary<String> _externPaths; + + // Dotted path from module root to file containing the source, sans ".smp". + // e.g. module root: "sys", nested source name "sys.io". public final String _srcName; // Only available for tests, otherwise source comes from the CompUnit @@ -73,8 +80,12 @@ public class CodeGen { // Current Working Directory; default module base private final String _cwd; - // Source files discovered in this invocation. All live initializers - // participate in cycle checking, including fully inlined bodies. + // Compilation Units used in this compile; typically one per source/object + // file, although you can nest structs and get more than one. These are all + // required to compile, and are expected to have their source timestamps + // ahead of their obj file. Some of these may entirely be dead or inlined + // in this CompUnit and thus not needed in any linking stage. All the + // alive ones (inlined away or not) participate in class init cycle checks. public HashMap<String,CompUnit> _compunits; // Test shortcut for only one compilation unit @@ -88,7 +99,7 @@ public class CodeGen { // True when fidx is published through a public class or instance field. public boolean publicFIDX(int fidx) { - if( fidx < LocalIds.RESERVED ) return false; + if( fidx < GlobalBits.RESERVED ) return false; // A public class initializer is itself an external root; unlike // constructors and methods, it is not reached through a class field. FunNode fun = _linker.atX(fidx); @@ -142,7 +153,7 @@ public class CodeGen { void freezePublicInterface() { assert _publicFIDXs==null && _publicAliases==null; int[] fidxs = XInt.EMPTY; - for( int fidx=LocalIds.RESERVED; fidx<_linker._len; fidx++ ) + for( int fidx=GlobalBits.RESERVED; fidx<_linker._len; fidx++ ) if( publicFIDX(fidx) ) fidxs = XInt.make(fidxs,fidx); int[] aliases = XInt.EMPTY; @@ -185,15 +196,15 @@ public class CodeGen { // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen public CodeGen( String src, Type arg ) { - this(null,null,null, src, 126L, true, arg); + this(null,null,null,null, src, 126L, true, arg); } // Test setup; no module nor file; can alter seed & argument; can re-run same CodeGen public CodeGen( String src, long workListSeed, boolean resetTypes ) { - this(null,null,null, src, workListSeed, resetTypes, TypeInteger.BOT); + this(null,null,null,null, src, workListSeed, resetTypes, TypeInteger.BOT); } // Generic CodeGen, including full module setup - public CodeGen( String modDir, String buildDir, + public CodeGen( String modDir, String buildDir, Ary<String> externPaths, String srcName, String src, long workListSeed, boolean resetTypes, Type arg ) { // Public singleton to avoid passing about this state to a huge count // of places. Probably becomes a TLS at some point. @@ -203,6 +214,7 @@ public class CodeGen { _cwd = System.getProperty("user.dir")+"/"; _modDir = modDir == null ? _cwd : modDir; _buildDir = buildDir == null ? _cwd : buildDir; + _externPaths = externPaths; _srcName = srcName; _callingConv = null; // Calling convention // Source code from test strings, not files @@ -225,7 +237,9 @@ public class CodeGen { } - // Run the requested phases. ELF output contains machine code and data. + // Run requested phases. File export must request Serialize before Lower; + // requesting Export up front does that automatically. Encoding alone does + // not retain reloadable ideal IR. // No code emission, just IR generation public CodeGen driver( Phase phase ) { return driver(phase,null,null,false,false,0); } @@ -245,7 +259,8 @@ public class CodeGen { // The Generic driver public CodeGen driver( Phase target, String cpu, String callingConv, boolean inMemory, boolean emitEntrySymbol, int dump ) { - // Parse the entry source and discover all referenced source files. + // Parse a Simple file, and for mentioned external symbols either load + // from .o or recursively parse step(target, Phase.Parse, this::parse, dump); // Run peepholes to a fixed point step(target, Phase.Iter, this::iter, dump); @@ -257,12 +272,16 @@ public class CodeGen { step(target, Phase.FinalizeIR, this::finalizeIR, dump); // Final error check - bad programs fail here step(target, Phase.TypeCheck, this::typeCheck, dump); + // Save reloadable ideal IR for a later seperate compilation + step(target, Phase.Serialize, () -> Serialize.forTarget(this,target,inMemory), dump); // Replace "fat" nodes with their exploded explicit IR; this can // introduce CFG diamonds step(target, Phase.Lower, this::lower, dump); // Compute the loop-tree, used for approximating exec frequencies for // scheduling and register allocation step(target, Phase.LoopTree, this::loopTree, dump); + // Drop imports for machine selection, retain them for ideal evaluation. + step(target, Phase.Unlink, () -> unlink(cpu!=null), dump); // Instruction selection step(target, Phase.Select, () -> instSelect(cpu,callingConv), dump); // Global Code Motion @@ -273,7 +292,7 @@ public class CodeGen { step(target, Phase.RegAlloc, this::regAlloc, dump); // Encode machine instructions into bits step(target, Phase.Encoding, this::encode, dump); - // Export machine code and data into one ELF file + // Export bits (and serialized IR) into ELF files step(target, Phase.Export, () -> exportELF(inMemory,emitEntrySymbol), dump); return this; } @@ -329,13 +348,28 @@ public class CodeGen { } - // Allocate dense alias/function/call IDs within this invocation. - // Class slots let a forward reference reserve an initializer's identity. - public final LocalIds _aliases = new LocalIds(); + // These next fields all 2-way map some *global* program feature to a + // local dense index, suitable for packing in BitSets. The mapping takes a + // global value - always a {source file/class} name, and an order number + // counting up per feature in the same file. The dense local index can be + // different in different compilations. + + // The global info allows loading the same remote class info from different + // paths and aligning them. Example: Compiling A loads pre-compiled B and + // C, both of which load pre-compiled D. The 2 different D loads unify via + // this global info. + + // These mappings are all trivial identities when compiling one file; they + // only become complex when loading separately compiled code. + + // Compute local function index (FIDX) from global function info. This is + // called *in order* during parsing, and that order is part of the global + // unique mapping + public final GlobalBits _aliases = new GlobalBits(); public int alias(String clz) { return _aliases.next(clz); } // C storage has one global alias per symbol, including across object files. - public int externAlias(String name) { return _aliases.next("C:"+name,LocalIds.RESERVED); } + public int externAlias(String name) { return _aliases.next("C:"+name,GlobalBits.RESERVED); } // External data addresses supplied by an in-memory linker (image offsets). public final HashMap<String,Integer> _externDataAddresses = new HashMap<>(); @@ -343,14 +377,14 @@ public class CodeGen { // Compute local function index (FIDX) from global function info. This is // called *in order* during parsing, and that order is part of the global // unique mapping - public final LocalIds _fidxs = new LocalIds(); + public final GlobalBits _fidxs = new GlobalBits(); // Return local index for specific global file & order. Used to find fidxs for e.g. FREF class <init> fcns public int fidx( String clz, int order ) { return _fidxs.next(clz, order); } // New fidx in the current file public int fidx( String clz ) { return fidx(clz, -1); } // Compute local RPC index from global RPC info, one per call - public final LocalIds _rpcs = new LocalIds(); + public final GlobalBits _rpcs = new GlobalBits(); public int rpc( String clz ) { return _rpcs.next(clz); } @@ -407,7 +441,6 @@ public class CodeGen { // TFPs all have exact single fidxs and their return is wiped to BOTTOM (so // the return is not part of the match). public final Ary<FunNode> _linker = new Ary<>(FunNode.class); - public final Ary<CallNode> _calls = new Ary<>(CallNode.class); // Extern function declarations; input is the FIDX assigned to the name. final HashMap<Integer,String> _externFunc = new HashMap<>(); @@ -430,6 +463,8 @@ public class CodeGen { // --------------------------- // Parser object + public final Ary<CallNode> _calls = new Ary<>(CallNode.class); + public final Parser P; // Parse ASCII text into Sea-of-Nodes IR @@ -483,17 +518,20 @@ public class CodeGen { // --------------------------- // TypeCheck queued surviving CLInits during its existing error walk. public CodeGen lower() { - return phase(Phase.Lower, _phase==Phase.TypeCheck, () -> _iter.iterate(this)); + return phase(Phase.Lower, (_phase==Phase.TypeCheck || _phase==Phase.Serialize), () -> _iter.iterate(this)); } // --------------------------- // Build the loop tree; break never-exit loops public CodeGen loopTree() { - return phase(Phase.LoopTree, _phase==Phase.Lower, () -> { _start.buildLoopTree(_linker,_stop); FinishCalls.run(this); }); + return phase(Phase.LoopTree, _phase==Phase.Lower, () -> _start.buildLoopTree(_linker,_stop)); } // --------------------------- - + public BAOS _serial; + public void serialize() { + phase(Phase.Serialize, _phase==Phase.TypeCheck, () -> Serialize.serialize(this)); + } // --------------------------- // Code generation CPU target @@ -522,7 +560,12 @@ public class CodeGen { } // --------------------------- - + public void unlink() { + unlink(true); + } + private void unlink(boolean removeImports) { + phase(Phase.Unlink, _phase==Phase.LoopTree, () -> Unlink.run(this,removeImports)); + } // --------------------------- // Control Flow Graph in Reverse Post Order. @@ -530,7 +573,7 @@ public class CodeGen { // Global schedule (code motion) nodes public CodeGen GCM() { - return phase(Phase.Schedule, (_phase==Phase.LoopTree || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); + return phase(Phase.Schedule, (_phase==Phase.Unlink || _phase==Phase.Select), () -> GlobalCodeMotion.buildCFG(this)); } // --------------------------- @@ -576,6 +619,110 @@ public class CodeGen { // --------------------------- + // Search a external path list, each path is recursively searched for .o + // files, which are partially loaded and searched for public symbols. + + // This is a state machine which lazily searches down the set of search + // paths until the requested module is class is found. + + // Map from external Strings to either partially read Simple ElfFile or ExternNode + public final HashMap<String,Object> _externSymbols = new HashMap<>(); + + // State machine elements; the outermost element is _externPaths + private int _extPathIdx; // Search index into the extern path list + private final Ary<File> _files = new Ary<>(File.class); // Files in the current extern path being searched + private int _extFileIdx; // Index into _files + + public ElfReader findExternalSimple( String name ) { + return findExternalSymbol(name) instanceof ElfReader elf ? elf : null; + } + + public ExternNode findExternal( String name ) { + return findExternalSymbol(name) instanceof ExternNode extern ? extern : null; + } + + // Search the search-path for the name; return an ElfReader if found in a + // Simple-made ELF; return an ExternNode if from another ELF, or null if + // not found. + private Object findExternalSymbol( String name ) { + // State Machine! + + while( true ) { + // Check for an immediate hit + switch( _externSymbols.get(name) ) { + + case ExternNode extern: + // Name maps to an ExternNode + return extern; + + case ElfReader elf: + return elf; + + case null: + // Name is unknown. Advance the file-system search, pulling + // out new ELF files from the search directory list and loading + // their published symbols. + + // The last directory was mined out, so get the next search + // directory and find all ELF-like files. + if( _extFileIdx >= _files._len ) { + if( _externPaths==null || _extPathIdx >= _externPaths._len ) + return null; // A true miss in the whole search path + loadExtPath(); // Load next batch file of files + break; + } + // Load and parse an ELF header + ElfReader elf = getElf(_files.at(_extFileIdx++)); + if( elf == null ) break; // Not an ELF + // Load public symbols from the ELF + elf.loadPublicSymbols(); + if( elf._strs==null ) break; // No .simple section with strings + // Put public symbol in global table; first names shadow all others + // Map from symbol string to ELFReader; most lookups + // will miss and no need to unpack ElfReader types + _externSymbols.putIfAbsent(elf._strs[1],elf); + + // Publish definitions only; referenced classes belong to other objects. + for( String fname : elf._units ) + _externSymbols.putIfAbsent(Parser.addClzPrefix(fname.replace('/','.')),elf); + break; + + default: throw Utils.TODO("should not reach here"); + } + } + } + + // Load all the .o files in the next external path. + private void loadExtPath() { + _files.clear(); + _extFileIdx = 0; + String extpath = _externPaths.at(_extPathIdx++); + File f = new File(extpath); + if( !f.isAbsolute() ) + f = new File(_cwd+extpath); + fillExtFiles(f); + } + + // Recursive search (TODO: gzip, archives) and gather all .o files. + private void fillExtFiles(File dir) { + if( dir.isDirectory() ) + for( File f : dir.listFiles() ) + fillExtFiles(f); + else if( dir.getName().endsWith(".o") ) + _files.add(dir); + } + + // Map from object file names to ElfReaders + public final HashMap<String,ElfReader> _elfs = new HashMap<>(); + ElfReader getElf(File f) { + ElfReader elf = _elfs.get(f.getPath()); + if( elf != null ) + return elf; + _elfs.put(f.getPath(), elf = ElfReader.load(f,null)); + return elf; + } + + // --------------------------- public boolean _asmLittle=true; public String asm() { return asm(new SB()).toString(); } SB asm(SB sb) { diff --git a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java index c8b0a82c..71126795 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java @@ -12,23 +12,30 @@ import java.nio.file.Path; import java.util.*; import static com.seaofnodes.simple.codegen.CodeGen.CODE; -// A source file and its class. Parent links follow the source directory tree. +// A compilation-unit, which is an external reference and source and object +// files. These are mirrored over a file system tree (so form a tree), both +// the source tree and build/object tree. public class CompUnit { public final CompUnit _par; // Parent, e.g. A/B final String _fname; // Full slashed file name starting from module root, e.g. A/B/C final public String _cname; // Full dotted class name starting from module root, e.g. A.B.C final String _name; // Base name, e.g. C + final ExternNode _ext; // Found in external libs; e.g. libc final File _smp; // Simple source file, e.g. module_root/A/B/C.smp + public final File _obj; // ELF output file, e.g. build/A/B/C.o final public String _src; // Source code, from file or test case + // Original source path from an imported diagnostic location. Does not + // affect discovery/rebuild decisions, which use _smp and _src. + public String _sourceFile; public String sourceFile() { - return _smp!=null ? _smp.getAbsolutePath() : null; + return _smp!=null ? _smp.getAbsolutePath() : _sourceFile; } public TypeStruct _clz; // The one TypeStruct being published // _deps records units required for types, code, or class references, - // without requiring their initializers to run. These source + // without requiring their initializers to run. These discovery/rebuild // dependencies may form a cycle. Ary<CompUnit> _deps; @@ -45,17 +52,16 @@ public class CompUnit { _fname= fname; _cname= cname; _name = name; - _smp = source(fname); + _ext = null; + _smp = new File( CODE. _modDir + "/" + fname + ".smp"); + _obj = new File( CODE._buildDir + "/" + fname + ".o" ); - _src = _smp.exists() ? Files.readString(_smp.toPath()) : null; - } - - // The bundled library is ordinary source. A local sys tree can replace it; - // this chapter never loads Simple code from an object file. - static File source(String fname) { - File file=new File(CODE._modDir,fname+".smp"); - if( file.exists() || !(fname.equals("sys") || fname.startsWith("sys/")) ) return file; - return new File("src/main/smp",fname+".smp"); + boolean mustCompile = _smp.exists() && // Has source to compile + ( fname.equals(CODE._srcName) || // Explicit input is a compilation request + !_obj.exists() || // No object file + _smp.lastModified() > _obj.lastModified() || // Out-of-date with source? + checkDependentObjs() ); // Out-of-date with other objs? + _src = mustCompile ? new String(Files.readAllBytes(_smp.toPath())) : null; } // Test case. No source file. Source code passed in as a String. Fake @@ -65,11 +71,49 @@ public class CompUnit { _name = fname; _fname= fname; _cname= fname; + _ext = null; _smp = null; + _obj = null; _src = src; } - // Record source discovery without adding an initialization edge. + // External CompUnit, pulled in from an external library like libc + CompUnit( ExternNode ext, String symbol ) { + _par = null; + _name = symbol; + _fname= _name; + _cname= null; + _ext = ext; + _smp = null; + _obj = null; + _src = null; + } + + // External Simple object file, or namespace parent, found on an external search path. + CompUnit( File obj, CompUnit par, String fname, String cname, String name ) { + _par = par; + _name = name; + _fname= fname; + _cname= cname; + _ext = null; + _smp = null; + _obj = obj; + _src = null; + } + + // Return true if _obj is out-of-date relative to dependents. + private boolean checkDependentObjs() { + ElfReader elf = CODE.getElf(_obj); + elf.loadPublicSymbols(); + for( String dep : elf._deps ) { + File obj = new File(CODE._buildDir+"/"+dep+".o"); + if( obj.lastModified() > _obj.lastModified() ) // Out-of-date with deps? + return true; + } + return false; + } + + // Add a discovered dependency, for later writing out in an ELF file, ".simple" section void addDep(CompUnit dep) { if( _deps == null ) _deps = new Ary<>(CompUnit.class); _deps.add(dep); @@ -91,7 +135,9 @@ public class CompUnit { @Override public String toString() { String x = "{"+_cname; if( _smp!=null && _smp.exists()) x += ",hasSMP"; + if( _obj!=null && _obj.exists()) x += ",hasObj"; if( _src!=null ) x += ",hasSrc"; + if( _ext != null ) x += ",isExt"; x += "}"; return x; } diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java new file mode 100644 index 00000000..10720300 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfReader.java @@ -0,0 +1,236 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.type.TypeMemPtr; +import com.seaofnodes.simple.type.TypeStruct; +import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; +import com.seaofnodes.simple.util.Utils; +import java.io.*; +import java.nio.file.Files; +import java.util.HashMap; + +public class ElfReader { + + public final File _file; + public final byte[] _buf; + int _x; // Cursor into buffer + // ELF Header + public final ElfHeader _header; + // All sections + public final Section[] _sections; + // Simple section, if available + public final Section _simple; + // Byte array in/out stream - used as a reader + public final BAOS _bais; + // Compilation unit; written into FunNodes + public final CompUnit _compunit; + + // Strings from the Simple section, either small public set or whole set + public String[] _strs; + // Dependent file names + public String[] _deps; + // Compilation units defined by this object, independent of init analysis. + public String[] _units; + // Only published symbol this file + public TypeStruct _clz; + // Canonical named types, distinct from optimized same-named graph states. + public TypeStruct[] _pubTypes; + // Nodes read in this Elf + public Ary<Node> _nodes; + + // Load an Elf file (mostly lazily) + public static ElfReader load( File f, CompUnit cu ) { + try { return new ElfReader(f,cu); } + catch( IOException ioe ) { return null; } + } + + // Load the Simple section from the ELF file + private ElfReader( File f, CompUnit cu ) throws IOException { + _file = f; + _compunit = cu; + _buf = Files.readAllBytes(f.toPath()); + _header = new ElfHeader(); + // No attempt is made to parse the program header table. + _sections = new Section[_header._shnum]; + for( int i=0; i<_header._shnum; i++ ) + _sections[i] = new Section(i); + + // Load section names + Section secstr = _sections[_header._shstrndx]; + for( Section sec : _sections ) + if( sec._type != 0 ) + sec._name = secstr.str(sec._noff); + + Section simple = null; + for( Section sec : _sections ) + if( ".simple".equals(sec._name) ) + simple = sec; + _simple = simple; + _bais = new BAOS(_buf, (int)_simple._offset); + } + + // For Serialize self-test + ElfReader( BAOS bais ) { + _file = null; + _compunit = null; + _buf = bais.buf(); + _header = null; + _sections = null; + _simple = null; + _bais = bais; + } + + // Load the public symbols and dependent objs, but not the whole IR + void loadPublicSymbols() { + // Check already loaded and cached + if( _strs == null && _simple != null ) + // Read only the published public strings, for speed purposes when + // scanning a large count of ELF files but getting hits in only a + // few of them. i.e. optimizing (prematurely?) for the traditional + // case of linking a small file against a large library + Serialize.read_public_strs(this); + } + + // Loads the entire IR + public TypeStruct loadSimple(CodeGen code) { + Serialize.readAll(code, this, code._aliases, code._fidxs, code._rpcs); + return _clz; + } + + // Loads strings, mappings, and types, but not Nodes. Used after the + // public-string scan finds a matching Simple ELF, so parsing can resolve + // imported field/array aliases before the full graph is linked in later. + public TypeStruct loadPublicTypes(CodeGen code) { + Serialize.readTypes(code, this, code._aliases, code._fidxs, code._rpcs); + return _clz; + } + + int u1() { return _buf[_x++]&0xFF; } + int magic() { // Big endian + return (u1() << 24) | (u1() << 16) | (u1() << 8) | u1(); + } + int u2() { return u1() | (u1()<<8); } // Little endian + int u4() { // Little endian + return u1() | (u1() << 8) | (u1() << 16) | (u1() << 24); + } + long u8() { return u4() | ((long)u4()<<32); } + void skip(int skip) { _x += skip; } + + + public class ElfHeader { + final int _magic; + final boolean _format32; // Format32 or format64 + final byte _osabi; + final boolean _little; // True if little endian, false if big endian + final char _type; + final char _machine; + final long _entry; // Process entry point + final long _phoff; // Program header table offset, from file start + final long _shoff; // Section header table offset, from file start + final int _flags; // Flags + final int _phnum; // Number of program header entries + final int _shentsize; + final int _shnum; // Number of section header entries + final int _shstrndx; // Section header index contains section names + + + ElfHeader() throws IOException { + _x = 0; + if( (_magic = magic()) != 0x7F454C46 ) bad("magic number",_magic); + byte EI_CLASS = (byte)u1(); + if( EI_CLASS != 1 && EI_CLASS != 2 ) bad("EI_CLASS",EI_CLASS); + _format32 = (EI_CLASS==1); + byte EI_DATA = (byte)u1(); + if( EI_DATA != 1 && EI_DATA != 2 ) bad("EI_DATA",EI_DATA); + _little = EI_DATA == 1; + if( u1() != 1 ) bad("version",1); + if( (_osabi=(byte)u1()) != 0 ) bad("EI_VERSION",_osabi); + byte abiversion = (byte)u1(); + if( abiversion != 0 ) bad("EI_ABIVERSION",abiversion); + skip(7); // Pad + + // Endian matters now + if( !_little ) throw new IOException("TODO: Big endian"); + if( (_type = (char)u2()) != 1 ) bad("ET_REL",_type); + if( (_machine = (char)u2()) != 0x3E ) bad("AMD x86-64",_machine); + int ver = u4(); + if( ver != 1 ) bad("Version",ver); + // Format32 matters now + if( _format32 ) bad("Format",1); + _entry = u8(); // Process entry point + _phoff = u8(); // Program header table offset + _shoff = u8(); // Section header table offset + _flags = u4(); // Flags + int ehsize = u2(); + if( ehsize != 0x40 ) bad("EHSIZE",ehsize); + int phentsize = u2(); + if( phentsize != 0x38 && phentsize != 0 ) bad("PHENTSIZE",phentsize); + _phnum = u2(); + _shentsize = u2(); + if( _shentsize != 0x40 ) bad("SHENTSIZE",_shentsize); + _shnum = u2(); + // String section + _shstrndx = u2(); + assert _x == ehsize; + } + } + + public class Section { + final int _noff; // Offset in string section for name + final int _type; // Section type + final long _flags; + final long _addr; // Offset in virtual mem, if loaded + final long _offset; // Offset in file + final long _size; // Size in bytes + final int _link; // Associated section index, varies + final int _info; // Varies + final byte _align; // Log2 alignment + final int _esize; // Element size, if non-zero + String _name; + + Section(int sidx) throws IOException { + _x = (int)(_header._shoff + (sidx * _header._shentsize)); + _noff = u4(); + _type = u4(); + _flags = u8(); + _addr = u8(); + _offset= u8(); + _size = u8(); + _link = u4(); + _info = u4(); + long align = u8(); + if( align==0 ) align=1; + _align = (byte)Long.numberOfTrailingZeros(align); + if( (1L << _align ) != align ) + throw new IOException("Bad section alignment: "+align); + _esize = (int)u8(); + } + + String str(int off) { + assert _type == 3/*SHT_STRTAB*/; // String table section header + int start = (int)(_offset+off); + int x = start; + while( _buf[x++] !=0 ) ; + return new String(_buf,start,x-start-1); + } + } + + private static void bad(String msg, int val) throws IOException { + throw new IOException("Bad "+msg+": "+val); + } + + + + //public TypeMemPtr lookup( String name ) { + // if( _simple == null ) return null; + // BAOS baos = new BAOS(_buf, (int)_simple._offset); + // Ary<String> strs = Serialize.read_strs(baos); + // + // + // + // Ary<Node> nodes = Serialize.read_types(baos); + // + // throw Utils.TODO("Elf load symbol "+name); + //} +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java index c52209dd..5a280723 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ElfWriter.java @@ -27,6 +27,7 @@ public class ElfWriter { static final int SHT_SYMTAB = 2; static final int SHT_STRTAB = 3; static final int SHT_RELA = 4; + static final int SHT_SIMPLE = 10; // Simple section final String _name; final int _type, _entsize, _index, _name_pos, _flags; @@ -275,6 +276,9 @@ public class ElfWriter { public static final int SECTION_HDR_SIZE = 64; // ------------------------------------------------------------------------ + public class SimpleSection extends DataSection { + SimpleSection(BAOS serial) { super(".simple", SHT_SIMPLE, serial, 0); } + } // ------------------------------------------------------------------------ @@ -300,6 +304,8 @@ public class ElfWriter { } public ElfWriter export(boolean emitEntrySymbol) { + if( _code._serial==null ) + throw new IllegalStateException("ELF export needs ideal IR: request Export from the driver, or Serialize before Lower"); // Sections are created in the order they are emitted. _sections = new Ary<>(Section.class); @@ -311,7 +317,7 @@ public class ElfWriter { _strtab = new StringSection(); // place all the symbols - int nlocals = 1/*null*/+9/*number of sections*/; + int nlocals = 1/*null*/+9/*number of sections*/+1/*Simple section*/; SymbolSection symbols = new SymbolSection(nlocals); // we've already constructed these entire sections in the encoding phase @@ -392,6 +398,7 @@ public class ElfWriter { } // Create a "Simple" section for Simple types and ir + SimpleSection simple = new SimpleSection(_code._serial); // Write the local section header symbols assert nlocals == 1+_sections._len; diff --git a/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java b/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java deleted file mode 100644 index 7ba696d3..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/FinishCalls.java +++ /dev/null @@ -1,57 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import com.seaofnodes.simple.node.*; - -// Detach analysis call edges after building the loop tree. Every live body -// belongs to this invocation; preserve it for scheduling and emission. -abstract class FinishCalls { - - - static void run(CodeGen code) { - - // The remaining passes assume all calls are unlinked; i.e. we are throwing - // away the Call Graph here. Functions only reachable from internal calls - // need to be re-hooked to stop/start less they go dead. - for( FunNode fun : code._linker ) { - // Already linked to start, not going dead - if( fun==null || fun.isDead() ) - continue; - - // Insert the post-Opto code-generation hook. Unlike an Opto-time - // Start input, this no longer carries unknown-caller semantics. - ReturnNode ret = fun.ret(); - StartNode start = fun._compunit._start; - assert start!=null; - if( fun.nIns() <= 1 || fun.in(1) != start ) { - fun.insertDef(1,start); - for( Node use : fun._outputs ) - if( use instanceof ParmNode parm ) - parm.insertDef(1,ConstantNode.raw(parm._type)); - if( fun._compunit._stop._inputs.find(ret) == -1 ) - fun._compunit._stop.addDef(ret); - } - // Unlink from Call - for( int i=2; i<fun.nIns(); i++ ) - ((CallNode)fun.in(i)).unlink(fun,i--); - if( fun.rpc()==null ) { // Ensure valid RPC - // First make sure a valid RPC; single-call into multi-fun will have each - // function having a single call site, so the RPC becomes a constant and - // folds - but since multiple targets, the Call never inlines. Recreate a - // valid RPC so codegen (and Eval2) understands the calling convention. - ParmNode rpc = new ParmNode( "$rpc", 0, ret.rpc()._type, fun ); - rpc.addDef(ret.rpc()); - ret.setDef( 3, rpc.init() ); - } - } - - code._stop.walk(n -> { - if( n instanceof CallEndNode cend ) - for( int i=1; i<cend.nIns(); i++ ) - if( cend.in(i) instanceof ReturnNode ) - cend.delDef(i--); - if( n instanceof CallNode call ) - call.unlink_all(); - return null; - }); - } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java new file mode 100644 index 00000000..bc9c9d39 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalBits.java @@ -0,0 +1,177 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.util.*; +import java.util.HashMap; +import java.util.Arrays; +import java.util.Objects; + + +// This utility 2-way maps some *global* program feature to a local dense +// index, suitable for packing in BitSets. The mapping takes a global value - +// always a {source file/class} name and an order number counting up per +// feature in the same file. The dense local index can be different in +// different compilations. + +// The global info allows loading the same remote class info from different +// paths and aligning them. Example: Compiling A loads pre-compiled B and C, +// both of which load pre-compiled D. The 2 different D loads unify via this +// global info. + +// These mappings are all trivial identities when compiling one file; they +// only become complex when loading seperately compiled code. + +public class GlobalBits { + public static final int RESERVED = 2; + private final HashMap<String,int[]> _clzOrder2Local = new HashMap<>(); + private final Ary<String> _local2Clz = new Ary<>(String.class); + private final AryInt _local2Order = new AryInt(); + // Local dense index + private int _local; + + GlobalBits() { + _local = RESERVED; + // Reserved null-class bits are global identities and are never + // remapped. + int[] xs = new int[RESERVED]; + xs[0] = RESERVED; // Per-class next order counter + for( int i=0; i<RESERVED; i++ ) { + if( i > 0 ) xs[i] = i; + _local2Clz .setX(i,null); + _local2Order.setX(i,i); + } + _clzOrder2Local.put(null,xs); + } + + // Get a next local index for this clz + int next( String clz ) { return next(clz,-1); } + + // Given a clz and order, return an existing local index or make a new + // mapping and return that. + int next(String clz, int order ) { + // Get the per-clz Order->Local mapping + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; // Make, if it does not exist + // Caller does not have an order in mind, just take the next one stored + // in xs[0] + if( order == -1 ) + order = xs[0]++; + // Order exists from prior compilation, but not recorded locally + else if( order >= xs[0] ) + xs[0] = order+1; + // Grow as needed + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + // Have a local mapping already? + if( xs[order] != 0 ) + return xs[order]; + int local = _local++; + bind(local,clz,order); + return local; // The dense local index + } + + // Bind a specific dense local index to {clz,order}. Used by both fresh + // allocation and deserialization, where local indexes must not compact + // across holes because XInt bitsets are serialized against this space. + private void bind( int local, String clz, int order ) { + if( _local <= local ) + _local = local+1; + _local2Clz .setX(local,clz ); + _local2Order.setX(local,order); + + // Inline-only fidx holes are represented as {null,0}. They need the + // reverse mapping above, but no forward map because xs[0] is the + // per-class next-order counter. + if( clz==null && order==0 ) + return; + + int[] xs = _clzOrder2Local.get(clz); + if( xs == null ) + xs = new int[]{RESERVED,1}; + if( order >= xs[0] ) + xs[0] = order+1; + while( xs.length <= order ) + xs = Arrays.copyOf(xs,xs.length*2); + _clzOrder2Local.put(clz,xs); + xs[order] = local; + } + + // A file-local function that will inline, and never write to disk + public int nextInline( ) { + int local = _local++; + _local2Clz .setX(local,null); + _local2Order.setX(local,0); + return local; + } + // Get a next local index for the same clz as this old index + public int next( int old ) { return next(_local2Clz.at(old)); } + + // Map a file-local dense index to this compilation unit's local dense index. + public int map( GlobalBits fileBits, int fileLocal ) { + if( fileLocal >= fileBits._local2Clz.size() ) + throw new ArrayIndexOutOfBoundsException(""+fileLocal+" >= "+fileBits._local2Clz.size()); + return findOrNext(fileBits._local2Clz.at(fileLocal), fileBits._local2Order.at(fileLocal)); + } + + // Map a global {clz,order} to a local one; keep any existing mapping or + // make a new one as needed. + private int findOrNext(String clz, int order ) { + // Reserved null-class identities are not represented in xs[order], + // because xs[0] is the next-order counter. + if( clz==null && order < _local2Clz.size() && _local2Order.at(order)==order && _local2Clz.at(order)==null ) + return order; + int[] xs = _clzOrder2Local.get(clz); + if( xs != null && order < xs.length ) { + int local = xs[order]; + if( local < _local2Clz.size() && _local2Order.at(local)==order && Objects.equals(_local2Clz.at(local),clz) ) + return local; + } + return next(clz,order); + } + + // Stable native symbol identity, independent of this compilation's dense IDs. + String owner(int local) { return _local2Clz.at(local); } + String symbol(int local) { + return _local2Clz.at(local)+"$F$"+_local2Order.at(local); + } + + // Write out to BAOS enough bits to unwind the local back to global index + void packed( BAOS baos, HashMap<String,Integer> strs ) { + // Unwind a local index to the clz. + baos.packed2(_local2Clz.size()); + for( int i=RESERVED; i<_local2Clz.size(); i++ ) { + String clz = _local2Clz.at(i); + baos.packed2(clz==null ? 0 : strs.get(clz)); + baos.packed2( _local2Order.at(i) ); + } + } + + void gather( HashMap<String,Integer> strs ) { + for( int i=RESERVED; i<_local2Clz.size(); i++ ) + Serialize.gather(strs,_local2Clz.at(i)); + } + + // Read in the BAIS bits needed to make a file-local -> global mapping + static GlobalBits packed( BAOS bais, String[] strs ) { + var gb = new GlobalBits(); + int n = bais.packed2(); + for( int i=RESERVED; i<n; i++ ) { + int sx = bais.packed2(); + String clz = strs[sx]; + if( clz.isEmpty() ) clz = null; + int order = bais.packed2(); + gb.bind(i,clz,order); + } + return gb; + } + + @Override public String toString() { + SB sb = new SB().p('['); + for( int i=0; i<_local2Clz.size(); i++ ) { + if( i > 0 ) sb.p(','); + sb.p(i).p(" <-> ").p(_local2Clz.at(i)).p('#').p(_local2Order.at(i)); + } + return sb.p(']').toString(); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 4477025b..09eb8d33 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -60,7 +60,7 @@ public abstract class GlobalCodeMotion { if( use==null || globals.containsKey(use) ) continue; FunNode fun = useFun(use); if( fun==null ) continue; // Global metadata has no function owner. - assert CodeGen.CODE._mach==null || CodeGen.CODE.owns(fun); + assert CodeGen.CODE._mach==null || CodeGen.CODE.owns(fun); // Ideal evaluation includes imported bodies. var local = copies.computeIfAbsent(fun,f -> new IdentityHashMap<>()); Node copy = cloneGlobal(con,fun,globals,local); for( int i=0; i<use.nIns(); i++ ) diff --git a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java index db35d524..5fc002a1 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java +++ b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java @@ -14,7 +14,7 @@ class InstSelect { static CodeGen select(CodeGen code, String cpu, String callingConv, String base) { // Ideal evaluation schedules the ideal graph without a CPU port. if( cpu==null ) return code; - return code.phase(CodeGen.Phase.Select, code._phase==CodeGen.Phase.LoopTree, + return code.phase(CodeGen.Phase.Select, code._phase==CodeGen.Phase.Unlink, () -> new InstSelect(code).run(cpu,callingConv,base)); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Iter.java b/src/main/java/com/seaofnodes/simple/codegen/Iter.java index 1ffd9737..c5120370 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Iter.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Iter.java @@ -3,15 +3,19 @@ package com.seaofnodes.simple.codegen; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -// Establish a pessimistic fixed point after parsing. Later Iter runs +// Establish a pessimistic fixed point after parsing/loading. Later Iter runs // reuse the worklist and types produced by the preceding phase. abstract class Iter { static void run(CodeGen code) { - // Close parser-in-progress states. Seed a fresh pessimistic solve; - // exposure sets start at FULL and can only shrink during Iter. + // The phase shift closes all parser-in-progress states and freezes + // unknown external inputs. Imported nodes carry post-Opto escape + // precision, but Iter is a fresh pessimistic solve: memory escape + // summaries must restart at FULL so newly discovered private escapes + // can only be removed, never added. Seed the complete graph once. + boolean hasImports = code._externPaths != null; code._start.walk(n -> { if( !(n instanceof ConstantNode) ) - n._type = iterEscapeReset(n._type); + n._type = hasImports ? iterImportReset(n._type) : iterEscapeReset(n._type); code.add(n); return null; }); @@ -34,5 +38,23 @@ abstract class Iter { return t; } - + private static Type iterImportReset(Type t) { + if( t.isHigh() ) + return t.dual(); + if( t instanceof TypeMem mem ) + return TypeMem.make(mem._alias,iterImportReset(mem._t),mem._one,mem._clz,mem._final,XInt.FULL,XInt.FULL); + if( t instanceof TypeMemPtr ) + return t.makeStorage(); + if( t instanceof TypeStruct ) + return t.makeStorage(); + if( t instanceof TypeTuple tt ) { + TypeTuple rez = tt; + for( int i=0; i<tt._types.length; i++ ) { + Type tx = iterImportReset(tt._types[i]); + if( tx != tt._types[i] ) rez = rez.makeFrom(i,tx); + } + return rez; + } + return t; + } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java b/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java deleted file mode 100644 index 462248dd..00000000 --- a/src/main/java/com/seaofnodes/simple/codegen/LocalIds.java +++ /dev/null @@ -1,33 +0,0 @@ -package com.seaofnodes.simple.codegen; - -import java.util.HashMap; -import java.util.Arrays; - -// Dense IDs for this invocation. A class slot can be reserved before its file -// is parsed; every later reference to that slot gets the same ID. -public class LocalIds { - public static final int RESERVED=2; - private int _next=RESERVED; - private final com.seaofnodes.simple.util.Ary<String> _owners=new com.seaofnodes.simple.util.Ary<>(String.class); - private final HashMap<String,int[]> _slots=new HashMap<>(); - - public int next(String owner) { return next(owner,-1); } - public int next(String owner, int slot) { - int[] ids=_slots.get(owner); - if( ids==null ) ids=new int[]{RESERVED,1}; - if( slot==-1 ) slot=ids[0]++; - else if( slot>=ids[0] ) ids[0]=slot+1; - if( slot>=ids.length ) ids=Arrays.copyOf(ids,Math.max(slot+1,ids.length*2)); - if( ids[slot]==0 ) { ids[slot]=_next++; _owners.setX(ids[slot],owner); } - _slots.put(owner,ids); - return ids[slot]; - } - public String owner(int id) { return _owners.atX(id); } - public String symbol(int id) { return owner(id)+".$fun"+id; } - public int nextInline() { return _next++; } - public int next(int old) { - int id=_next++; - _owners.setX(id,owner(old)); - return id; - } -} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Module.java b/src/main/java/com/seaofnodes/simple/codegen/Module.java new file mode 100644 index 00000000..a5d85dbc --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Module.java @@ -0,0 +1,98 @@ +package com.seaofnodes.simple.codegen; + + +/*** + Modules!?!?!? + + Goal: under no circumstances can you load from an uninitialized variable + (although you can see default inits for fields that have defaults). + Goal: nested tree-structured name spaces, to control complexity. + Goal: field decl order within a file is fairly flexible. + + A Module a root-level SMP file, and the full file path must be provided on + the command line. All other Simple structs are relative to this file. + + Example: "simple /user/Dave/hello.smp" + + Defines a module "hello" in directory "/user/Dave", compiles and produces + a `hello` or `hello.exe` output file, and runs it. + + A SMP file has some <finit> file-init code which is static-global. + This code is executed on "first touch" of the file (defined below). + + Example: hello.smp contains: + sys.io.p("Hello World!"); + On first-touch, will print "Hello World!". + + A SMP file is a lexical scope, and code inside it can reference those names. + + Example: hello.smp contains: + val greet = "Hello World!"; // Declare file-scoped variable + sys.io.p(greet); // Reference file-scoped variable + + Static code is NOT allowed to have forward-references AND be executed + before the <finit> finishes initializing all variables. After var + initialization, a singleton instance of the implied file struct is made, + and then <finit> code can call anything. + + Example: + sys.io.p(greet); // Illegal forward reference + val greet = "Oops!"; + + Example: + val delay = { -> greet }; // Legal forward ref, but cannot execute (yet) + val greet = "Hello World!"; // Ref is resolved + sys.io.p(delay()); // Allowed to call delay() + val nprimes = { N -> + // compute number of primes < N + } + // Can otherwise execute any code in a <finit> + sys.io.p(nprimes(100)); + + Inside a directory, you can have sibling SMP files: + File hello.smp contains: + sys.io.p(I9A.GREETING); // File hello references sibling file I9A static globals + File I9A.smp contains: + val GREETING = translate("Hello World!"); + val translate = { str msg -> ... }; + + <finit> code cannot reference sibling files (nor child files, see below) + until all static variables are initialized. This prevents cyclic + initialization bugs, where file A uses vars from file B and vice-versa. + + File Chicken.smp contains: + val lay = Egg.hatch; // Illegal, defining var 'lay' after calling sibling Egg + File Egg.smp contains: + val hatch = Chicken.lay; // Illegal + + You can make cross references, if they get delayed until after all fields + are declared. + + File Chicken.smp contains: + int lay = 2; + lay = Egg.egg; + + File Egg.smp contains: + int egg = 3; + egg = Chicken.lay; + + The problem here, of course, is that you need to touch one of Chicken or + Egg first. + + + Inside a SMP file, you can define structs; structs are also a lexical + scope. Bare code in the struct is part of the struct's <init> and only + runs when an instance is created. Structs do not have static <clinit> (nor + <finit>). Structs <init> cannot have any forward references, and locally + declared functions cannot have both forward references and be executed (or + passed along to a possibly-executing function). + + In the same directory as a SMP file, Simple allows other directories with + names matching SMP files. Inside these dirs can be more SMP files that are + lexically nested, similar to embedded structs. + + +*/ + +public abstract class Module { +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index 4db277df..3b3f9f19 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -74,7 +74,7 @@ abstract public class Opto { // Start is a semantic unknown-caller edge. Public functions // keep it; closed-world functions must be reached by a // concrete Call edge discovered during SCCP. Initializers, - // including private ones, are called by opaque CLInit + // including private/imported ones, are called by opaque CLInit // obligations whose Call edges are introduced only in Lower. if( !fun.isClz() && !code.publicFIDX(fun.sig().fidx()) && diff --git a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java index 171d9923..c55f9a90 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java +++ b/src/main/java/com/seaofnodes/simple/codegen/ParseAll.java @@ -28,21 +28,34 @@ public abstract class ParseAll { // Worklist of symbols to search and files to parse private static final Ary<CompUnit> WORK = new Ary<>(CompUnit.class); + private static final Ary<CompUnit> NEEDS_LOAD = new Ary<>(CompUnit.class); // Return a compilation unit (cached or new). If new, it does not necessarily // need to be compiled. public static CompUnit makeCUnit( CodeGen code, CompUnit par, String name ) throws IOException { - int idx=name.indexOf('/'); - if( idx>=0 ) return makeCUnit(code,makeCUnit(code,par,name.substring(0,idx)),name.substring(idx+1)); - String fname=par==null ? name : par._fname+"/"+name; - CompUnit cu=code._compunits.get(fname); - if( cu==null ) { - String cname=par==null ? name : par._cname+"."+name; - code._compunits.put(fname,cu=new CompUnit(par,fname,cname,name)); - } - return cu; + return makeCUnit(code,par,name,null,false); + } + + private static CompUnit makeCUnit( CodeGen code, CompUnit par, String name, File obj ) throws IOException { + return makeCUnit(code,par,name,obj,obj!=null); } + private static CompUnit makeCUnit( CodeGen code, CompUnit par, String name, File obj, boolean external ) throws IOException { + // Slashed file name? Move leading parts into parent CUs. + int idx = name.indexOf("/"); + if( idx >= 0 ) { + String head = name.substring(0,idx); + CompUnit sub = makeCUnit(code,par,head,external ? externalObj(code,par,head) : null,external); + return makeCUnit(code,sub,name.substring(idx+1).intern(),obj,external); + } + + String fname = par==null ? name : (par._fname + "/" + name).intern(); + CompUnit cunit = code._compunits.get(fname); + if( cunit != null ) return cunit; + String cname = par==null ? name : (par._cname + "." + name).intern(); + code._compunits.put(fname, cunit = external ? new CompUnit(obj,par,fname,cname,name) : new CompUnit(par,fname,cname,name)); + return cunit; + } // Parse a top-level string, used for e.g. testing static void parseSource( CodeGen code, String src ) { @@ -69,22 +82,29 @@ public abstract class ParseAll { } private static void enqueue(CompUnit cu) { - if( cu._par!=null ) enqueue(cu._par); + if( cu._par!=null && (cu._par._src!=null || (cu._par._obj!=null && cu._par._obj.exists())) ) enqueue(cu._par); if( cu._start==null && WORK.find(cu)==-1 ) WORK.add(cu); } private static void parseAll(CodeGen code, CompUnit cunit) { WORK.clear(); // Cleanup from prior tests + NEEDS_LOAD.clear(); // Prime the pump with the first CompUnit enqueue(cunit); // Work through all unparsed compilation units and parse while( !WORK.isEmpty() ) { CompUnit cu = WORK.remove(0); - if( cu._src==null ) - throw new RuntimeException("Missing source file '"+cu._fname+".smp'"); - parseOne(code,cu); + // No source code? Means we do not need to parse, but instead need to load the symbols as-if we parsed + if( cu._src==null || cu._src.isEmpty() ) + loadDeps(code,cu); // Load recursive dependents + else + parseOne( code, cu ); // Parse } + // Load all pre-compiled CompUnits + for( CompUnit cu : NEEDS_LOAD ) + loadCompUnit(code,cu); + // Many types will have been declared cyclically either internally or // across multiple compilation units. @@ -97,7 +117,8 @@ public abstract class ParseAll { for( TypeStruct ts : tss ) Parser.TYPES.put(ts._name,ts); for( CompUnit cu : code._compunits.values() ) - cu._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cu._cname)); + if( cu._ext==null ) + cu._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cu._cname)); // Walk over all Nodes, and upgrade the internal constants to the // closed-over types. @@ -135,6 +156,9 @@ public abstract class ParseAll { // Adds sort by NIDs, which just got shuffled if( n instanceof AddNode add ) code.add(add); + // All imported bodies are loaded; link them before Iter checks types. + if( n instanceof CallNode call && !NEEDS_LOAD.isEmpty() ) + code.add(call).idealize(); return null; } ); @@ -157,6 +181,8 @@ public abstract class ParseAll { // Search the module for the fref try { CompUnit xcunit = findCUnitModule(code,cunit,fref._name); + if( xcunit == null ) + xcunit = findCUnitExternalSimple(code,fref._name); if( xcunit != null ) { // Replace the FRef with the discovered class name. fref._name = Parser.addClzPrefix(xcunit._cname); @@ -200,9 +226,88 @@ public abstract class ParseAll { if( xcunit != null ) return xcunit; } - return null; + return findCUnitExternalSimple(code,typeName); + } + + // Load the public symbols for this CompUnit, and add dependent CompUnits to the NEEDS_LOAD list. + private static void loadDeps(CodeGen code, CompUnit cunit) { + // Load IR after parsing + if( NEEDS_LOAD.find(cunit) != -1 ) + return; // Already on the to-be-loaded list? + for( CompUnit loaded : NEEDS_LOAD ) + if( loaded._obj.equals(cunit._obj) ) return; // Another class in the same object. + try { + NEEDS_LOAD.add(cunit); + // Load dependent classes + ElfReader elf = ElfReader.load(cunit._obj,cunit); + elf.loadPublicSymbols(); + // Register bundled definitions before resolving dependencies or IR. + for( String fname : elf._units ) + makeCUnit(code,null,fname,cunit._obj); + for( String fname : elf._deps ) { + // Check CompUnit for being up to date + CompUnit sub = code._compunits.get(fname); + if( sub==null ) sub=makeCUnit(code,null,fname,depObj(code,cunit,fname)); + // If not seen before or out of date, parse the new nested cunit + if( sub._clz == null && WORK.find(sub)==-1 && NEEDS_LOAD.find(sub)==-1 ) + enqueue(sub); + } + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + } + + private static File depObj(CodeGen code, CompUnit cunit, String fname) { + if( cunit._smp != null ) + return null; + ElfReader elf = code.findExternalSimple(Parser.addClzPrefix(fname.replace('/','.'))); + if( elf == null ) + throw new RuntimeException("Cannot find external Simple dependency '"+fname+"'"); + return elf._file; + } + + private static File externalObj(CodeGen code, CompUnit par, String name) { + String cname = par==null ? name : par._cname + "." + name; + ElfReader elf = code.findExternalSimple(Parser.addClzPrefix(cname)); + return elf == null ? null : elf._file; } + private static void loadCompUnit(CodeGen code, CompUnit cunit) { + // Expecting a previously compiled object file + assert cunit._obj != null; + // Extract published symbols and put them in the internal tables; + // cross-references will pick them up there. + ElfReader elf = ElfReader.load(cunit._obj,cunit); + elf.loadSimple(code); + cunit._clz = (TypeStruct)Parser.TYPES.get(Parser.addClzPrefix(cunit._cname)); + StartNode lstart = (StartNode)elf._nodes.at(0); + StopNode lstop = ( StopNode)elf._nodes.last(); + + // Add all new loaded functions to the linker table + for( Node n : lstop._inputs ) { + StopCUNode stop = (StopCUNode)n; + StartCUNode start = stop.start(); + CompUnit cu = code._compunits.get(start._fname); + cu._start = start; + cu._stop = stop ; + + for( Node ret : stop._inputs ) { + FunNode fun = ((ReturnNode)ret).fun(); + code.link(fun); + } + } + + // Hook the new code into the existing code graph + for( Node lstopcu : lstop._inputs ) + code._stop.addDef(lstopcu); + lstart.subsume(code._start); + + // Add the new top-level loaded class + Parser.TYPES.put(cunit._clz._name,cunit._clz); + Field inst = cunit._clz.field(cunit._name); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem ) + Parser.TYPES.put(cunit._cname,mem._t); + } // Symbol not found in source code (or we would not be here). // Search the module for the fref @@ -219,7 +324,7 @@ public abstract class ParseAll { CompUnit local = findCUnitModule(code,cu,symbol); if( local != null ) return local; - return null; + return findCUnitExternalSimple(code,symbol); } catch( IOException ioe ) { throw new RuntimeException(ioe); } @@ -235,12 +340,8 @@ public abstract class ParseAll { // However if A/B contains "Y", the search would be for A.B.Y then A.Y both of // which do not exist. private static CompUnit findCUnitModule( CodeGen code, CompUnit cunit, String symbol ) throws IOException { - if( cunit == null ) { - if( !symbol.equals("sys") || !CompUnit.source("sys").exists() ) return null; - CompUnit sys=makeCUnit(code,null,"sys"); - enqueue(sys); - return sys; - } + if( cunit == null ) // Ran off top of module scope? + return null; // Failed search // Check self if( cunit._name.equals(symbol) ) @@ -256,10 +357,11 @@ public abstract class ParseAll { String pre = symbol.substring(0,dotIdx); String rest = symbol.substring(dotIdx+1 ); String fname = cunit._fname + "/" + pre; - File f = CompUnit.source(fname); + File f = new File( code._modDir + "/" + fname + ".smp" ); if( f.exists() ) { CompUnit sub = makeCUnit(code,cunit,pre); - // enqueue also parses parents: their initialization must precede a child. + // Note that "sub" itself is not put on the to-be-parsed-list. We're + // referring to a child class and do not need to parse the middles. CompUnit dcunit = findCUnitModule(code,sub,rest); if( dcunit != null ) return dcunit; // Nested dot search found cunit @@ -268,7 +370,7 @@ public abstract class ParseAll { // Look in mod / fname / name / symbol.smp String fname = cunit._fname + "/" + symbol; - File f = CompUnit.source(fname); + File f = new File( code._modDir + "/" + fname + ".smp" ); if( f.exists() ) { CompUnit sub = makeCUnit(code,cunit,symbol); // If not seen before or out of date, parse the new nested cunit @@ -281,5 +383,34 @@ public abstract class ParseAll { return findCUnitModule( code, cunit._par, symbol ); } + // Search external Simple objects only. C linkage uses explicit "C" + // declarations, which produce ExternNodes and are resolved by the linker. + public static CompUnit findCUnitExternalSimple( CodeGen code, String symbol ) { + String clzName = symbol.startsWith(Parser.CLZ) ? symbol : Parser.addClzPrefix(symbol); + String cname = clzName.substring(Parser.CLZ.length()); + String fname = cname.replace('.','/'); + CompUnit cunit = code._compunits.get(fname); + if( cunit != null ) + return cunit; + + ElfReader elf = code.findExternalSimple(clzName); + if( elf == null ) + return null; + + try { + cunit = makeCUnit(code,null,fname,elf._file); + } catch( IOException ioe ) { + throw new RuntimeException(ioe); + } + ElfReader typedElf = ElfReader.load(cunit._obj,cunit); + if( typedElf != null ) typedElf.loadPublicTypes(code); + TypeStruct clz = (TypeStruct)Parser.TYPES.get(clzName); + if( clz == null ) + Parser.TYPES.put(clzName,clz = TypeStruct.make(clzName,true)); + cunit._clz = clz; + if( WORK.find(cunit) == -1 && NEEDS_LOAD.find(cunit) == -1 ) + enqueue(cunit); + return cunit; + } } diff --git a/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java new file mode 100644 index 00000000..5a74ded2 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -0,0 +1,687 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.*; +import java.util.*; + +abstract public class Serialize { + + // Encoding/emulation need only machine code. File export also needs ideal + // IR for a later compiler to import; an explicit Serialize request stops here. + static void forTarget(CodeGen code, CodeGen.Phase target, boolean inMemory) { + if( target==CodeGen.Phase.Serialize || (target.ordinal()>=CodeGen.Phase.Export.ordinal() && !inMemory) ) + code.serialize(); + } + + static void serialize( CodeGen code ) { + + // Get all Nodes in a sane order + Ary<Node> nodes = nodeOrder(code); + + // Array of dependent file names + HashSet<String> xdeps = new HashSet<>(); + for( CompUnit cu : code._compunits.values() ) { + if( cu._deps != null ) + for( CompUnit cudep : cu._deps ) + xdeps.add(cudep._fname); + } + String[] deps = xdeps.toArray(new String[xdeps.size()]); + Arrays.sort(deps); + Ary<String> owned = new Ary<>(String.class); + for( CompUnit cu : code._compunits.values() ) + if( cu._src!=null ) owned.add(cu._fname); + String[] units = owned.asAry(); + Arrays.sort(units); + + // Top-level clazz being reported + String topName = code._srcName == null ? "Test" : code._srcName; + CompUnit top = code._compunits.get(topName); + TypeStruct clz = top._clz; + + // Preserve which same-named structs are the source-level declarations. + // Optimized graph types can carry sharper field states (e.g. len==0), + // and cannot be used to reconstruct this mapping during loading. + TreeMap<String,TypeStruct> named = new TreeMap<>(); + for( Type type : Parser.TYPES.values() ) + if( type instanceof TypeStruct ts ) + named.put(ts._name,ts); + TypeStruct[] pubTypes = named.values().toArray(new TypeStruct[0]); + + // Compress into bytes + BAOS baos = write(nodes, clz, pubTypes, deps, units, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // --- Expensive bijection assert + if( false ) { + // Inflate into POJOs; renumbers everything + ElfReader elf = new ElfReader(new BAOS(baos.toByteArray())); + readAll(code,elf, code._aliases, code._fidxs, code._rpcs); + BAOS baos2 = write(elf._nodes,elf._clz,elf._pubTypes,elf._deps,elf._units, code._aliases, code._fidxs, code._rpcs, code._externFunc); + + // Bi-jection + for( int i=0; i<baos.size(); i++ ) + assert baos.buf()[i]==baos2.buf()[i] : "bijection mismatch at "+i+": "+(baos.buf()[i]&0xFF)+" != "+(baos2.buf()[i]&0xFF); + assert baos.size()==baos2.size() : "bijection size mismatch: "+baos.size()+" != "+baos2.size(); + } + // --- Expensive bijection assert + + // Record serialized IR for later ELF writing + code._serial = baos; + } + + // -------------------------------------------------- + static BAOS write(Ary<Node> nodes, TypeStruct clz, TypeStruct[] pubTypes, String[] depobjs, String[] units, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs, HashMap<Integer,String> externFunc) { + // Initialize the mapping from bits/tags to types + Type.TAGOFFS(); + + IdentityHashMap<Node,Integer> anodes = new IdentityHashMap<>(); + for( Node n : nodes ) anodes.put(n,anodes.size()+1); // 0 is null. + // The saved wrappers summarize this object's units only. Keep the + // live whole-program graph intact for subsequent lowering. + TypeTuple stopType = TypeTuple.STOP_HIGH; + for( Node n : nodes.last()._inputs ) + if( anodes.containsKey(n) ) stopType = (TypeTuple)stopType.meet(n._type); + Type startType = TypeTuple.make(Type.CONTROL,stopType.mem(),((StartNode)nodes.at(0)).arg()); + + BAOS baos = new BAOS(); + // A - Print the C0DE header. The format is not versioned yet. + baos.write('C').write('0').write('D').write('E'); + + // Count unique Types + var types = new HashMap<Type,Integer>(); + // Count published types *first*, so can align with published strings + types.put(Type.TOP,0); + types.put( clz, types.size() ); + // Have to visit the innards specially, since they did not get the + // normal recursive visit when first touching a type, because the + // published types are packed early to align with their string names so + // lookup in ElfReader can be fast. + for( int i=0; i<clz.nkids(); i++ ) + clz.at(i).gather(types); + // Gather types from all sources + for( Node n : nodes ) { + n._type.gather(types); + if( n instanceof CallEndNode cend ) cend._rpc.gather(types); + if( n instanceof FunNode fun ) fun.sig().gather(types); + if( n instanceof ParmNode parm ) parm._declaredType.gather(types); + if( n instanceof TypeNode con ) con._con .gather(types); + } + stopType.gather(types); + startType.gather(types); + // A defined class remains importable even when its initializer body dies. + // Nested structs also need their class declaration: <new> and <ctor> + // can be absent from graph types even while their function bodies live. + // Keep the nearest file owner, so an imported child is not re-exported + // merely because its parent was compiled here. + for( TypeStruct ts : pubTypes ) + if( ownedClass(ts,units) ) + ts.gather(types); + + // Only record canonical declarations already reachable from this + // object's graph. Pulling unrelated parser types into this closure + // can include open or partially built types from other units. + Ary<TypeStruct> writtenPubs = new Ary<>(TypeStruct.class); + for( TypeStruct ts : pubTypes ) + if( types.containsKey(ts) ) + writtenPubs.add(ts); + // Radix sort by Type ID# + Type[] atypes = new Type[types.size()]; + for( Type t : types.keySet() ) + atypes[types.get(t)] = t; + + // Count all unique Strings + var strs = new HashMap<String,Integer>(); + strs.put("",0); // Null string is always 0 + // Find and count *published* Strings first + gather(strs,clz._name); + // Find and count dependent object file string names + if( depobjs != null ) + for( String fname : depobjs ) + gather(strs,fname); + for( String fname : units ) gather(strs,fname); + // Count strings from all types + for( Type t : atypes ) { + if( t instanceof Field fld ) gather(strs,fld._fname); + if( t instanceof TypeStruct ts ) gather(strs,ts . _name); + } + // Count strings used by local->global bit mappings. + aliases.gather(strs); + fidxs .gather(strs); + rpcs .gather(strs); + for( String extern : externFunc.values() ) + gather(strs,extern); + // Count strings from nodes + for( Node n : nodes ) + n.gather(strs); + // Radix sort by string ID# + String[] astrs = new String[strs.size()]; + for( String s : strs.keySet() ) + astrs[strs.get(s)] = s; + + // Check that published strings and types align + assert astrs[1] == ((TypeStruct)atypes[1])._name; + if( depobjs != null ) + for( int i=0; i<depobjs.length; i++ ) + assert astrs[1+i+1] == depobjs[i]; + + + // B - Write unique strings + baos.packed4(depobjs==null ? 0 : depobjs.length); + baos.packed4(strs.size()); + // Write in ID# order; the first depobjs.length of these are dependent strings + for( String s : astrs ) + baos.packedS(s); + + // Defined units are loader metadata, not initialization dependencies. + baos.packed4(units.length); + for( String fname : units ) baos.packed4(strs.get(fname)); + + // B.2 - Write the local->global mappings + aliases.packed(baos,strs); + fidxs .packed(baos,strs); + rpcs .packed(baos,strs); + ArrayList<Integer> externFidxs = new ArrayList<>(externFunc.keySet()); + Collections.sort(externFidxs); + baos.packed2(externFidxs.size()); + for( int fidx : externFidxs ) { + baos.packed2(fidx); + baos.packed2(strs.get(externFunc.get(fidx))); + } + + // C - Write unique Types + baos.packed4(atypes.length); + baos.packed2(writtenPubs._len); + for( TypeStruct ts : writtenPubs ) + baos.packed4(types.get(ts)); + // Write Types in ID# order, no children + for( Type t : atypes ) + t.packed(baos,strs); + // Write Types in ID# order, only child IDs + for( Type t : atypes ) { + int nkids = t.nkids(); + for( int i=0; i<nkids; i++ ) + baos.packed4(types.get(t.at(i))); + } + + + // D - Write the nodes. Since this is expected to be the bulk of the + // data, we might want to explore various options. + + // How many nodes? + baos.packed4(nodes._len); + + // First cut: 1 byte opcode, optional per-node info, includes variable nIns + for( Node n : nodes ) { + baos.packed1(n.serialTag().ordinal()); + baos.packed2(types.get(n==nodes.at(0) ? startType : n==nodes.last() ? stopType : n._type)); + n.packed(baos,strs,types,anodes); + } + // Write out the input indices packed. + for( Node n : nodes ) { + for( int j=0; j<n.nIns(); j++ ) { + if( !writeInput(n,j,anodes) ) continue; + Node def = n.in(j); + Integer idx = def==null ? Integer.valueOf(0) : anodes.get(def); + // Imported function constants retain their symbol, not a body. + if( idx==null && n instanceof FunPtrNode && j==1 ) idx=0; + assert idx != null : "Missing serialized input for "+n+" input "+j+" def "+def; + baos.packed2(idx); + } + if( n instanceof FunNode fun ) + baos.packed2(anodes.get(fun.ret())); + } + + return baos; + } + + // Omit cross-object call-graph links without unlinking the live IR. + // A parameter follows exactly the same retained callers as its function. + private static boolean writeInput(Node n, int i, IdentityHashMap<Node,Integer> nodes) { + if( n instanceof ParmNode parm ) n=parm.fun(); + if( (n instanceof FunNode || n instanceof CallEndNode) && i>0 ) + return nodes.containsKey(n.in(i)); + if( n instanceof StopNode ) return nodes.containsKey(n.in(i)); + return true; + } + + public static int nIns(Node n, IdentityHashMap<Node,Integer> nodes) { + int len=0; + for( int i=0; i<n.nIns(); i++ ) if( writeInput(n,i,nodes) ) len++; + return len; + } + public static <T> void gather( HashMap<T,Integer> strs, T s) { + if( s!=null && !strs.containsKey(s) ) + strs.put(s,strs.size()); + } + public static void gather( AryInt is, int s) { + if( is.atX(s)==0 ) { + int cnt=0; + for( int i=1; i<is._len; i++ ) + if( is._es[i] != 0 ) + cnt++; + is.setX(s,cnt+1); + } + } + + // Returned array of *public* strings only. + private static boolean ownedClass(TypeStruct ts, String[] units) { + if( !Parser.startsClzPrefix(ts._name) ) return false; + String name=ts._name.substring(Parser.CLZ.length()).replace('.','/'); + while( true ) { + if( CodeGen.CODE._compunits.containsKey(name) ) + return Arrays.binarySearch(units,name)>=0; + int slash=name.lastIndexOf('/'); + if( slash<0 ) return false; + name=name.substring(0,slash); + } + } + + static void read_public_strs(ElfReader elf) { + BAOS bais = elf._bais; + Type.TAGOFFS(); + + // A - Read a header + if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' ) + throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file"); + + // B - Packed read of #strings, then strings + int ndependents = bais.packed4(); // Number of dependent object files + int nstrs = bais.packed4(); // Total number of strings + String[] strs = new String[nstrs]; + for( int i=0; i<nstrs; i++ ) + strs[i] = bais.packedS(); + elf._strs = strs; + + // Collect dependent file names + elf._deps = new String[ndependents]; + for( int i=0; i<ndependents; i++ ) + elf._deps[i] = strs[1+i+1]; + elf._units = new String[bais.packed4()]; + for( int i=0; i<elf._units.length; i++ ) + elf._units[i] = strs[bais.packed4()]; + } + + // -------------------------------------------------- + record TypeRead(Type[] types, String[] strs, GlobalBits fileAliases, GlobalBits fileFidxs, GlobalBits fileRpcs) {} + + static TypeRead readTypes( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + BAOS bais = elf._bais; + // Initialize the mapping from bits/tags to types + Type.TAGOFFS(); + + // If not read the strings already, read them now + String[] strs = elf._strs; + if( strs == null ) { + // A - Read a header + if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' ) + throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" ); + + // B - Packed read of #strings, then strings + int ndependents = bais.packed4(); // Number of dependent object files + int nstrs = bais.packed4(); // Total number of strings + elf._strs = strs = new String[nstrs]; + for( int i = 0; i < nstrs; i++ ) + strs[i] = bais.packedS(); + + // Collect dependent file names + elf._deps = new String[ndependents]; + for( int i = 0; i < ndependents; i++ ) + elf._deps[i] = strs[1 + i + 1]; + elf._units = new String[bais.packed4()]; + for( int i=0; i<elf._units.length; i++ ) + elf._units[i] = strs[bais.packed4()]; + } + + // B.2 - Read the local->global mappings. Further down we will map + // Elf file-local -> global, then global -> CodeGen.CODE local + GlobalBits fileAliases = GlobalBits.packed(bais,strs); + GlobalBits fileFidxs = GlobalBits.packed(bais,strs); + GlobalBits fileRpcs = GlobalBits.packed(bais,strs); + int nexterns = bais.packed2(); + for( int i=0; i<nexterns; i++ ) { + int fileFidx = bais.packed2(); + String extern = strs[bais.packed2()]; + int fidx = fileFidx < GlobalBits.RESERVED ? fileFidx : fidxs.map(fileFidxs,fileFidx); + String old = code.externFunc(fidx); + if( old == null ) + code.externFunc(fidx,extern); + else + assert old.equals(extern); + } + + + // C - Packed read of #types, then types + int ntypes = bais.packed4(); + int npubTypes = bais.packed2(); + int[] pubTypeIds = new int[npubTypes]; + for( int i=0; i<npubTypes; i++ ) + pubTypeIds[i] = bais.packed4(); + Type[] types = Type.packed(bais,strs,ntypes, Parser.TYPES, + fileAliases,aliases, + fileFidxs ,fidxs, + fileRpcs ,rpcs); + + // aliases.set(0,0); + // Check and collect first published symbols map to TypeStructs + elf._clz = (TypeStruct)types[1/*skip zero*/]; + assert elf._clz._name==strs[1/*skip null ptr*/]; + for( Type type : types ) + if( type instanceof TypeStruct ts ) + Parser.TYPES.put(ts._name,ts); + for( Type type : types ) { + if( !(type instanceof TypeStruct ts) || !Parser.startsClzPrefix(ts._name) ) + continue; + String cname = ts._name.substring(Parser.CLZ.length()); + int dot = cname.lastIndexOf('.'); + String name = dot == -1 ? cname : cname.substring(dot+1); + Field inst = ts.field(name.intern()); + if( inst != null && inst._t instanceof TypeFunPtr tfp && tfp._ret instanceof TypeMem mem && mem._t instanceof TypeStruct its ) + Parser.TYPES.put(cname,its); + } + elf._pubTypes = new TypeStruct[npubTypes]; + for( int i=0; i<npubTypes; i++ ) { + TypeStruct ts = elf._pubTypes[i] = (TypeStruct)types[pubTypeIds[i]]; + Parser.TYPES.put(ts._name,ts); + } + return new TypeRead(types,strs,fileAliases,fileFidxs,fileRpcs); + } + + static void readAll( CodeGen code, ElfReader elf, GlobalBits aliases, GlobalBits fidxs, GlobalBits rpcs ) { + BAOS bais = elf._bais; + TypeRead tread = readTypes(code, elf, aliases, fidxs, rpcs); + Type[] types = tread.types(); + String[] strs = tread.strs(); + GlobalBits fileAliases = tread.fileAliases(); + + // D - Read the nodes + + // Number of nodes + int num = bais.packed4(); + // Packed array of nodes + Ary<Node> nodes = new Ary<>(Node.class); + CompUnit cu = null; + for( int i=0; i<num; i++ ) { + Node.Tag tag = Node.Tag.VALS[bais.packed1()]; + Type t = types[bais.packed2()]; + Node n = tag.make(bais,strs,types,fileAliases,aliases); + n._type = t; + nodes.push(n); + // A little extra for FunNodes + if( n instanceof StartCUNode startcu ) { + cu = code._compunits.get(startcu._fname==null ? (code._srcName==null ? "Test" : code._srcName) : startcu._fname); + assert cu != null; + } + if( n instanceof StopCUNode stopcu ) { + cu = null; + } + if( n instanceof FunNode fun ) { + assert cu != null; + fun._compunit = cu; + } + if( n instanceof ExternNode ext && ext._con instanceof TypeFunPtr tfp && tfp.isConstant() ) { + String old = code.externFunc(tfp.fidx()); + if( old == null ) + code.externFunc(tfp.fidx(), ext._extern); + else + assert old.equals(ext._extern); + } + } + + // Node edges + for( Node n : nodes ) { + int len = n.nIns(); + for( int i=0; i<len; i++ ) { + int idx = bais.packed2(); + Node def = idx==0 ? null : nodes.at(idx-1); + // MemMerge precise aliases are encoded by their input slot. + // Remap populated file-local slots into this compilation's + // local alias numbering; null holes carry no identity. + int local = i; + if( n instanceof MemMergeNode && i >= GlobalBits.RESERVED ) { + if( def == null ) continue; + local = aliases.map(fileAliases,i); + } + n.setDefX(local,def); + // Call's output[0] is always the CallEnd + if( n instanceof CallEndNode cend && i==0 ) { + var outs = cend.call()._outputs; + outs.swap(0,outs._len-1); + } + } + // A little extra for FunNodes + if( n instanceof FunNode fun ) { + // Return is hooked like an edge + ReturnNode ret = (ReturnNode)nodes.at(bais.packed2()-1); + fun.setRet(ret); + ret._fun = fun; + } + } + // Add edge from Start to Stop + StartNode start = (StartNode)nodes.at(0); + StopNode stop = (StopNode)nodes.last(); + start.setDef(1,stop); + + assert check(code,nodes); + elf._nodes = nodes; + } + + // Check loaded types and nodes are consistent + private static boolean check( CodeGen code, Ary<Node> nodes ) { + // Loaded nodes are complete, unlike nodes still being built by the + // parser. Recompute them with post-parse semantics. The compilation- + // unit Stop is the exception: its escape type depends on the complete + // program's public interface, which ParseAll freezes only after every + // compilation unit has been loaded. + boolean good = true; + CodeGen.Phase phase = code._phase; + code._phase = CodeGen.Phase.Opto; + try { + for( Node n : nodes ) { + if( n instanceof StopCUNode && !code.publicInterfaceFrozen() ) + continue; + // Cross-object calls are relinked only after every body has + // loaded. Their saved return types cannot be recomputed yet. + if( n instanceof CallEndNode end && end.call().fptr()._type instanceof TypeFunPtr fp && + end.nIns()<=fp.nfcns() ) continue; + Type nval = n.compute(); + if( nval != n._type ) { + System.err.println("Node "+n+" read in as "+n._type+" but computes as "+nval); + good = false; + } + } + } finally { + code._phase = phase; + } + return good; + } + + // -------------------------------------------------- + public static Ary<Node> nodeOrder( CodeGen code, CompUnit cu ) { + BitSet visit = code.visit(); + Ary<Node> nodes = new Ary<>(Node.class); + visit.set(code._stop._nid); + // Walk all listed functions, in this single compilation unit + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._compunit == cu ) + _funWalk(fun,nodes,visit); + + // Just constants used by the listed functions + Ary<Node> cons = new Ary<>(Node.class); + cons.add(code._start); + for( Node n : code._start._outputs ) { + if( n instanceof ConstantNode con && !visit.get(con._nid) ) { + for( Node use : con.outs() ) { + // PtrToInt is another zero-code value rooted at a global + // constant. Its array-body Add is the value used by the + // function, so include that extra link in the ownership + // test as well. + if( use instanceof PtrToIntNode ptr ) + for( Node add : ptr.outs() ) { + for( Node addUse : add.outs() ) + conUsed(add,addUse,visit,cons); + conUsed(ptr,add,visit,cons); + } + // Constant used by somebody, so flag for output + conUsed(con,use,visit,cons); + } + } + } + // StartCU and memory projection + cons.add(cu._start); + for( Node n : cu._start._outputs ) + if( n instanceof ProjNode ) cons.add(n); + // All the innards of functions + cons.addAll(nodes); + // StopCU, Stop + cons.add(cu._stop); + cons.add(code._stop); + visit.clear(); + return cons; + } + + private static void conUsed( Node con, Node use, BitSet visit, Ary<Node> cons ) { + if( use == null || !visit.get(use._nid) || visit.get(con._nid) ) return; + cons.add(con); + visit.set(con._nid); + } + + // -------------------------------------------------- + public static Ary<Node> nodeOrder( CodeGen code ) { + Ary<Node> nodes = new Ary<>(Node.class); + BitSet visit = code.visit(); + nodes.add(code._start); + + // All the global constants + for( Node n : code._start._outputs ) { + if( n.isConst() ) { + visit.set( n._nid ); + nodes.add( n ); + // Special for Cast:BOT + for( Node cast : n._outputs ) + if( cast != null && cast.nIns() == 2 && cast.in( 0 ) == null ) { + visit.set( cast._nid ); + nodes.add( cast ); + // Array pointer conversion adds the body offset after + // the zero-code PtrToInt. Both nodes are global-value + // descendants of the constant and otherwise have no + // function-local root from which to walk them. + if( cast instanceof PtrToIntNode ) + for( Node add : cast.outs() ) + if( add instanceof AddNode && !visit.get(add._nid) ) { + visit.set(add._nid); + nodes.add(add); + } + } + } + } + + // All the CompUnits + for( CompUnit cu : code._compunits.values() ) { + // Whole CompUnits have no users, went dead + if( cu._src!=null && cu._start != null && !cu._start.isDead() ) { + nodes.add(cu._start); + // A memory-free, nonreturning unit can lose its memory projection. + ProjNode mem=cu._start.proj(1); + if( mem!=null ) nodes.add(mem); + // All the functions, including internal ones, in comp-unit order + for( FunNode fun : code._linker ) + if( fun!=null && !fun.isDead() && fun._compunit == cu ) + _funWalk(fun,nodes,visit); + nodes.add(cu._stop); + } + } + + nodes.add(code._stop); + visit.clear(); + return nodes; + } + + // Walk and print whole functions at a time, in CG order + private static void _funWalk( FunNode fun, Ary<Node> rpo, BitSet visit ) { + int start = rpo._len; + _funRPO(fun,rpo,visit); + // A nonreturning function still owns a Return, even before LoopTree + // inserts synthetic exits. No loop-depth ordering is needed on disk. + _funRPO(fun.ret(),rpo,visit); + int len = rpo._len - start; + for( int i=0; i< len>>1; i++ ) + rpo.swap(start+i,start+len-1-i); + } + + // Walk and gather RPO nodes. + private static void _funRPO(Node n, Ary<Node> rpo, BitSet visit ) { + if( visit.get(n._nid) ) return; // Been there, done that + visit.set(n._nid); // Stop recursion + // Walk outputs ordered + if( n instanceof CFGNode ncfg ) { + if( n instanceof IfNode iff ) { + CProjNode c0 = iff.cproj(0); + CProjNode c1 = iff.cproj(1); + _funRPO(c0,rpo,visit); + _funRPO(c1,rpo,visit); + } else if( n instanceof StopNode ) { + // nothing + } else { + // CFG to CFG before CFG to data + for( Node use : n._outputs ) + if( use instanceof CFGNode usecfg && !ncfg.skip(usecfg) ) // Do not walk from Call to Fun + _funRPO(use,rpo,visit); + } + // Walk CFG to data eventually + for( Node use : n._outputs ) + if( !(use instanceof CFGNode) ) + _funRPO(use,rpo,visit); + } else { + // Do not walk from a non-CFG to a CFG; CFGs walk to CFGs to + // preserve CFG order. Do not walk *into* Phis; wait for the + // Region to walk the Phis (otherwise you visit some of the + // Phis ahead of others forcing the Phis to be spread around). + for( Node use : n._outputs ) { + if( use!=null && !(use instanceof CFGNode) && !(use instanceof PhiNode) ) + _funRPO(use,rpo,visit); + } + } + + // If parent is a Multi, do not add (yet). + // If self is a Multi, add self and children. + if( multiChild(n) || n instanceof CallEndNode ) { + // nothing; delay until Multi-head or CallNode + } else if( n instanceof MultiNode ) { + // Now lump all multi/projections together + printMulti(n,rpo); + } else if( n instanceof CallNode call ) { + printMulti(call.cend(),rpo); + rpo.add(call); + } else if( n instanceof RegionNode ) { + // Now lump all Phis together + int old = rpo._len; + for( Node use : n._outputs ) + if( use instanceof PhiNode ) + rpo.add(use); + // Sort by label? Want Phis before control outputs + Arrays.sort( rpo._es, old, rpo._len, (x,y) -> y.label().compareTo(x.label()) ); + rpo.add(n); + } else if( n instanceof StopNode ) { + // nothing + } else { + rpo.add(n); // Post-order add + } + } + + private static boolean multiChild(Node n) { + return n instanceof Proj || n instanceof PhiNode; + } + + private static void printMulti(Node n, Ary<Node> rpo) { + // Now lump all multi/projections together + for( Node use : n._outputs ) + rpo.add(use); + // Sort by projection order + if( !(n instanceof StartNode) ) + Arrays.sort( rpo._es,rpo._len-n.nOuts(),rpo._len, + (x,y) -> x instanceof ProjNode px && y instanceof ProjNode py ? (py.idx() - px.idx()) : (y._nid - x._nid) ); + rpo.add(n); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/codegen/Unlink.java b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java new file mode 100644 index 00000000..fb1c4a6f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/codegen/Unlink.java @@ -0,0 +1,112 @@ +package com.seaofnodes.simple.codegen; + +import com.seaofnodes.simple.node.*; + +// Discard call-graph edges after LoopTree. Machine selection keeps only this +// object's bodies; ideal evaluation keeps imports so their calls can execute. +abstract class Unlink { + private static void unlinkImports(CodeGen code) { + // Imported function constants keep their symbolic identity, not an + // embedded copy of the other object's Return and body. + for( Node n : code._start._outputs.asAry() ) + if( n instanceof FunPtrNode ptr && ptr.ret()!=null && !code.owns(ptr.fun()) ) { + ptr.liftType(ptr._type); + ptr.setDef(1,null); + } + for( FunNode fun : code._linker ) { + if( fun==null || fun.isDead() || code.owns(fun) ) + continue; + for( int i=1; i<fun.nIns(); i++ ) + if( fun.in(i) instanceof CallNode call ) + call.unlink(fun,i--); + } + for( int i=0; i<code._stop.nIns(); i++ ) { + StopCUNode stop=(StopCUNode)code._stop.in(i); + CompUnit cu=code._compunits.get(stop.start()._fname); + if( cu._src==null ) code._stop.delDef(i--); + } + // The whole-object wrappers now summarize only the emitted units. + code._stop ._type=code._stop .compute(); + code._start._type=code._start.compute(); + } + + static void run(CodeGen code, boolean removeImports) { + if( removeImports ) unlinkImports(code); + + // The remaining passes assume all calls are unlinked; i.e. we are throwing + // away the Call Graph here. Functions only reachable from internal calls + // need to be re-hooked to stop/start less they go dead. + for( FunNode fun : code._linker ) { + // Already linked to start, not going dead + if( fun==null || fun.isDead() ) + continue; + + // Imported functions are not emitted by this object. Ideal + // evaluation retains them so their calls can actually execute. + if( removeImports && !code.owns(fun) ) { + while( fun.nIns() > 1 ) { + if( fun.in(1) instanceof CallNode call ) + call.unlink(fun,1); + else + fun.removeDeadPath(1); + } + StartCUNode start = fun._compunit._start; + StopCUNode stop = fun._compunit._stop; + // Unhook the Stop->Return edge also + ReturnNode ret = fun.ret(); + int idx = stop._inputs.find(ret); + if( idx != -1 ) { + stop._inputs.del(idx); + ret.delUse(stop); + } + // + if( stop.nIns()==0 ) { + idx = code._stop._inputs.find(stop); + if( idx != -1 ) + code._stop.delDef(idx); + if( start.nIns() > 0 && start.in(0) != null ) + start.setDef(0,null); + if( start.nIns() > 1 && start.in(1) != null ) + start.setDef(1,null); + } + continue; + } + + // Insert the post-Opto code-generation hook. Unlike an Opto-time + // Start input, this no longer carries unknown-caller semantics. + ReturnNode ret = fun.ret(); + StartNode start = fun._compunit._start; + assert start!=null; + if( fun.nIns() <= 1 || fun.in(1) != start ) { + fun.insertDef(1,start); + for( Node use : fun._outputs ) + if( use instanceof ParmNode parm ) + parm.insertDef(1,ConstantNode.raw(parm._type)); + if( fun._compunit._stop._inputs.find(ret) == -1 ) + fun._compunit._stop.addDef(ret); + } + // Unlink from Call + for( int i=2; i<fun.nIns(); i++ ) + ((CallNode)fun.in(i)).unlink(fun,i--); + if( fun.rpc()==null ) { // Ensure valid RPC + // First make sure a valid RPC; single-call into multi-fun will have each + // function having a single call site, so the RPC becomes a constant and + // folds - but since multiple targets, the Call never inlines. Recreate a + // valid RPC so codegen (and Eval2) understands the calling convention. + ParmNode rpc = new ParmNode( "$rpc", 0, ret.rpc()._type, fun ); + rpc.addDef(ret.rpc()); + ret.setDef( 3, rpc.init() ); + } + } + + code._stop.walk(n -> { + if( n instanceof CallEndNode cend ) + for( int i=1; i<cend.nIns(); i++ ) + if( cend.in(i) instanceof ReturnNode ) + cend.delDef(i--); + if( n instanceof CallNode call ) + call.unlink_all(); + return null; + }); + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 8835208b..a29ba73b 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -7,7 +7,7 @@ public class AddNode extends ArithNode { @Override boolean allowFloat() { return true; } public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public AddNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - + @Override public Tag serialTag() { return Tag.Add; } @Override public String label() { return "Add"; } @Override public String op() { return "+"; } diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index a737b703..f02007bc 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class AndNode extends ArithNode { public AndNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.And; } @Override public String op() { return "&"; } @Override long doOp( long x, long y ) { return x & y; } diff --git a/src/main/java/com/seaofnodes/simple/node/ArithNode.java b/src/main/java/com/seaofnodes/simple/node/ArithNode.java index 094b927f..92ebd587 100644 --- a/src/main/java/com/seaofnodes/simple/node/ArithNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ArithNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; @@ -18,7 +19,9 @@ public abstract class ArithNode extends Node implements ModeNode { public ArithNode( Parser.Lexer loc, Node lhs, Node rhs) { super(null, lhs, rhs); _loc = loc; } public ArithNode( Parser.Lexer loc, Node lhs, Node rhs, byte mode) { this(loc,lhs,rhs); _mode=mode; } - + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes) { + baos.packed1(_mode); + } abstract String op(); @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index dd0bc996..73e786e3 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -17,7 +18,9 @@ abstract public class BoolNode extends Node implements ModeNode { public BoolNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public BoolNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs); _mode = mode; } - + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes) { + baos.packed1(_mode); + } abstract public String op(); // String opcode name @@ -116,7 +119,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } public EQ(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - + @Override public Tag serialTag() { return Tag.EQ; } public String op() { return "=="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; @@ -130,7 +133,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class NE extends BoolNode { public NE(Node lhs, Node rhs) { super(lhs,rhs); } public NE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - + @Override public Tag serialTag() { return Tag.NE; } public String op() { return "!="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1==i2 && i1.isConstant() ) return TRUE; @@ -144,7 +147,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } public LT(Node lhs, Node rhs, byte mode) { super(lhs,rhs, mode); } - + @Override public Tag serialTag() { return Tag.LT; } public String op() { return "<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max < i2._min ) return TRUE; @@ -158,7 +161,7 @@ abstract public class BoolNode extends Node implements ModeNode { public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } public LE(Node lhs, Node rhs, byte mode) { super(lhs,rhs,mode); } - + @Override public Tag serialTag() { return Tag.LE; } public String op() { return "<="; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( i1._max <= i2._min ) return TRUE; @@ -176,7 +179,7 @@ abstract public class BoolNode extends Node implements ModeNode { super(lhs,rhs,(byte)1); assert mode==1; } - + @Override public Tag serialTag() { return Tag.ULT; } public String op() { return "u<" ; } TypeInteger doOp(TypeInteger i1, TypeInteger i2) { if( Long.compareUnsigned(i1._max,i2._min) < 0 ) return TRUE; diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index df9e4fff..c6a6ff3b 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -1,8 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -44,6 +46,28 @@ public class BulkMemPhiNode extends PhiNode { public boolean isSplit(int alias) { return _aliases.get(alias); } + @Override public Tag serialTag() { return Tag.BulkMemPhi; } + + @Override + public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, + IdentityHashMap<Node,Integer> anodes) { + super.packed(baos,strs,types,anodes); + baos.packed2(_aliases.cardinality()); + for( int alias = _aliases.nextSetBit(0); alias >= 0; alias = _aliases.nextSetBit(alias+1) ) + baos.packed2(alias); + } + + static Node make(BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + BitSet bits = new BitSet(); + for( int i=bais.packed2(); i>0; i-- ) { + int alias = bais.packed2(); + if( alias >= GlobalBits.RESERVED ) alias = aliases.map(fileAliases,alias); + bits.set(alias); + } + return new BulkMemPhiNode(label,bits.isEmpty() ? EMPTY : bits,ins); + } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java index 0a0de3cf..7bc17c75 100644 --- a/src/main/java/com/seaofnodes/simple/node/CLInitNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CLInitNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.CompUnit; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.*; // Track class initializers - the code just after this point expects the named @@ -22,6 +23,12 @@ public class CLInitNode extends CFGNode implements MultiNode { _loc = loc; } + CLInitNode(BAOS bais, String[] strs) { super(null,null,null,null); _loc=Parser.Lexer.unpack(bais,strs); } + @Override public Tag serialTag() { return Tag.CLInit; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + Parser.Lexer.packed(_loc,baos,strs); + } + @Override public void gather(HashMap<String,Integer> strs) { Parser.Lexer.gather(_loc,strs); } public CLInitNode(CLInitNode init) { super(init); diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 2bd48d92..073e4658 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -3,8 +3,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -23,7 +25,14 @@ public class CProjNode extends CFGNode implements Proj { _label = label; } public CProjNode(CProjNode c) { super(c); _idx = c._idx; _label = c._label; } - + @Override public Tag serialTag() { return Tag.CProj; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(_idx); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs ) { + return new CProjNode(null, bais.packed1(), strs[bais.packed2()] ); + } @Override public String label() { return _label; } @@ -70,4 +79,7 @@ public class CProjNode extends CFGNode implements Proj { @Override public int idx() { return _idx; } + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 4422265f..fc6effdc 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -37,7 +38,21 @@ public class CallEndNode extends CFGNode implements MultiNode { super(new Node[nIns]); _rpc = rpc; } - + @Override public Tag serialTag() { return Tag.CallEnd; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(Serialize.nIns(this,anodes)); + // Linked CallEnds depend on Return types which depend on CallEnds; + // break the cycle + baos.packed2(types.get(_type)); + baos.packed2(types.get(_rpc)); + } + static Node make( BAOS bais, Type[] types ) { + int nIns = bais.packed1(); + Type type = types[bais.packed2()]; + Node cend = new CallEndNode(nIns,(TypeRPC)types[bais.packed2()]); + cend._type = type; + return cend; + } @Override public boolean blockHead() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index f791225a..bcb756fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -9,6 +9,7 @@ import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeRPC; import com.seaofnodes.simple.type.XInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -23,7 +24,16 @@ public class CallNode extends CFGNode { public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc=loc; CodeGen.CODE._calls.add(this); } public CallNode(CallNode call) { super(call); _loc = call._loc; } - + @Override public Tag serialTag() { return Tag.Call; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(nIns()); + Parser.Lexer.packed(_loc,baos,strs); + } + @Override public void gather(HashMap<String,Integer> strs) { Parser.Lexer.gather(_loc,strs); } + static Node make( BAOS bais, String[] strs ) { + int nIns = bais.packed1(); + return new CallNode(Parser.Lexer.unpack(bais,strs),new Node[nIns]); + } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { String fname = name(); @@ -44,6 +54,7 @@ public class CallNode extends CFGNode { } + Node ctrl() { return in(0); } Node mem () { return in(1); } // Args mapped 1-to-1 on inputs, so conceptually start at 2 diff --git a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java index 0b8053e2..284220ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConFldOffNode.java @@ -21,7 +21,7 @@ public class ConFldOffNode extends ConstantNode { public TypeStruct _ts; // Struct holding field public final String _fname; // Field name public ConFldOffNode( TypeStruct ts, String fname ) { super(TypeInteger.BOT); _ts = ts; _fname = fname; } - + @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @Override public String label() { return _fname == " len" ? "sizeof("+_ts._name+")" : "#"+_fname; diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index eabf2639..0569f352 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFunPtr; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -30,7 +31,11 @@ public class ConstantNode extends TypeNode { _type = type; } public ConstantNode( ConstantNode con ) { super(con); } - + @Override public Tag serialTag() { return Tag.Con; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed2(types.get(_con)); // NPE if fails lookup + } + static Node make( BAOS bais, Type[] types) { return raw(types[bais.packed2()]); } // Semantic constant construction through Lower. A unique internal // function identity carries a lifetime edge to the function's Return. diff --git a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java index 813e6fcb..62140873 100644 --- a/src/main/java/com/seaofnodes/simple/node/CtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CtrlNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; public class CtrlNode extends CFGNode { public CtrlNode() { super(CodeGen.CODE._start); } - + @Override public Tag serialTag() { throw com.seaofnodes.simple.util.Utils.TODO(); } @Override public String label() { return "Ctrl"; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Cctrl"); } @Override public boolean isConst() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 0db2b7a2..f173f0ef 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -9,7 +9,7 @@ public class DivNode extends ArithNode { @Override boolean allowFloat() { return true; } public DivNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public DivNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - + @Override public Tag serialTag() { return Tag.Div; } @Override public String op() { return _mode==1 ? "//" : "/"; } diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java index f7518184..3e95fffb 100644 --- a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -35,6 +35,13 @@ public class EscapeNode extends TypeNode { public Node pub () { return in(3); } public Field fld() { return (Field)_con; } + @Override public Tag serialTag() { return Tag.Escape; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed2(types.get(_con)); + } + static Node make( BAOS bais, Type[] types) { + return new EscapeNode((Field)types[bais.packed2()], null,null,null); + } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { diff --git a/src/main/java/com/seaofnodes/simple/node/ExternNode.java b/src/main/java/com/seaofnodes/simple/node/ExternNode.java index 2d1dc29f..978298fc 100644 --- a/src/main/java/com/seaofnodes/simple/node/ExternNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ExternNode.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.BitSet; @@ -17,11 +19,20 @@ public class ExternNode extends ConstantNode { // Its lifetime and eventual relocation are carried by the extern symbol // and CodeGen's FIDX-to-extern mapping instead. public ExternNode(Type t, String ex) { super(t,true); _extern = ex; } - + @Override public Tag serialTag() { return Tag.Extern; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed2(types.get(_con )); + baos.packed2( strs.get(_extern)); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + return new ExternNode(types[bais.packed2()], strs[bais.packed2()]); + } @Override public String label() { return "#"+_con+":"+_extern; } @Override public boolean eq(Node n) { return this==n; } - + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_extern); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java b/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java index 23ed5468..409ce5d1 100644 --- a/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ExternOffsetNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -10,7 +11,9 @@ import java.util.IdentityHashMap; // selection replaces it with this symbol's address and a zero displacement. public class ExternOffsetNode extends ExternNode { public ExternOffsetNode(String name) { super(TypeInteger.BOT,name); } - + @Override public Tag serialTag() { return Tag.ExternOffset; } @Override public Node copy() { return new ExternOffsetNode(_extern); } - + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> nodes) { + baos.packed2(strs.get(_extern)); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java index 535241a6..a9f8d692 100644 --- a/src/main/java/com/seaofnodes/simple/node/FldOffNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FldOffNode.java @@ -19,7 +19,7 @@ public class FldOffNode extends TypeNode { public final String _fname; // Field name public final Parser.Lexer _loc; // public FldOffNode( Node base, String fname, Parser.Lexer loc ) { super(TypeInteger.BOT,base); _fname = fname; _loc=loc; } - + @Override public Tag serialTag() { throw Utils.TODO("should not reach here"); } @Override public String label() { return _fname == " len" ? "sizeof()" : "#"+_fname; diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index ad79130e..edde247a 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; import java.util.Arrays; @@ -41,7 +42,24 @@ public class FunNode extends RegionNode { _compunit = fun._compunit; _extern = fun._extern; } - + @Override public Tag serialTag() { return Tag.Fun; } + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes ) { + assert !_folding; + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls + baos.packed2(types.get(_sig)); // NPE if fails lookup + baos.packed2(_name==null ? 0 : strs.get(_name)); + baos.packed2(_approxUIDs); + // _compunit set from context on loading, do not write + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + TypeFunPtr sig = (TypeFunPtr)types[bais.packed2()]; + String name = strs[bais.packed2()]; + FunNode fun = new FunNode(null,sig,name,null,ins); + fun._approxUIDs = bais.packed2(); + // _compunit set from context on loading, do not read + return fun; + } @Override public String label() { return _name == null ? "$fun"+_sig.fidx() : _name; } @@ -460,4 +478,7 @@ public class FunNode extends RegionNode { return slotRotate*8; } + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_name); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java index 3d6031b8..82053fd8 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunPtrNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -14,8 +15,13 @@ public class FunPtrNode extends TypeNode { super(tfp,start,ret); } public FunPtrNode(FunPtrNode fptr) { super(fptr); } - - + @Override public Tag serialTag() { return Tag.FunPtr; } + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes) { + baos.packed2(types.get(_con)); + } + static Node make(BAOS bais, Type[] types) { + return new FunPtrNode((TypeFunPtr)types[bais.packed2()],null,null); + } public ReturnNode ret() { return (ReturnNode)in(1); } public FunNode fun() { return ret().fun(); } diff --git a/src/main/java/com/seaofnodes/simple/node/GuardNode.java b/src/main/java/com/seaofnodes/simple/node/GuardNode.java index e985da72..0ce504d9 100644 --- a/src/main/java/com/seaofnodes/simple/node/GuardNode.java +++ b/src/main/java/com/seaofnodes/simple/node/GuardNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeScalar; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; @@ -24,6 +25,11 @@ public class GuardNode extends Node { _nonZero = guard._nonZero; } + @Override public Tag serialTag() { return Tag.Guard; } + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes) { + baos.write(_nonZero ? 1 : 0); + } + static Node make(BAOS bais) { return new GuardNode(bais.read()!=0,null,null); } @Override public String label() { return _nonZero ? "(!=0)" : "(==0)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 471a28fe..c83c81d0 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -13,7 +13,7 @@ public class IfNode extends CFGNode implements MultiNode { CodeGen.CODE.add(this); // Because idoms are complex, just add it } public IfNode(IfNode iff) { super(iff); } - + @Override public Tag serialTag() { return Tag.If; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index e1a495ad..c58bba39 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -4,7 +4,9 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; @@ -25,7 +27,11 @@ public class LoadNode extends MemOpNode { public LoadNode(Parser.Lexer loc, String name, int alias, Node ctrl, Node mem, Node ptr, Node off) { super(loc, name, alias, true, Type.BOTTOM, ctrl, mem, ptr, off); } - + LoadNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + super(bais,strs,types,fileAliases,aliases,true); + _con = Type.BOTTOM; // Serialized slot retained while MemOps share TypeNode + } + @Override public Tag serialTag() { return Tag.Load; } @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && !clobbered(dep); diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 005a6624..df686bcf 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -11,7 +12,8 @@ import java.util.IdentityHashMap; public class LoopNode extends RegionNode { public LoopNode( Parser.Lexer loc, Node xctrl, Node entry ) { super(loc,xctrl,entry,null); } public LoopNode( LoopNode loop ) { super(loop); } - + @Override public Tag serialTag() { return Tag.Loop; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { } public CFGNode entry() { return cfg(1); } public CFGNode back () { return cfg(2); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index cbf19c55..dfe8794d 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Utils; @@ -17,7 +18,9 @@ public class MemMergeNode extends Node { public MemMergeNode( Node ...nodes) { super(nodes); _type = TypeMem.BOT; } public MemMergeNode(MemMergeNode mem) { super(mem); } - + @Override public Tag serialTag() { return Tag.MemMerge; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { Node mem = new MemMergeNode(); mem.setDefX(bais.packed1()-1,null); return mem; } @Override public String label() { return "ALLMEM"; } @Override public boolean isMem() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index fa399e1d..bfbd46c3 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.lang.StringBuilder; @@ -60,6 +61,24 @@ public abstract class MemOpNode extends TypeNode { _isLoad= mop._isLoad; } + MemOpNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases, boolean isLoad ) { + this(null, + strs[bais.packed2()], + mapAlias(bais,fileAliases,aliases),isLoad, + types[bais.packed2()],null,null,null,null); + } + + private static int mapAlias( BAOS bais, GlobalBits fileAliases, GlobalBits aliases ) { + int alias = bais.packed2(); + return alias < GlobalBits.RESERVED ? alias : aliases.map(fileAliases,alias); + } + + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed2(_name==null ? 0 : strs.get(_name)); + baos.packed2(_alias); + baos.packed2(types.get(_con)); // NPE if fails lookup + assert _isLoad == this instanceof LoadNode; // No machine ops + } static String mlabel(String name) { return "[]"==name ? "ary" : ("#"==name ? "len" : name); } String mlabel() { return mlabel(_name); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java index 5ae716a7..aaaedb89 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.codegen.GlobalBits; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,6 +24,22 @@ public class MemPhiNode extends PhiNode { _alias = phi._alias; } + @Override public Tag serialTag() { return Tag.MemPhi; } + + @Override + public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, + IdentityHashMap<Node,Integer> anodes) { + super.packed(baos,strs,types,anodes); + baos.packed2(_alias); + } + + static Node make(BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + int alias = bais.packed2(); + if( alias >= GlobalBits.RESERVED ) alias = aliases.map(fileAliases,alias); + return new MemPhiNode(label,alias,ins); + } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 4d7e3ddb..e84eb611 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -4,6 +4,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -14,7 +15,10 @@ public class MinusNode extends Node implements ModeNode { public MinusNode(Node in) { super(null, in); } public MinusNode(Node in, byte mode) { super(null, in); _mode = mode; } - + @Override public void packed(BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes) { + baos.packed1(_mode); + } + @Override public Tag serialTag() { return Tag.Minus; } @Override public byte mode() { return _mode; } @Override public Node setMode(byte mode) { diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 49c6432a..bb99cad5 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -9,7 +9,7 @@ public class MulNode extends ArithNode { @Override boolean allowFloat() { return true; } public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public MulNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs, mode); } - + @Override public Tag serialTag() { return Tag.Mul; } @Override public String op() { return "*"; } diff --git a/src/main/java/com/seaofnodes/simple/node/NeverNode.java b/src/main/java/com/seaofnodes/simple/node/NeverNode.java index a7b4cf65..ba1dab8c 100644 --- a/src/main/java/com/seaofnodes/simple/node/NeverNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NeverNode.java @@ -12,7 +12,7 @@ import com.seaofnodes.simple.type.TypeTuple; public class NeverNode extends IfNode { public NeverNode(NeverNode ctrl) { super(ctrl); } public NeverNode(float ignore, Node ctrl) { super(ctrl,null); } - + @Override public Tag serialTag() { return Tag.Never; } @Override public String label() { return "Never"; } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 5cbe1b61..fe80f690 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -4,6 +4,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,7 +23,14 @@ public class NewNode extends Node implements MultiNode { // --- Serialization public NewNode(NewNode nnn) { super(nnn); _ts = nnn._ts; } - + @Override public Tag serialTag() { return Tag.New; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed2(types.get(_ts)); + } + static Node make( BAOS bais, Type[] types) { + TypeStruct ts = (TypeStruct)types[bais.packed2()]; + return new NewNode(ts,null,null); + } @Override public String label() { return "new_"+(_ts.isAry() ? "ary_"+_ts._fields[1]._t.str() : _ts.str()); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index de39ca80..8718f351 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.BaseNode; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.print.IRPrinter; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; @@ -67,8 +68,84 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { _hash = 0; } + // Disk/serialized opcode tags + public enum Tag { + Add,And,BulkMemPhi,EQ,NE,LT,LE,ULT, + CallEnd,Call,ConFldOff,Con,CLInit,CProj, + Div,Escape,Extern,ExternOffset,Fun,FunPtr,Guard, + If,Load,Loop,MemMerge,MemPhi,Minus,Mul, + New,Never,Not,Or,Parm,Phi,Proj,PtrToInt, + ReadOnly,Return,Region,RoundF32, + Sar,Shl,Shr,Start,StartCU,StopCU,Stop,Store,Sub, + ToInteger,ToFloat,XCtrl,Xor; + public static final Tag[] VALS = values(); + public Node make( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + return switch(this) { + case Add -> new AddNode(null,null,(byte)bais.packed1()); + case And -> { int mode=bais.packed1(); assert mode==1; yield new AndNode(null,null,null); } + case Div -> new DivNode(null,null,(byte)bais.packed1()); + case Guard -> GuardNode.make(bais); + case If -> new IfNode(null,null); + case Loop -> new LoopNode(null,null,null); + case Minus -> new MinusNode(null,(byte)bais.packed1()); + case Mul -> new MulNode(null,null,(byte)bais.packed1()); + case Never -> new NeverNode(1.2f, null); + case Not -> new NotNode(null); + case Or -> { int mode=bais.packed1(); assert mode==1; yield new OrNode(null,null,null); } + case ReadOnly-> new ReadOnlyNode((Node)null); + case Return ->new ReturnNode(null,null,null,null,null); + case RoundF32-> new RoundF32Node(null); + case PtrToInt-> new PtrToIntNode((Node)null); + case Sar -> { int mode=bais.packed1(); assert mode==1; yield new SarNode(null,null,null); } + case Shl -> { int mode=bais.packed1(); assert mode==1; yield new ShlNode(null,null,null); } + case Shr -> { int mode=bais.packed1(); assert mode==1; yield new ShrNode(null,null,null); } + case Start -> new StartNode(null,null,TypeInteger.BOT); + case Sub -> new SubNode(null,null,(byte)bais.packed1()); + case ToFloat-> new ToFloatNode(null); + case ToInteger-> new ToIntegerNode(null); + case XCtrl -> new XCtrlNode(); + case Xor -> { int mode=bais.packed1(); assert mode==1; yield new XorNode(null,null,null); } + + case EQ -> new BoolNode.EQ (null,null,(byte)bais.packed1()); + case NE -> new BoolNode.NE (null,null,(byte)bais.packed1()); + case LT -> new BoolNode.LT (null,null,(byte)bais.packed1()); + case LE -> new BoolNode.LE (null,null,(byte)bais.packed1()); + case ULT -> new BoolNode.ULT(null,null,(byte)bais.packed1()); + + case Call -> CallNode.make(bais,strs); + case CallEnd-> CallEndNode.make(bais ,types); + case CLInit -> new CLInitNode(bais,strs); + case CProj -> CProjNode.make(bais,strs); + case Con -> ConstantNode.make(bais ,types); + case Escape-> EscapeNode.make(bais ,types); + case Extern-> ExternNode.make(bais,strs,types); + case ExternOffset-> new ExternOffsetNode(strs[bais.packed2()]); + case FunPtr-> FunPtrNode.make(bais, types); + case Fun -> FunNode.make(bais,strs,types); + case Load -> new LoadNode(bais,strs,types,fileAliases,aliases); + case MemMerge->MemMergeNode.make(bais); + case MemPhi-> MemPhiNode.make(bais,strs,types,fileAliases,aliases); + case BulkMemPhi-> BulkMemPhiNode.make(bais,strs,types,fileAliases,aliases); + case New -> NewNode.make(bais ,types); + case Parm -> ParmNode.make(bais,strs,types); + case Phi -> PhiNode.make(bais,strs,types); + case Proj -> ProjNode.make(bais,strs); + case Store -> new StoreNode(bais,strs,types,fileAliases,aliases); + case Stop -> StopNode.make(bais); + case StartCU-> StartCUNode.make(bais,strs,types); + case StopCU -> StopCUNode.make(bais); + case Region-> RegionNode.make(bais); + + default -> throw Utils.TODO("Should not reach here"); + }; + } + }; + public Tag serialTag() { throw Utils.TODO(); } + // Serialize extra data, including input counts + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {} + // Easy reading label for debugger, e.g. "Add" or "Region" or "EQ" - public String label() { return getClass().getSimpleName().replace("Node",""); } + public String label() { return serialTag().toString(); } public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } @@ -667,6 +744,7 @@ public abstract class Node extends BaseNode<Node> implements Cloneable { return null; } + public void gather(HashMap<String,Integer> strs ) { } // If a Type upgrade happens, put on worklist boolean _upgradeType( HashMap<String,Type> TYPES ) { return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e22d16b6..2328c287 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.util.Utils; public class NotNode extends Node { public NotNode(Node in) { super(null, in); } - + @Override public Tag serialTag() { return Tag.Not; } @Override protected String format() { return "(!%1)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index 263c3e87..9d50d1a9 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class OrNode extends ArithNode { public OrNode( Parser.Lexer loc, Node lhs, Node rhs) { super(loc,lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Or; } @Override public String label() { return "Or"; } @Override public String op() { return "|"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ParmNode.java b/src/main/java/com/seaofnodes/simple/node/ParmNode.java index 316efb93..91c471c0 100644 --- a/src/main/java/com/seaofnodes/simple/node/ParmNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ParmNode.java @@ -3,6 +3,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.codegen.Serialize; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -20,7 +22,19 @@ public class ParmNode extends PhiNode { _type = declaredType; } public ParmNode(ParmNode parm) { super(parm, parm._label ); _idx = parm._idx; _declaredType = parm._declaredType; } - + @Override public Tag serialTag() { return Tag.Parm; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(Serialize.nIns(this,anodes)); // Object-local linked calls + baos.packed2(_label==null ? 0 : strs.get(_label)); + baos.packed2(types.get(_declaredType)); // NPE if fails lookup + baos.packed1(_idx); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + String label = strs[bais.packed2()]; + Type minType = types[bais.packed2()]; + return new ParmNode(label, bais.packed1(), minType, ins); + } @Override public String label() { return MemOpNode.mlabel(_label); } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 61e4b468..3cf6f854 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.util.HashMap; @@ -35,7 +36,15 @@ public class PhiNode extends Node { while( nIns() < r.nIns() ) addDef(sample); } - + @Override public Tag serialTag() { return Tag.Phi; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(nIns()); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs, Type[] types) { + Node[] ins = new Node[bais.packed1()]; + return new PhiNode(strs[bais.packed2()], ins); + } @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @@ -272,4 +281,7 @@ public class PhiNode extends Node { return Parser.error(sb.unchar(5).toString(),null); } + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index a0142379..fcc113a8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -2,9 +2,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeTuple; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -22,7 +24,14 @@ public class ProjNode extends Node implements Proj { _label = label; } public ProjNode(ProjNode p) { super(p); _idx = p._idx; _label = p._label; } - + @Override public Tag serialTag() { return Tag.Proj; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + baos.packed1(_idx); + baos.packed2(_label==null ? 0 : strs.get(_label)); + } + static Node make( BAOS bais, String[] strs ) { + return new ProjNode(null, bais.packed1(), strs[bais.packed2()] ); + } @Override public String label() { return _label; } @@ -56,4 +65,7 @@ public class ProjNode extends Node implements Proj { @Override public int idx() { return _idx; } + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_label); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java index 094734fa..d3d38060 100644 --- a/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PtrToIntNode.java @@ -18,7 +18,7 @@ public class PtrToIntNode extends Node { public PtrToIntNode(Node ptr) { super(null,ptr); } public PtrToIntNode(PtrToIntNode ptr) { super(ptr); } - + @Override public Tag serialTag() { return Tag.PtrToInt; } @Override protected String format() { return "(i64*)%1"; } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java index ab7e0ae0..0a720d5b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -10,7 +10,7 @@ import com.seaofnodes.simple.type.TypeMemPtr; public class ReadOnlyNode extends Node { public ReadOnlyNode( Node n ) { super(null,n); } public ReadOnlyNode( ReadOnlyNode n ) { super(n); } - + @Override public Tag serialTag() { return Tag.ReadOnly; } @Override protected String format() { return "(const)%1"; } @Override public Type compute() { diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 923773c4..8883ba8e 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import java.util.*; public class RegionNode extends CFGNode { @@ -14,7 +15,9 @@ public class RegionNode extends CFGNode { public RegionNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } public RegionNode(RegionNode r, Parser.Lexer loc) { super(r); _loc = loc; } public RegionNode(RegionNode r) { super(r); if( r!=null ) _loc = r._loc; } - + @Override public Tag serialTag() { return Tag.Region; } + public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { return new RegionNode(null,new Node[bais.packed1()]); } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p(label()); diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 0bb090ee..0431f7d5 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -28,7 +28,7 @@ public class ReturnNode extends CFGNode { _fun = fun; } public ReturnNode( ReturnNode ret, FunNode fun ) { super(ret); _fun = fun; } - + @Override public Tag serialTag() { return Tag.Return; } public Node ctrl() { return in(0); } public Node mem () { return in(1); } diff --git a/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java index 02d3bbaa..65f10a79 100644 --- a/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java +++ b/src/main/java/com/seaofnodes/simple/node/RoundF32Node.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeFloat; public class RoundF32Node extends Node { public RoundF32Node(Node lhs) { super(null, lhs); } - + @Override public Tag serialTag() { return Tag.RoundF32; } @Override protected String format() { return "((f32)%1)"; } diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index fa63334b..737b531f 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class SarNode extends ArithNode { public SarNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Sar; } @Override public String op() { return ">>"; } @Override long doOp( long x, long y ) { return x >> y; } diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 380fc246..f657cf51 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ShlNode extends ArithNode { public ShlNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Shl; } @Override public String op() { return "<<"; } @Override long doOp( long x, long y ) { return x << y; } diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index 17170a1f..e93ea0e8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ShrNode extends ArithNode { public ShrNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Shr; } @Override public String op() { return ">>>"; } @Override long doOp( long x, long y ) { return x >>> y; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartCUNode.java b/src/main/java/com/seaofnodes/simple/node/StartCUNode.java index 0f7a322a..cd51f603 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartCUNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartCUNode.java @@ -1,7 +1,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -11,12 +13,21 @@ public class StartCUNode extends StartNode { public final String _fname; public StartCUNode(StartNode start, StopCUNode stop, Type arg, String fname) { super(start,stop,arg); _fname = fname; } public StartCUNode(StartCUNode start) { super(start); _fname = start._fname; } - + @Override public Tag serialTag() { return Tag.StartCU; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node,Integer> anodes ) { + baos.packed2(types.get(_arg)); + baos.packed2(strs.get(_fname)); + } + static Node make( BAOS bais, String[] strs, Type[] types ) { + return new StartCUNode(null,null,types[bais.packed2()],strs[bais.packed2()]); + } @Override public CFGNode cfg0() { return (CFGNode)in(0); } // IDom is cfg0() and depth is always Start+1 which is 0+1 or 1 @Override public int idepth() { return 1; } @Override public CFGNode idom(Node dep) { return cfg0(); } - + @Override public void gather( HashMap<String,Integer> strs ) { + Serialize.gather(strs,_fname); + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 3c605e30..495be0a2 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -29,7 +29,7 @@ public class StartNode extends LoopNode implements MultiNode { public StartNode(StartNode start, StopNode stop, Type arg) { super(null,start,stop); _arg = arg; } public StartNode(StartNode start) { super(start); _arg = start==null ? null : start._arg; } - + @Override public Tag serialTag() { return Tag.Start; } public Type arg() { return _arg; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { diff --git a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java index 53c2325c..43acf631 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopCUNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopCUNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -10,7 +11,13 @@ import java.util.IdentityHashMap; public class StopCUNode extends StopNode { public StopCUNode() { super(); } public StopCUNode(StopNode stop) { super(stop); } - + @Override public Tag serialTag() { return Tag.StopCU; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(nIns()); } + static Node make( BAOS bais ) { + StopCUNode stop = new StopCUNode(); + stop.setDefX(bais.packed1()-1,null); + return stop; + } public StartCUNode start() { for( Node use : _outputs ) diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 7238f1f9..a7e52563 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -3,7 +3,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.Serialize; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; import java.util.IdentityHashMap; @@ -16,7 +18,13 @@ public class StopNode extends CFGNode { _type = compute(); } public StopNode(StopNode stop) { super(stop); } - + @Override public Tag serialTag() { return Tag.Stop; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { baos.packed1(Serialize.nIns(this,anodes)); } + static Node make( BAOS bais ) { + StopNode stop = new StopNode(); + stop.setDefX(bais.packed1()-1,null); + return stop; + } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index bdd07c8d..5fa0b99f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -4,7 +4,9 @@ import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.*; import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.HashMap; import java.util.IdentityHashMap; @@ -35,7 +37,18 @@ public class StoreNode extends MemOpNode { _init = init; _size = size; } - + StoreNode( BAOS bais, String[] strs, Type[] types, GlobalBits fileAliases, GlobalBits aliases ) { + super(bais,strs,types,fileAliases,aliases,false); + addDef(null); + _init = bais.read() != 0; + _size = (byte)bais.read(); + } + @Override public Tag serialTag() { return Tag.Store; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) { + super.packed(baos,strs,types, anodes ); + baos.write(_init ? 1 : 0); + baos.write(_size); + } @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && _init==((StoreNode)other)._init; @@ -114,7 +127,7 @@ public class StoreNode extends MemOpNode { // Freeze the semantic Store variant as soon as the pointer exposes a // canonical field declaration. Waiting until after structural memory // peeps can lose the declaration to a flow-sensitive constant field - // state. + // state. Imported Stores already carry a serialized non-zero width. if( _size==0 && (_size= storageType()) != 0 ) { unlock(); // Width participates in the cached hash. return init(); diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index adad2ed5..8eb1f4cc 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -9,7 +9,7 @@ public class SubNode extends ArithNode { @Override boolean allowFloat() { return true; } public SubNode(Node lhs, Node rhs) { super(null, lhs, rhs); } public SubNode(Node lhs, Node rhs, byte mode) { super(null, lhs, rhs,mode); } - + @Override public Tag serialTag() { return Tag.Sub; } @Override public String op() { return "-"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java index 1acf55b6..151a326e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToFloatNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class ToFloatNode extends Node { public ToFloatNode(Node lhs) { super(null, lhs); } - + @Override public Tag serialTag() { return Tag.ToFloat; } @Override protected String format() { return "(flt)%1"; } diff --git a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java index 9136aacc..33806300 100644 --- a/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ToIntegerNode.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.type.TypeInteger; // Truncate toward zero, saturating overflow; NaN converts to zero. public class ToIntegerNode extends Node { public ToIntegerNode(Node lhs) { super(null,lhs); } - + @Override public Tag serialTag() { return Tag.ToInteger; } @Override public String label() { return "ToInteger"; } @Override protected String format() { return "(int)%1"; } diff --git a/src/main/java/com/seaofnodes/simple/node/TypeNode.java b/src/main/java/com/seaofnodes/simple/node/TypeNode.java index 970472da..3ab2d6f9 100644 --- a/src/main/java/com/seaofnodes/simple/node/TypeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/TypeNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.BitSet; import java.util.HashMap; diff --git a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java index 3792e224..32e1deb9 100644 --- a/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XCtrlNode.java @@ -8,7 +8,7 @@ import com.seaofnodes.simple.type.Type; public class XCtrlNode extends CFGNode { public XCtrlNode() { super(new Node[]{CodeGen.CODE._start}); } - + @Override public Tag serialTag() { return Tag.XCtrl; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { return p.p("Xctrl"); } @Override public boolean isConst() { return true; } @Override public Type compute() { return Type.XCONTROL; } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index e9cd13a5..c825f396 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.type.TypeInteger; public class XorNode extends ArithNode { public XorNode(Parser.Lexer loc, Node lhs, Node rhs) { super(loc, lhs, rhs, (byte)1); } - + @Override public Tag serialTag() { return Tag.Xor; } @Override public String op() { return "^"; } @Override long doOp( long x, long y ) { return x ^ y; } diff --git a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java index 58506e9c..e8218afd 100644 --- a/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java +++ b/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java @@ -7,9 +7,9 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.util.BAOS; import java.util.ArrayList; import com.seaofnodes.simple.codegen.Encoding; +import com.seaofnodes.simple.util.BAOS; import java.util.HashMap; /** Machine-specific facts; traversal, columns and byte display live in print/. */ diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index ec4a588d..beaa719c 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.*; @@ -130,7 +131,18 @@ public class Field extends Type { @Override public Type at( int idx ) { return _t; } @Override public void set( int idx, Type t ) { _t = t; } // Tags: final/!final; +alias+name+external-storage flag - + @Override int TAGOFF() { return 2; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + baos.write(TAGOFFS[_type] + (_final ? 1 : 0)); + baos.packed2(_alias); + baos.packed2(strs.get(_fname)); + baos.write(_extern ? 1 : 0); + } + static Field packed( int tag, BAOS bais, String[] strs ) { + int alias = bais.packed2(); + String fname = strs[bais.packed2()]; + return malloc(fname,null,alias,(tag&1)==1,bais.read()!=0); + } @Override public SB _print( SB sb, BitSet visit, boolean html ) { diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 1979368e..980daf0f 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.util.*; import java.util.*; @@ -512,6 +513,123 @@ public class Type /*implements Cloneable*/ { Type _upgradeType(HashMap<String,Type> TYPES) { assert is_nokids(); return this; } + // Recursively gather all types + public void gather(HashMap<Type,Integer> types ) { + if( types.containsKey(this) ) return; // TEST + types.put(this,types.size()); // SET + int nkids = nkids(); + for( int i=0; i<nkids; i++ ) + at(i).gather(types); + } + + // Compute serialization byte tag compression space + final static int[] TAGOFFS = new int[TMAX+1]; + public static int[] TAGOFFS() { + if( TAGOFFS[TMAX-1]==0 ) + // One entry per unique tag-space, using the BOT value from that + // tag-space except for the first tag-space which uses 1 tag for + // multiple Types instead of 1 Type having multiple tags. Has to + // be ordered to match _type enum. + for( Type t : new Type[]{Type.XNIL,TypeScalar.BOT,TypePtr.PTR,TypeInteger.BOT,TypeFloat.F64,TypeConAryB.ABC,TypeRPC.BOT,TypeMemPtr.BOT,TypeFunPtr.BOT,TypeMem.BOT,Field.BOT,TypeStruct.BOT,TypeTuple.BOT} ) + TAGOFFS[t._type+1] = TAGOFFS[t._type] + t.TAGOFF(); + assert TAGOFFS[TMAX] <= 255; + return TAGOFFS; + } + // Reserve 6 tags, 0-5, for plain Types + int TAGOFF() { assert is_simple(); return 6; } + + public void packed( BAOS baos, HashMap<String,Integer> strs ) { + assert is_simple(); + baos.write(_type); + } + static Type packed( int tag ) { + return switch( tag ) { + case TBOT -> BOTTOM; + case TTOP -> TOP; + case TCTRL -> CONTROL; + case TXCTRL->XCONTROL; + case TNIL -> NIL; + default -> throw Utils.TODO("Should not reach here: unknown simple type tag"); + }; + } + + // Produce a type with null child types + static Type packed( BAOS bais, String[] strs ) { + int x = bais.read(); + int type = Arrays.binarySearch( TAGOFFS, x ); + if( type < 0 ) type = -(type+1)-1; + int off = x - TAGOFFS[type]; + return switch( type ) { + case 0, 1, 2, 3, 4, 5 -> Type.packed( off ); + case TSCALAR -> TypeScalar .packed( off ); + case TPTR -> TypePtr .packed( off ); + case TINT -> TypeInteger.packed( off, bais ); + case TFLT -> TypeFloat .packed( off, bais ); + case TCONARY -> TypeConAry .packed( off, bais ); + case TRPC -> TypeRPC .packed( off, bais ); + case TMEMPTR -> TypeMemPtr .packed( off, bais ); + case TFUNPTR -> TypeFunPtr .packed( off, bais ); + case TMEM -> TypeMem .packed( off, bais ); + case TFLD -> Field .packed( off, bais, strs ); + case TSTRUCT -> TypeStruct .packed( off, bais, strs ); + case TTUPLE -> TypeTuple .packed( off, bais ); + default -> throw Utils.TODO("Should not reach here: unknown packed type tag"); + }; + } + + // Read a packed Type array + public static Type[] packed( BAOS bais, String[] strs, int ntypes, HashMap<String,Type> existingTypes, + GlobalBits fileAliases, GlobalBits aliases, + GlobalBits fileFidxs , GlobalBits fidxs , + GlobalBits fileRpcs , GlobalBits rpcs ) { + Type[] types = new Type[ntypes]; + // Read Types in ID# order, no children + for( int i=0; i<ntypes; i++ ) + types[i] = Type.packed(bais,strs); + // Start possibly recursive type collection + BOTTOM.recurOpen(); + // Read Types in ID# order, only children + for( int i=0; i<ntypes; i++ ) { + VISIT.put(types[i]._uid,types[i]); + int nkids = types[i].nkids(); + for( int j=0; j<nkids; j++ ) + types[i].set(j,types[bais.packed4()]); + } + // Remap file-local aliases/fidxs/rpcs into this compilation unit's + // local dense indexes via their global identities. + for( int i=0; i<ntypes; i++ ) { + if( types[i] instanceof Field fld ) { + if( fld._alias >= GlobalBits.RESERVED ) + fld._alias = aliases.map(fileAliases,fld._alias); + } + if( types[i] instanceof TypeFunPtr tfp ) + tfp._fidxs = remapBits(fileFidxs,fidxs,tfp._fidxs,GlobalBits.RESERVED); + if( types[i] instanceof TypeRPC rpc ) + rpc._rpcs = remapBits(fileRpcs,rpcs,rpc._rpcs,GlobalBits.RESERVED); + if( types[i] instanceof TypeMem mem ) { + if( mem._alias >= GlobalBits.RESERVED ) + mem._alias = aliases.map(fileAliases,mem._alias); + mem._escFs = remapBits(fileFidxs ,fidxs ,mem._escFs,GlobalBits.RESERVED); + mem._escAs = remapBits(fileAliases,aliases,mem._escAs,GlobalBits.RESERVED); + } + } + + // Intern them all at once + BOTTOM.recurClose(types); + return types; + } + + private static int[] remapBits(GlobalBits fileBits, GlobalBits bits, int[] fileLocals, int firstMapped ) { + if( fileLocals == XInt.EMPTY || fileLocals == XInt.FULL ) + return fileLocals; + assert !XInt.isHigh(fileLocals); + int[] locals = XInt.EMPTY; + for( int fileLocal = XInt.next(fileLocals,-1); fileLocal >=0; fileLocal = XInt.next(fileLocals,fileLocal) ) + locals = XInt.make(locals,fileLocal < firstMapped ? fileLocal : bits.map(fileBits,fileLocal)); + return locals; + } + + // ---------------------------------------------------------- // Size in bits to hold an instance of this type. diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java index 860cefc5..c9093e3b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAry.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAry.java @@ -74,7 +74,17 @@ public abstract class TypeConAry<A> extends TypeScalar { public abstract long at8(int idx); public abstract int len(); @Override public abstract int log_size(); - - public void write( BAOS baos ) { throw Utils.TODO("Should not reach here: abstract constant array cannot be written"); } + + // Reserve tags for u8 array + @Override int TAGOFF() { return 1; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + assert log_size()==0 && !_any; + baos.write(TAGOFFS[TCONARY]+0); + baos.packed4(len()); + baos.write((byte[])_ary); + } + static TypeConAry packed( int tag, BAOS bais ) { + return TypeConAryB.make(bais.read(new byte[bais.packed4()])); + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java index bddcb1fb..5877c309 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeConAryB.java @@ -16,6 +16,5 @@ public class TypeConAryB extends TypeConAry<byte[]> { @Override public String str() { return "[\""+new String(_ary)+"\"]"; } @Override boolean eq(Type t) { return t instanceof TypeConAryB ary && _widen==ary._widen && Arrays.equals(_ary,ary._ary); } @Override int hash() { return Arrays.hashCode(_ary); } - @Override public void write( BAOS baos ) { baos.write(_ary); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 8638b8c9..d410e9cf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.HashMap; @@ -98,6 +99,26 @@ public class TypeFloat extends TypeScalar { @Override public Type makeZero() { return FZERO; } + // Reserve tags for F64,F32,constant + @Override int TAGOFF() { return 3; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + if( this==F64 ) baos.write(TAGOFFS[_type] + 0); + else if( this==F32 ) baos.write(TAGOFFS[_type] + 1); + else { + assert isConstant(); + baos.write(TAGOFFS[_type] + 2); + baos.packed8(Double.doubleToLongBits(_con)); + } + } + + static Type packed( int tag, BAOS bais ) { + return switch( tag ) { + case 0 -> F64; + case 1 -> F32; + case 2 -> constant(Double.longBitsToDouble(bais.packed8())); + default -> throw Utils.TODO("Should not reach here: unknown float type tag"); + }; + } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz ^ (1<<17)); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 301fcc8b..56f47bff 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -75,6 +75,7 @@ public class TypeFunPtr extends TypeNil { } + @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } public TypeFunPtr makeFrom( int fidx ) { return make1(_nil,_open,_sig,_ret,fidx); } @@ -236,6 +237,33 @@ public class TypeFunPtr extends TypeNil { else _sig[idx] = t; } + // Reserve tags for null/not and open/close, one fidx/bitset, 0-6 args + // Tags 0-5 - not,close,1 fidx, 0-5 args (+fidx) + // Tag 6 - not ,close+fidxs+nargs + // Tag 7 - null,close+fidxs+nargs + @Override int TAGOFF() { return 8; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + assert _open; // Open: Passing extra args is fine, and extras ignored. + if( _nil==2 && nargs()<6 && nfcns() == 1 && fidx() < 64 ) { + baos.write(TAGOFFS[_type] + nargs()); + baos.packed2(fidx()); + } else { + baos.write(TAGOFFS[_type] + 6 + (_nil==2 ? 0 : 1)); + baos.packed1(nargs()); + XInt.packed(baos,_fidxs); + } + } + static TypeFunPtr packed( int tag, BAOS bais ) { + if( tag < 6 ) { + int fidx = bais.read(); + assert fidx < 64; // Need a larger fidx space + return malloc((byte)2,true,new Type[tag],null, XInt.make(fidx)); + } + byte nil = (byte)(tag==6 ? 2 : 3); + int nargs = bais.packed1(); + int[] fidxs = XInt.packed(bais); + return malloc(nil,true,new Type[nargs],null,fidxs); + } @Override int hash() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index a2cf08b0..a0c2266d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.util.ArrayList; import java.util.HashMap; @@ -176,7 +177,38 @@ public class TypeInteger extends TypeScalar { if( _isConstant() ) return BOT; return isHigh() ? dual() : this; } + // Reserve tags for I64,I32,U32,0,constant,generic + @Override int TAGOFF() { return 7; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + if( this==BOT ) baos.write(TAGOFFS[_type] + 0); + else if( this==I32 ) baos.write(TAGOFFS[_type] + 1); + else if( this==U32 ) baos.write(TAGOFFS[_type] + 2); + else if( this==BOOL) baos.write(TAGOFFS[_type] + 3); + else if( this==ZERO) baos.write(TAGOFFS[_type] + 4); + else if( isConstant() ) { + baos.write(TAGOFFS[_type] + 5); + baos.packed8(_min); + } else { + baos.write(TAGOFFS[_type] + 6); + baos.packed8(_min); + baos.packed8(_max); + assert -3 <= _widen && _widen <= 3; + baos.packed1(_widen + 3); + } + } + static Type packed( int tag, BAOS bais ) { + return switch( tag ) { + case 0 -> BOT; + case 1 -> I32; + case 2 -> U32; + case 3 -> BOOL; + case 4 -> ZERO; + case 5 -> constant(bais.packed8()); + case 6 -> make(bais.packed8(),bais.packed8(),(byte)(bais.packed1()-3)); + default -> throw Utils.TODO("Should not reach here: unknown integer type tag"); + }; + } @Override int hash() { return Utils.fold(_min) * Utils.fold(_max) + _widen; } @Override public boolean eq( Type t ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 4234a5e5..9ae68bcf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -173,7 +173,31 @@ public class TypeMem extends Type { @Override public int nkids() { return 1; } @Override public Type at( int idx ) { return _t; } @Override public void set( int idx, Type t ) { _t = t; } - + // one tag for alias#1, one tag for generic alias. + // tag bit for _one, another bit for _final. + @Override int TAGOFF() { return 12; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + baos.write(TAGOFFS[_type] + + (_alias==1 ? 0 : 1) + + (!_final ? 0 : 2) + + (!_one ? 0 : (_clz ? 4 : 8))); + if( _alias!=1 ) { + // generic alias + assert _alias <= 255; + baos.packed1( _alias ); + } + XInt.packed(baos,_escFs); + XInt.packed(baos,_escAs); + } + static TypeMem packed( int tag, BAOS bais ) { + int alias = (tag&1)==0 ? 1 : bais.packed1(); + boolean xfinal= (tag&2)==2; + boolean one = (tag&12)!=0; + boolean clz = (tag&4)==4; + int[] escFs = XInt.packed(bais); + int[] escAs = XInt.packed(bais); + return malloc(alias,null,one,clz,xfinal,escFs,escAs); + } @Override public SB _print(SB sb, BitSet visit, boolean html) { if( this==BOT ) return sb.p("MemBot"); diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 73ca6190..175b1c63 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.SB; +import com.seaofnodes.simple.util.BAOS; import java.util.*; /** @@ -162,6 +163,19 @@ public class TypeMemPtr extends TypeNil { @Override public Type at( int idx ) { return _obj; } @Override public void set( int idx, Type t ) { _obj = (TypeStruct)t; } + // Reserve tags for null/not, one/general, public/private and read-only access + @Override int TAGOFF() { return 16; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + assert _nil>=2; + baos.write(TAGOFFS[_type] + + (_nil==2 ? 0 : 1) + + (!_one ? 0 : 2) + + (!_pub ? 0 : 4) + + (!_ro ? 0 : 8) ); + } + static TypeMemPtr packed( int tag, BAOS bais ) { + return malloc((byte)((tag&1)+2),null,(tag&2)==2,(tag&4)==4).access((tag&8)==8); + } @Override public String str() { if( this==BOT ) return "PtrBot"; diff --git a/src/main/java/com/seaofnodes/simple/type/TypePtr.java b/src/main/java/com/seaofnodes/simple/type/TypePtr.java index 7e9e70e4..38941ed1 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypePtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypePtr.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.AryInt; import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; +import com.seaofnodes.simple.util.BAOS; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; @@ -52,6 +53,14 @@ public class TypePtr extends TypeNil { @Override TypePtr _makeStorage() { return PTR; } + // Reserve 2 tags, PTR and NPTR + @Override int TAGOFF() { return 2; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + assert _nil>=2; + baos.write(TAGOFFS[_type] + (_nil==2 ? 0 : 1)); + } + static TypePtr packed( int tag ) { return tag==0 ? NPTR : PTR; } + @Override public String str() { return STRS[_nil]; } @Override public SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java index 7acc99de..8a12f50a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeRPC.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeRPC.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.type; import com.seaofnodes.simple.util.Ary; +import com.seaofnodes.simple.util.BAOS; import java.util.*; /** @@ -74,6 +75,25 @@ public class TypeRPC extends Type { @Override boolean _isConstant() { return XInt.isConstant(_rpcs); } @Override TypeRPC _makeStorage() { return this; } + // Reserve tags for ALL, singleton, generic + @Override int TAGOFF() { return 3; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + if( this==BOT ) { + baos.write( TAGOFFS[_type] + 0 ); + } else if( XInt.isConstant(_rpcs) ) { // Singleton + baos.write(TAGOFFS[_type] + 1); + baos.packed2(rpc()); + } else { // Generic + assert !XInt.isHigh(_rpcs); // Not serializing above-center RPC + baos.write(TAGOFFS[_type] + 2); + XInt.packed(baos,_rpcs); + } + } + static TypeRPC packed( int tag, BAOS bais ) { + if( tag==0 ) return BOT; + if( tag==1 ) return malloc(XInt.make(bais.packed2())); + return malloc(XInt.packed(bais)); + } @Override int hash() { return XInt.hash(_rpcs); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeScalar.java b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java index e369e6a5..eaba0a1c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeScalar.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeScalar.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.SB; import java.util.ArrayList; @@ -39,6 +40,17 @@ public class TypeScalar extends Type { @Override public boolean isHigh() { return this == TOP; } @Override Type _makeStorage() { return BOT; } + // Reserve tags for both lattice endpoints. Unlike most concrete scalar + // families, generic scalar TOP can survive into a serialized graph. + @Override int TAGOFF() { return 2; } + @Override public void packed(BAOS baos, HashMap<String,Integer> strs) { + assert this == BOT || this == TOP; + baos.write(TAGOFFS[_type] + (this == BOT ? 0 : 1)); + } + static TypeScalar packed(int tag) { + assert tag == 0 || tag == 1; + return tag == 0 ? BOT : TOP; + } @Override public String str() { return isHigh() ? "~scalar" : "scalar"; } @Override SB _print(SB sb, BitSet visit, boolean html) { return sb.p(str()); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 67169009..4c5ae6ea 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -528,7 +528,22 @@ public class TypeStruct extends Type { // Tags 5 - closed(+ nflds +name) // Tags 6-10- open +#nflds (+name) // Tags 11 - open (+ nflds +name) - + @Override int TAGOFF() { return 24; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + baos.write(TAGOFFS[_type]+ (_fref ? 12 : 0) + (_open ? 6 : 0) + Math.min(5,_fields.length)); + if( _fields.length >= 5 ) + baos.packed2(_fields.length); + baos.packed2(strs.get(_name)); + // TODO: Write aliases summary + } + static TypeStruct packed( int tag, BAOS bais, String[] strs ) { + boolean fref = tag >= 12; + if( fref ) tag -= 12; + int ntag = tag >= 6 ? tag-6 : tag; + int nflds = ntag < 5 ? ntag : bais.packed2(); + String name = strs[bais.packed2()]; + return malloc(name,ntag!=tag,fref,new Field[nflds]); + } @Override SB _print(SB sb, BitSet visit, boolean html ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 0d70bdf2..075698dc 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -124,6 +124,20 @@ public class TypeTuple extends Type { @Override public Type at( int idx ) { return _types[idx]; } @Override public void set( int idx, Type t ) { _types[idx] = t; } + // Reserve tags for tuples with 2,3,generic + @Override int TAGOFF() { return 4; } + @Override public void packed( BAOS baos, HashMap<String,Integer> strs ) { + if( _types.length==2 ) baos.write(TAGOFFS[_type] + 0); + else if( _types.length==3 ) baos.write(TAGOFFS[_type] + 1); + else if( _types.length==4 ) baos.write(TAGOFFS[_type] + 2); + else baos.write(TAGOFFS[_type] + 3).packed2(_types.length); + } + static TypeTuple packed( int tag, BAOS bais ) { + if( tag==0 ) return malloc(new Type[2]); + if( tag==1 ) return malloc(new Type[3]); + if( tag==2 ) return malloc(new Type[4]); + return malloc(new Type[bais.packed2()]); + } @Override SB _print(SB sb, BitSet visit, boolean html ) { if( this==TOP ) return sb.p("[TOP]"); diff --git a/src/main/java/com/seaofnodes/simple/type/XInt.java b/src/main/java/com/seaofnodes/simple/type/XInt.java index 126a4e64..752c1419 100644 --- a/src/main/java/com/seaofnodes/simple/type/XInt.java +++ b/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -196,6 +196,19 @@ public abstract class XInt { } + public static void packed(BAOS baos, int[] xs) { + baos.packed1(xs.length); + for( int i=1; i<xs.length; i++ ) + baos.packed4(xs[i]); + } + public static int[] packed(BAOS bais) { + int len = bais.packed1(); + int[] xs = free(len); + for( int i=1; i<len; i++ ) + xs[i] = bais.packed4(); + return intern(xs); + } + // Next set bit, or -1 // for( int bit = XInt.next(bits,0); bit >=0; bit = XInt.next(bits,bit) ) {...bit...} public static int next(int[] xs, int x) { @@ -208,6 +221,17 @@ public abstract class XInt { } // Remap all bits + public static int[] remap( int[] xs, AryInt map ) { + if( xs==FULL ) return xs; + assert !isHigh(xs); + int[] ys = free(xs.length); + for( int bit = next(xs,0); bit >=0; bit = next(xs,bit) ) { + int bat = map.at(bit); + ys[idx(bat)] |= mask(bat); + } + return intern(ys); + } + public static String str(int[] xs) { return str(new SB(),xs).toString(); } diff --git a/src/test/java/com/seaofnodes/simple/BoundaryTest.java b/src/test/java/com/seaofnodes/simple/BoundaryTest.java index 68d8175f..b736ccb3 100644 --- a/src/test/java/com/seaofnodes/simple/BoundaryTest.java +++ b/src/test/java/com/seaofnodes/simple/BoundaryTest.java @@ -75,14 +75,9 @@ public class BoundaryTest { } } - @Test public void testLibrarySource() { - CodeGen code=new CodeGen("return sys.char.toupper('a');").driver(CodeGen.Phase.TypeCheck); - assertEquals("65",Eval2.eval(code,0)); - } - @Test public void testLazyTables() { for( long seed : new long[]{1,123,987654321} ) { - CodeGen code=new CodeGen("src/test/smp/lazy","build/objs","App/Main",null,seed,true,TypeInteger.BOT) + CodeGen code=new CodeGen("src/test/smp/lazy","build/objs",null,"App/Main",null,seed,true,TypeInteger.BOT) .driver(CodeGen.Phase.TypeCheck); assertEquals("0",Eval2.eval(code,0)); assertEquals("125",Eval2.eval(code,1)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 39c7040e..6892db0c 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -39,6 +39,7 @@ public class Chapter10Test { } + private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; new Point = { int v -> x = v; }; }; !Point?[] !points = new !Point?[2]; @@ -373,6 +374,7 @@ return ret.v0; } + @Test public void testModGlobalInConstructor() { CodeGen code = new CodeGen( diff --git a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 62dbbde4..4019fd38 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -300,7 +300,7 @@ A x = new A; for( String fields : new String[] { "!B !b; new A = { -> if (arg) b = new B; };", "!B !b; new A = { -> if (arg) return 0; b = new B; };", - "!B !b; new A = { !B !b -> b = new B; };", // Mutable argument shadows field + "!B !b; new A = { !B !b -> b = new B; };", // Argument shadows field "new A = { -> }; !B !b;", // Field declared later } ) { CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return 0;"); @@ -538,6 +538,7 @@ for(;;arg++;) {} } + // --------------------------------------------------------------- @Test public void testForward0() { diff --git a/src/test/java/com/seaofnodes/simple/Chapter25Test.java b/src/test/java/com/seaofnodes/simple/Chapter25Test.java new file mode 100644 index 00000000..31a616b5 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter25Test.java @@ -0,0 +1,528 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.isa.eval.EvalRisc5; + +import com.seaofnodes.isa.eval.EvalArm64; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; +import com.seaofnodes.simple.codegen.ElfReader; +import com.seaofnodes.simple.codegen.ParseAll; +import com.seaofnodes.simple.node.CallNode; +import com.seaofnodes.simple.node.FunNode; +import com.seaofnodes.simple.node.LoopNode; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.io.File; +import java.io.FileWriter; +import java.io.IOException; +import java.io.ByteArrayOutputStream; +import java.io.PrintStream; +import java.nio.charset.StandardCharsets; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Ignore; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter25Test { + + @Test public void testFlagSpills() throws IOException { + com.seaofnodes.simple.codegen.FlagSpillTestSupport.run(); + } + + @Ignore + @Test + public void testJig() { + String src = "{ i32 -> i32 } close = \"C\"; val main = { u8[] a -> if (a# > 1) return close(0); return a[0]; };"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); + assertEquals("return (arg+3);", code.print()); + assertEquals("3",Eval2.eval(code,0)); + } + + @Test public void testConditionalClassInitX86() throws IOException { + Path build=Path.of("build/objs"); + Files.createDirectories(build); + Path dir=Files.createTempDirectory(build,"init_flags_"); + // Keep B separately compiled so its first-touch check survives. + new CodeGen(null,dir.toString(),null,"B","int value=17+arg;",123,true,TypeInteger.BOT) + .driver("x86_64_v2","win64",false,false); + // GCM can hoist the fused B.$init compare above the test of take. + // Its flags then cross another flag definition and need a legal split. + new CheckedCodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","val run={int take -> return take ? B.value : 0; };",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.Encoding,"x86_64_v2","win64"); + // Remove successful fixtures; preserve the object if compilation fails. + Files.delete(dir.resolve("B.o")); + Files.delete(dir); + } + + @Test public void testPublicInstanceMethod() { + String src = """ + struct Scan { + val visible = { u8 c -> c==255; }; + val _hidden = { u8 c -> c==1; }; + }; + struct _Private { + val hiddenClassMethod = { u8 c -> c==2; }; + }; + return new Scan.visible(44); + """; + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.Parse); + FunNode visible = null; + int checked = 0; + for( FunNode fun : code._linker ) { + if( fun==null || fun._name==null ) continue; + if( fun._name.equals("visible") ) { + assertTrue(code.publicFIDX(fun.sig().fidx())); + visible = fun; + checked++; + } + if( fun._name.equals("_hidden") || fun._name.equals("hiddenClassMethod") ) { + assertFalse(code.publicFIDX(fun.sig().fidx())); + checked++; + } + } + assertEquals(3,checked); + code.driver(CodeGen.Phase.TypeCheck); + assertTrue(visible.unknownCallers()); + assertEquals(TypeInteger.U8,visible.parm(3)._type); + assertEquals("0",Eval2.eval(code,0)); + } + } + + @Test public void testNeverReturnPointerRiscV() { + new CodeGen(""" + struct _S { int x; }; + !_S !s = new _S; + if(arg) while(1) { s.x += arg; } + return s; + """).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); + } + + @Test public void testInlineNeverExit() { + String[] sources={ + "val _spin={ -> while(1) {} return 1; }; _spin(); return 2;", + // Two callers require cloning, including the non-exiting arm. + "val _spin={int x -> if(x) while(1) {} return 7; }; return _spin(arg)+_spin(arg);" + }; + for( int i=0; i<sources.length; i++ ) { + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen(sources[i],seed,true).driver(CodeGen.Phase.TypeCheck); + assertNull("Calls should inline",code._start.walk(n -> n instanceof CallNode ? n : null)); + assertNotNull("The non-exiting path must survive",code._start.walk(n -> n instanceof LoopNode && n!=code._start ? n : null)); + if( i==1 ) assertEquals("14",Eval2.eval(code,0,10)); + assertNull(Eval2.eval(code,1,10)); + } + for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) + new CheckedCodeGen(sources[i]).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + } + } + + @Test + public void testExternData() throws IOException { + String src = """ + i32 counter="C"; + i8 small="C"; + f64 fraction="C"; + {int} bump="C"; + val test_global={ -> + val before=counter; + counter=before; + counter=++counter+1; + counter+=1; + val mid=bump(); + small++; + fraction=fraction+0.5; + return before*10000+mid*100+counter; + }; + """; + TestC.runC(src,"extern_data","",-1); + } + + @Test + public void testExternDataEncoding() { + for( String cpu : new String[]{"arm","riscv"} ) { + CodeGen code = new CheckedCodeGen("i32 counter=\"C\"; counter=counter+3; return counter;"); + // Exercise signed low-12 relocation arithmetic, past the first page. + int addr = 0x3800; + code._externDataAddresses.put("counter",addr); + code.driver(cpu,"SystemV",true,false); + byte[] image = new byte[1<<20]; + var bits = code._encoding._bits; + System.arraycopy(bits.buf(),0,image,0,bits.size()); + if( cpu.equals("arm") ) { + EvalArm64 arm = new EvalArm64(image,1<<16); + arm.st4(addr,-7); + assertEquals(0,arm.step(1000)); + assertEquals(-4,arm.regs[0]); + assertEquals(-4,arm.ld4s(addr)); + } else { + EvalRisc5 r5 = new EvalRisc5(image,1<<16); + r5.st4(addr,-7); + assertEquals(0,r5.step(1000)); + assertEquals(-4,r5.regs[10]); + assertEquals(-4,r5.ld4s(addr)); + } + } + } + + @Test + public void testExternDataImports() throws IOException { + Path dir = Files.createTempDirectory(Path.of("build/objs"),"extern_data_"); + String globals = "i32 counter=\"C\"; val read={ -> counter; };"; + CodeGen globalCode = new CodeGen(null,dir.toString(),null,"Globals",globals,126,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + var clz = globalCode.compunit()._clz; + int counter = clz.find("counter"); + assertTrue(clz._fields[counter]._extern); + assertEquals(-1,clz.offset(counter)); + assertEquals(clz.remove(counter).size(),clz.size()); + // Load the serialized declaration and ideal graph from Globals.o. + String src = """ + i32 counter="C"; + val test_global={ -> + val before=Globals.counter; + Globals.counter=before+1; + counter+=2; + return before*100+Globals.read(); + }; + """; + Ary<String> paths = new Ary<>(new String[]{dir.toString()}); + for( boolean imported : new boolean[]{true,false} ) { + Path root = dir.resolve(imported ? "binary" : "source"); + Files.createDirectories(root.resolve("Main")); + if( !imported ) Files.writeString(root.resolve("Main/Globals.smp"),globals); + new CodeGen(root.toString(),root.toString(),imported ? paths : null,"Main",src,126,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + assertEquals("",TestC.gcc(root+"/Main.o","",TestC.C_DRIVERS_DIR+"extern_data_import.c", + (String)null,new Ary<>(new String[]{dir+"/Globals.o"}),root+"/program"+(TestC.OS.startsWith("Windows") ? ".exe" : ""))); + } + } + + @Test public void testPrintingConstantPool() throws Exception { + com.seaofnodes.simple.codegen.PrintRegTestSupport.checkConstantPool(); + } + + private static final String SYS_BLDDIR = "build/objs/lib_"+TestC.CPU_ABI; + private static final File SYS_FILE = new File(SYS_BLDDIR+"/sys.o"); + + @Test + public void testForwardConstructor() { + CodeGen code = new CodeGen("src/test/java/com/seaofnodes/simple/test_smp/forward_ctor", + "build/objs/forward_ctor_parse",null, + "m",null,123L,true,TypeInteger.BOT); + code.driver(CodeGen.Phase.TypeCheck); + } + + + @Test + public void testPostfixFieldUpdate() { + String src = """ + struct V { + u32 !len = 0; + i64[] !buf; + new V = { i64[] b -> buf=b; }; + val grow = { i64 n -> self; }; + val add = { i64 x -> grow(1).buf[len++] = x; self; }; + }; + return new V(new i64[1]).add(7).len; + """; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("1",Eval2.eval(code,0)); + } + + @Test + public void testStringEscapes() { + String src = "u8[~] s=\"A\\n\\t\\r\\\\\\\"B\"; " + + "return s#==7 && s[0]=='A' && s[1]==10 && s[2]==9 && s[3]==13 && " + + "s[4]==92 && s[5]==34 && s[6]=='B';"; + CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); + assertEquals("1",Eval2.eval(code,0)); + } + + @Test + public void testCharacterEscapes() { + CodeGen code = new CodeGen("return '\\n'==10 && '\\t'==9 && '\\r'==13;") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("1",Eval2.eval(code,0)); + } + + @Test + public void testFuzzerUnresolvedNumericLoop() { + CodeGen code = new CodeGen(""" + arg=0; + while(arg+0) + while(-arg) + arg=0; + """).driver(CodeGen.Phase.TypeCheck); + assertEquals("return 0;",code.print()); + } + + @Test + public void testFuzzerBadLCA() { + new CodeGen(""" + int v0=arg; + if(v0&&--v0?0:arg) {} + """).driver(CodeGen.Phase.LocalSched); + } + + @Test @Ignore + public void testModule0() throws IOException { + String MODDIR = "src/test/java/com/seaofnodes/simple/test0"; + String BLDDIR = "build/objs/test0"; + String a_obj = BLDDIR+"/A.o"; + String ab_obj = BLDDIR+"/A/B.o"; + // Remove any prior results so the test runs from scratch. + delELFiles(new File(BLDDIR)); + writeB(MODDIR,5); + + // Compile MODDIR/A.smp into MODDIR/A.o + // Since A refers to B also: + // Compile MODDIR/A/B.smp into MODDIR/A/B.o + CodeGen code1 = new CodeGen(MODDIR, BLDDIR,null, + "A",null,123L,true,TypeInteger.BOT); + code1.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION); + + // Verify produces A.o, A/B.o + File a_file = new File( a_obj); + File ab_file = new File(ab_obj); + assertTrue( a_file.exists() ); + assertTrue( ab_file.exists() ); + long a_msec1 = a_file.lastModified(); + long ab_msec1 = ab_file.lastModified(); + + // Link and execute: arg is true, so compute "5+1" as the exit code + String rez1 = TestC.gcc("A", 1.2, a_obj, ab_obj); + assertEquals("exec exit code: 6",rez1); + + // Compile again A, expecting both A.o and A/B.o to be up-to-date and not compiled + CodeGen code2 = new CodeGen(MODDIR, BLDDIR, null, + "A",null,123L,true,TypeInteger.BOT); + code2.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION); + + assertTrue( a_file.exists() ); + assertTrue( ab_file.exists() ); + long a_msec2 = a_file.lastModified(); + long ab_msec2 = ab_file.lastModified(); + + assertEquals( a_msec1, a_msec2 ); + assertEquals( ab_msec1, ab_msec2 ); + + // Touch A.smp and recompile. A/B.o should not recompile. + new File(MODDIR+"/A.smp").setLastModified(System.currentTimeMillis()); + CodeGen code3 = new CodeGen(MODDIR, BLDDIR,null, + "A",null,123L,true,TypeInteger.BOT); + code3.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION); + + long a_msec3 = a_file.lastModified(); + long ab_msec3 = ab_file.lastModified(); + assertTrue ( a_msec1 < a_msec3 ); + assertEquals( ab_msec1, ab_msec3 ); + + // Link and execute: arg is true, so compute "5+1" as the exit code + String rez3 = TestC.gcc("A", 1.2, a_obj, ab_obj); + assertEquals("exec exit code: 6",rez3); + + + // Modify B.smp and recompile A/B.o; it should recompile and A.o should not. + writeB(MODDIR,7); + CodeGen code4 = new CodeGen(MODDIR, BLDDIR,null, + "A/B",null,123L,true,TypeInteger.BOT); + code4.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION); + + long a_msec4 = a_file.lastModified(); + long ab_msec4 = ab_file.lastModified(); + assertEquals( a_msec3, a_msec4 ); + assertTrue ( ab_msec3 < ab_msec4 ); + + // Link and execute: uses stale A.o, so remains '6' not '7+1' == 8 + String rez4 = TestC.gcc("A", 1.2, a_obj, ab_obj); + assertEquals("exec exit code: 6",rez4); + + // Recompile A.o, it should recompile despite not being touched because + // it depends on A/B.o which recompiled in the prior step. + CodeGen code5 = new CodeGen(MODDIR, BLDDIR,null, + "A",null,123L,true,TypeInteger.BOT); + code5.driver(CodeGen.Phase.Export,TestC.CPU_PORT,TestC.CALL_CONVENTION); + + long a_msec5 = a_file.lastModified(); + long ab_msec5 = ab_file.lastModified(); + assertTrue ( a_msec4 < a_msec5 ); + assertEquals( ab_msec4, ab_msec5 ); + + // Link and execute: updates A.o from B.o inlining, without compiling B.o + String rez5 = TestC.gcc("A", 1.2, a_obj, ab_obj); + assertEquals("exec exit code: 8",rez5); + // Reset for next time + writeB(MODDIR,5); + } + + private void writeB(String MODDIR, int x) throws IOException { + var bsmp = new FileWriter(MODDIR+"/A/B.smp"); + bsmp.write("val x="+x+";\n"); + bsmp.close(); + } + + + // Recursive search (TODO: gzip, archives) and delete all .o files + private void delELFiles( File dir) { + if( dir.isDirectory() ) + for( File f : dir.listFiles() ) + delELFiles(f); + else if( dir.getName().endsWith(".o") ) + dir.delete(); + } + + + @Test + public void testSys() { + assertTrue("Missing "+SYS_FILE+"; run make tests_sys", SYS_FILE.exists()); + + // Can read the ELF files + CodeGen code1 = new CodeGen("return 0;"); + ElfReader sys_elf = ElfReader.load(SYS_FILE, null); + sys_elf.loadPublicTypes(code1); + + // Elf files are sane + + // Sys depends on io, libc, char, collections, and array utilities. + assertArrayEquals(new String[]{"sys", "sys/adt", "sys/adt/bitset", "sys/ary", + "sys/aryi64", "sys/aryu8", "sys/char", "sys/io", "sys/libc", "sys/scan"},sys_elf._deps); + assertSame("class:sys" ,sys_elf._clz._name); + } + + @Test + public void testConstantClassInitialization() throws IOException { + TestC.runSF("val x = 42; return 0;","constantClassInt","",0); + TestC.runSF("val f = { -> 7; }; return 0;","constantClassFunction","",0); + } + + @Test + public void testHelloWorld() throws IOException { + String expected = "Hello, World!\n"; + String prog = "return sys.io.p(\""+expected+"\") - "+expected.length()+";"; + // tests_raw1 concurrently builds Chapter22Test's helloWorld executable. + TestC.run(prog,"helloWorldSys",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION, null, null, expected,0); + } + + @Test + public void testHelloWorldDriver() throws Exception { + String out = "build/objs/helloWorldDriver/"; + Simple.main(new String[]{"-L",SYS_BLDDIR,"-o",out,"--norun","src/test/smp/examples/A_helloWorld.smp"}); + assertTrue(Files.isRegularFile(Path.of(out,"A_helloWorld.o"))); + } + + @Test + public void testHelloWorldDriverLibFile() throws Exception { + ByteArrayOutputStream output = new ByteArrayOutputStream(); + PrintStream saved = System.out; + try( PrintStream capture = new PrintStream(output,true,StandardCharsets.UTF_8) ) { + System.setOut(capture); + Simple.main(new String[]{"-L",SYS_FILE.toString(),"-o","build/objs/helloWorldDriverLibFile/", + "src/test/smp/examples/A_helloWorld.smp"}); + } finally { + System.setOut(saved); + } + assertEquals("Hello, World!\n",output.toString(StandardCharsets.UTF_8)); + } + + @Test + public void testHelloWorldNoInline() throws Exception { + String base = "helloWorldNoInline"; + String expected = "Hello, World!\n"; + String prog = "return sys.io.p_noInline(\""+expected+"\") - "+expected.length()+";"; + CodeGen code = new CheckedCodeGen(null,"build/objs",new Ary<>(new String[]{SYS_BLDDIR}), + base,prog,123L,true,TypeInteger.BOT); + code.driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,true); + + String obj = "build/objs/"+base+".o"; + String exe = "build/objs/"+base+(TestC.OS.startsWith("Windows") ? ".exe" : ""); + String syms = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,"nm",obj); + assertTrue(syms, syms.contains(" U sys.io.p_noInline")); + + TestC.linkExe(obj,null,null,new Ary<>(new String[]{SYS_FILE.toString()}),exe); + String rez = TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe); + assertEquals(expected,rez); + } + + @Test + public void testRedirectedRead() throws IOException { + String src = """ +u8[] buf = new u8[10]; +i64 ptr = buf; +int rez = sys.libc.read(0,ptr,buf#); +return rez < buf# ? 0 : sys.libc._exit(-2); +"""; + TestC.run(src,"redirectedRead",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION, null, null, + "abc", "", -1); + } + + @Test + public void testErrnoAccessor() throws IOException { + String src = "val status=sys.libc.close(-1); return status != -1 || sys.libc.errno()==0;"; + TestC.run(src,"errnoAccessor",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,"",-1); + } + + @Test + public void testBubbles() throws IOException { + String src = Files.readString( Path.of("src/test/smp/examples/BubbleSort.smp")); + String exe = TestC.compile(src,"BubbleSort",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("[-17, 2, 3, 999]\n", + TestC.exec(exe,"[3, 2,-17, 999 ]")); + assertEquals("[1, 2, 3, 4, 4, 5]\n", + TestC.exec(exe,"[4, 5, 3, 1, 4, 2]")); + assertEquals("[1, 2, 3, 4, 5]\n", + TestC.exec(exe,"[1, 2, 3, 4, 5]")); + assertEquals("[1, 2, 3, 4, 5, 6, 7, 8, 9]\n", + TestC.exec(exe,"[9, 8, 7, 6, 5, 4, 3, 2, 1]")); + + String usage = "Usage: please provide a list of at least two integers to sort in the format \"[1, 2, 3, 4, 5]\"\n"; + assertEquals(usage,TestC.exec(exe)); + assertEquals(usage,TestC.exec(exe,"")); + assertEquals(usage,TestC.exec(exe,"[1]")); + assertEquals(usage,TestC.exec(exe,"[4 5 3]")); + } + + @Test + public void testCapitalize() throws IOException { + String src = Files.readString(Path.of("src/test/smp/examples/Capitalize.smp")); + String exe = TestC.compile(src,"Capitalize",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("Hello world\n",TestC.exec(exe,"hello world")); + assertEquals("Hello World\n",TestC.exec(exe,"Hello World")); + assertEquals("123 apples\n",TestC.exec(exe,"123 apples")); + assertEquals("Usage: please provide a string\n",TestC.exec(exe)); + assertEquals("Usage: please provide a string\n",TestC.exec(exe,"")); + assertEquals("Use quotes around multiple strings.\n",TestC.exec(exe,"hello","world")); + } + + @Test + public void testDijkstra() throws IOException { + String src = Files.readString(Path.of("src/test/smp/examples/Dijkstra.smp")); + String matrix = "[0, 2, 0, 6, 0, 2, 0, 3, 8, 5, 0, 3, 0, 0, 7, 6, 8, 0, 0, 9, 0, 5, 7, 9, 0]"; + String exe = TestC.compile(src,"Dijkstra",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("2\n",TestC.exec(exe,matrix,"0","1")); + String usage = "Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"; + assertEquals("7\n",TestC.exec(exe,matrix,"0","4")); + assertEquals(usage,TestC.exec(exe)); + assertEquals(usage,TestC.exec(exe,"","","")); + assertEquals(usage,TestC.exec(exe,"[1, 0, 3, 0, 5, 1]","1","2")); + assertEquals(usage,TestC.exec(exe,"[0, 0, 0, 0]","0","1")); + } + + @Test + public void testFileIO() throws IOException { + String src = Files.readString(Path.of("src/test/smp/examples/FileIO.smp")); + String exe = TestC.compile(src,"FileIO",new Ary<>(new String[]{SYS_BLDDIR}), + TestC.CALL_CONVENTION,null,null,-1); + assertEquals("File I/O succeeded\n",TestC.exec(exe)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java index 6b4a987d..47e10f97 100644 --- a/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java +++ b/src/test/java/com/seaofnodes/simple/ClassInitDependenciesTest.java @@ -57,7 +57,7 @@ public class ClassInitDependenciesTest { Files.createDirectories(path.getParent()); Files.writeString(path,source.getValue()); } - return new CodeGen(root.toString(),root.resolve("obj").toString(), + return new CodeGen(root.toString(),root.resolve("obj").toString(),null, "Root",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); } @@ -194,26 +194,119 @@ public class ClassInitDependenciesTest { assertTrue(touches(code,new ClassInitDependencies(code),"Root/A","Root/B")); code=compile("A",Map.of("A","{int} native=\"C\"; return native();"),123); + Path dir=tempDir("import-"); + new CodeGen(null,dir.toString(),null,"B","int value=1;",123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "A","return B.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertTrue(touches(code,new ClassInitDependencies(code),"A","B")); } - private void object(Path dir, Path unused, String name, String source) throws Exception { - Path file=dir.resolve("Root/"+name+".smp"); - Files.createDirectories(file.getParent()); - Files.writeString(file,source); + private CodeGen object(Path dir, Path imports, String name, String source) { + return new CodeGen(null,dir.toString(),new Ary<>(new String[]{imports.toString()}), + name,source,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); } - private void module(Path dir, Path unused, String name, Map<String,String> sources) throws Exception { - for( var entry : sources.entrySet() ) object(dir,dir,entry.getKey(),entry.getValue()); + private CodeGen module(Path dir, Path imports, String name, Map<String,String> sources) throws Exception { + Path src=tempDir("import-"); + for( var entry : sources.entrySet() ) { + Path file=src.resolve(entry.getKey()+".smp"); + Files.createDirectories(file.getParent()); + Files.writeString(file,entry.getValue()); + } + return new CodeGen(src.toString(),dir.toString(),new Ary<>(new String[]{imports.toString()}), + name,null,123,true,TypeInteger.BOT).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); } - private CodeGen entry(Path dir, String source, long seed) throws Exception { - Files.writeString(dir.resolve("Root.smp"),""); - object(dir,dir,"Main",source); - return new CodeGen(dir.toString(),dir.toString(),"Root/Main",null,seed,true,TypeInteger.BOT); + @Test public void testImportedInitialization() throws Exception { + Path dir=tempDir("import-"), stubs=tempDir("import-"); + object(stubs,stubs,"A","int value=arg;"); + object(stubs,stubs,"B","int value=arg;"); + // Each object is independently acyclic. Combining their real bodies + // must recheck the graph rather than trust either object's local order. + String asrc="int value=arg;\nvalue=B.value;"; + CodeGen acode=module(dir,stubs,"A",Map.of("A",asrc)); + String afile=acode._compunits.get("A").sourceFile(); + module(dir,stubs,"B",Map.of("B","int value=arg; value=A.value;")); + for( String entry : new String[]{"A","B"} ) { + try { + new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return "+entry+".value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + fail("Expected imported initialization cycle"); + } catch( Parser.ParseException ex ) { + assertCycle(ex.getMessage(),"A -> B -> A"); + assertTrue(ex.getMessage(),ex.getMessage().contains("value=B.value;\n -------^")); + assertTrue(ex.getMessage(),ex.getMessage().contains("\n"+afile+":2:8: error: cyclic class initialization\n")); + } + } + // The imported object must still report its saved path and offset + // when the original source is no longer available. + Files.delete(Path.of(afile)); + try { + new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return A.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + fail("Expected imported initialization cycle"); + } catch( Parser.ParseException ex ) { + assertCycle(ex.getMessage(),"A -> B -> A"); + assertTrue(ex.getMessage(),ex.getMessage().contains("\n"+afile+": error: cyclic class initialization (source unavailable at byte offset "+asrc.indexOf('.')+")")); + } } - private CodeGen emit(Path dir, String name, String source) throws Exception { - return entry(dir,source,123).driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + @Test public void testImportedDiamondAndHelpers() throws Exception { + Path diamond=tempDir("import-"); + CodeGen dcode=object(diamond,diamond,"D","int value=arg;"); + var data=dcode._encoding._data.entries().stream().filter(obj -> obj.symbol.equals("D.$class")).findFirst().orElseThrow(); + var dclz=dcode._compunits.get("D")._clz; + assertEquals(0,dcode._encoding._sdata.buf()[data.offset+dclz.offset(dclz.find("$init"))]); + object(diamond,diamond,"B","int value=D.value;"); + object(diamond,diamond,"C","int value=D.value;"); + for( long seed : new long[]{1,123,987654321} ) { + CodeGen code=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","int value=B.value+C.value;",seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + CompUnit b=code._compunits.get("B"), d=code._compunits.get("D"); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertTrue(touches(code,deps,"B","D")); + assertTrue(touches(code,deps,"C","D")); + assertTrue(touches(code,deps,"Main","B")); + assertTrue(touches(code,deps,"Main","C")); + Field flag=d._clz.field("$init"); + assertSame(TypeInteger.U1,flag._t); + assertFalse(flag._final); + assertNotEquals(flag._alias,b._clz.field("$init")._alias); + // Loading just the header/types uses the same alias identity and + // does not require allocating any graph nodes. + ElfReader elf=ElfReader.load(diamond.resolve("D.o").toFile(),d); + assertEquals(flag._alias,elf.loadPublicTypes(code).field("$init")._alias); + assertNull(elf._nodes); + } + object(diamond,diamond,"Helper","val get={ -> D.value; }; val get_noInline={ -> D.value; };"); + for( String name : new String[]{"get","get_noInline"} ) { + CodeGen code=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","return Helper."+name+"();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + ClassInitDependencies deps=new ClassInitDependencies(code); + assertTrue(touches(code,deps,"Main","D")); + assertFalse(touches(code,deps,"Helper","D")); + } + object(diamond,diamond,"Wrapper","val get_noInline={ -> Helper.get_noInline(); };"); + CodeGen wrapped=new CodeGen(null,diamond.toString(),new Ary<>(new String[]{diamond.toString()}), + "Main","return Wrapper.get_noInline();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertTrue(touches(wrapped,new ClassInitDependencies(wrapped),"Main","D")); + } + + @Test public void testInterleavedModules() throws Exception { + // Two objects, each providing a parent and children. Their orders + // must interleave: P.B precedes Q.A, which precedes P.A. + Path modules=tempDir("import-"), qstub=tempDir("import-"); + module(qstub,qstub,"Q",Map.of("Q","val A=A;", "Q/A","int value=arg;")); + module(modules,qstub,"P",Map.of("P","val A=A; val B=B;", + "P/A","int value=arg; value=Q.A.value;", "P/B","int value=arg;")); + module(modules,modules,"Q",Map.of("Q","val A=A;", "Q/A","int value=arg; value=P.B.value;")); + CodeGen combined=new CodeGen(null,modules.toString(),new Ary<>(new String[]{modules.toString()}), + "Main","return P.A.value;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + ClassInitDependencies deps=new ClassInitDependencies(combined); + assertTrue(touches(combined,deps,"Q/A","P/B")); + assertTrue(touches(combined,deps,"P/A","Q/A")); } @Test public void testCycleReportDirection() throws Exception { @@ -346,28 +439,30 @@ public class ClassInitDependenciesTest { object(dir,dir,"B","State.count++; int value=17+arg;"); String src="int value=arg ? B.value+B.value : 0; return value+100*State.count;"; for( long seed : new long[]{1,123,987654321} ) { - CodeGen code=entry(dir,src,seed).driver(CodeGen.Phase.TypeCheck); + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main",src,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); assertNotNull(code._stop.walk(n -> n instanceof CLInitNode ? n : null)); assertEquals("0",Eval2.eval(code,0)); assertNull(code._stop.walk(n -> n instanceof CLInitNode ? n : null)); assertEquals("134",Eval2.eval(code,1)); } - emit(dir,"Main","val run={int take -> "+src.replace("arg ?","take ?")+" };"); + object(dir,dir,"Main","val run={int take -> "+src.replace("arg ?","take ?")+" };"); Path cfile=dir.resolve("check.c"); Files.writeString(cfile,""" #include <stdint.h> - __attribute__((CALL_CONV)) extern int64_t run(int64_t take) __asm__("Root.Main.run"); + __attribute__((CALL_CONV)) extern int64_t run(int64_t take); int main(void) { return run(0)!=0 || run(1)!=134 || run(1)!=134 || run(0)!=100; } """); String exe=dir.resolve(TestC.OS.startsWith("Windows") ? "check.exe" : "check").toString(); - TestC.linkExe(dir.resolve("Root/Main.o").toString(),TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", - cfile.toString(),null,exe); + TestC.linkExe(dir.resolve("Main.o").toString(),TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", + cfile.toString(),new Ary<>(new String[]{dir.resolve("B.o").toString(),dir.resolve("State.o").toString()}),exe); assertEquals("",TestC.exec(exe)); for( String cpu : new String[]{"arm","riscv"} ) - entry(dir,src,123).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main",src,123,true,TypeInteger.BOT).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); } @Test public void testParentInitializationExecution() throws Exception { @@ -376,29 +471,49 @@ public class ClassInitDependenciesTest { module(dir,dir,"P",Map.of("P","val C=C; State.count=State.count*10+1;", "P/C","State.count=State.count*10+2; int value=arg;")); for( long seed : new long[]{1,123,987654321} ) { - CodeGen code=entry(dir,"return P.C.value+State.count;",seed).driver(CodeGen.Phase.TypeCheck); + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return P.C.value+State.count;",seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); assertEquals("12",Eval2.eval(code,99)); } - emit(dir,"Main","val run={ -> P.C.value+State.count; };"); + object(dir,dir,"Main","val run={ -> P.C.value+State.count; };"); Path cfile=dir.resolve("check.c"); Files.writeString(cfile,""" #include <stdint.h> - __attribute__((CALL_CONV)) extern int64_t run(void) __asm__("Root.Main.run"); + __attribute__((CALL_CONV)) extern int64_t run(void); int main(void) { return run()!=12 || run()!=12; } """); String exe=dir.resolve(TestC.OS.startsWith("Windows") ? "check.exe" : "check").toString(); - TestC.linkExe(dir.resolve("Root/Main.o").toString(),TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", - cfile.toString(),null,exe); + TestC.linkExe(dir.resolve("Main.o").toString(),TestC.CALL_CONVENTION.equals("win64") ? "ms_abi" : "sysv_abi", + cfile.toString(),new Ary<>(new String[]{dir.resolve("P.o").toString(),dir.resolve("State.o").toString()}),exe); assertEquals("",TestC.exec(exe)); } @Test public void testNonreturningObject() throws Exception { Path dir=tempDir("nonreturning-"); object(dir,dir,"Spin","val spin_noInline={ -> while(1) {} return 7; };"); - CodeGen code=entry(dir,"Spin.spin_noInline(); return 7;",123).driver(CodeGen.Phase.TypeCheck); + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","Spin.spin_noInline(); return 7;",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); assertNull(Eval2.eval(code,0,10)); } + @Test public void testImportedPrivateInitializer() throws Exception { + Path dir=tempDir("private-"); + module(dir,dir,"Library",Map.of("Library","val read={ -> _Hidden.value; };", + "Library/_Hidden","int value=17+arg;")); + CodeGen code=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return Library.read();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + assertEquals("17",Eval2.eval(code,99)); + // Even a request stopping at Select must drop imported bodies. They + // remain available only to the ideal evaluator above, not this object. + for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) { + CodeGen selected=new CodeGen(null,dir.toString(),new Ary<>(new String[]{dir.toString()}), + "Main","return Library.read();",123,true,TypeInteger.BOT).driver(CodeGen.Phase.Select,cpu,"SystemV"); + assertNull(selected._serial); + for( CompUnit cu : selected._compunits.values() ) + if( cu._src==null ) assertNull(cu._stop); + selected.driver(CodeGen.Phase.Encoding,cpu,"SystemV"); + } + } @Test public void testOverlappingFunctionAndClassCycles() throws Exception { // Fixed function graph: Opto/inlining must not erase the overlap that diff --git a/src/test/java/com/seaofnodes/simple/ModulesTest.java b/src/test/java/com/seaofnodes/simple/ModulesTest.java deleted file mode 100644 index be54b43d..00000000 --- a/src/test/java/com/seaofnodes/simple/ModulesTest.java +++ /dev/null @@ -1,248 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.isa.eval.EvalRisc5; - -import com.seaofnodes.isa.eval.EvalArm64; - -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.codegen.RegAllocTestSupport.CheckedCodeGen; -import com.seaofnodes.simple.codegen.ParseAll; -import com.seaofnodes.simple.node.CallNode; -import com.seaofnodes.simple.node.FunNode; -import com.seaofnodes.simple.node.LoopNode; -import com.seaofnodes.simple.type.TypeInteger; -import com.seaofnodes.simple.util.Ary; -import java.io.File; -import java.io.FileWriter; -import java.io.IOException; -import java.io.ByteArrayOutputStream; -import java.io.PrintStream; -import java.nio.charset.StandardCharsets; -import java.nio.file.Files; -import java.nio.file.Path; -import org.junit.Ignore; -import org.junit.Test; - -import static org.junit.Assert.*; - -public class ModulesTest { - - @Test public void testFlagSpills() throws IOException { - com.seaofnodes.simple.codegen.FlagSpillTestSupport.run(); - } - - @Ignore - @Test - public void testJig() { - String src = "{ i32 -> i32 } close = \"C\"; val main = { u8[] a -> if (a# > 1) return close(0); return a[0]; };"; - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); - assertEquals("return (arg+3);", code.print()); - assertEquals("3",Eval2.eval(code,0)); - } - - @Test public void testConditionalClassInitX86() throws IOException { - Path build=Path.of("build/objs"); - Files.createDirectories(build); - Path dir=Files.createTempDirectory(build,"init_flags_"); - Files.createDirectories(dir.resolve("Main")); - Files.writeString(dir.resolve("Main/B.smp"),"int value=17+arg;"); - // GCM can hoist the fused B.$init compare above the test of take. - // Its flags then cross another flag definition and need a legal split. - new CheckedCodeGen(dir.toString(),dir.toString(), - "Main","val run={int take -> return take ? B.value : 0; };",123,true,TypeInteger.BOT) - .driver(CodeGen.Phase.Encoding,"x86_64_v2","win64"); - // Remove successful fixtures; preserve the object if compilation fails. - Files.delete(dir.resolve("Main/B.smp")); - Files.delete(dir.resolve("Main")); - Files.delete(dir); - } - - @Test public void testPublicInstanceMethod() { - String src = """ - struct Scan { - val visible = { u8 c -> c==255; }; - val _hidden = { u8 c -> c==1; }; - }; - struct _Private { - val hiddenClassMethod = { u8 c -> c==2; }; - }; - return new Scan.visible(44); - """; - for( long seed : new long[]{1,123,987654321} ) { - CodeGen code = new CodeGen(src,seed,true).driver(CodeGen.Phase.Parse); - FunNode visible = null; - int checked = 0; - for( FunNode fun : code._linker ) { - if( fun==null || fun._name==null ) continue; - if( fun._name.equals("visible") ) { - assertTrue(code.publicFIDX(fun.sig().fidx())); - visible = fun; - checked++; - } - if( fun._name.equals("_hidden") || fun._name.equals("hiddenClassMethod") ) { - assertFalse(code.publicFIDX(fun.sig().fidx())); - checked++; - } - } - assertEquals(3,checked); - code.driver(CodeGen.Phase.TypeCheck); - assertTrue(visible.unknownCallers()); - assertEquals(TypeInteger.U8,visible.parm(3)._type); - assertEquals("0",Eval2.eval(code,0)); - } - } - - @Test public void testNeverReturnPointerRiscV() { - new CodeGen(""" - struct _S { int x; }; - !_S !s = new _S; - if(arg) while(1) { s.x += arg; } - return s; - """).driver(CodeGen.Phase.Encoding,"riscv","SystemV"); - } - - @Test public void testInlineNeverExit() { - String[] sources={ - "val _spin={ -> while(1) {} return 1; }; _spin(); return 2;", - // Two callers require cloning, including the non-exiting arm. - "val _spin={int x -> if(x) while(1) {} return 7; }; return _spin(arg)+_spin(arg);" - }; - for( int i=0; i<sources.length; i++ ) { - for( long seed : new long[]{1,123,987654321} ) { - CodeGen code=new CodeGen(sources[i],seed,true).driver(CodeGen.Phase.TypeCheck); - assertNull("Calls should inline",code._start.walk(n -> n instanceof CallNode ? n : null)); - assertNotNull("The non-exiting path must survive",code._start.walk(n -> n instanceof LoopNode && n!=code._start ? n : null)); - if( i==1 ) assertEquals("14",Eval2.eval(code,0,10)); - assertNull(Eval2.eval(code,1,10)); - } - for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) - new CheckedCodeGen(sources[i]).driver(CodeGen.Phase.Encoding,cpu,"SystemV"); - } - } - - @Test - public void testExternData() throws IOException { - String src = """ - i32 counter="C"; - i8 small="C"; - f64 fraction="C"; - {int} bump="C"; - val test_global={ -> - val before=counter; - counter=before; - counter=++counter+1; - counter+=1; - val mid=bump(); - small++; - fraction=fraction+0.5; - return before*10000+mid*100+counter; - }; - """; - TestC.runC(src,"extern_data","",-1); - } - - @Test - public void testExternDataEncoding() { - for( String cpu : new String[]{"arm","riscv"} ) { - CodeGen code = new CheckedCodeGen("i32 counter=\"C\"; counter=counter+3; return counter;"); - // Exercise signed low-12 relocation arithmetic, past the first page. - int addr = 0x3800; - code._externDataAddresses.put("counter",addr); - code.driver(cpu,"SystemV",true,false); - byte[] image = new byte[1<<20]; - var bits = code._encoding._bits; - System.arraycopy(bits.buf(),0,image,0,bits.size()); - if( cpu.equals("arm") ) { - EvalArm64 arm = new EvalArm64(image,1<<16); - arm.st4(addr,-7); - assertEquals(0,arm.step(1000)); - assertEquals(-4,arm.regs[0]); - assertEquals(-4,arm.ld4s(addr)); - } else { - EvalRisc5 r5 = new EvalRisc5(image,1<<16); - r5.st4(addr,-7); - assertEquals(0,r5.step(1000)); - assertEquals(-4,r5.regs[10]); - assertEquals(-4,r5.ld4s(addr)); - } - } - } - - - @Test public void testPrintingConstantPool() throws Exception { - com.seaofnodes.simple.codegen.PrintRegTestSupport.checkConstantPool(); - } - - - @Test - public void testForwardConstructor() { - CodeGen code = new CodeGen("src/test/java/com/seaofnodes/simple/test_smp/forward_ctor", - "build/objs/forward_ctor_parse", - "m",null,123L,true,TypeInteger.BOT); - code.driver(CodeGen.Phase.TypeCheck); - } - - - @Test - public void testPostfixFieldUpdate() { - String src = """ - struct V { - u32 !len = 0; - i64[] !buf; - new V = { i64[] b -> buf=b; }; - val grow = { i64 n -> self; }; - val add = { i64 x -> grow(1).buf[len++] = x; self; }; - }; - return new V(new i64[1]).add(7).len; - """; - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); - assertEquals("1",Eval2.eval(code,0)); - } - - @Test - public void testStringEscapes() { - String src = "u8[~] s=\"A\\n\\t\\r\\\\\\\"B\"; " + - "return s#==7 && s[0]=='A' && s[1]==10 && s[2]==9 && s[3]==13 && " + - "s[4]==92 && s[5]==34 && s[6]=='B';"; - CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); - assertEquals("1",Eval2.eval(code,0)); - } - - @Test - public void testCharacterEscapes() { - CodeGen code = new CodeGen("return '\\n'==10 && '\\t'==9 && '\\r'==13;") - .driver(CodeGen.Phase.TypeCheck); - assertEquals("1",Eval2.eval(code,0)); - } - - @Test - public void testFuzzerUnresolvedNumericLoop() { - CodeGen code = new CodeGen(""" - arg=0; - while(arg+0) - while(-arg) - arg=0; - """).driver(CodeGen.Phase.TypeCheck); - assertEquals("return 0;",code.print()); - } - - @Test - public void testFuzzerBadLCA() { - new CodeGen(""" - int v0=arg; - if(v0&&--v0?0:arg) {} - """).driver(CodeGen.Phase.LocalSched); - } - - - // Recursive search (TODO: gzip, archives) and delete all .o files - - - @Test - public void testConstantClassInitialization() throws IOException { - TestC.runSF("val x = 42; return 0;","constantClassInt","",0); - TestC.runSF("val f = { -> 7; }; return 0;","constantClassFunction","",0); - } - - -} diff --git a/src/test/java/com/seaofnodes/simple/NativeExecutionTest.java b/src/test/java/com/seaofnodes/simple/NativeExecutionTest.java index fa914d28..f3f65183 100644 --- a/src/test/java/com/seaofnodes/simple/NativeExecutionTest.java +++ b/src/test/java/com/seaofnodes/simple/NativeExecutionTest.java @@ -48,6 +48,7 @@ public class NativeExecutionTest { @Test public void testHelloWorldArtifacts() throws IOException { new Chapter22Test().testHelloWorld(); + new Chapter25Test().testHelloWorld(); // Model a parallel run paused between Chapter 22's link and execution. // Chapter 25 must not replace the executable Chapter 22 is about to run. String exe = "build/objs/helloWorld"+(TestC.OS.startsWith("Windows") ? ".exe" : ""); diff --git a/src/test/java/com/seaofnodes/simple/PhaseTest.java b/src/test/java/com/seaofnodes/simple/PhaseTest.java index 5ff7fcd6..7252378a 100644 --- a/src/test/java/com/seaofnodes/simple/PhaseTest.java +++ b/src/test/java/com/seaofnodes/simple/PhaseTest.java @@ -22,22 +22,43 @@ public class PhaseTest { code.driver(Phase.TypeCheck); code.driver(Phase.TypeCheck); // A repeated request does not rerun anything. code.driver(Phase.LocalSched); - assertEquals("Parse Iter Opto IterPostOpto FinalizeIR TypeCheck Lower LoopTree Schedule LocalSched", + assertEquals("Parse Iter Opto IterPostOpto FinalizeIR TypeCheck Lower LoopTree Unlink Schedule LocalSched", String.join(" ",phases)); + assertNull(code._serial); assertNull(code._mach); assertEquals("45",Eval2.eval(code,10)); } - @Test public void testEncodingAndResume() { + @Test public void testEncodingWithoutSerialization() { for( String cpu : new String[]{"x86_64_v2","arm","riscv"} ) { CodeGen code = new CodeGen(SRC).driver(Phase.TypeCheck); - code.driver(Phase.LoopTree,cpu,"SystemV"); + code.driver(Phase.Unlink,cpu,"SystemV"); code.driver(Phase.Select,cpu,"SystemV"); code.driver(Phase.Encoding,cpu,"SystemV"); + assertNull(code._serial); byte[] staged = code._encoding._bits.toByteArray(); CodeGen direct = new CodeGen(SRC).driver(Phase.Encoding,cpu,"SystemV"); assertArrayEquals(staged,direct._encoding._bits.toByteArray()); } } + @Test public void testExplicitSerializationAndMemoryExport() { + CodeGen code = new CodeGen(SRC).driver(Phase.Serialize); + assertNotNull(code._serial); + assertEquals(Phase.Serialize,code._phase); + code.driver(Phase.Encoding,"riscv","SystemV"); + assertNotNull(code._serial); + + CodeGen memory = new CodeGen(SRC).driver("riscv","SystemV",true,false); + assertNull(memory._serial); + assertEquals(Phase.Export,memory._phase); + + CodeGen late = new CodeGen(SRC).driver(Phase.Encoding,"riscv","SystemV"); + try { + late.exportELF(false,false); + fail("Cannot recover ideal IR after lowering and instruction selection"); + } catch( IllegalStateException expected ) { + assertTrue(expected.getMessage().contains("Serialize before Lower")); + } + } } diff --git a/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java new file mode 100644 index 00000000..4576bc94 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/SeparateCompilationTest.java @@ -0,0 +1,90 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.util.Ary; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +public class SeparateCompilationTest { + @Test public void testImportedNativeExposure() throws Exception { + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"callbacks-"); + String src=""" + val run={int n -> + val power={int base,int exponent -> + if(exponent<=0) return 1; + return base*power(base,exponent-1); + }; + { {int int -> int} -> int } retain="C"; + retain(power); + return power(2,n); + }; + """; + new CodeGen(null,lib.toString(),null,"Callbacks",src,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + CodeGen code=new CodeGen(null,null,new Ary<>(new String[]{lib.toString()}), + "Client","return Callbacks.run(arg);",123,true,TypeInteger.BOT) + .driver(CodeGen.Phase.Opto); + assertNull(code._compunits.get("Callbacks")._src); + ParmNode base=code._start.walk(n -> n instanceof ParmNode p && p._label.equals("base") ? p : null); + assertNotNull(base); + assertSame("Native code may call the saved callback with any base",TypeInteger.BOT,base._type); + code.driver(CodeGen.Phase.TypeCheck); + } + + // The client root contains no library source. The saved constructor must + // keep local loop values, and retained calls must use the library's storage. + @Test public void testImportedConstructorAndState() throws Exception { + Path fixtures=Path.of("src/test/smp/separate"); + Path build=Path.of("build/objs/separate"); + Files.createDirectories(build); + Path lib=Files.createTempDirectory(build,"library-"); + Path client=Files.createTempDirectory(build,"client-"); + new CodeGen(fixtures.resolve("library").toString(),lib.toString(),null, + "Counters",null,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + assertTrue(Files.isRegularFile(lib.resolve("Counters.o"))); + assertFalse(Files.exists(fixtures.resolve("client/Counters.smp"))); + var paths=new Ary<>(new String[]{lib.toString()}); + for( long seed : new long[]{2,13,123} ) { + CodeGen code=new CodeGen(fixtures.resolve("client").toString(),client.toString(),paths, + "Main",null,seed,true,TypeInteger.BOT).driver(CodeGen.Phase.TypeCheck); + CompUnit imported=code._compunits.get("Counters"); + assertNotNull(imported); + assertNull("Library source must not be parsed",imported._src); + assertEquals(lib.resolve("Counters.o").toRealPath(),imported._obj.toPath().toRealPath()); + assertEquals("0",Eval2.eval(code,0)); + assertEquals("107",Eval2.eval(code,3)); + assertEquals("131",Eval2.eval(code,5)); + } + new CodeGen(fixtures.resolve("client").toString(),client.toString(),paths, + "Main",null,123,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + Path driver=client.resolve("driver.c"); + Files.writeString(driver,""" + #include <stdio.h> + __attribute__((CALL_CONV)) extern long long run(long long); + int main(void) { + long long args[]={0,3,5,0,3}, expected[]={0,107,231,0,307}; + for(int i=0;i<5;i++) { + long long actual=run(args[i]); + if(actual!=expected[i]) { + printf("call %d: got %lld, expected %lld\\n",i,actual,expected[i]); + return 1; + } + } + return 0; + } + """); + String exe=client.resolve(TestC.OS.startsWith("Windows")?"test.exe":"test").toString(); + TestC.linkExe(client.resolve("Main.o").toString(), + TestC.CALL_CONVENTION.equals("win64")?"ms_abi":"sysv_abi",driver.toString(), + new Ary<>(new String[]{lib.resolve("Counters.o").toString()}),exe); + assertEquals("",TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Simple.java b/src/test/java/com/seaofnodes/simple/Simple.java index 437fcd81..7cfdf57d 100644 --- a/src/test/java/com/seaofnodes/simple/Simple.java +++ b/src/test/java/com/seaofnodes/simple/Simple.java @@ -31,6 +31,7 @@ Options: '/', then all result files use relative paths to 'output', using a input file root-relative path. If --root is missing, the one result file is named 'output' + -L path - add an external Simple object search path --eval - (slowly) evaluate the compiled code in emulator --run - run the compiled code natively; this is the default --main - export the top-level initializer as C `main` @@ -104,6 +105,7 @@ Options: String cpu = null; String abi = null; String out = null; + ArrayList<String> libPaths = new ArrayList<>(); // Parse command line int i; for( i = 0; i < args.length; i++ ) { @@ -144,6 +146,9 @@ Options: case "--root": if( root!=null || i+1>=args.length ) bad_usage(); root=args[++i]; break; + case "-L": if (i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); + libPaths.add(args[++i]); + break; case "--cpu": if (cpu != null || i + 1 >= args.length || args[i + 1].charAt(0) == '-') bad_usage(); cpu = args[++i]; break; @@ -218,11 +223,16 @@ Options: if( cpu == null ) cpu = TestC.CPU_PORT; if( abi == null ) abi = TestC.CALL_CONVENTION; - // Read input file + String simpleHome = System.getenv("SIMPLE_HOME"); + if( simpleHome != null && !simpleHome.isEmpty() ) + libPaths.add(Path.of(simpleHome,cpu+"_"+abi).toString()); + + // Keep file-backed units so discovery sees parents and siblings. src = input_filename.isEmpty() ? getInput() : null; // Compilation pipeline - CodeGen code = new CodeGen(modPath.toString(), outPath.toString(), srcName, src, 456, true, TypeInteger.BOT ); + Ary<String> externPaths = libPaths.isEmpty() ? null : new Ary<>(libPaths.toArray(new String[0])); + CodeGen code = new CodeGen(modPath.toString(), outPath.toString(), externPaths, srcName, src, 456, true, TypeInteger.BOT ); code.driver(do_eval && !do_codegen ? Phase.TypeCheck : Phase.LastPhase, cpu,abi, false, emit_main || do_run || do_eval, dump); @@ -247,7 +257,7 @@ Options: if ( !TestC.CPU_PORT.equals( cpu ) || !TestC.CALL_CONVENTION.equals( abi ) ) throw bad("cannot run code on not native target"); String exe = TestC.OS.startsWith("Windows") ? outBase+".exe" : outBase; - String result = TestC.gcc(outBase+".o", null, null, "", TestC.linkObjs(null), exe); + String result = TestC.gcc(outBase+".o", null, null, "", TestC.linkObjs(externPaths), exe); System.out.print(result); } } diff --git a/src/test/java/com/seaofnodes/simple/SpillStats.java b/src/test/java/com/seaofnodes/simple/SpillStats.java index 944f7ef5..d43f1a36 100644 --- a/src/test/java/com/seaofnodes/simple/SpillStats.java +++ b/src/test/java/com/seaofnodes/simple/SpillStats.java @@ -20,7 +20,7 @@ public class SpillStats extends RunListener { @Override public void testFinished(Description test) { _test = null; } public static void record25(CodeGen code) { - if( ACTIVE==null || ACTIVE._test==null || ACTIVE._test.getTestClass()!=ModulesTest.class ) return; + if( ACTIVE==null || ACTIVE._test==null || ACTIVE._test.getTestClass()!=Chapter25Test.class ) return; ACTIVE.record(code,"Chapter25",ACTIVE._test.getMethodName(),code._mach.getClass().getSimpleName(),code._callingConv); } @@ -54,7 +54,7 @@ public class SpillStats extends RunListener { String[] row = line.split("\t"); try { String src = Files.readString(dir.resolve(row[5])); - CodeGen code = new CheckedCodeGen(null,null,null,src,123L,true,TypeInteger.BOT) + CodeGen code = new CheckedCodeGen(null,null,null,null,src,123L,true,TypeInteger.BOT) .driver(CodeGen.Phase.RegAlloc,row[2],row[3]); ACTIVE.record(code,row[0],row[1],row[2],row[3]); } catch( Throwable error ) { @@ -65,7 +65,7 @@ public class SpillStats extends RunListener { } // Include the library's allocation even when make's sys.o is up to date. try { - CodeGen code = new CheckedCodeGen("src/main/smp","build/spill-sys","sys", + CodeGen code = new CheckedCodeGen("src/main/smp","build/spill-sys",null,"sys", Files.readString(Path.of("src/main/smp/sys.smp")),456L,true,TypeInteger.BOT) .driver(CodeGen.Phase.Encoding,TestC.CPU_PORT,TestC.CALL_CONVENTION); ACTIVE.record(code,"Chapter25","sys",TestC.CPU_PORT,TestC.CALL_CONVENTION); @@ -75,7 +75,7 @@ public class SpillStats extends RunListener { } JUnitCore junit = new JUnitCore(); junit.addListener(ACTIVE); - Result result = junit.run(ModulesTest.class); + Result result = junit.run(Chapter25Test.class); for( Failure failure : result.getFailures() ) System.err.println(failure.getTrace()); failures += result.getFailureCount(); if( failures!=0 ) System.out.println("FAILED: totals are not a complete comparison."); @@ -89,4 +89,4 @@ public class SpillStats extends RunListener { ACTIVE = null; if( failures!=0 ) System.exit(1); } -} +}
\ No newline at end of file diff --git a/src/test/java/com/seaofnodes/simple/StaticDataTest.java b/src/test/java/com/seaofnodes/simple/StaticDataTest.java index b8f5f1d1..88d0246d 100644 --- a/src/test/java/com/seaofnodes/simple/StaticDataTest.java +++ b/src/test/java/com/seaofnodes/simple/StaticDataTest.java @@ -69,7 +69,7 @@ public class StaticDataTest { @Test public void testNativeImage() throws Exception { Path dir=Path.of("build/objs/static-data"); Files.createDirectories(dir); - CodeGen code=new CodeGen(null,dir.toString(),"Test",SRC,123L,true, + CodeGen code=new CodeGen(null,dir.toString(),null,"Test",SRC,123L,true, TypeInteger.BOT) .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); TypeStruct ts=(TypeStruct)root(code).type; @@ -102,7 +102,7 @@ public class StaticDataTest { for( int i=0; i<2; i++ ) { String name=i==0 ? "A" : "B"; String src="{ i32 -> i32 } abs = \"C\"; val get"+name+"={ -> abs; }; return 0;"; - CodeGen code=new CodeGen(null,dir.toString(),name,src,123L,true,TypeInteger.BOT) + CodeGen code=new CodeGen(null,dir.toString(),null,name,src,123L,true,TypeInteger.BOT) .driver(CodeGen.Phase.TypeCheck); assertNull("The native address is initialized in the static image", code._stop.walk(n -> n instanceof StoreNode st && st._name.equals("abs") ? n : null)); @@ -140,18 +140,19 @@ public class StaticDataTest { } } - // Two source files must reference the same mutable class object. + // Two separately compiled users must reference the same mutable class object. @Test public void testSharedClass() throws Exception { Path dir=Path.of("build/objs/static-data-shared"); Files.createDirectories(dir); - Files.createDirectories(dir.resolve("Main")); + Path lib=dir.resolve("lib"); + Files.createDirectories(lib); + var paths=new Ary<>(new String[]{lib.toString()}); String[] names={"Globals","A","B"}; String[] sources={"int count=0;", "val a={ -> Globals; };", "val b={ -> Globals; };"}; for( int i=0; i<names.length; i++ ) - Files.writeString(dir.resolve("Main/"+names[i]+".smp"),sources[i]); - new CodeGen(dir.toString(),dir.toString(),"Main","val a={ -> A.a(); }; val b={ -> B.b(); };",123L,true,TypeInteger.BOT) - .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); + new CodeGen(null,(i==0?lib:dir).toString(),i==0?null:paths,names[i],sources[i],123L,true,TypeInteger.BOT) + .driver(TestC.CPU_PORT,TestC.CALL_CONVENTION,false,false); Path driver=dir.resolve("driver.c"); Files.writeString(driver,""" #include <stdint.h> @@ -164,9 +165,9 @@ public class StaticDataTest { } """); String exe=dir.resolve(TestC.OS.startsWith("Windows")?"test.exe":"test").toString(); - TestC.linkExe(dir.resolve("Main.o").toString(), + TestC.linkExe(lib.resolve("Globals.o").toString(), TestC.CALL_CONVENTION.equals("win64")?"ms_abi":"sysv_abi", - driver.toString(),null,exe); + driver.toString(),new Ary<>(new String[]{dir+"/A.o",dir+"/B.o"}),exe); assertEquals("",TestC.exec(TestC.TEST_TIMEOUT_SECONDS,exe)); } } diff --git a/src/test/java/com/seaofnodes/simple/TestC.java b/src/test/java/com/seaofnodes/simple/TestC.java index 164168f6..b08be824 100644 --- a/src/test/java/com/seaofnodes/simple/TestC.java +++ b/src/test/java/com/seaofnodes/simple/TestC.java @@ -120,7 +120,7 @@ public abstract class TestC { String obj = pathBase+".o"; String exe = pathBase+(OS.startsWith("Windows") ? ".exe" : ""); // Compile simple, emit ELF - CodeGen code = new CheckedCodeGen(null,"build/objs",base,src,126L,true,TypeInteger.BOT); + CodeGen code = new CheckedCodeGen(null,"build/objs",externPaths,base,src,126L,true,TypeInteger.BOT); code.driver( CPU_PORT, simple_conv, false, cfile==null ); linkExe(obj, c_conv, cfile, linkObjs(externPaths), exe); diff --git a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index 4398827e..292f1ae7 100644 --- a/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -169,9 +169,9 @@ public class RegAllocTestSupport { // Check the scheduled graph before encoding adds untyped branches or rewrites tail calls. public static class CheckedCodeGen extends CodeGen { public CheckedCodeGen(String src) { super(src); } - public CheckedCodeGen(String modDir, String buildDir, + public CheckedCodeGen(String modDir, String buildDir, com.seaofnodes.simple.util.Ary<String> externPaths, String srcName, String src, long seed, boolean reset, TypeInteger arg) { - super(modDir,buildDir,srcName,src,seed,reset,arg); + super(modDir,buildDir,externPaths,srcName,src,seed,reset,arg); } @Override public CodeGen regAlloc() { super.regAlloc(); diff --git a/src/test/smp/examples/A_helloWorld.smp b/src/test/smp/examples/A_helloWorld.smp new file mode 100644 index 00000000..4ed6abdf --- /dev/null +++ b/src/test/smp/examples/A_helloWorld.smp @@ -0,0 +1,2 @@ +sys.io.p("Hello, World!\n"); +return 0; diff --git a/src/test/smp/examples/BubbleSort.smp b/src/test/smp/examples/BubbleSort.smp new file mode 100644 index 00000000..ca6906b5 --- /dev/null +++ b/src/test/smp/examples/BubbleSort.smp @@ -0,0 +1,36 @@ + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + sys.aryi64?! more = nums; + while( more ) { + more = null; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) + more = nums.swap(i,i+1); + } +}; + +// Read one process argument of the form "[ 4, 3, 2, 1]" and print it sorted. +// args[0] is the executable name, as with native C argc/argv. +val main = { u8[~][] args -> + val usage = { -> + sys.io.p("Usage: please provide a list of at least two integers to sort in the format \"[1, 2, 3, 4, 5]\"\n"); + return 0; + }; + if( args# != 2 ) return usage(); + + var nums = sys.aryi64.parseAryI64(args[1]); + if( !nums ) return usage(); + if( nums.len < 2 ) return usage(); + + // Bubble sort array of integers + sort(nums); + + // Print the same bracketed array-list format accepted as input. + nums.str().add('\n').write(1); + return 0; +}; diff --git a/src/test/smp/examples/Capitalize.smp b/src/test/smp/examples/Capitalize.smp new file mode 100644 index 00000000..8e31c18f --- /dev/null +++ b/src/test/smp/examples/Capitalize.smp @@ -0,0 +1,22 @@ + +// An implementation of +// https://sampleprograms.io/projects/capitalize/ + +val main = { u8[~][] args -> + if( args# > 2 ) { + sys.io.p("Use quotes around multiple strings.\n"); + return 0; + } + if( args# != 2 || args[1]# == 0 ) { + sys.io.p("Usage: please provide a string\n"); + return 0; + } + + u8[~] input = args[1]; + var output = new u8[input# + 1]; + sys.ary.copy(output,0,input,0,input#); + output[0] = sys.char.toupper(input[0]); + output[input#] = '\n'; + sys.io.p(output); + return 0; +}; diff --git a/src/test/smp/examples/Dijkstra.smp b/src/test/smp/examples/Dijkstra.smp new file mode 100644 index 00000000..fd595eb5 --- /dev/null +++ b/src/test/smp/examples/Dijkstra.smp @@ -0,0 +1,72 @@ + +// An implementation of +// https://sampleprograms.io/projects/dijkstra/ + +val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst -> + i64 infinity = (1 << 63)-1; + var dist = new i64[nodes]; + var visited = new sys.adt.bitset(); + // All nodes are infinitely far from each other + for( int i=0; i<nodes; i++ ) dist[i] = infinity; + // Starting point is zero far from starting point + dist[src] = 0; + + i64 result = -1; + int count = 0; + while( count < nodes && result < 0 ) { + int nearest = -1; + i64 best = infinity; + for( int node=0; node<nodes; node++ ) + if( !visited.get(node) && dist[node] < best ) { + nearest = node; + best = dist[node]; + } + if( nearest < 0 ) count = nodes; + else { + if( nearest == dst ) return best; + visited.set(nearest); + for( int node=0; node<nodes; node++ ) { + i64 weight = matrix.get(nearest*nodes + node); + if( weight > 0 && !visited.get(node) && best+weight < dist[node] ) + dist[node] = best+weight; + } + } + count++; + } + return result; +}; + +val usage = { -> + sys.io.p("Usage: please provide three inputs: a serialized matrix, a source node and a destination node\n"); + return 0; +}; + +val main = { u8[~][] args -> + // Exactly 3 args + if( args# != 4 ) return usage(); + // First is a serialized square matrix of positive numbers + var matrix = sys.aryi64.parseAryI64(args[1]); + if( !matrix ) return usage(); + if( !matrix.len ) return usage(); + // All numbers are positive + for( int i=0; i<matrix.len; i++ ) + if( matrix.get(i) < 0 ) return usage(); + // Matrix is square + int nodes = 0; + while( nodes*nodes < matrix.len ) nodes++; + if( nodes*nodes != matrix.len ) + return usage(); // Not a square matrix + + // src,dst are values within the matrix + i64 src = sys.aryu8.atoi(args[2]); + i64 dst = sys.aryu8.atoi(args[3]); + if( src < 0 || src >= nodes || dst < 0 || dst >= nodes ) + return usage(); // Source and destination land within the graph + + i64 cost = shortestPath(matrix,nodes,src,dst); + if( cost >= 0 ) { + new sys.aryu8().num(cost).add('\n').write(1); + return 0; + } + return usage(); +}; diff --git a/src/test/smp/examples/FileIO.smp b/src/test/smp/examples/FileIO.smp new file mode 100644 index 00000000..e48d435b --- /dev/null +++ b/src/test/smp/examples/FileIO.smp @@ -0,0 +1,50 @@ + +// An implementation of +// https://sampleprograms.io/projects/file-input-output/ + +val FILE = "output.txt"; + +val main = { u8[~][] args -> + var str = new sys.aryu8(); + str.addAry("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.\n"); + str.addAry("Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.\n"); + str.addAry("Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur.\n"); + str.addAry("Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.\n"); + + // Create + i32 fd = sys.io.create(FILE); + if( fd == -1 ) return _error(); + // Write + int wrote = sys.io.writeOff(fd,str.buf,0,str.len); + if( wrote == -1 ) return _error(); + if( wrote != str.len ) return _error2(-2); + // Close + if( sys.io.close(fd) != 0 ) return _error(); + + // Open + i32 fd2 = sys.io.open(FILE); + if( fd2 == -1 ) return _error(); + // Read + var got = sys.io.read(fd2); + if( got# != str.len ) return _error2(-3); + // Close + if( sys.io.close(fd2) != 0 ) return _error(); + + // Check contents are equal + if( sys.ary.cmp(got,0,str.buf,0,str.len) ) + return _error2(-4); + + // Remove + if( sys.io.remove(FILE) != 0 ) return _error(); + + sys.io.p("File I/O succeeded\n"); + return 0; +}; + +val _error2 = { i32 errno -> + sys.io.remove(FILE); + new sys.aryu8().addAry("Failed with error code ").num(errno).add('\n').write(sys.libc.STDERR); + sys.libc._exit(errno); +}; + +val _error = { -> _error2(sys.libc.errno()); }; diff --git a/src/test/smp/separate/client/Main.smp b/src/test/smp/separate/client/Main.smp new file mode 100644 index 00000000..077f6575 --- /dev/null +++ b/src/test/smp/separate/client/Main.smp @@ -0,0 +1,6 @@ +val run={int n -> + if(!n) return 0; + val c=new Counters.Counter(n); + return c.get()+100*Counters.next_noInline(); +}; +return run(arg); diff --git a/src/test/smp/separate/library/Counters.smp b/src/test/smp/separate/library/Counters.smp new file mode 100644 index 00000000..a3e36562 --- /dev/null +++ b/src/test/smp/separate/library/Counters.smp @@ -0,0 +1,12 @@ +// A library can keep shared state and publish instance constructors. +int calls=0; +val next_noInline={ -> calls++; return calls; }; + +struct Counter { + val value=1; + new Counter={int n -> + value=0; + for(int i=0; i<n; i++) value=value*2+1; + }; + val get={ -> value; }; +}; |
