From b5ebb2032aa04cf4506d533127d373d4cf5a25c6 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 13 Jun 2025 15:42:08 -0700 Subject: Chapter 24: Chaining Relationals and Sparse Conditional Constant Propagation MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Hadházy Tamás Co-authored-by: Claude Opus 5 --- docs/chapter24/24-grammar.ja.md | 168 ++++++++ docs/chapter24/24-grammar.md | 168 ++++++++ docs/chapter24/Makefile | 12 + docs/chapter24/README.ja.md | 262 ++++++++++++ docs/chapter24/README.md | 325 +++++++++++++++ docs/chapter24/examples/A_helloWorld.smp | 3 + docs/chapter24/examples/BubbleSort.smp | 37 ++ docs/chapter24/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter24/ifg_trim.pdf | Bin 0 -> 155190 bytes docs/chapter24/lattice.gv | 203 +++++++++ docs/chapter24/lattice.svg | 691 +++++++++++++++++++++++++++++++ docs/chapter24/lattice2.gv | 85 ++++ docs/chapter24/lattice2.svg | 260 ++++++++++++ docs/chapter24/pardoe.docx | Bin 0 -> 22583 bytes docs/chapter24/webtcp.min.js | 65 +++ 15 files changed, 2279 insertions(+) create mode 100644 docs/chapter24/24-grammar.ja.md create mode 100644 docs/chapter24/24-grammar.md create mode 100644 docs/chapter24/Makefile create mode 100644 docs/chapter24/README.ja.md create mode 100644 docs/chapter24/README.md create mode 100644 docs/chapter24/examples/A_helloWorld.smp create mode 100644 docs/chapter24/examples/BubbleSort.smp create mode 100644 docs/chapter24/font-awesome-4.7.0.zip create mode 100644 docs/chapter24/ifg_trim.pdf create mode 100644 docs/chapter24/lattice.gv create mode 100644 docs/chapter24/lattice.svg create mode 100644 docs/chapter24/lattice2.gv create mode 100644 docs/chapter24/lattice2.svg create mode 100644 docs/chapter24/pardoe.docx create mode 100644 docs/chapter24/webtcp.min.js (limited to 'docs') diff --git a/docs/chapter24/24-grammar.ja.md b/docs/chapter24/24-grammar.ja.md new file mode 100644 index 00000000..fd3fa232 --- /dev/null +++ b/docs/chapter24/24-grammar.ja.md @@ -0,0 +1,168 @@ +# 第24章の文法 + +[English](24-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. +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 : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +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. 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)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +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/chapter24/24-grammar.md b/docs/chapter24/24-grammar.md new file mode 100644 index 00000000..22867355 --- /dev/null +++ b/docs/chapter24/24-grammar.md @@ -0,0 +1,168 @@ +# Grammar for Chapter 24 + +English | [日本語](24-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. +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 : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +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. 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)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +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/chapter24/Makefile b/docs/chapter24/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter24/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter24/README.ja.md b/docs/chapter24/README.ja.md new file mode 100644 index 00000000..bf412061 --- /dev/null +++ b/docs/chapter24/README.ja.md @@ -0,0 +1,262 @@ +# 第24章: 関係演算の連鎖と疎な条件付き定数伝播 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第23章](../chapter23/README.ja.md) | +[次の章: 第25章](../chapter25/README.ja.md) + +この章では、たとえば `(60 <= score < 90)` のような条件の *連鎖* を許し、中央の `score` を繰り返さずに済むようにします。 + +コンパイラの主な変更は、手続き間の疎な条件付き定数伝播（SCCP）です。呼び出しグラフの辺も発見する、楽観的な型の求解です。メモリは第11章の遅延分割に従います。BulkMemPhi はメモリ全体を表し、MemPhi は正確なエイリアスをマージし、割り当てはインスタンスフィールドの部分メモリを消費・生成します。SCCP 中、メモリ Phi は到達不能入力を無視し、割り当て結果は制御が到達するまで高いままです。第25章には、不完全な型のための大きな SSA 再設計、非公開のコンストラクタメモリ、分割コンパイルを残します。[バックポートのレビュー待ち一覧](../chapter-backports.md) を参照してください。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter24) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter23...linear-chapter24) することもできます。 + +この章の[完全な言語文法](24-grammar.ja.md)はこちらです。 + +## 関係比較の連鎖 + +関係比較の連鎖により、同じ変数を繰り返さず、連続する比較をすっきりと読みやすく書けます。 + +```java +if (min <= x && x < max) +``` + +は、次になります。 + +```java +if (min <= x < max) +``` + +この構文は場所を節約し、数学で範囲検査を書く方法に似た、直感的な条件にします。たとえば: + +```java +int score = 75; +if (60 <= score < 90) { + sys.io.p("Pass"); +} +``` + +これは `score` を繰り返さず、60以上90未満かを検査します。 + +`<=` と `>=` の両方を使うなど、逆向きの比較を混ぜる式は、Simple の方向規則では許されません。 + +```java +if (a <= b >= c) +``` + +### 演算子の方向規則 + +重ねた比較は、すべての比較演算子が同じ方向を「向く」場合 *だけ* 有効です。 + +- `<` と `<` +- `<` と `<=` +- `>` と `>` +- `>` と `>=` + +等値演算子（`==` と `!=`）は通常どおり、より低い優先順位を持ちます。関係演算の連鎖をつなぐ要素ではありません。 + +1つの連鎖で方向を混ぜることはできません。 + +```java +if (a <= b >= c) // Invalid +``` + +真偽値を使えば、比較を数値の文脈に強制できます。次は有効ですが、珍しい書き方です。 + +```java +return (0 < arg) > 1; +``` + +`(0 < arg)` の結果に応じて、次のいずれかになります。 + +```java +return 0 > 1; +``` + +または + +```java +return 1 > 1; +``` + +等値演算子もこの形式で有効ですが、比較より優先順位が低いため、 + +```java +a < b == c +``` + +は次のように解析されます。 + +```java +(a < b) == c +``` + +これは意図した連鎖比較とは違うかもしれません。より明示的な代替は次です。 + +```java +a < b && b == c +``` + +比較は任意の長さで連鎖でき、同じ方向を向く限り、異なる比較演算子を自由に混ぜられます。中間の各オペランドは1回だけ評価します。後のオペランドは、前の比較が成功した場合だけ評価するため、連鎖内の呼び出しや更新は短絡評価されます。 + +例: + +``` +return 0 < arg < arg+1 < 4; +``` + +### 注意が必要な境界例 + +```java +return 0 != arg != 1; +``` + +これは連鎖した不等比較ではなく、標準の優先順位規則により次のように解析します。 + +```java +return ((0 != arg) != 1); +``` + +```java +return a == b == c; +``` + +同様に、これは次のように解析します。 + +```java +return ((a == b) == c); +``` + +## 疎な条件付き定数伝播 + +[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation) は、これまで行ってきたピープホール最適化／定数畳み込みの、上から下へ進む版です。アルゴリズムの規則は文献でよく知られ、大学で一般に教えられています。[スライドの例](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf) があります。 + +- すでに束を持っています。 +- すでに SSA 形式を持っています。したがってアルゴリズムは *疎* です。 +- ノードから型への対応（`Node._type`）を持っています。 +- すでに伝達関数（`Node.compute`）を持っています。 + +すべての `_type` を、⊥ ではなく ⊤ に初期化し、すべてのノードをワークリストに置きます。そこからノードを取り、伝達関数 `node.compute()` を実行します。結果が `node._type` と変われば更新し、その出力側の隣接ノードをワークリストへ入れます。アサーションとデバッグ補助をすべて取り除いた簡略版は次のとおりです。 + +```java +while( (n = code._iter._work.pop()) != null ) { + Type nval = n.compute(); + if( n._type != nval ) { + assert n._type.isa(nval); // Types start high and always fall + n._type = nval; // Update type in Node + code._iter.addAll(n._outputs);// Neighbors might change, need to inspect + } +} +``` + +このアルゴリズムは必ず停止し、一般にはかなり速く、束と伝達関数の制限内での「最良の答え」である *不動点* に必ず到達します。得られる型はピープホール規則で見つけたものより単調に改善されます。その後、型が改善されたノードでピープホール規則を実行し、無関係なピープホール最適化が適用できるかを調べられます。たとえば新しく発見した定数が、計算を ConstantNode に置き換えます。 + +以下は SSA の擬似コードです。`phi` はマージを意味し、Simple の構文ではありません。 + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT) + x2 = 2 - x1; // x2 = BOT = 2 - BOT +} +return x1 +``` + +SCCP がなければ、この小さなプログラムは `x` の計算を畳み込めません。見れば `x` は常に `1` とわかりますが、下から上へ進む悲観的手法は、x1 が BOT なので x2 が BOT、したがって x1 が BOT と判断します。行き詰まりを解くには楽観的手法が必要です。x1 が `1` と *仮定* すれば、x2 も `1` と発見できます。値の畳み込みは、ループ停止を証明したり、その条件と副作用を除去可能にしたりするものではありません。 + +アルゴリズムは左から右へ進み、変化がなくなったら停止します。 + +| 変数 | 初期 | x0=1 | x1=phi(1,T) | x2=2-x1 | x1=phi(1,1) | +|---|----|----|-----------|-------|-----------| +| x0 | T | 1 | 1 | 1 | 1 | +| x1 | T | T | 1 | 1 | 1 | +| x2 | T | T | T | 1 | 1 | + +### 条件付き + +制御フローがデータフローと同じグラフ内にあるため（これが Sea-of-Nodes の大きな要点です）、特別なことをする必要はなく、アルゴリズムはすでに *条件付き* です。ここでも例が役に立ちます。 + +再び SSA の擬似コードを使います。 + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT) + if( x1 == 1 ) // Since x1 is BOT, both true and false arms are taken + x2 = 2 - x1; // x2 = BOT = 2 - BOT + else x3 = 99; // x3 = 99 + x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99) +} +return x1 +``` + +再び左から右へ進みますが、今度はすべての経路が到達可能とは限りません。`if` の結果は Control 値の対で、経路が生きていれば `C`、そうでなければ `X` で示します。これは `x4 = phi(x2,x3)` の計算で使います。`PhiNode` は `if` の対応する制御入力 *も* 確認し、生きた経路だけをマージします。 + +| 変数 | 初期 | x0=1 | x1=phi(1,T) | 1 == 1? | x2=2-x1 | x3=99 | x4=phi(C/1,X/99) | x1=phi(1,1) | +|---|-----|----|-----------|---------|---------|---------|----------------|-----------| +| x0 | T | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +| x1 | T | T | 1 | 1 | 1 | 1 | 1 | 1 | +| if | T | T | T | [C,X] | [C,X] | [C,X] | [C,X] | [C,X] | +| x2 | T | T | T | T | 1 | 1 | 1 | 1 | +| x3 | T | T | T | T | T | 99 | 99 | 99 | +| x4 | T | T | T | T | T | T | 1 | 1 | + +この種の条件付き定数伝播は、条件が真か偽と証明できると、最適化後のプログラムから検査と分岐を除去するので、非常に役立ちます。よくあるのが null 検査です。同じプログラムで、整数の代わりに null ポインタを使います。 + +```java +List head = notNullList(); +while( rand ) { + if( head ) head = new List(head,payload); + else { head = null; default_action(); } +} +``` + +`head` は非 null で始まるため、決して null にならず、`default_action` も起きません。ループは簡略化できます。 + +```java +List head = notNullList(); +while( rand ) { + head = new List(head,payload); +} +``` + +### 手続き間 + +**Simple** では、ここでもほぼ何もせず、SCCP を手続き間で実行します。`CallNode` は `FunNode` を呼び、`ReturnNode` は `CallEndNode` に戻り、まったく通常の方法で型情報を渡します。ただし問題が1つあります。`Call` と `Fun`、および `Return` と `CallEnd` の間に辺がありません。そのような辺が [呼び出しグラフ](https://en.wikipedia.org/wiki/Call_graph) を構成します。 + +通常の SCCP を拡張し、`Call` の関数ポインタ入力が変わり、新しい関数対象を得る時点を監視します。対象の数は有限なので、前の章で説明した *関数インデックス* で正確に表します。分割コンパイルでは、このコンパイル単位の外で呼ばれる無限の未知関数に対して、特別なインデックスを追加します。 + +`Call` で新しい *fidx* を見つけたら、`Call` と `Fun`、`Return` と `CallEnd` を *リンク* します。このリンクは、`Call` から `Fun`、そして `Call` の引数から `Fun` の `ParmNode` へ CFG 辺を追加したかのように動きます。`FunNode` は `RegionNode` を、`ParmNode` は `PhiNode` を拡張するため、同じ意味規則を使います。`Fun` は呼ばれると到達可能になり、`Parm` はすべての呼び出し引数をマージ（*meet*）します。同様に `CallEnd` は、すべての `Return` の *meet* を計算して、呼ばれたすべての関数の結果をマージします。 + +この *リンク* 段階はアルゴリズムの内部ループにいくつかの検査を加え、正確な呼び出しグラフも構築し、SCCP の手続き間実行を可能にします。進行中に新しい辺を少し発見する以外は、中核アルゴリズムは変わりません。不動点解で停止することが保証され、たとえば特定の呼び出しパラメータが、すべての呼び出し経路で定数、あるいは非 null と発見できることがあります。 + +## RegAlloc の改良: 低頻度側のループ分割を先に試す + +ループの Phi と後退辺は、ある命令で値が共存しなければならなくても、同じ生存区間に属する場合があります。この自己衝突は区間の分割を必要とします。第23章は Phi の定義と入力値をすぐに分割しました。この章では先に、高頻度の定義／後退辺をそのままにし、ループ外のコピーを試します。彩色が成功すれば各反復の移動を避けられます。2アドレス演算を含むほかの衝突は、既存の処理を保持します。 + +割り当て器は、どの Phi にこの機会を与えたかを記憶します。同じ Phi が再び自己衝突すると、次は通常の積極的な分割を使います。区間は各ラウンドで再構築するため、記録には Phi の同一性を使います。最初の試行でコピーを挿入しない、後退辺だけの衝突も対象です。その試行も、1回だけ許された遅延を消費しなければなりません。回帰テストは、安い最初の試行と、必須の代替処理の両方を確認します。 + +第21章の隣接コピー転送も引き継ぎます。彩色後、次の命令に唯一の使用がある場合、オペランドマスクが許し、2アドレスの結び付きを壊さなければコピー元レジスタを読めます。以下の表は、この整理と遅延メモリの前方移植を含みます。第22章の群には、以前の監査後に追加した移動0の C 戻り値 ABI 確認2件も含むようになりました（24ではなく26項目）。 + +`make spill-stats` を実行してください。全行は **第24章のコンパイラ**、最適化器のシード123、以前の群の表と同じソース／対象の組み合わせを使います。この Windows 結果は、x86 SystemV/Win64 と RISC-V/ARM SystemV を合わせ、遅延メモリの前方移植後に再測定したものです。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 320 | 439 | +| 第21章 | 52 | 420 | 952 | +| 第22章 | 26 | 67 | 67 | +| 第23章 | 30 | 78 | 225 | +| 第24章 | 67 | 422 | 1,325 | +| **合計** | **214** | **1,307** | **3,008** | + +`_spills` はレジスタ移動を含む残存 SplitNode を数えます。`_spillScaled` は `8^loopDepth` で重み付けするコスト推定で、測定されたメモリアクセスではありません。診断マシングラフはこの表の割り当てに寄与しません。報告器は、スピル期待値が異なっても、割り当ての合法性とネイティブ／エミュレーション結果を確認し、いずれの失敗でも失敗終了します。 + +後のコンパイラ修正より前の、元の2026-09-20割り当て器監査では、表の合計は1,332／2,956でした。低頻度側を先にする規則だけを無効にすると、同じコンパイラとプログラムは **1,338移動／2,962重み付き移動** でした。この規則は各6を減らします。RISC-V MergeSort の1ケースは1移動増えますが、ほかの MergeSort、Sieve、ARM ループの1ケースの改善が相殺します。集計測定はこの局所的な悪化を受け入れる根拠となります。ここでの改善は小さく、普遍的ではありません。 + +その監査で第20〜23章の群だけを見ると、第23章は933／1,745、第24章は900／1,614でした。それぞれの削減のうち、この割り当て器変更によるものは6だけです。残りは SCCP を含むほかのコンパイラ変更です。章だけの比較では、ヒューリスティックの効果を過大に見積もってしまいます。 + +以前の群は64ビット Person、ガード付き String、短いエミュレータ引数リストを保持します。改訂した Jig、BubbleSort、Newton、スタック引数入力は、既存のテストとともに第24章の群に属します。固定した String 処理対象は、インライン化の支配ノード走査で null 検査が欠けていたことも明らかにしました。その正しさの修正はヒューリスティック比較の両側に含めています。面積／コストのスピル順位付けは第25章に残します。 + +現在の関数ポインタ規則は、アドレスが直接呼び出し対象としてだけでなく、値として使われるたびに、未知の呼び出し側を保持します。これにより脱出解析なしで呼び出し可能な本体を保存しますが、Phi で選ばれた関数は一般的なパラメータ型を保持します。return のない String ケースは、今では未使用のハッシュ本体を除去し、分割を必要としません。ソース／対象の構成は変わりません。これらのグラフ変更は、上の低頻度側優先の割り当て器比較とは別です。 diff --git a/docs/chapter24/README.md b/docs/chapter24/README.md new file mode 100644 index 00000000..5a72ab42 --- /dev/null +++ b/docs/chapter24/README.md @@ -0,0 +1,325 @@ +# Chapter 24: Chaining Relationals and Sparse Conditional Constant Propagation + +English | [日本語](README.ja.md) + +[Previous: Chapter 23](../chapter23/README.md) | +[Next: Chapter 25](../chapter25/README.md) + +In this Chapter we allow *chaining* conditionals, e.g. `(60 <= score < 90)` +where `score` in the middle does not have to be repeated. + +The main compiler change is Interprocedural Sparse Conditional Constant +Propagation (SCCP): an optimistic type solve which also discovers call-graph +edges. Memory follows Chapter 11's lazy partitioning: BulkMemPhi represents +whole memory, MemPhi merges precise aliases, and allocations consume and produce +partial memory for their instance fields. During SCCP, memory Phis ignore +unreachable inputs and allocation results stay high until control reaches them. +Chapter 25 retains the larger incomplete-types SSA redesign, private constructor +memory, and separate compilation; see the [backport review queue](../chapter-backports.md). + + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter24) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter23...linear-chapter24) it to the previous chapter. + + +Here is the [complete language grammar](24-grammar.md) for this chapter. + +## Chaining Relational Tests + +Chaining relational tests offer a cleaner, more readable way to write chained +comparisons without repeating the same variable. + +```java +if (min <= x && x < max) +``` + +becomes + +```java +if (min <= x < max) +``` + +This syntax saves space and makes the condition more intuitive, similar to how +range checks are written in mathematics. E.g. + +```java +int score = 75; +if (60 <= score < 90) { + sys.io.p("Pass"); +} +``` +This checks if score is between 60 (inclusive) and 90 (exclusive), without repeating `score`. + +Expressions that mix opposite directions of comparison, like using both +`<=` and `>=`, are not allowed by Simple's direction rule. + +```java +if (a <= b >= c) +``` + + +### Operator direction rules +Stacked comparisons are *only* valid if all the comparison operators +"point" the same way: +- `<` with `<` +- `<` with `<=` +- `>` with `>` +- `>` with `>=` + +Equality operators (`==` and `!=`) have their normal, lower precedence; they +are not links in a relational chain. + +It is not allowed to mix directions in a single chain: +```java +if (a <= b >= c) // Invalid +``` + +Comparisons can be forced into numeric context using booleans. +This is valid but unusual: +```java +return (0 < arg) > 1; +``` +Depending on the result of (0 < arg) this will turn into either +```java +return 0 > 1; +``` +OR +```java +return 1 > 1; +``` +The equality operator is valid in this form, but since it has lower precedence than comparisons, +```java +a < b == c +``` +is parsed as: +```java +(a < b) == c +``` +This might not be the intended chained comparison. +A more explicit alternative is: +```java +a < b && b == c +``` +Comparisons can be chained together in any length, and different comparison operators may be +mixed freely as long as they point in the same direction. +Each intermediate operand is evaluated once. Later operands are evaluated only +if earlier comparisons succeed, so calls and updates in a chain short-circuit. + +E.g: +``` +return 0 < arg < arg+1 < 4; +``` + +### Tricky edge cases +```java +return 0 != arg != 1; +``` + +This is parsed by standard precedence rules as: +```java +return ((0 != arg) != 1); +``` +not as chained inequality. + +```java +return a == b == c; +``` +Similarly, this is parsed as: +```java +return ((a == b) == c); +``` + + + +## Sparse Conditional Constant Propagation + +[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation) +is the top-down version of the same peephole/constant-folding work we have +been doing all along. The rules for the algorithm are well known from the +literature and commonly taught at the college level; +[example slides](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf). + +- We have a lattice already +- We have SSA form already (hence the algorithm is *sparse*) +- We have a mapping from Nodes to Types (`Node._type`) +- We have transfer functions (`Node.compute`) already. + +We initialize all `_type` fields to ⊤ (as opposed to ⊥), and place all Nodes on +a worklist. We pull a Node from the worklist, run the transfer function +`node.compute()`, and if the result changes from `node._type` we update +`node._type` and put its output neighbors on the worklist. A simplified +version with all asserts and debug helpers removed: + +```java +while( (n = code._iter._work.pop()) != null ) { + Type nval = n.compute(); + if( n._type != nval ) { + assert n._type.isa(nval); // Types start high and always fall + n._type = nval; // Update type in Node + code._iter.addAll(n._outputs);// Neighbors might change, need to inspect + } +} +``` + +This algorithm always terminates (and generally fairly quickly) and always +reaches a *fixed point*, as "best answer" subject to the limits of our lattice +and transfer functions. The resulting types are monotonically better than +those found by the peephole rules; we can then run the peephole rules on nodes +with improved types, to see if unrelated peepholes can fire - such as newly +discovered constants replacing computations with ConstantNodes. + +The following is SSA pseudocode; `phi` denotes a merge, not Simple syntax. + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT) + x2 = 2 - x1; // x2 = BOT = 2 - BOT +} +return x1 +``` + +Without SCCP, this small program cannot fold the computation of `x`. +A glance at the program tells us `x` must always be a `1` but +the bottom-up (pessimistic) approach decides that since x1 is BOT, x2 must be +BOT so x1 must be BOT. We need the optimistic approach to break the +stalemate, and just *assume* x1 is `1`, and then we can discover that x2 is +also a `1`. Folding the value does not prove the loop terminates or make +its condition and side effects removable. + + +The algorithm progresses from left to right and stops when no more changes +happen: + +|Var|init|x0=1|x1=phi(1,T)|x2=2-x1|x1=phi(1,1)| +|---|----|----|-----------|-------|-----------| +|x0 | T | 1 | 1 | 1 | 1 | +|x1 | T | T | 1 | 1 | 1 | +|x2 | T | T | T | 1 | 1 | + + + +### Conditional + +Since our control flow is in the same graph as our data flow (that's the major +point of Sea-of-Nodes!), we need not do anything special and our algorithm is +*conditional* already. Again an example is interesting: + +Again using SSA pseudocode: + +```text +int x0 = 1; // x0 = 1 +while( rand ) { + x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT) + if( x1 == 1 ) // Since x1 is BOT, both true and false arms are taken + x2 = 2 - x1; // x2 = BOT = 2 - BOT + else x3 = 99; // x3 = 99 + x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99) +} +return x1 +``` + +Again the algorithm progresses from left to right, although this time not all +paths are reachable. The `if` result is a pair of Control values, shown as +either `C` if the path is alive or `X` if not. This is used when we compute +`x4 = phi(x2,x3)`; the `PhiNode` ALSO checks the corresponding control input +from the `if` and only merges alive paths. + + +|Var|init |x0=1|x1=phi(1,T)| 1 == 1? | x2=2-x1 | x3=99 |x4=phi(C/1,X/99)|x1=phi(1,1)| +|---|-----|----|-----------|---------|---------|---------|----------------|-----------| +|x0 | T | 1 | 1 | 1 | 1 | 1 | 1 | 1 | +|x1 | T | T | 1 | 1 | 1 | 1 | 1 | 1 | +|if | T | T | T | [C,X] | [C,X] | [C,X] | [C,X] | [C,X] | +|x2 | T | T | T | T | 1 | 1 | 1 | 1 | +|x3 | T | T | T | T | T | 99 | 99 | 99 | +|x4 | T | T | T | T | T | T | 1 | 1 | + +This kind of conditional constant propagation really helps if a condition can +be proven true or false, as this removes a test and branch from the optimized +program. A common way this happens is with null tests; here is the same +program above, but using null pointers instead of integers: + +```java +List head = notNullList(); +while( rand ) { + if( head ) head = new List(head,payload); + else { head = null; default_action(); } +} +``` + +Here since `head` starts not-null, it can never be null and the +`default_action` can never happen, and the loop can +simplify: + +```java +List head = notNullList(); +while( rand ) { + head = new List(head,payload); +} +``` + +### Interprocedural + +In **Simple**, we let our SCCP run interprocedurally, again by (nearly) doing nothing: +`CallNodes` call `FunNodes`, `ReturnNodes` return to `CallEndNodes` and they +pass their type information along in exactly the normal way... except for one issue: +there are no edges between `Calls` and `Funs` (nor `Returns` and `CallEnds`). +Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph). + +We extend the normal SCCP algorithm to observe when a `Call`s function pointer +input changes - when it picks up new function targets. There are only a finite +number so we represent them exactly with *function indices* as described in an +earlier chapter. (Separate compilation adds a special index for the infinite +unknown functions that are called outside this compilation unit). + +Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`, +and the `Return` with the `CallEnd`. Such linkage acts exactly as-if we added +a CFG edge from the `Call` to the `Fun`, and the `Call`s arguments to the +`Fun`s `ParmNodes`. `FunNodes` extend `RegionNodes` (and `ParmNodes` extend +`PhiNodes`), so this linkage uses the same semantics. `Fun`s become reachable +when called; `Parm`s merge (*meet*) all calling arguments, and so on. +Similarly, `CallEnd`s merge results from all called functions, computing the +*meet* over all the `Return`s. + +This *link* step adds a few checks to our algorithm's inner loop, and also +builds a precise Call Graph which allows our SCCP to run interprocedurally. +Other than discovering a few new edges as the algorithm proceeds, the core +algorithm is unchanged. We are guaranteed to terminate with a fixed point +solution, and may discover e.g. certain call parameters are constants (or +e.g. not-null) on all calling paths. + + +## RegAlloc improvements: try cold loop splits first + +A loop Phi and its backedge can belong to one live range even though their +values must coexist at some instruction. This self-conflict requires splitting +the range. Chapter 23 split the Phi's definition and incoming values right away. +This chapter first leaves the hot definition/backedge alone and tries the +outside-loop copies. If coloring succeeds, it avoids moves on every iteration. +Other conflicts, including two-address operations, keep their existing handling. + +The allocator remembers which Phis have had this chance. If the same Phi +self-conflicts again, the next attempt uses the ordinary aggressive splitting. +The record uses Phi identity because live ranges are rebuilt each round. It +also covers a backedge-only conflict where the first attempt inserts no copy: +that attempt must still consume the one permitted delay. A regression checks +both the cheaper first attempt and the mandatory fallback. + +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../regalloc-spills.md) for coverage. + + +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | +|---|---:|---:|---:|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | + + diff --git a/docs/chapter24/examples/A_helloWorld.smp b/docs/chapter24/examples/A_helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/docs/chapter24/examples/A_helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/docs/chapter24/examples/BubbleSort.smp b/docs/chapter24/examples/BubbleSort.smp new file mode 100644 index 00000000..938e3181 --- /dev/null +++ b/docs/chapter24/examples/BubbleSort.smp @@ -0,0 +1,37 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + var done = false; + while( !done ) { + done = true; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) { + int tmp = nums.buf[i]; + nums.buf[i] = nums.buf[i+1]; + nums.buf[i+1] = tmp; // Swap + done = false; + } + } +}; + +// Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. +val main = { -> + // Parse array of numbers from stdin + var nums = sys.parseAryI64( sys.io.stdin() ); + if( !nums ) { + sys.io.p("stdin must look like [4, 3, 2, 1]"); + return 1; + } + + // Bubble sort array of integers + sort(nums); + + // Print a list of numbers to stdout + nums.str().write(1); + return 0; +}; diff --git a/docs/chapter24/font-awesome-4.7.0.zip b/docs/chapter24/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter24/font-awesome-4.7.0.zip differ diff --git a/docs/chapter24/ifg_trim.pdf b/docs/chapter24/ifg_trim.pdf new file mode 100644 index 00000000..d952fd4f Binary files /dev/null and b/docs/chapter24/ifg_trim.pdf differ diff --git a/docs/chapter24/lattice.gv b/docs/chapter24/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter24/lattice.gv @@ -0,0 +1,203 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.2; + ranksep=0.2; + + TOP [label=<⊤>, fillcolor=black, fontcolor=white]; + BOT [label=<⊥>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<⊤:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<⊥:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<⊤:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<⊥:int>, fillcolor=lightblue, shape=oval]; + + INT_HI [label="[min>max]" , fillcolor=lightblue, shape=oval]; + INT_XBOOL [label="[1...0]", fillcolor=lightblue, shape=oval]; + INT_CON [label="constants", fillcolor=lightblue, shape=oval]; + INT_CON0 [label="0", fillcolor=lightblue]; + INT_CON1 [label="1", fillcolor=lightblue]; + INT_BOOL [label="[0...1]", fillcolor=lightblue,shape=oval]; + INT_LO [label="[min INT_TOP; + INT_TOP -> INT_HI; + INT_HI -> INT_XBOOL; + INT_XBOOL -> INT_CON0; + INT_XBOOL -> INT_CON1; + INT_HI -> INT_CON; + INT_CON0 -> INT_BOOL; + INT_CON1 -> INT_BOOL; + INT_BOOL -> INT_LO; + INT_CON -> INT_LO; + INT_LO -> INT_BOT; + INT_BOT -> BOT; + + INT_CON0 -> INT_CON1 -> INT_CON [style=invis]; + + // ---------------------- + // Floats + FLT_TOP [label=<⊤:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<⊥:flt>, fillcolor=aqua, shape=oval]; + + FLT_CON64 [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval]; + FLT_CON32 [label="32b consts", fillcolor=aqua, shape=oval]; + FLT_CONPI [label="3.14159...", fillcolor=aqua, shape=oval]; + FLT_X32 [label="~f32", fillcolor=aqua]; + FLT_CON0 [label="0." , fillcolor=aqua]; + FLT_32 [label="f32" , fillcolor=aqua]; + + TOP -> FLT_TOP; + FLT_TOP -> FLT_CON64 + FLT_TOP -> FLT_CONPI + FLT_CON64 -> FLT_BOT + FLT_CONPI -> FLT_BOT + + FLT_TOP -> FLT_X32; + FLT_X32 -> FLT_CON0; + FLT_X32 -> FLT_CON32; + FLT_CON0 -> FLT_32; + FLT_CON32 -> FLT_32; + FLT_32 -> FLT_BOT + + FLT_BOT -> BOT; + + FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis]; + + + // ---------------------- + // Pointers, just a boolean nil/not and a struct + PTR [shape=none, fillcolor=none, label=< + + + +
*ptr
struct
+ >]; + PTR0 [shape=none, fillcolor=none, label=< + + + +
*ptr?
struct
+ >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<⊤:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<⊥:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + + +
fieldint/ptr
+ >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + + + +
fieldint/ptr
fieldint/ptr
+ >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + + + + +
fieldint/ptr
... int/ptr
fieldint/ptr
+ >]; + + + TOP -> STRUCT_TOP; + STRUCT_TOP -> STRUCT_S1; + STRUCT_TOP -> STRUCT_S2; + STRUCT_TOP -> STRUCT_SN; + STRUCT_S1 -> STRUCT_BOT; + STRUCT_S2 -> STRUCT_BOT; + STRUCT_SN -> STRUCT_BOT; + STRUCT_BOT -> BOT; + + STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; + + // ---------------------- + // Memory + MEM_TOP [label=<⊤:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<⊥:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white]; + MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_ALIAS1; + MEM_TOP -> MEM_ALIASDOTS; + MEM_TOP -> MEM_ALIASN; + MEM_ALIAS1 -> MEM_BOT; + MEM_ALIASDOTS -> MEM_BOT; + MEM_ALIASN -> MEM_BOT; + MEM_BOT -> BOT; + + MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<⊤:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<⊥:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + + + +
Tuple
type
+ >]; + TUPLE2 [shape=none, fillcolor=none, label=< + + + + +
Tuple
type
type
+ >]; + TUPLEN [shape=none, fillcolor=none, label=< + + + + + +
Tuple
type
...
type
+ >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // ---------------------- + // Additional customization + {rank=same; TOP;} + {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP} + {rank=same; INT_CON; INT_CON0; INT_CON1; + FLT_CON32; FLT_CON64; FLT_CON0; FLT_CONPI; + STRUCT_S1; STRUCT_S2; STRUCT_SN; + MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN; + TUPLE1; TUPLE2; TUPLEN; + } + {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter24/lattice.svg b/docs/chapter24/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter24/lattice.svg @@ -0,0 +1,691 @@ + + + + + + +Lattice + + + +TOP + +⊤ + + + +XCTRL + +⊤ +:ctrl + + + +TOP->XCTRL + + + + + +INT_TOP + +⊤ +:int + + + +TOP->INT_TOP + + + + + +FLT_TOP + +⊤ +:flt + + + +TOP->FLT_TOP + + + + + +PTR + + + +*ptr + + +struct + + + +TOP->PTR + + + + + +STRUCT_TOP + +⊤ +:struct + + + +TOP->STRUCT_TOP + + + + + +MEM_TOP + +⊤ +:mem + + + +TOP->MEM_TOP + + + + + +TUPLE_TOP + +⊤ +:tuple + + + +TOP->TUPLE_TOP + + + + + +BOT + +⊥ + + + +CTRL + +⊥ +:ctrl + + + +XCTRL->CTRL + + + + + +CTRL->BOT + + + + + +INT_HI + +[min>max] + + + +INT_TOP->INT_HI + + + + + +INT_BOT + +⊥ +:int + + + +INT_BOT->BOT + + + + + +INT_XBOOL + +[1...0] + + + +INT_HI->INT_XBOOL + + + + + +INT_CON + +constants + + + +INT_HI->INT_CON + + + + + +INT_CON0 + +0 + + + +INT_XBOOL->INT_CON0 + + + + + +INT_CON1 + +1 + + + +INT_XBOOL->INT_CON1 + + + + + +INT_LO + +[min<max] + + + +INT_CON->INT_LO + + + + + + +INT_BOOL + +[0...1] + + + +INT_CON0->INT_BOOL + + + + + + +INT_CON1->INT_BOOL + + + + + +INT_BOOL->INT_LO + + + + + +INT_LO->INT_BOT + + + + + +FLT_CON64 + +64b consts +[excludes +32b consts] + + + +FLT_TOP->FLT_CON64 + + + + + +FLT_CONPI + +3.14159... + + + +FLT_TOP->FLT_CONPI + + + + + +FLT_X32 + +~f32 + + + +FLT_TOP->FLT_X32 + + + + + +FLT_BOT + +⊥ +:flt + + + +FLT_BOT->BOT + + + + + +FLT_CON64->FLT_BOT + + + + + +FLT_CON32 + +32b consts + + + + +FLT_32 + +f32 + + + +FLT_CON32->FLT_32 + + + + + +FLT_CONPI->FLT_BOT + + + + + + +FLT_X32->FLT_CON32 + + + + + +FLT_CON0 + +0. + + + +FLT_X32->FLT_CON0 + + + + + + +FLT_CON0->FLT_32 + + + + + +FLT_32->FLT_BOT + + + + + +PTR0 + + + +*ptr? + + +struct + + + +PTR->PTR0 + + + + + +PTR0->BOT + + + + + +STRUCT_S1 + + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S1 + + + + + +STRUCT_S2 + + + +field + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_S2 + + + + + +STRUCT_SN + + + +field + + + + + + + + +int/ptr + + +...   + + + + + + + + +int/ptr + + +field + + + + + + + + +int/ptr + + + +STRUCT_TOP->STRUCT_SN + + + + + +STRUCT_BOT + +⊥ +:struct + + + +STRUCT_BOT->BOT + + + + + +STRUCT_S1->STRUCT_BOT + + + + + + +STRUCT_S2->STRUCT_BOT + + + + + + +STRUCT_SN->STRUCT_BOT + + + + + +MEM_ALIAS1 + +#1 + + + +MEM_TOP->MEM_ALIAS1 + + + + + +MEM_ALIASDOTS + +... + + + +MEM_TOP->MEM_ALIASDOTS + + + + + +MEM_ALIASN + +#n + + + +MEM_TOP->MEM_ALIASN + + + + + +MEM_BOT + +⊥ +:mem + + + +MEM_BOT->BOT + + + + + +MEM_ALIAS1->MEM_BOT + + + + + + +MEM_ALIASDOTS->MEM_BOT + + + + + + +MEM_ALIASN->MEM_BOT + + + + + +TUPLE1 + + + +Tuple + + +type + + + +TUPLE_TOP->TUPLE1 + + + + + +TUPLE2 + + + +Tuple + + +type + + +type + + + +TUPLE_TOP->TUPLE2 + + + + + +TUPLEN + + + +Tuple + + +type + + +... + + +type + + + +TUPLE_TOP->TUPLEN + + + + + +TUPLE_BOT + +⊥ +:tuple + + + +TUPLE_BOT->BOT + + + + + +TUPLE1->TUPLE_BOT + + + + + +TUPLE2->TUPLE_BOT + + + + + +TUPLEN->TUPLE_BOT + + + + + diff --git a/docs/chapter24/lattice2.gv b/docs/chapter24/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter24/lattice2.gv @@ -0,0 +1,85 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=oval, style=filled]; + nodesep=0.2; + ranksep=0.4; + + TOP [label="~scalar\n+int+tmp+0", fillcolor=black, fontcolor=white, group=center]; + + // ------------------------ + PTRHQ [label="~tmp\n+tmp+0", fillcolor=green, fontcolor=white, group=left]; + TOP -> PTRHQ + + VALH_ [label="~nscalar\n+int+tmp", fillcolor=white, group=center]; + TOP -> VALH_ + + INTHQ [label="~int\n+int+0", fillcolor=lightblue, group=right]; + TOP -> INTHQ + + LEFTHI [label="junk", style=invis, group=junkleft] + + + PTRHQ -> LEFTHI-> VALH_ -> INTHQ [style=invis]; + { rank=same; PTRHQ; LEFTHI; VALH_; INTHQ } + + // ------------------------ + PTRH_ [label="~ntmp\n+tmp", fillcolor=green, fontcolor=white, group=left]; + VALH_ -> PTRH_ + PTRHQ -> PTRH_ + + INTH_ [label="~nint\n+int", fillcolor=lightblue, group=right]; + VALH_ -> INTH_ + INTHQ -> INTH_ + { rank=same; PTRH_; INTH_ } + + // ------------------------ + NILX_ [label="~nil\n[int,tmp]+0", fillcolor=aqua, group=junkleft]; + INTHQ -> NILX_ + PTRHQ -> NILX_ + + NIL__ [label="nil\n[+int+tmp],0", fillcolor=pink]; + VALH_ -> NIL__; + + NILX_ -> NIL__ [style=invis]; + { rank=same; NIL__; NILX_ } + + // ------------------------ + PTRL_ [label="ntmp\ntmp", fillcolor=green, fontcolor=white, group=left]; + PTRH_ -> PTRL_ + + INTL_ [label="nint\nint", fillcolor=lightblue, group=right]; + INTH_ -> INTL_ + { rank=same; PTRL_; INTL_ } + + // ------------------------ + PTRL0 [label="tmp\ntmp,0", fillcolor=green, fontcolor=white, group=left]; + PTRL_ -> PTRL0 + NIL__ -> PTRL0 + + VALL_ [label="nscalar\nint,tmp", fillcolor=white, group=center]; + PTRL_ -> VALL_ + INTL_ -> VALL_ + NILX_ -> VALL_ + + INTL0 [label="int\nint,0", fillcolor=lightblue, group=right]; + INTL_ -> INTL0 + NIL__ -> INTL0 + + PTRL0 -> VALL_ -> INTL0 [style=invis]; + { rank=same; PTRL0; VALL_; INTL0 } + + // ------------------------ + BOT [label="scalar\nint,tmp,0", fillcolor=black, fontcolor=white, group=center]; + PTRL0 -> BOT + INTL0 -> BOT + VALL_ -> BOT + + // ------------------------ + // Verticle alignment + TOP -> VALH_ -> VALL_ -> BOT [style=invis]; + PTRHQ -> PTRH_ -> PTRL_ -> PTRL0 [style=invis]; + INTHQ -> INTH_ -> INTL_ -> INTL0 [style=invis]; + LEFTHI -> NILX_ [style=invis] +} diff --git a/docs/chapter24/lattice2.svg b/docs/chapter24/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter24/lattice2.svg @@ -0,0 +1,260 @@ + + + + + + +Lattice + + + +TOP + +~scalar ++int+tmp+0 + + + +PTRHQ + +~tmp ++tmp+0 + + + +TOP->PTRHQ + + + + + +VALH_ + +~nscalar ++int+tmp + + + +TOP->VALH_ + + + + + + +INTHQ + +~int ++int+0 + + + +TOP->INTHQ + + + + + + + +PTRH_ + +~ntmp ++tmp + + + +PTRHQ->PTRH_ + + + + + + +NILX_ + +~nil +[int,tmp]+0 + + + +PTRHQ->NILX_ + + + + + + +VALH_->PTRH_ + + + + + +INTH_ + +~nint ++int + + + +VALH_->INTH_ + + + + + +NIL__ + +nil +[+int+tmp],0 + + + +VALH_->NIL__ + + + + + +VALL_ + +nscalar +int,tmp + + + + +INTHQ->INTH_ + + + + + + +INTHQ->NILX_ + + + + + + + +PTRL_ + +ntmp +tmp + + + +PTRH_->PTRL_ + + + + + + +INTL_ + +nint +int + + + +INTH_->INTL_ + + + + + + + +NILX_->VALL_ + + + + + +PTRL0 + +tmp +tmp,0 + + + +NIL__->PTRL0 + + + + + +INTL0 + +int +int,0 + + + +NIL__->INTL0 + + + + + +PTRL_->PTRL0 + + + + + + +PTRL_->VALL_ + + + + + +INTL_->VALL_ + + + + + +INTL_->INTL0 + + + + + + + +BOT + +scalar +int,tmp,0 + + + +PTRL0->BOT + + + + + + +VALL_->BOT + + + + + + +INTL0->BOT + + + + + diff --git a/docs/chapter24/pardoe.docx b/docs/chapter24/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/docs/chapter24/pardoe.docx differ diff --git a/docs/chapter24/webtcp.min.js b/docs/chapter24/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter24/webtcp.min.js @@ -0,0 +1,65 @@ +function Http(j){this.cID=Math.random().toString(36).substr(2);this.webtcp=j;this.webtcp.httpClients[this.cID]=this;this.createPacket=function(){return{cID:this.cID,type:"http",host:this.remoteAddress,port:this.remotePort,method:null,data:null}};this.ondata=function(){};this.get=function(g,c){this.on("data",c);this.rpc("httpGet",[g])};this.post=function(g,c,j){this.on("data",j);this.rpc("httpPost",[g,c])}}Http.prototype=new WebTCPIO;function Socket(j,g,c,p){this.sID=Math.random().toString(36).substr(2);this.webtcp=j;this.closed=this.ready=!1;this.options=p;this.sockOpts={_updating:!1};this.remoteAddress=g;this.remotePort=c;this.webtcp.sockets[this.sID]=this;this.createPacket=function(){return{id:Math.random().toString(36).substr(2),sID:this.sID,type:"tcp",options:this.options,host:this.remoteAddress,port:this.remotePort,data:null}};this.onconnect=function(){this.webtcp.sockets[sID].ready=!0;this.webtcp.sockets[sID].closed=!1}; +this.ondata=function(){};this.onend=function(){};this.ontimeout=function(){};this.ondrain=function(){};this.onclose=function(){this.webtcp.sockets[sID].ready=!1;this.webtcp.sockets[sID].closed=!0};this.getSockOpts=function(){this.sockOpts._updating=!0;this.rpc("getSockOpts")};this.onSockOptsRcv=function(c){this.sockOpts=c;this.sockOpts._updating=!1}}Socket.prototype=new WebTCPIO;var JSON;JSON||(JSON={}); +(function(){function j(c,p){var q,t,n,x,i=k,e,l=p[c];l&&"object"==typeof l&&"function"==typeof l.toJSON&&(l=l.toJSON(c));"function"==typeof r&&(l=r.call(p,c,l));switch(typeof l){case "string":return g(l);case "number":return isFinite(l)?String(l):"null";case "boolean":case "null":return String(l);case "object":if(!l)return"null";k+=v;e=[];if("[object Array]"===Object.prototype.toString.apply(l)){x=l.length;for(q=0;qc?"0"+c:c}"use strict";"function"!=typeof Date.prototype.toJSON&&(Date.prototype.toJSON=function(){return isFinite(this.valueOf())?this.getUTCFullYear()+"-"+c(this.getUTCMonth()+1)+"-"+c(this.getUTCDate())+"T"+c(this.getUTCHours())+":"+c(this.getUTCMinutes())+":"+c(this.getUTCSeconds())+"Z":null},String.prototype.toJSON=Number.prototype.toJSON=Boolean.prototype.toJSON=function(){return this.valueOf()});var p=/[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g, +n=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,k,v,D={"\b":"\\b","\t":"\\t","\n":"\\n","\f":"\\f","\r":"\\r",'"':'\\"',"\\":"\\\\"},r;"function"!=typeof JSON.stringify&&(JSON.stringify=function(c,g,p){var n;v=k="";if("number"==typeof p)for(n=0;n=a};c.countRTO=function(a){var b;return 100b;b++)d.push(String.fromCharCode(b));B=(r.lastIndex=0,d.join("").replace(r,function(a){return c[a]="\\u"+("0000"+a.charCodeAt(0).toString(16)).slice(-4),""}),r.lastIndex=0,c)}a=a.replace(r,function(a){return B[a]})}return a};var q="websocket xdr-streaming xhr-streaming iframe-eventsource iframe-htmlfile xdr-polling xhr-polling iframe-xhr-polling jsonp-polling".split(" "); +c.probeProtocols=function(){for(var a={},b=0;b