From 84a70fd744f83e2d701e15fc3d17109eb59ac707 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 11:01:47 -0800 Subject: Chapter 18: Functions and Calls 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: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter18/18-grammar.ja.md | 141 +++++++ docs/chapter18/18-grammar.md | 141 +++++++ docs/chapter18/Makefile | 1 + docs/chapter18/README.ja.md | 226 +++++++++++ docs/chapter18/README.md | 363 ++++++++++++++++++ docs/chapter18/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter18/inline-after.json | 101 +++++ docs/chapter18/inline-after.svg | 81 ++++ docs/chapter18/inline-before.json | 276 ++++++++++++++ docs/chapter18/inline-before.svg | 117 ++++++ docs/chapter18/lattice.gv | 203 ++++++++++ docs/chapter18/lattice.svg | 691 ++++++++++++++++++++++++++++++++++ docs/chapter18/lattice2.gv | 85 +++++ docs/chapter18/lattice2.svg | 260 +++++++++++++ docs/chapter18/webtcp.min.js | 65 ++++ 15 files changed, 2751 insertions(+) create mode 100644 docs/chapter18/18-grammar.ja.md create mode 100644 docs/chapter18/18-grammar.md create mode 100644 docs/chapter18/Makefile create mode 100644 docs/chapter18/README.ja.md create mode 100644 docs/chapter18/README.md create mode 100644 docs/chapter18/font-awesome-4.7.0.zip create mode 100644 docs/chapter18/inline-after.json create mode 100644 docs/chapter18/inline-after.svg create mode 100644 docs/chapter18/inline-before.json create mode 100644 docs/chapter18/inline-before.svg create mode 100644 docs/chapter18/lattice.gv create mode 100644 docs/chapter18/lattice.svg create mode 100644 docs/chapter18/lattice2.gv create mode 100644 docs/chapter18/lattice2.svg create mode 100644 docs/chapter18/webtcp.min.js (limited to 'docs') diff --git a/docs/chapter18/18-grammar.ja.md b/docs/chapter18/18-grammar.ja.md new file mode 100644 index 00000000..4c90e442 --- /dev/null +++ b/docs/chapter18/18-grammar.ja.md @@ -0,0 +1,141 @@ +# 第18章の文法 + +[English](18-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 block ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +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 ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : 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 ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_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+) ; +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 ; +``` diff --git a/docs/chapter18/18-grammar.md b/docs/chapter18/18-grammar.md new file mode 100644 index 00000000..656bd63a --- /dev/null +++ b/docs/chapter18/18-grammar.md @@ -0,0 +1,141 @@ +# Grammar for Chapter 18 + +English | [日本語](18-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 block ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +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 ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : bitwiseExpression ('?' assignment (':' assignment)?)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : 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 ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_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+) ; +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 ; +``` diff --git a/docs/chapter18/Makefile b/docs/chapter18/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter18/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter18/README.ja.md b/docs/chapter18/README.ja.md new file mode 100644 index 00000000..9f3157d4 --- /dev/null +++ b/docs/chapter18/README.ja.md @@ -0,0 +1,226 @@ +# 第18章: 関数と呼び出し + +[English](README.md) | 日本語 + +[前: 第17b章](../chapter17b/README.ja.md) | +[次: 第19章](../chapter19/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +第17b章までは、プログラムは入力 `arg` と結果を持つ1つの本体からなっていました。分岐、ループ、オブジェクトの割り当て、メモリの更新はできますが、まだ関数に分割できません。この章では、再帰呼び出しも含めた関数値と呼び出しを追加します。 + +グラフ表現には、なじみのある部品を使います。関数の入口は Region、パラメータは Phi で、出口は1つの Return に合流します。呼び出しは関数境界を越えてこれらを結びます。関数の呼び出し元が1つだけなら、境界を取り除くことで通常のピープホール最適化が結合されたグラフを簡略化できます。これが最初の形のインライン化です。 + +この章の[完全な言語文法](18-grammar.ja.md)はこちらです。 + +## 目次 + +1. [関数を書く](#関数を書く) +2. [グラフ内の関数](#グラフ内の関数) +3. [呼び出しをまたぐメモリ](#呼び出しをまたぐメモリ) +4. [関数型と呼び出し先](#関数型と呼び出し先) +5. [インライン化](#インライン化) +6. [スケジューリングと実行](#スケジューリングと実行) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの線形の Git リビジョン履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18)を読むことや、前章との[差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter17b...linear-chapter18)を見ることもできます。 + +## 関数を書く + +関数式は型付きのパラメータを列挙し、`->` と本体を続けます。 + +```simple +val sq = { int x -> x*x; }; +return sq(arg); +``` + +初期化子は関数値を作り、宣言がそれを `sq` に束縛します。呼び出し `sq(arg)` は引数を評価し、その値を `x` に束縛して本体を実行し、結果を返します。実行が本体の末尾に到達すると、最後の式が結果を供給します。明示的な `return` なら途中で終了できます。 + +関数型は、パラメータ名を含めず、パラメータ型と結果型を列挙します。同じ平方関数を明示的な型で宣言できます。 + +```simple +{int -> int} sq = { int x -> x*x; }; +return sq(4); // 16 +``` + +関数は匿名の値です。変数に代入すれば診断用の名前を付けられますが、束縛はほかの変数と同じ規則に従います。`val` は固定の束縛、`var` は再代入可能な束縛を推論します。関数を引数として渡したり、結果として返したり、式で選んだりできます。 + +パラメータは[第17a章](../chapter17a/README.ja.md)の明示的な宣言構文を使います。`!Point p` は固定されたパラメータ束縛を通じた書き込みを許し、`Point !p` は読み取り専用参照の再代入を許し、`int ~limit` はプリミティブのパラメータを固定します。パラメータ型は必須です。`var` と `val` は、関数を保持する変数に適用するもので、パラメータには適用しません。 + +### 戻り値とスコープ + +本体には周囲の言語と同じ文が使えます。ここでは早期 return で、最初の一致する配列要素を探します。 + +```simple +val find = { int[] es, int e -> + for( int i=0; i x+offset; }; +return addOffset(arg); +``` + +`val offset` を `int offset` に変えると束縛が可変になり、関数定義は拒否されます。同様に `val offset = arg` は固定ですが定数ではないので、入れ子の関数から使えません。固定された関数定数はこの規則を満たすため、フレームを捕捉せずに、ある関数から別の関数を参照できます。 + +### 再帰 + +関数は自身の束縛を参照できます。 + +```simple +val fact = { int n -> + n <= 1 ? 1 : n*fact(n-1); +}; +return fact(arg); +``` + +パーサーは、本体をパースする前に関数の入口を登録します。`fact` への前方参照は、宣言がその関数値を受け取ると解決されます。それによって再帰呼び出しも、外からの呼び出しと同じ入口を見つけられます。この章では戻り値の型推論はまだ悲観的です。相互再帰する定義には、[第24章](../chapter24/README.ja.md)の SCCP で導入する、より強力な解析が必要なことがあります。 + +## グラフ内の関数 + +これまでは `Start` が1つのプログラム本体への入力を供給していました。今度はその本体を、整数パラメータ `arg` を持つ暗黙の `main` としてパースします。評価器は `Start` から `main` に入り、結果を外の世界に渡します。そのため既存のプログラムは、ソース構文を維持したまま、明示的に宣言された関数と同じ関数表現を得ます。 + +### 入口、パラメータ、出口 + +[FunNode](../../src/main/java/com/seaofnodes/simple/node/FunNode.java) は `RegionNode` を継承します。Region が異なる分岐からの制御を合流するのに対し、Fun は異なる呼び出し元からの制御を合流します。リンクされた呼び出しが、1本の流入制御エッジを供給します。 + +[ParmNode](../../src/main/java/com/seaofnodes/simple/node/ParmNode.java) は `PhiNode` を継承します。Phi が流入分岐に属する値を選ぶのと同じように、各パラメータは流入呼び出しに属する引数を選びます。パラメータの添字が、呼び出し元の供給するものを識別します。 + +| パラメータの添字 | 値 | +|---|---| +| 0 | 復帰地点: 呼び出し元の実行再開位置 | +| 1 | メモリ全体 | +| 2 以降 | ソース言語の引数 | + +各関数は、`Start` で表される暗黙の未知の呼び出し元も持ちます。これは宣言されたパラメータ型と未知のメモリを供給します。呼び出しをまだ発見している間、これによって入口を保守的に保ちます。 + +ソース上のすべての `return` は、1つの出口 Region に寄与します。値の Phi が結果を合流し、BulkMemPhi がそのメモリ状態を合流します。結果の [ReturnNode](../../src/main/java/com/seaofnodes/simple/node/ReturnNode.java) の入力は `{control, memory, value, return point}` です。出口が1つなら、Region と Phi はしばしば畳み込まれて消えます。`Stop` は、`main` のものも含め、関数の Return を保持します。 + +これにより、本体に分岐、ループ、複数の return 文があっても、各関数は1つの入口と1つの合流した出口を持ちます。 + +### 呼び出しと復帰地点 + +[CallNode](../../src/main/java/com/seaofnodes/simple/node/CallNode.java) の入力は `{control, memory, arguments..., function pointer}` です。最後の入力が呼び出し先を決めます。定数の関数でも、関数値を持つ式の結果でもかまいません。引数式は、Call が制御とメモリの入力を取る前に評価します。 + +各 Call には [CallEndNode](../../src/main/java/com/seaofnodes/simple/node/CallEndNode.java) があり、呼び出し元が継続する地点となります。CallEnd は Call と、リンクされた呼び出し先の Return を入力に取ります。その射影は、それぞれスロット 0、1、2 に制御、メモリ、結果を供給します。 + +呼び出される側は、どの CallEnd に戻るかを知る必要があります。隠れたパラメータ 0 が、本体を通じて Return までその復帰地点を運びます。*return program counter*（復帰プログラムカウンタ）の略である `TypeRPC` は、関数ポインタ型が取り得る入口の集合を記述するのと同じように、取り得る復帰地点の集合を記述します。これらは内部値であり、ソースプログラムは RPC 変数を宣言しません。 + +呼び出しグラフのエッジは、呼び出しがどの関数に到達し得るかを記述します。これは1つの関数内の制御フローとは別です。通常グラフをたどるときには、呼び出しと関数の付近で注意が必要です。多くの探索は、単一の関数内でだけ有効だからです。 + +## 呼び出しをまたぐメモリ + +前の章では、フィールドのエイリアスごとにメモリを遅延的に分割しました。関数内では今もそうしますが、関数入口のメモリは未知です。引数が、呼び出し元で割り当てて変更したオブジェクトを参照するかもしれません。流入するヒープが空だとは、もう仮定できません。 + +Call は、MemMerge に包まれたスライスも含め、完全なメモリ状態を受け取ります。その CallEnd は新しいメモリ全体の値を生成します。この章では、すべての呼び出しがすべてのエイリアスを変更し得ると扱います。呼び出される関数がわかっていても、どのフィールドに書くかという要約はまだ得られません。 + +```simple +struct Counter { int n; }; +val bump = { !Counter p -> p.n++; return null; }; +val p = new Counter; +int before = p.n; +bump(p); +bump(p); +return before*10+p.n; // 2 +``` + +最初の `p.n` の読み出しは、初期化された値を観測します。最後の読み出しは両方の呼び出し後のメモリを使う必要があり、最初の読み出しを再利用できません。2つの呼び出しも、メモリの入出力によって順序が維持されます。書き込み可能なパラメータ権限が更新を許し、メモリエッジがその時点を記録します。 + +関数内では、MemMerge、MemPhi、BulkMemPhi が引き続き精密なスライスを露出し、分岐やループの状態を合流します。境界では、メモリ Parm 1 と CallEnd のメモリ結果は不透明なままです。大域的コード移動は、Load を配置するときに呼び出しを潜在的な書き込みとして扱います。呼び出しはブロックを終了するため、Call より前である必要がある Load は、その終端命令より前にスケジュールします。 + +インライン化は呼び出しの境界を取り除き、実際の Load と Store を既存のエイリアス最適化に露出します。グラフに残る呼び出しの作用をより精密に扱うには、後のエスケープ解析が必要です。 + +## 関数型と呼び出し先 + +[TypeFunPtr](../../src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java) は、引数タプル、結果型、null 許容性、関数添字の集合（`fidxs`）を記録します。ある引数シグネチャ内で、各関数は小さな整数の添字を得ます。ビット集合は、そのシグネチャを持つ1つの既知の関数や、複数の可能な関数を記述できます。`CodeGen` は具体的な関数の識別情報を FunNode に対応付けます。この章の IR の実行に、機械語コードのアドレスは不要です。 + +たとえば、以下の両分岐は型 `{int -> int}` を持ちますが、関数添字は異なります。 + +```simple +val f = arg ? { int x -> x+x; } : { int x -> x*x; }; +return f(3); // 6 when arg is nonzero, otherwise 9 +``` + +`f` の Phi は、2つの関数ポインタ型を組み合わせます。呼び出し先の集合は両方の関数を含みます。関数を選ぶことは、その本体の実行ではありません。 + +関数ポインタも、なじみのある接尾辞 `?` で null を許容できます。 + +```simple +{int -> int}? f = arg ? { int x -> x*x; } : null; +if( f ) return f(3); +return 0; +``` + +ガードは、呼び出し時にポインタが null でないことを証明します。呼び出しは、引数の個数、型、アクセス権限もチェックします。構造体ポインタと関数ポインタは、`Type.NIL` で表される特別な `null` 値を共有します。`TypeNil` が、共通の null 許容性の仕組みを供給します。 + +### 既知の呼び出し先のリンク + +ここで*リンク*とは、呼び出しと関数の間に IR エッジを追加することです。オブジェクトファイルのリンクではありません。既知の各呼び出し先について、コンパイラは Call を Fun の入力として追加し、引数をその Parm に追加し、その Return を CallEnd の入力として追加します。対応する入力位置が、呼び出し元と引数の関係を保ちます。 + +この章ではすでに、上の条件式の例にある両方の関数も含め、既知の呼び出し先の有限集合をリンクします。未知の関数をまだ含む無限集合は列挙できません。この不確実性を、すべての呼び出しからすべての関数へのエッジで表すのは避けます。二次的に増大するためです。 + +代わりに Fun は*未知の呼び出し元*の入力を保持します。これまでに見つかった呼び出しが定数を渡していても、パラメータは宣言型を受け入れる必要があります。呼び出し元が1つ見つかっても、ほかにないという証明にはなりません。同様に、CallEnd は関数ポインタ型から結果型を得て、メモリ結果を未知のままにします。リンクされた Return エッジだけでは、これらの保守的な仮定を取り除きません。 + +インライン化は、関数の呼び出し元が1つだけであるという局所的な証明に依存します。後の SCCP の章では、どの関数や呼び出しに到達可能かについて、より強力な解析を構築し、残る境界を越えてより多くの情報を流せるようにします。 + +## インライン化 + +関数値をちょうど1つの呼び出しが使う関数を考えます。 + +```simple +val inc = { int x -> x+1; }; +return inc(arg); +``` + +この呼び出しが `inc` にリンクすると、CallEnd は、呼び出し先が1つで、その関数ポインタにほかの使用がないことを証明できます。引数が有効で自己再帰呼び出しがなければ、関数本体を呼び出し元の一部にできます。 + +| インライン化前 | インライン化後 | +|---|---| +| ![呼び出しは inc のパラメータに arg を供給し、その和を受け取る。](inline-before.svg) | ![同じ Add が arg を直接使い、main の return に供給する。](inline-after.svg) | + +これらはグラフの模式的な断片で、書き換え前後でノード ID は変わりません。引数、結果、リンクのエッジを示し、周囲の制御フロー、メモリ、RPC の配線は省略しています。`Parm_x` への `int` 入力は、インライン化前の未知の呼び出し元の引数を表します。 + +書き換えは未知の呼び出し元の経路を取り除き、関数入口を呼び出しの流入制御につなぎます。その後、通常の Region と Phi の簡略化がパラメータを実引数に置き換えます。CallEnd の射影は、呼び出された関数の返す制御、メモリ、値になります。Call、関数境界、復帰地点の仕組みは、使用が消えるにつれて消えます。 + +Add は残りますが、今度は `arg` を直接消費します。引数が `3` なら、第2章から使っている同じ定数畳み込み規則によって `4` を生成します。インライン化で露出した Load と Store も、既存のメモリ規則で同じように簡略化できます。 + +この形のインライン化は、呼び出し元が1つの本体をその呼び出し元へ移動します。複数の呼び出し箇所のために本体を複製するわけではありません。`fact` のような再帰関数は呼び出しを保持し、評価器が処理します。 + +## スケジューリングと実行 + +この章で新しく導入する [CodeGen](../../src/main/java/com/seaofnodes/simple/CodeGen.java) は、コンパイル処理と関数の検索テーブルを所有します。次のフェーズ順序を強制します。 + +| フェーズ | 目的 | +|---|---| +| Parse | 関数と呼び出しを直接 IR に構築する。 | +| Opto | 呼び出しのリンクと自明なインライン化を含め、ピープホール最適化を反復する。 | +| TypeCheck | 型と死んだ制御が落ち着いた後で、生き残ったグラフをチェックする。 | +| Schedule | 大域的コード移動で演算を基本ブロックに配置する。 | +| LocalSched | 実行のために各ブロック内の演算を順序付ける。 | + +例: + +```java +CodeGen code = new CodeGen("val sq = { int x -> x*x; }; return sq(arg);"); +code.parse().opto().typeCheck().GCM().localSched(); +``` + +大域的コード移動は、[第13章](../chapter13/README.ja.md)の処理を複数の関数に拡張します。関数本体を別々に保ち、共有される定数式には、それを使う各関数内に局所的なコピーを与え、呼び出しをまたぐメモリへの作用を尊重します。 + +その後 [ListScheduler](../../src/main/java/com/seaofnodes/simple/ListScheduler.java) が各ブロックを順序付けます。未スケジュールの局所依存を数え、準備のできた演算を選び、依存が満たされるにつれてそのユーザーを準備済みにします。Phi は入口に、制御移動は出口に属します。ここには機械のタイミングモデルがなく、さまざまな改善の余地がありますが、この章の範囲外です。目標は、引き続き合法な実行順序です。 + +[Eval2](../../src/test/java/com/seaofnodes/simple/Eval2.java) はそのスケジュールを実行し、IR の演算を、無制限の値スロットを持つ命令として扱います。各呼び出しには独自のフレームがあるため、同じノードの再帰的な呼び出しも異なる値を保持します。呼び出し時には、呼び出し元のフレームと復帰地点を保存し、呼び出される側のフレームを作り、選ばれた関数に移ります。return 時には呼び出し元を復元し、その CallEnd に値を渡します。Region では、結果を代入する前に、選ばれたすべての Phi 入力を読みます。そのため並列代入は正しさを保ちます。 + +これでスケジュールされた関数からなる実行可能なプログラムができましたが、演算はまだ機械に依存しません。[第19章](../chapter19/README.ja.md)では、スケジューリング前に命令選択を挿入します。これらの理想的な演算は、選んだ CPU のレジスタ制約と呼び出し規約を持つ命令になります。 diff --git a/docs/chapter18/README.md b/docs/chapter18/README.md new file mode 100644 index 00000000..1306efb5 --- /dev/null +++ b/docs/chapter18/README.md @@ -0,0 +1,363 @@ +# Chapter 18: Functions and Calls + +English | [日本語](README.ja.md) + +[Previous: Chapter 17b](../chapter17b/README.md) | +[Next: Chapter 19](../chapter19/README.md) + +Through Chapter 17b, a program has one body, with an input `arg` and a result. +We can branch, loop, allocate objects, and update memory, but cannot yet break +up the program into functions. This chapter adds function values and calls, +including recursive calls. + +The graph representation builds on familiar pieces. A function entry is a +Region, its parameters are Phis, and its exits merge into one Return. Calls +connect these pieces across function boundaries. When a function has just one +caller, removing that boundary lets ordinary peepholes simplify the combined +graph: this is our first form of inlining. + +Here is the [complete language grammar](18-grammar.md) for this chapter. + +## Table of Contents + +1. [Writing functions](#writing-functions) +2. [Functions in the graph](#functions-in-the-graph) +3. [Memory across calls](#memory-across-calls) +4. [Function types and call targets](#function-types-and-call-targets) +5. [Inlining](#inlining) +6. [Scheduling and execution](#scheduling-and-execution) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter18) 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-chapter17b...linear-chapter18) it to the previous chapter. + +## Writing functions + +A function expression lists typed parameters, followed by `->` and a body: + +```simple +val sq = { int x -> x*x; }; +return sq(arg); +``` + +The initializer creates a function value; the declaration binds it to `sq`. +The call `sq(arg)` evaluates its argument, executes the body with that value +bound to `x`, and yields the result. The final expression supplies the result +when execution reaches the end of the body. An explicit `return` can exit +earlier. + +A function type lists the parameter types and result type, without parameter +names. The same square function can be declared with an explicit type: + +```simple +{int -> int} sq = { int x -> x*x; }; +return sq(4); // 16 +``` + +Functions are anonymous values. Assigning one to a variable can give it a name +for diagnostics, but the binding follows the same rules as other variables. +`val` infers a fixed binding; `var` infers a reassignable one. Functions can +be passed as arguments, returned as results, and selected by expressions. + +Parameters use the explicit declaration syntax from +[Chapter 17a](../chapter17a/README.md): `!Point p` allows writes through a fixed +parameter binding, `Point !p` allows reassignment of a read-only reference, +and `int ~limit` fixes a primitive parameter. Parameter types are required; +`var` and `val` apply to the variable holding a function, not its parameters. + +### Returns and scope + +The body has the same statements as the surrounding language. Here an early +return finds the first matching array element: + +```simple +val find = { int[] es, int e -> + for( int i=0; i x+offset; }; +return addOffset(arg); +``` + +Changing `val offset` to `int offset` makes the binding mutable and the function +definition is rejected. Likewise, `val offset = arg` is fixed but not constant, +so it cannot be used from the nested function. Fixed function constants satisfy +this rule, allowing one function to refer to another without capturing a frame. + +### Recursion + +A function can refer to its own binding: + +```simple +val fact = { int n -> + n <= 1 ? 1 : n*fact(n-1); +}; +return fact(arg); +``` + +The parser registers the function entry before parsing its body. A forward +reference to `fact` is resolved when the declaration receives its function +value. Recursive calls can then find the same entry as calls from outside. +Return-type inference is still pessimistic in this chapter; mutually recursive +definitions can require the stronger analysis introduced with SCCP in +[Chapter 24](../chapter24/README.md). + +## Functions in the graph + +Until now, `Start` supplied the input to one program body. We now parse that +body as an implicit `main` with an integer parameter `arg`. The evaluator +enters `main` from `Start` and delivers its result to the outside world. +Existing programs therefore keep their source syntax while acquiring the same +function representation as explicitly declared functions. + +### Entries, parameters, and exits + +[FunNode](../../src/main/java/com/seaofnodes/simple/node/FunNode.java) extends +`RegionNode`. Where a Region merges control from different branches, a Fun +merges control from different callers. A linked call supplies one incoming +control edge. + +[ParmNode](../../src/main/java/com/seaofnodes/simple/node/ParmNode.java) extends +`PhiNode`. Each parameter selects the argument belonging to the incoming call, +just as a Phi selects the value belonging to an incoming branch. The parameter +index identifies what the caller supplies: + +| Parameter index | Value | +|---|---| +| 0 | Return point: where execution resumes in the caller | +| 1 | Whole memory | +| 2 onward | Source-language arguments | + +Each function also has an implicit unknown caller, represented by `Start`. +It supplies the declared parameter types and unknown memory. This keeps the +entry conservative while calls are still being discovered. + +Every source-level `return` contributes to one exit Region. A value Phi merges +the results, and a BulkMemPhi merges their memory states. The resulting +[ReturnNode](../../src/main/java/com/seaofnodes/simple/node/ReturnNode.java) has inputs +`{control, memory, value, return point}`. A single exit often folds away the +Region and Phis. `Stop` retains the functions' Returns, including `main`'s. + +This gives each function a single entry and a single merged exit even when its +body contains branches, loops, and several return statements. + +### Calls and return points + +[CallNode](../../src/main/java/com/seaofnodes/simple/node/CallNode.java) takes inputs +`{control, memory, arguments..., function pointer}`. The final input determines +the target; it can be a constant function or the result of a function-valued +expression. Argument expressions are evaluated before the Call takes its +control and memory inputs. + +Each Call has a [CallEndNode](../../src/main/java/com/seaofnodes/simple/node/CallEndNode.java), +the point where its caller continues. CallEnd takes the Call and the Returns +of linked targets as inputs. Its projections provide control, memory, and the +result, in slots 0, 1, and 2 respectively. + +The callee needs to know which CallEnd to return to. Its hidden parameter 0 +carries that return point through the body to the Return. `TypeRPC`, short for +*return program counter*, describes sets of possible return points, much as +function-pointer types describe sets of possible entries. These are internal +values; a source program does not declare RPC variables. + +Call-graph edges describe which functions a call may reach. They are distinct +from the control flow within one function: walking the graph typically requires +taking care around calls and functions, as most walks are only valid from within +a single function. + +## Memory across calls + +Earlier chapters split memory lazily by field alias. That still happens within +a function, but a function's entry memory is unknown: an argument may refer to +an object allocated and modified by its caller. We can no longer assume that +the incoming heap is empty. + +A Call receives the complete memory state, including any slices packaged in a +MemMerge. Its CallEnd produces a new whole-memory value. This chapter treats +every call as potentially modifying every alias; knowing which function is +called does not yet provide a summary of which fields it writes. + +```simple +struct Counter { int n; }; +val bump = { !Counter p -> p.n++; return null; }; +val p = new Counter; +int before = p.n; +bump(p); +bump(p); +return before*10+p.n; // 2 +``` + +The first read of `p.n` observes its initialized value. The final read must use +memory after both calls; it cannot reuse the first read. The two calls also +remain ordered by their memory inputs and outputs. The writable parameter +permission allows the updates, while the memory edges record when they occur. + +Inside a function, MemMerge, MemPhi, and BulkMemPhi continue to expose precise +slices and merge branch or loop states. At the boundary, memory Parm 1 and the +CallEnd memory result stay opaque. Global code motion respects a call as a +possible writer when placing Loads. Calls end their blocks, so a Load that +must precede a Call is scheduled before that terminator. + +Inlining removes the call boundary and exposes its actual Loads and Stores +to the existing alias optimizations. More precise effects for calls that remain +in the graph require later escape analysis. + +## Function types and call targets + +[TypeFunPtr](../../src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java) records +an argument tuple, a result type, nullability, and a set of function indices +(`fidxs`). Within an argument signature, each function gets a small integer +index. A bit set can then describe one known function or several possible +functions with that signature. `CodeGen` maps a concrete function identity to +its FunNode; no machine code address is needed to execute this chapter's IR. + +For example, both arms below have type `{int -> int}`, but different function +indices: + +```simple +val f = arg ? { int x -> x+x; } : { int x -> x*x; }; +return f(3); // 6 when arg is nonzero, otherwise 9 +``` + +The Phi for `f` combines the two function-pointer types. Its set of targets +contains both functions; choosing a function does not execute its body. + +Function pointers can also be nullable, using the familiar `?` suffix: + +```simple +{int -> int}? f = arg ? { int x -> x*x; } : null; +if( f ) return f(3); +return 0; +``` + +The guard proves the pointer non-null at the call. A call also checks its +argument count, types, and access permissions. Struct pointers and function +pointers share the distinguished `null` value, represented by `Type.NIL`; +`TypeNil` supplies their common nullability machinery. + +### Linking known targets + +Here *linking* means adding IR edges between a call and a function. It is not +object-file linking. For each known target, the compiler adds the Call as an +input to the Fun, adds arguments to its Parms, and adds its Return as an input +to the CallEnd. Corresponding input positions preserve the relationship +between a caller and its arguments. + +This chapter already links finite sets of known targets, including both +functions in the conditional example above. The infinite set that still +includes unknown functions cannot be enumerated. We avoid representing that +uncertainty with edges from every call to every function, which would grow +quadratically. + +Instead, a Fun retains its *unknown-caller* input. Its parameters must accept +their declared types even when the calls found so far pass constants. Finding +one caller is not proof that no other callers exist! Similarly, CallEnd obtains +its result type from the function-pointer type and keeps its memory result +unknown. Linked Return edges alone do not remove these conservative assumptions. + +Inlining relies on a local proof that a function has only one caller. The later +SCCP chapter develops stronger analysis of which functions and calls are +reachable, allowing more information to flow across boundaries that remain. + +## Inlining + +Consider a function whose value is used by exactly one call: + +```simple +val inc = { int x -> x+1; }; +return inc(arg); +``` + +Once this call links to `inc`, CallEnd can prove that it has one target and +that the target has no other uses of its function pointer. With valid +arguments and no self-recursive call, the function body can become part of +the caller. + +| Before inlining | After inlining | +|---|---| +| ![The call supplies arg to inc's parameter and receives its sum.](inline-before.svg) | ![The same Add uses arg directly and supplies main's return.](inline-after.svg) | + +These are schematic slices of the graph, with stable node IDs across the +rewrite. They show the argument, result, and linking edges; the surrounding +control flow, memory, and RPC plumbing are omitted. The `int` input to `Parm_x` +represents the unknown caller's argument before inlining. + +The rewrite removes the unknown-caller path and connects the function entry to +the call's incoming control. Ordinary Region and Phi simplifications then +replace the parameter with the actual argument. CallEnd's projections become +the callee's returned control, memory, and value. The Call, function boundary, +and return-point machinery disappear as their uses disappear. + +The Add remains, but now consumes `arg` directly. If the argument had instead +been `3`, the same constant-folding rules used since Chapter 2 would produce +`4`. Loads and Stores exposed by inlining can similarly simplify using the +existing memory rules. + +This form of inlining moves a body with one caller into that caller; it does +not clone the body for several call sites. A recursive function such as +`fact` retains its calls and is handled by the evaluator. + +## Scheduling and execution + +New in this chapter is +[CodeGen](../../src/main/java/com/seaofnodes/simple/CodeGen.java) which owns the +compilation process and its function lookup table. It enforces the phase order: + +| Phase | Purpose | +|---|---| +| Parse | Build the functions and calls directly in the IR. | +| Opto | Iterate peepholes, including call linking and trivial inlining. | +| TypeCheck | Check the surviving graph after types and dead control have settled. | +| Schedule | Use global code motion to place operations in basic blocks. | +| LocalSched | Order operations within each block for execution. | + +For example: + +```java +CodeGen code = new CodeGen("val sq = { int x -> x*x; }; return sq(arg);"); +code.parse().opto().typeCheck().GCM().localSched(); +``` + +Global code motion extends the work of [Chapter 13](../chapter13/README.md) to +multiple functions. It keeps their bodies separate, gives shared constant +expressions a local copy in each function that uses them, and respects memory +effects across calls. + +[ListScheduler](../../src/main/java/com/seaofnodes/simple/ListScheduler.java) then +orders each block. It counts unscheduled local dependencies, chooses a ready +operation, and makes its users ready as their dependencies are satisfied. Phis +belong at entry and control transfers at exit. There is room for all sorts of +improvements - there is no machine timing model here, but this is out of scope +for this chapter. The goal remains a legal execution order. + +[Eval2](../../src/test/java/com/seaofnodes/simple/Eval2.java) executes that schedule, +treating IR operations as instructions with an unlimited supply of value +slots. Each invocation has its own frame, so recursive invocations of the same +nodes keep distinct values. At a call it saves the caller's frame and return +point, creates a callee frame, and transfers to the selected function. At a +return it restores the caller and delivers the value to its CallEnd. At a +Region, it reads all selected Phi inputs before assigning any results, so +parallel assignments remain correct. + +We now have an executable program made of scheduled functions, still expressed +in machine-independent operations. [Chapter 19](../chapter19/README.md) inserts +instruction selection before scheduling: those ideal operations become +instructions for a chosen CPU, with its register constraints and calling +convention. diff --git a/docs/chapter18/font-awesome-4.7.0.zip b/docs/chapter18/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter18/font-awesome-4.7.0.zip differ diff --git a/docs/chapter18/inline-after.json b/docs/chapter18/inline-after.json new file mode 100644 index 00000000..64e36e97 --- /dev/null +++ b/docs/chapter18/inline-after.json @@ -0,0 +1,101 @@ +{ + "ver": 1, + "comp": "inline", + "step": 2, + "roots": [ + 12 + ], + "scope": 0, + "nodes": [ + { + "id": 1, + "label": "Parm_arg", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 2, + "label": "Con", + "type": "1", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 8, + "label": "Add", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 1, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 2, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 12, + "label": "Return main", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 8, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/docs/chapter18/inline-after.svg b/docs/chapter18/inline-after.svg new file mode 100644 index 00000000..f376ce7f --- /dev/null +++ b/docs/chapter18/inline-after.svg @@ -0,0 +1,81 @@ +#8[1] → #1 · DATA#8[2] → #2 · DATA#12[2] → #8 · DATAParm_arg  #1int#1 Parm_arg +int + +[0] → — ASSOC +[1] → — DATA01Con  #21#2 Con +1 + +Add  #8int#8 Add +int + +[0] → — CTRL +[1] → #1 DATA +[2] → #2 DATA012Return main  #12#12 Return main +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #8 DATA +[3] → — DATA0123 diff --git a/docs/chapter18/inline-before.json b/docs/chapter18/inline-before.json new file mode 100644 index 00000000..243aff79 --- /dev/null +++ b/docs/chapter18/inline-before.json @@ -0,0 +1,276 @@ +{ + "ver": 1, + "comp": "inline", + "step": 1, + "roots": [ + 12 + ], + "scope": 0, + "nodes": [ + { + "id": 1, + "label": "Parm_arg", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 2, + "label": "Con", + "type": "1", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 3, + "label": "Con inc", + "type": "{int -> int}", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 4, + "label": "Call", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 1, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 3, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 5, + "label": "inc", + "type": null, + "kind": "FUN", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 2, + "def": 4, + "role": "CTRL", + "label": null + } + ], + "proj": null + }, + { + "id": 6, + "label": "Con", + "type": "int", + "kind": "DATA", + "edges": [], + "proj": null + }, + { + "id": 7, + "label": "Parm_x", + "type": "int", + "kind": "PHI", + "edges": [ + { + "idx": 0, + "def": 5, + "role": "ASSOC", + "label": null + }, + { + "idx": 1, + "def": 6, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 1, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 8, + "label": "Add", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 7, + "role": "DATA", + "label": null + }, + { + "idx": 2, + "def": 2, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 9, + "label": "Return inc", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 8, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 10, + "label": "CallEnd", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 4, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 9, + "role": "DATA", + "label": null + } + ], + "proj": null + }, + { + "id": 11, + "label": "result", + "type": "int", + "kind": "DATA", + "edges": [ + { + "idx": 0, + "def": 10, + "role": "DATA", + "label": null + } + ], + "proj": { + "par": 10, + "idx": 2 + } + }, + { + "id": 12, + "label": "Return main", + "type": null, + "kind": "CTRL", + "edges": [ + { + "idx": 0, + "def": 0, + "role": "CTRL", + "label": null + }, + { + "idx": 1, + "def": 0, + "role": "MEM", + "label": null + }, + { + "idx": 2, + "def": 11, + "role": "DATA", + "label": null + }, + { + "idx": 3, + "def": 0, + "role": "DATA", + "label": null + } + ], + "proj": null + } + ], + "groups": [] +} diff --git a/docs/chapter18/inline-before.svg b/docs/chapter18/inline-before.svg new file mode 100644 index 00000000..8e15f6ea --- /dev/null +++ b/docs/chapter18/inline-before.svg @@ -0,0 +1,117 @@ +#4[2] → #1 · DATA#4[3] → #3 · DATA#5[2] → #4 · CTRL#7[1] → #6 · DATA#7[2] → #1 · DATA#8[1] → #7 · DATA#8[2] → #2 · DATA#9[2] → #8 · DATA#10[0] → #4 · CTRL#10[1] → #9 · DATA#12[2] → #11 · DATAParm_arg  #1int#1 Parm_arg +int + +[0] → — ASSOC +[1] → — DATA01Con  #21#2 Con +1 + +Con inc  #3{int -> int}#3 Con inc +{int -> int} + +Call  #4#4 Call +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #1 DATA +[3] → #3 DATA0123inc  #5#5 inc +Type not computed + +[0] → — ASSOC +[1] → — CTRL +[2] → #4 CTRL012Con  #6int#6 Con +int + +Parm_x  #7int#7 Parm_x +int + +[0] → #5 ASSOC +[1] → #6 DATA +[2] → #1 DATA[0] → #5012Add  #8int#8 Add +int + +[0] → — CTRL +[1] → #7 DATA +[2] → #2 DATA012Return inc  #9#9 Return inc +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #8 DATA +[3] → — DATA0123CallEnd  #10#10 CallEnd +Type not computed + +[0] → #4 CTRL +[1] → #9 DATA01result  #11/2int#11 result +Projection 2 of #10 +int + +[0] → #10 DATAReturn main  #12#12 Return main +Type not computed + +[0] → — CTRL +[1] → — MEM +[2] → #11 DATA +[3] → — DATA0123 diff --git a/docs/chapter18/lattice.gv b/docs/chapter18/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter18/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/chapter18/lattice.svg b/docs/chapter18/lattice.svg new file mode 100644 index 00000000..030f4826 --- /dev/null +++ b/docs/chapter18/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/chapter18/lattice2.gv b/docs/chapter18/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter18/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/chapter18/lattice2.svg b/docs/chapter18/lattice2.svg new file mode 100644 index 00000000..857bca2d --- /dev/null +++ b/docs/chapter18/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/chapter18/webtcp.min.js b/docs/chapter18/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter18/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