From 8309071562b63f77a15425ab2146e05dbcb5acfd Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 6 May 2025 13:44:10 -0700 Subject: Chapter 23: Methods and Revisiting Types MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- docs/chapter23/23-grammar.ja.md | 168 ++++++++ docs/chapter23/23-grammar.md | 168 ++++++++ docs/chapter23/Makefile | 12 + docs/chapter23/README.ja.md | 345 +++++++++++++++ docs/chapter23/README.md | 483 +++++++++++++++++++++ docs/chapter23/examples/A_helloWorld.smp | 3 + docs/chapter23/examples/BubbleSort.smp | 37 ++ docs/chapter23/font-awesome-4.7.0.zip | Bin 0 -> 669808 bytes docs/chapter23/ifg_trim.pdf | Bin 0 -> 155190 bytes docs/chapter23/lattice.gv | 203 +++++++++ docs/chapter23/lattice.svg | 691 +++++++++++++++++++++++++++++++ docs/chapter23/lattice2.gv | 85 ++++ docs/chapter23/lattice2.svg | 260 ++++++++++++ docs/chapter23/pardoe.docx | Bin 0 -> 22583 bytes docs/chapter23/webtcp.min.js | 65 +++ 15 files changed, 2520 insertions(+) create mode 100644 docs/chapter23/23-grammar.ja.md create mode 100644 docs/chapter23/23-grammar.md create mode 100644 docs/chapter23/Makefile create mode 100644 docs/chapter23/README.ja.md create mode 100644 docs/chapter23/README.md create mode 100644 docs/chapter23/examples/A_helloWorld.smp create mode 100644 docs/chapter23/examples/BubbleSort.smp create mode 100644 docs/chapter23/font-awesome-4.7.0.zip create mode 100644 docs/chapter23/ifg_trim.pdf create mode 100644 docs/chapter23/lattice.gv create mode 100644 docs/chapter23/lattice.svg create mode 100644 docs/chapter23/lattice2.gv create mode 100644 docs/chapter23/lattice2.svg create mode 100644 docs/chapter23/pardoe.docx create mode 100644 docs/chapter23/webtcp.min.js (limited to 'docs/chapter23') diff --git a/docs/chapter23/23-grammar.ja.md b/docs/chapter23/23-grammar.ja.md new file mode 100644 index 00000000..682bd967 --- /dev/null +++ b/docs/chapter23/23-grammar.ja.md @@ -0,0 +1,168 @@ +# 第23章の文法 + +[English](23-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)* ; + +// Compare adjacent operands once; stop after the first false comparison. +// Keep one direction per chain; < and <= (or > and >=) may mix. +comparisonExpression + : shiftExpression (('<' | '<=') 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/chapter23/23-grammar.md b/docs/chapter23/23-grammar.md new file mode 100644 index 00000000..cd231b08 --- /dev/null +++ b/docs/chapter23/23-grammar.md @@ -0,0 +1,168 @@ +# Grammar for Chapter 23 + +English | [日本語](23-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)* ; + +// Compare adjacent operands once; stop after the first false comparison. +// Keep one direction per chain; < and <= (or > and >=) may mix. +comparisonExpression + : shiftExpression (('<' | '<=') 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/chapter23/Makefile b/docs/chapter23/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter23/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/chapter23/README.ja.md b/docs/chapter23/README.ja.md new file mode 100644 index 00000000..62b69094 --- /dev/null +++ b/docs/chapter23/README.ja.md @@ -0,0 +1,345 @@ +# 第23章: メソッドと型の再検討 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第22章](../chapter22/README.ja.md) | +[次の章: 第24章](../chapter24a/README.ja.md) + +この章では *メソッド* を追加します。構造体内で定義し、隠れた `self` 引数を取り、構造体のフィールドへアクセスできる関数です。文字列のようなクラスの `indexOf` メソッドを示します。 + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i int } indexOf; }` + +これは `String` という名前の型で、フィールド `u8[~] buf` と、final で代入済みの定数フィールド `indexOf` を持ちます。後者自身の型は `{ !String !self, u8 c -> int }` です。つまり `String` の型は、`indexOf` の型の内側に自分自身への参照を持ちます。`String` の型は *循環* しています。 + +## 循環の少ない型 + +循環する型の問題は古くからあり、対処のための実績ある方法がいくつもあります。簡単なものの1つは、型の *定義* と、それとは別の型の *参照* を持つ方法です。参照は何らかの検索で型を参照します。たとえば型名とパーサーのシンボル表を使う、ハッシュ表検索です。 + +このモデルでは循環を実質的に回避します。型の循環内の「後退辺」は、すべて参照辺、場合によってはハッシュ表検索で実現します。 + +では、なぜこの方法を採用しないのでしょうか。 + +すべての型参照が同じ型定義へ戻るためです。型情報を特化しても失われます。*すべての* 参照が同じ定義へ戻るため、*すべての* 経路の MEET を取ることになるのです。 + +Java の `Object`、または C の `void*` をデータとして持つ連結リストの例を示します。 + +```java +struct List { + !List !next; + Object payload; // equivalently for C: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +`nums` の型は何でしょうか。`*List`、つまり次の型です。 + +``` +struct List { List *next; Object payload } +``` + +`Object` を `int` や `String` に精密化できません。すべての List オブジェクトのデータ型は `Object` で、`Object` MEET `int` は `Object` に戻るためです。 + +真に循環する型を許せば、このような場面で `*List { *List next, int payload }` という精密な型を発見、あるいは推論できます。基本的に最適化器内で *ジェネリクス* を構築するのです。言語のジェネリクスや型変数そのものではありませんが、それにかなり近づきます。 + +## 循環する型の扱い + +この章で Simple は循環する型を直接扱います。子の型が元の型へ戻る `Type` オブジェクトを持つため、型に対して [*再帰下降*](https://en.wikipedia.org/wiki/Recursive_descent_parser) がそのままでは使えなくなります。 + +これまでは型構築に再帰下降を使ってきました。子の型を先に作ってインターンし、インターン済みの子で次の階層を構築します。各階層がインターンされ、再帰下降がインターン済みの型で止まるので、共有する型での重複作業を避けられます。このため現在の型に対する演算は、旧型と新型の *差分* に対して線形となり、増分的で高速です。 + +新たな循環する型では、循環全体を見るまでインターンできない問題に直面します。またハッシュ表は等値検査を必要としますが、循環を等値比較するのに通常の再帰下降は使えません。 + +グラフの循環を扱う標準的な方法は、「以前ここに来た」ことを示す *訪問済み* の概念です。一意な型 ID をキーにするハッシュ表を使います。「訪問済み」は、一意な ID が表のキーにあるという意味です。各 Type は大域カウンタから一意な ID を得ます。型をインターンするので、必要な一意 ID 数は一意な型の数と、循環を構築・インターンするためのわずかな予備だけです。過去の経験では通常数千程度が最大なので、小さな整数で十分です。 + +もう1つ、既存の基盤をできる限り残したいので、既存の再帰下降による巡回を少しだけ修正してすべて保持します。 + +すべての型循環には `TypeStruct` が存在します。ただし関数が *自身* を引数に取る純粋な関数型の循環は例外です。それは奇妙なので、どう扱うかはそれほど気にしません。各 `TypeStruct` 生成器の中核で大域 `VISIT` ハッシュ表に要素を設定し、循環型作成の開始を示します。そしてその要素を検査し、循環を止めます。 + +例を見ましょう。 + +異なるデータ型の循環を持つかもしれない連結リストを使います。ただし、ここでは文字列だけです。連結リストは、簡単な代替と比べてひどく非効率なので、ほぼどんな仕事でも間違った構造であることが多いのですが、教材用のデータ構造としては優れています。 + +```java +struct List { + !List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +この構造体の型は宣言に一致します。 + +`struct List { List*? next, str !name };` + +これで文字列リストを構築できます。 + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + +### 循環する型の読み取り専用／final の検査 + +どこかで読み取り専用の不変な版を作りたいとします。 + +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +`hello` の型は何でしょうか。`List` の読み取り専用型です。しかし `List` は循環する型です。`Type.makeRO` を見ましょう。 + +> 訳注：原文では上の `val hello = list` を読み取り専用版の作成と説明しています。一方、第17b章では `val` は束縛を固定し、初期化式のアクセス権限を保持すると説明しています。この訳では、原文の例と説明を保持しています。 + +```java +public final Type makeRO() { + if( isFinal() ) return this; // First check if already read-only + return recurOpen()._makeRO().recurClose(); +} +``` + +そして `isFinal()`: + +```java +// Are all reachable struct Fields are final? +public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); } +boolean _isFinal() { assert _type < TCYCLIC; return true; } +``` + +`recurOpen()` を呼んで再帰走査を開始／開き、`_isFinal()` を呼びながら再帰し、走査を終了／閉じて、真偽値を返します。`_isFinal()` は Java の final ではなく、Type のサブクラスでオーバーライドします。大半のサブクラスは単に問題を転送します。 + +`@Override boolean _isFinal() { return _obj._isFinal(); }` + +そして `TypeStruct` に到達します。 + +```java +@Override boolean _isFinal() { + if( _open ) return false; // May have more non-final fields + if( VISIT.containsKey(_uid) ) // Test: been here before? + return true; // Cycles assume final + VISIT.put(_uid,this); // Set: don't do this again + for( Field fld : _fields ) + if( !fld._isFinal() ) + return false; + return true; +} +``` + +ここには循環処理の共通パターン、**test-and-set** があります。まず確定できる答えを調べます。開いた構造体は部分的にしか定義されず、未解析の non-final フィールドが現れる可能性があるので、決して読み取り専用ではありません。次に以前訪問したかを **検査** し、そうなら再帰を止めて何らかの答えを返します。`isFinal` では、循環のほかのものもすべて final なら「final である」を返します。 + +まだこの型を調べていなければ、ここを訪れたことを示す訪問ビットを **設定** し、通常の再帰下降でフィールドに同じ質問をします。 + +この例では、`VISIT` に番兵を置いて再帰を開き、`struct List` に `makeRO` を呼びます。それが `_isFinal` を呼び、`_open`（開いていない）、`VISIT`（未訪問）を確認し、UID を `VISIT` に設定してフィールドを走査します。フィールドの検査は次のとおりです。 + +`@Override boolean _isFinal() { return _final && _t._isFinal(); }` + +最初のフィールド `List*? !next` は non-final なので、すぐ `false` を返します。これで `List` の `_isFinal` が止まり、`isFinal()` 全体が `false` を返して再帰を終了／閉じます。`VISIT` もクリアします。 + +### 循環する読み取り専用／final 型の作成 + +構築してからインターンする手順を明確にするため、すべての型に一意 ID を付けましょう。一意な型の後ろに UID の例を付けた `List` 型を示します。フィールドも型なので UID を持ちます。 + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +同じ UID が繰り返されることから、`List#2` が2回現れています。List が循環しているためです。 + +今度は実際に循環する型を作る必要があり、`makeRO()` は次の行に進みます。 + +`return recurOpen()._makeRO().recurClose();`. + +再び `recurOpen` が再帰走査を開始／開き、それから子の Type クラスそれぞれでオーバーライドする `_makeRO()` を呼びます。`TypeStruct` 版を見ます。 + +```java +// Make a read-only version +@Override TypeStruct _makeRO() { + // Check for already visited + TypeStruct ts = (TypeStruct)VISIT.get(_name); + if( ts!=null ) return ts; // Already visited + ts = recurPre(_name,_open); // Make a new type with blank fields + Field[] flds = ts._fields; + for( Field fld : flds ) fld._final = true; + + // Now start the recursion + for( int i=0; i 訳注：原文の「all !fields !attached」は、続く説明と図に合わせて、フィールドの型が未設定である状態として訳しています。 + +``` +struct List#12 { + ____ next#14, + ____ name#15 +} +``` + +最後にすべてのフィールド型で `_makeRO` を再帰呼び出しし、設定します。`TypeMemPtr` に `_fields[i]._t._makeRO()` を呼ぶと、再帰する `List` の `_makeRO()` を呼んだ後に、新しい TMP を作ります。 + +この再帰は `TypeStruct._makeRO()` へ戻り、同じ型名で `VISIT` 表にヒットします。最初のフィールド設定を巻き戻すと、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + ____ name#15 +} +``` + +すべての型が新しい UID になっていることに注目してください。まだインターンできないので、以前の型にはできません。2番目のフィールド `str name` はすでに存在するため、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + str#2 name#15 // Reuse the interned type str#2 +} +``` + +ここで再帰を巻き戻し、複雑な `Type.recurClose()` に入ります。いくつかの例でコードを1ステップずつ実行してみるとよいでしょう。`TypeTest.testList` がこれらの型を構築します。高水準での概要は次のとおりです。 + +管理を容易にするため、訪問したすべての型を `VISIT` からコピーします。すでにインターン済みのものを発見したら後続の処理から除去しますが、HashMap 内にない方が簡単です。 + +**走査 #1:** 循環に属さない既存のインターン済み部分を探し、置き換えます。新しい型循環から古いインターン済み型へポインタが出ているのに、そのコピーを作ってしまっている場合があります。この段階の後も新しい循環は残りますが、出力辺は可能なら以前の型を指します。置き換えた型は、遅延した `FREES` リストへ入ります。 + +**走査 #2:** すべての型は *双対* を事前計算して直接使えるようにしています。ここで再帰的な循環する双対を作ります。 + +**走査 #3:** 新しい型を登録します。新しくインターンされた型への共通ポインタをここで発見する *可能性がある* ので、進みながら再び検査・置換し、使わない型を再度遅延 `FREES` リストへ入れます。この段階はハッシュ表検索を必要とし、それには循環ハッシュと循環 equals が必要です。 + +**走査 #4:** 遅延解放するすべての型をここで解放し、将来の型生成で再利用します。 + +最終的に、新しい `List` の循環型は完全にインターンされます。読み書き可能版 `List#2` は同じ読み書き可能版 `List#2` を指し、読み取り専用版 `List#12` は同じ読み取り専用版 `List#12` を指します。 + +### 循環する HashCode と Equals + +循環する `hashCode` と `equals` はさらに説明が必要です。2つの循環を等価比較するとき、比較の開始位置に関係なく等価であってほしいのです。つまり循環 `A<->B` は循環 `B<->A` と等しいべきです。両方のハッシュコードは同じでなければならず、順序で変化するハッシュは使えません。 + +たとえば A の静的ハッシュ値が1で、さらに B のハッシュから再帰的な成分があり、逆に B の静的値が3で A からの再帰成分があるとします。`parent.hash*7 + child.hash` で計算すると、A からは `A.hash * 7 + B.hash`、つまり `1 * 7 + 3 == 10` です。後で B から始めると `B.hash * 7 + A.hash`、つまり `3 * 7 + 1 == 22` になります。ハッシュが異なるため、ハッシュ表が等価性を見逃す可能性があります。また循環で単純に再帰下降すれば、スタックオーバーフローまで再帰してクラッシュします。 + +`TypeStruct.hash()` が再帰しないようにして解決します。そのためハッシュ関数はやや弱く、フィールド名とエイリアスだけに依存します。 + +*循環 equals* は `VISIT` 表が空でないことにより発動し、`VISIT` と関心を分離するため、別の訪問表 `CEQUALS` を使います。循環 equals 検査は通常の `eq` と同様、構成部分を再帰下降し、最初に確定的な静的検査を行い、再帰前にはおなじみの **test-and-set** を使います。 + +同じ2型を再び循環 equals で比較したら、ほかがすべて等しい限り、循環についても等しいと仮定します。 + +## メソッド、final フィールド、クラス + +メソッドは、構造体内で宣言され、暗黙の `self` 引数を取る、単なる関数値（final フィールド）です。 + +元の構造体定義で宣言した final フィールドは *値* であり、変化できません。すべてのインスタンスで同じです。構造体のメモリ占有部分から、final フィールドの値の集まりである *クラス* へ移動します。クラスは単なる名前空間で具体的な実装を持たず、実体化されません。 + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; + }; + + +}; + +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); +``` + +ここで `val add` フィールドは、定数関数値である *値* フィールドです。基本的な `vecInt` オブジェクトから `vecInt` の *クラス* へ移り、オブジェクト内で記憶領域を占めません。`_grow` も同様です。そのため `vecInt` インスタンスのサイズは、`u32` の長さと配列ポインタに、配置調整のパディングを加えたものです。配列ヘッダと要素は別の割り当てを占めます。拡張後の古いバッファの回収は、この例の範囲外です。`return primes.len*100+primes.buf[4];` を追加すると、RISC-V と ARM の両方で511になります。 + +## RegAlloc の改良: 多数の使用のグループ化 + +第22章では色の優先度と安いスピルの順序を改善しました。この章では、使用が互換性のないレジスタを要求する、よく使う値を分割する方法を追加します。たとえば複数のシフトが同じカウントレジスタを必要とし、別の使用が異なるレジスタを必要とする場合です。互換グループごとに1コピーを共有すると、使用ごとに別のコピーを挿入するのを避けられます。 + +割り当て器は、空のレジスタマスクと、2つより多い固定レジスタ使用を持つ、単一定義の区間にこれを適用します。重なる使用マスクの共通部分を取り、グループ化します。グループを狭めても以前の使用と互換なので、1走査で十分です。交わらないマスクは別グループにします。入力を接続し直す前に異なる使用側のスナップショットを取り、スケジューリング専用辺は無視し、値が複数引数を供給しても呼び出しを1回だけ数えます。 + +複数の呼び出しで使う値は、レジスタ破壊が共有コピーの利点を打ち消しがちなので、グループ化しません。すべての使用のループ深さが同じ場合に既存コピーを分割することも含め、通常のループ境界分割を代替として保持します。低頻度側を先にするループ分割は第24章、面積／コストのスピル順位付けは第25章に残します。 + +第21章の隣接コピー転送も引き継ぎます。彩色後、次の命令に唯一の使用がある場合、オペランドマスクが許し、2アドレスの結び付きを壊さなければコピー元レジスタを読めます。以下の表は、この整理と遅延メモリの前方移植を含みます。第22章の群には、以前の監査後に追加した移動0の C 戻り値 ABI 確認2件も含むようになりました（24ではなく26項目）。 + +このディレクトリで `make spill-stats` を実行してください。以下の全行は **この章のコンパイラ**、シード123、各群の固定されたソース／対象の組み合わせを使います。Windows 実行は x86 SystemV/Win64 と RISC-V/ARM SystemV を合わせます。診断マシングラフは別に確認し、数には寄与しません。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 323 | 442 | +| 第21章 | 52 | 433 | 965 | +| 第22章 | 26 | 67 | 67 | +| 第23章 | 30 | 78 | 225 | +| **合計** | **147** | **901** | **1,699** | + +`_spills` はレジスタ移動を含む残存 SplitNode を数え、`_spillScaled` は `8^loopDepth` で重み付けします。生成移動のコンパイラによる推定であり、実行時メモリアクセスではありません。報告器は個々のコンパイルと CPU/ABI 合計を表示し、スピル期待値や実行確認が失敗すれば、依然として失敗を報告します。 + +以前の監査では、隣接コピー転送前にグループ化を無効にしても、**同じ933移動／1,745重み付き移動** でした。元のグループ化コードも同じ合計です。したがってこのスイートには、グループ化によるスピル改善は見られません。縮小したマシングラフの回帰テストは、旧実装の null マスクによるクラッシュも含め、互換性と呼び出しの規則を検証します。もっともらしい割り当て器のヒューリスティックであっても、効果を主張するには、それが実際に適用される処理対象での測定が必要です。 + +以前の群だけでは、第22章コンパイラは838移動／1,496重み付き移動で、このコンパイラは849／1,514でした。この比較は割り当て以外の変更を含みます。特に第20章の固定した String 入力は、ここでは最適化後も残り16重み付き移動を要しますが、第22章はこのシードで除去しました。その差をグループ化に帰するのは誤解を招きます。 + +元の64ビット `person21` とガード付き `stringHash21` 入力は、第21章の群を維持します。改訂した String 入力とこの章で有効にした2つのエンコーディングテストは第23章の群に属します。群を固定することで、言語とテストが成長しても、以後の比較に意味が保たれます。 diff --git a/docs/chapter23/README.md b/docs/chapter23/README.md new file mode 100644 index 00000000..b91dc0b1 --- /dev/null +++ b/docs/chapter23/README.md @@ -0,0 +1,483 @@ +# Chapter 23: Methods and Revisiting Types + +English | [日本語](README.ja.md) + +[Previous: Chapter 22](../chapter22/README.md) | +[Next: Chapter 24a](../chapter24a/README.md) + +In this chapter we add *methods*, functions defined in structs which take a +hidden `self` argument and can access the struct fields. Here is an +`indexOf` method in a String-like class: + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i= b > c` are allowed; `a < b > c` is rejected. Equality +has lower precedence and does not join a chain. Parentheses can still make +the result of one comparison an operand of another. + +## Why Cyclic Types? + +Cyclic types give us a sharper analysis than the alternative, and thus admit +more programs or better optimizations or both. In Simple's case Types are also +used for type-checking, so sharper types means we allow more valid programs. + +**Why Cyclic Types Now**? Because we hit them as soon as we allow a +function definition inside of a struct which takes the struct as an argument, +i.e. *methods* taking a *self* argument. + +Let's look at our `String.indexOf` example above. Here we define a `String` +with an `indexOf` method; a hidden argument string `self` is passed in +and searched. What is the type of `struct String`? + +`struct String { u8[~] buf; { !String !self, u8 c -> int } indexOf; }` + +It is the type named `String` with a field `u8[~] buf` and a final assigned +constant field `indexOf`, itself with type `{ !String !self, u8 c -> int }`. +i.e., the type of `String` has a reference to itself, nested inside the type of +`indexOf`.... i.e. `String`'s type is *cyclic*. + + +## Less Cyclic Types + +This problem of cyclic types has been around for a long time, and there are a +number of tried and true methods for dealing with them. One easy one is to +have a type *definition* and a separate type *reference*. The reference refers +to the type by doing some kind of lookup; an easy one is via the type name and +the parser's symbol table i.e., some kind of hash table lookup. + +In this model the cycle is effectively avoided; all "back edges" in the type +cycle are really done by the reference edge (itself possibly a hash table +lookup). + +So why not go down this route? + +Because all type references lead back to the same type definition - which +means any specialization of type information is lost, because *all* type +references lead back to the same definition and you end up taking the MEET +over *all* paths. + +Here's an example, a Linked List with a Java `Object` or a C `void*` payload: + +```java +struct List { + !List !next; + Object payload; // equivalently for C: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +What is the type of `nums`? It's `*List`... which is: + +``` +struct List { List *next; Object payload } +``` + +No sharpening of `Object` to `int` nor `String` because every List object +has a payload of `Object` and `Object` MEET `int` is back to `Object`. + +If we allow truly cyclic types then in these kinds of places we can discover +(or infer) a sharper type: `*List { *List next, int payload }` +basically building up *generics* in the optimizer. This is not generics in the +language nor type-variables per-se, but it goes a long way towards them. + + +## Handling cyclic types + +In this Chapter Simple handles cyclic types directly. This means we have +`Type` objects whose child types can point back to the original - and that +means +[*recursive descent*](https://en.wikipedia.org/wiki/Recursive_descent_parser) +no longer works on Types. + +Up till now we've used recursive descent when building up Types: child types +are built first, then interned, then the interned children are used to build up +the next layer. Because each layer is interned and because recursive descent +stops at interned Types we avoid repeating work at shared Types. This makes +operations on the current Types linear in the *delta* between the old and new +Types, i.e. incremental and fast. + +With the new cyclic types we now run into the problem that we cannot intern a +cycle until we see the whole cycle. Also hash tables require an equality +check and we cannot use recursive descent to compare a cycle for equality. + +The standard way to deal with cycles in a graph is with some kind of *visited* +notion, a "I have been here before" indicator. We will use a hashtable keyed +from a unique type ID; "visited" just means your unique ID is a key in the +table. Every Type thus picks up a unique ID from a global counter. Since we +will be interning Types we only need as many unique IDs as we have unique Types +(plus a few spare to build and intern cycles). From prior history I know this +number typically maxes out in the low thousands so a small integer will do. + +Another thing - we want to keep as much of our existing infrastructure as +we can, so we are going to keep all our existing recursive descent visitations +with some small modifications. + +`TypeStructs` exist in every Type cycle (except pure function type cycles, +where a function takes *itself* as an argument, which are weird and we kinda +don't care how they get handled). So in the core part of every `TypeStruct` +generator we'll set an element in a global `VISIT` hashtable to signal the +start of a cyclic Type creation - and we'll check for those elements to stop +cycling. + + + + +Time for an example! + +Let's go with a linked list, where we might have cycles of unrelated payloads +(but here only strings). Mind you, a linked list is almost always the wrong +structure for any given job (being wildly inefficient compared to easy +alternatives) but it is a great tutorial data structure. + + +```java +struct List { + !List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +And the type of this struct matches its declaration: + +`struct List { List*? next, str !name };` + +We can use this to build up a list of strings: + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + + +### Checking a cyclic type for Read-Only / Final + +Suppose at some point we want to make a read-only immutable version: +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +What is the type of `hello`? It is the read-only type of `List`... and `List` is +a cyclic type. Follow the implementation of +[`Type.makeRO`, `isFinal`, and `_isFinal`](../../src/main/java/com/seaofnodes/simple/type/Type.java). + +We call `recurOpen()` to start/open the recursive walk, do the recursion +calling `_isFinal()` and end/close the recursive walk, and return a boolean +answer. `_isFinal()` is NOT Java final, and is overridden in the Type subclasses. +Subclasses implement the check for their own representation. For example, +[`TypeMemPtr._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java) +reads the pointer's access permission, while +[`TypeStruct._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +walks the fields and handles cycles. + +Here we see a common pattern in dealing with cycles: the **test-and-set**. We +check for any hard and fast answers (open structs are never read-only; they are +only partially defined and as-yet-unparsed non-final fields may appear), then +we **test** if we have been here before, and if so stop the recursion and +return some kind of answer. For "isFinal" the returned answer is "yes final" +as long as everything else in the cycle is also final. + +If we have not already checked this Type, we **set** the "visit" bit indicating +we've been here before, and then proceed to do normal recursive-descent on the +fields asking the same question recursively. + +For our example, we open the recursion (set a sentinel in `VISIT`), call +`makeRO` on `struct List`, which then calls `_isFinal` which then checks +the `_open` flag (not open), checks the `VISIT` (not visited), sets the +UID in `VISIT` and starts walking the fields. +[`Field._isFinal`](../../src/main/java/com/seaofnodes/simple/type/Field.java) +checks both the field's binding and its type. + +The first field is `List*? !next`, which is not-final, so immediately returns +`false`, which stops `_isFinal` on `List` and the whole `isFinal()` call returns +`false`, and ends/closes the recursion (clears `VISIT`). + + +### Making a cyclic type for Read-Only / Final + +To make the build-then-intern more obvious, let's put unique IDs on all our +Types. Here is the Type of `List` with sample UIDs following each unique type. +Fields are also just types so also get UIDs. + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +You can see from the repeated UIDs that `List#2` happens twice... because List +is cyclic. + +Now we do really need to make a cyclic type, and so our `makeRO()` call falls +into the recursive path in +[`Type.makeRO`](../../src/main/java/com/seaofnodes/simple/type/Type.java). + +Once again `recurOpen` starts/opens our recursive walk, and then we call +`_makeRO()` which is overridden in the child Type classes. Follow +[`TypeStruct._makeRO` and `recurPre`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +for the implementation. + +First up is the **test-and-set**. The **test** is by type name; we attempt to +get a `List` TypeStruct from `VISIT`, and if successful we return early - +without recursion. This means we can only have one `List` object in a R/O +cycle of types. You can imagine a tangle of multiple nested cyclic types where +some are "List-of-int" and some are "List-of-Lists-of-", but here in the name +of simplicity we choose to approximate our types to only a single instance of +`List`. + +In this example on first visit of `List` we will miss in `VISIT`. The next call +to `ts = recurPre(_name,_open)` does common shared pre-recursive work: we make +a new `TypeStruct` and **set** it in the `VISIT` table. The new `TypeStruct` +is a blank version of `List` with all !fields !attached; we force these fields to +be final right away but they are missing their types: + +``` +struct List#12 { + ____ next#14, + ____ name#15 +} +``` + + +Finally, we recursively call `_makeRO` on all the field types and set them in. +We call `_fields[i]._t._makeRO()` on a `TypeMemPtr` which makes a new +TMP after calling `_makeRO()` on the recursive `List`. + +This recursion comes right back to `TypeStruct._makeRO()`, and hits in the +`VISIT` table on the same type name. Unwinding the first field set, we have: + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + ____ name#15 +} +``` + +You should notice all new UIDs for all the Types. Since we cannot intern yet, +we cannot end up with prior types. The second field `str name` does already +exist, so we end up with: + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + str#2 name#15 // Reuse the interned type str#2 +} +``` + +At this point the recursion unwinds and we head into the complex +[`Type.recurClose()`](../../src/main/java/com/seaofnodes/simple/type/Type.java). +You might try single-stepping through +[`TypeTest.testList`](../../src/test/java/com/seaofnodes/simple/TypeTest.java), +which builds these types. Here is a high +level summary: + +Copy all the visited types out of `VISIT` for easier management; we might find +some of these types already interned, and then we'll remove them from further +processing; this is easier if they are not in a HashMap. + +**Pass#1:** look for pre-existing interned parts not in any cycle, and just +replace them. We could have a new cycle of Types with pointers off to older +interned types... that we made copies of. After this step, we'll still have +new cycles but the output edges will point to prior types if possible. +Replaced types hit the delayed `FREES` list. + +**Pass#2:** All types have their *duals* pre-computed and directly available. +Make the recursive cyclic duals now. + +**Pass#3:** Install the new types. It *is* possible to now discover common +pointers to newly interned types, and so again we need to test and replace as +we go (and put the unused types on the delayed `FREES` list again). This step +requires hash table probe - which requires a cyclic hash and cyclic equals. + +**Pass#4:** Free up all the delayed-free Types now, to be recycled in future +Type productions. + +In the end, the new `List` cyclic type is wholly interned - with a R/W version +of `List#2` pointing back to the R/W `List#2` and the R/O version `List#12` +pointing back to the same R/O `List#12`. + + + +### Cyclic HashCode and Equals + +Cyclic `hashCodes` and `equals` deserve more discussion. When comparing two +cycles for equivalence we want to be equivalent regardless of where the +comparison starts. i.e. cycle `A<->B` should be equal to cycle `B<->A`. This +means they both need the same hashcode, and this means we cannot use +order-varying hashes! + +E.g. Suppose A has static hash value 1 (plus something recursively from B's +hash), and vice-versa B has static hash value 3 (and something recursive from +A), and we compute hashes as `parent.hash*7 + child.hash`. If we compute A's +hash as `A.hash * 7 + B.hash` we get `1 * 7 + 3 == 10`, and then later we start +from B we get: `B.hash * 7 + A.hash` and which then becomes `3 * 7 + 1 == +22`... and their hashes differ so the hash table might miss the equivalence. +Also, if we simply use recursive descent in the cycle we'll +recurse until stack overflow and crash. + +We fix this by having `TypeStruct.hash()` *not* recurse - thus its hash +function is somewhat weak, depending only on the field names and aliases. + +*Cyclic-equals* is triggered by the `VISIT` table being not-empty, and uses +another unrelated *visit* table, the `CEQUALS` table, to separate concerns from +`VISIT`. The cycle-equals check proceeds like the normal `eq` with recursive +descent on the parts, and some up-front hard-and-fast static checks - and the +ubiquitous **test-and-set** pattern before the recursion. + +If we ever compare the same two types for cycle-equals again, we assume they +will be cycle-equals (all other things being equals). + + + +## Finalizing field layouts + +`FinalizeIR` now also settles field sizes and layouts, replaces symbolic field +offsets by constants, and runs peepholes exposed by those constants. Recursive +type construction must finish before layout is queried. The phase follows +`Iter` and precedes `TypeCheck`; the driver includes it when compiling through +any later stage. + +## Methods and Final Fields and Classes + +Methods are simply function values (final fields) declared inside a struct that +take an implicit `self` argument. + +Final fields declared in the original struct definition are *values* and cannot +change; they are the same for all instances. They get moved out of the +struct's memory footprint and into a *class* - a collection of values from the +final fields. Classes are just plain namespaces and have no concrete +implementation; they are not reified. + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; + }; + + +}; + +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); +``` + +Here the `val add` field is a *value* field, a constant function value. It is +moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no +storage space in `vecInt` objects. The same happens for `_grow`. The size of +a `vecInt` instance is thus its `u32` length and array pointer, plus alignment +padding. The array header and elements occupy a separate allocation. Reclaiming +the old buffer after growth is outside this example. Appending +`return primes.len*100+primes.buf[4];` produces 511 on both RISC-V and ARM. + +## RegAlloc improvements: grouping popular uses + +Chapter 22 improved color preferences and cheap-spill ordering. This chapter +adds a way to split a popular value whose uses demand incompatible registers. +For example, several shifts may need the same count register while another use +needs a different register. Sharing one copy for each compatible group can +avoid inserting a separate copy at every use. + +The allocator applies this to a single-definition live range with an empty +register mask and more than two fixed-register uses. It intersects overlapping +use masks into groups; narrowing a group keeps it compatible with its earlier +users, so one pass suffices. Disjoint masks start separate groups. It snapshots +distinct users before rewiring their inputs, ignores scheduling-only edges, +and counts a call once even when the value supplies several arguments. + +Grouping declines values used by multiple calls, whose register kills tend to +undo the benefit of a shared copy. The usual loop-boundary splitting remains +the fallback, including splitting an existing copy when all uses have the same +loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill +ranking remains for Chapter 25. + +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 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | + diff --git a/docs/chapter23/examples/A_helloWorld.smp b/docs/chapter23/examples/A_helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/docs/chapter23/examples/A_helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/docs/chapter23/examples/BubbleSort.smp b/docs/chapter23/examples/BubbleSort.smp new file mode 100644 index 00000000..938e3181 --- /dev/null +++ b/docs/chapter23/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/chapter23/font-awesome-4.7.0.zip b/docs/chapter23/font-awesome-4.7.0.zip new file mode 100644 index 00000000..b6bdb4bd Binary files /dev/null and b/docs/chapter23/font-awesome-4.7.0.zip differ diff --git a/docs/chapter23/ifg_trim.pdf b/docs/chapter23/ifg_trim.pdf new file mode 100644 index 00000000..d952fd4f Binary files /dev/null and b/docs/chapter23/ifg_trim.pdf differ diff --git a/docs/chapter23/lattice.gv b/docs/chapter23/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice.svg b/docs/chapter23/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice2.gv b/docs/chapter23/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice2.svg b/docs/chapter23/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter23/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/chapter23/pardoe.docx b/docs/chapter23/pardoe.docx new file mode 100644 index 00000000..24fde921 Binary files /dev/null and b/docs/chapter23/pardoe.docx differ diff --git a/docs/chapter23/webtcp.min.js b/docs/chapter23/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter23/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