- 浏览: 3013624 次
- 性别:
- 来自: 海外
文章分类
- 全部博客 (430)
- Programming Languages (23)
- Compiler (20)
- Virtual Machine (57)
- Garbage Collection (4)
- HotSpot VM (26)
- Mono (2)
- SSCLI Rotor (1)
- Harmony (0)
- DLR (19)
- Ruby (28)
- C# (38)
- F# (3)
- Haskell (0)
- Scheme (1)
- Regular Expression (5)
- Python (4)
- ECMAScript (2)
- JavaScript (18)
- ActionScript (7)
- Squirrel (2)
- C (6)
- C++ (10)
- D (2)
- .NET (13)
- Java (86)
- Scala (1)
- Groovy (3)
- Optimization (6)
- Data Structure and Algorithm (3)
- Books (4)
- WPF (1)
- Game Engines (7)
- 吉里吉里 (12)
- UML (1)
- Reverse Engineering (11)
- NSIS (4)
- Utilities (3)
- Design Patterns (1)
- Visual Studio (9)
- Windows 7 (3)
- x86 Assembler (1)
- Android (2)
- School Assignment / Test (6)
- Anti-virus (1)
- REST (1)
- Profiling (1)
- misc (39)
- NetOA (12)
- rant (6)
- anime (5)
- Links (12)
- CLR (7)
- GC (1)
- OpenJDK (2)
- JVM (4)
- KVM (0)
- Rhino (1)
- LINQ (2)
- JScript (0)
- Nashorn (0)
- Dalvik (1)
- DTrace (0)
- LLVM (0)
- MSIL (0)
最新评论
-
mldxs:
虽然很多还是看不懂,写的很好!
虚拟机随谈(一):解释器,树遍历解释器,基于栈与基于寄存器,大杂烩 -
HanyuKing:
Java的多维数组 -
funnyone:
Java 8的default method与method resolution -
ljs_nogard:
Xamarin workbook - .Net Core 中不 ...
LINQ的恶搞…… -
txm119161336:
allocatestlye1 顺序为 // Fields o ...
最近做的两次Java/JVM分享的概要
“简单”嘛说明肯定有更麻烦、效果可能更好的办法。这里提到的算法就是这样。
龙书第二版363页习题6.1.2有点意思。题目如下:
(c)原本在书上就是这么写的……很明显括号没配对是吧 = =
勘误表里没提到这项。莫非是国内的影印版的问题?我无法确认。正确的代码应该是:
a + a + (a + a + a + (a + a + a + a))
这样才对)
如何从表达式的源码生成DAG(Directed Acyclic Graph,有向无环图)呢?龙书在前面给出了一个算法:在解析源码并生成语法树的算法的基础上,如果在创建新的节点前先检查是否已存在相同的节点,若存在则返回已有节点,否则返回新建的节点。
假设DAG的节点是<op,left,right>形式的三元组,其中op是表示运算符的枚举类型的值,left和right是表示子节点的引用。那么在检查是否已存在相同的节点时,只需要分别检查op、left和right是否相同即可。
但是这个简单的算法很明显不保证生成最优(节点数最少)的DAG。以习题6.1.2中的a)和b)为例:
a)
AST:
DAG:
这个DAG的叶节点有2个,内部节点有2个。
对应到三地址代码,是:
b)
AST:
DAG:
这个DAG的叶节点也是两个,但内部节点却有3个,比a)的多一个。
对应到三地址代码,则是:
问题是什么呢?习题里a)和b)的源码所代表的表达式的运算结果显然应该是一样的,但由于对应的AST的形状不同,导致生成的DAG也有所不同。
如果尝试对AST做等价变形然后再生成DAG,或许是可以选择出较优的版本,不过是否值得为了这个优化而使编译器变得复杂就是另一个问题了。对AST做了等价变形后,要比以某节点N1为根的子树与另一以N2为根的子树是否相同,就得专门写一个TreeComparer了。前面的简单算法是在生成节点的时候就做了比较,等于是做过了自底而上的比较,实现起来很简单。
===================================================================================
要写个简单的解析器来生成上面的图十分简单。
首先定义语言的语法,尽量定义得简单些:
或者化简掉左递归后以EBNF表示:
其中ID为单字符的英文字母。
那么可以简单的实现解析器如下:
使用方法是直接运行该程序,然后在一行上输入一个符合前面语法规则的表达式,或者是在运行该程序的时候提供一个参数作为这个表达式。运行程序后,如果解析正常结束,那么会在标准输出上先后输出对应AST和DAG的DOT代码。
输出的DOT代码通过Graphviz的dot程序就能生成图片。
例如说运行程序后输入a + b + (a + b)回车,会看到:
和
用dot把它们分别转换成图片即可。假如对应DAG的这段DOT代码被保存到名为dag.dot文件里,则:
就可以得到名为dag.png的图片,跟本文顶上的第二张图是一样的。
Expression及其派生类是用来表示解析源码后得到的AST或DAG的节点。注意Expression类上的Add和Id这两个静态工厂方法中关于检查节点是否已经存在,并尽量返回已有节点的做法:这就是前面提到的简单DAG生成算法在上面这大堆代码里的实现。检测节点的相等性的代码主要是在BinaryExpression和IdExpression里实现的。
Cache本来我是想用HashSet的,不过.NET标准库里的HashSet在这里不好用:虽然很容易知道容器里是否已存在相同的节点,却没办法把那个节点迅速拿出来;要是最终还是得线性遍历的话,那还不如用线性容器。所以最后还是用了List。
Scanner和Parser分别最低限度的实现了词法分析器和递归下降语法分析器。只允许单字符变量名也就是为了方便Scanner的实现。不过这部分其实用ANTLR来生成更方便,也一样可以接上后面的程序运行。
DotGenerator用于根据AST或DAG生成DOT图,实现得有点乱。主要是原本为了保证生成的DOT代码中节点的顺序,而采用了广度优先的遍历顺序;可是后来用于强制指定顺序的代码反而带来了一些问题,所以注释掉了(第308行到第314行)。这样一来用两个Queue来记录着前一行与当前行的节点就不一定有必要了。不过懒得改,就这样吧……
编辑:嗯不行……前面的代码不改还是有问题。本来我是觉得DAG因为没有环所以只要记住“上一层”的节点就足以判断前面是否已经见过该节点,但熬夜写代码看来质量果然是不高啊,这想法是错的。还是乖乖的用一个HashSet来记着前面见到过的节点然后用深度优先遍历算了,免得麻烦。修改后的DotGenerator类如下:
对应习题里c)的DAG应该是:
上面的代码做出来的效果还有待改善就是了。对 a + b + (b + a) 这样的表达式,生成的DAG会是:
右侧中间的那个+下面的左节点与右节点的顺序反掉了。其实仔细留心的话,前面对习题的b)给出的DAG也有一个节点的左右关系是反了的。
要调整这个细节挺麻烦的,我还没想好怎么实现比较干净。不过暂时就这么凑合看看好了 = =
===================================================================================
顺带提一下.NET 3.5里的LINQ Expression Tree和DLR里的LINQ Expression Tree v2。
在LINQ与DLR的Expression tree(1):简介LINQ与Expression tree一帖的Expression tree与lambda表达式一节里,我简单的提到过“Expression Tree表示的是AST”这样的概念。当时只是为了说明方便,其实并不准确。
用那帖的例子来说,下面的lambda表达式:
在那帖里我给出了这样的AST图:
也说明了图中虚线连接的两个节点实际上是一个节点。
但我们都知道,树这种数据结构的重要性质就是它的每个节点都只有一个父节点(根节点除外)。上述lambda表达式对应的Expression Tree中的节点情况实际上应该这样画:
这样就可以看得比较清楚了。实际上这个图并不是一棵树,而是一个DAG。Expression Tree实际表示的也应该说是DAG才准确。不过用AST的概念来解释它还是比DAG方便一些就是了……
===================================================================================
Hmm,用Sun的javac 1.6.x和.NET Framework 3.5 SP1的csc编译习题里的那3个表达式,得到的结果都是没有用DAG做过优化的,即便给csc设置/o开关(近来Sun的javac会忽略-O,所以也不用设了)。因为对运行时里的JIT的高度优化能力有信心,这些编译器都不再做多少优化了,直接留给拥有更多信息因而能做出更多优化的JIT来解决问题。
对现在流行的托管高级语言来说,有一个问题是:语言规范中规定了很多细节,以致许多东西无法被优化,否则就保证不了语义。
例如,如果在C#里,用户对自己的一个类型重载了加法运算符,然后里面有副作用;则如果优化后减少了加法运算符调用的次数,这个行为就能带来用户可见的影响。因而不可以随便优化这样的运算。改变求值顺序也是不允许的,像Java和C#都规定要遵循从左向右的求值顺序,实现时必须保证其语义的正确性。
微软的csc应该通过分析定义-使用关系做了至少一趟优化,因为这段代码:
让csc编译过后就只剩下这么多了:
很明显如果继续用定义-使用关系来优化的话,整个Main()方法应该变成空的才对。
C#不允许用户对内建类型的运算符做重载,所以还好,至少System.Int32的加法运算符能保证没有可见的副作用,所以可以优化。不过试想一个这样的类:
然后要是foo是Foo的一个实例,我要是写:
要是被优化了的话,Console.WriteLine(_value)就只会发生一次,这就糟糕了。
GCC 4.3.0在编译这几个表达式的时候,使用-O2,对代码:
其中与i、j和k的初始化相关的表达式编译得到:
优化得相当彻底。此时i和j都由edx表示。
事实上不加上输出语句的话,整个foo()就没了 = =
================================================
LLVM通过-reassociate和-instcombine可以对这里的问题做优化,但有种歪打正着的感觉。
例如说对:
LLVM可以通过reassociate变成:
然后通过instcombine变成:
然后在后面lower到底层IR时再把* 3转换为机器相关的更高效形式,例如lea。
original IR
after reassociate:
after instcombine:
-reassociate的相关部分是Reassociate::OptimizeAdd()做的。
http://www.opensource.apple.com/source/clang/clang-137/src/lib/Transforms/Scalar/Reassociate.cpp
话说这reassociate+instcombine的组合对纯加法还ok,但是对其它情况(例如说带有减法)就不太能行了。
看这个例子:
LLVM居然给生成出了:
================================================
拿HotSpot 22.0也试了试上面的习题b)。发现HotSpot Server Compiler也没对这种情况优化嘛,哈哈
还是有3个加在这里,而不是理想的2个加
龙书第二版363页习题6.1.2有点意思。题目如下:
Compilers - Principles, Techniques, & Tools, Second Edition 写道
Exercise 6.1.2: Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming + associates from the left.
a) a + b + (a + b)
b) a + b + a + b
c) a + a + ((a + a + a + (a + a + a + a))
a) a + b + (a + b)
b) a + b + a + b
c) a + a + ((a + a + a + (a + a + a + a))
(c)原本在书上就是这么写的……很明显括号没配对是吧 = =
勘误表里没提到这项。莫非是国内的影印版的问题?我无法确认。正确的代码应该是:
a + a + (a + a + a + (a + a + a + a))
这样才对)
如何从表达式的源码生成DAG(Directed Acyclic Graph,有向无环图)呢?龙书在前面给出了一个算法:在解析源码并生成语法树的算法的基础上,如果在创建新的节点前先检查是否已存在相同的节点,若存在则返回已有节点,否则返回新建的节点。
假设DAG的节点是<op,left,right>形式的三元组,其中op是表示运算符的枚举类型的值,left和right是表示子节点的引用。那么在检查是否已存在相同的节点时,只需要分别检查op、left和right是否相同即可。
但是这个简单的算法很明显不保证生成最优(节点数最少)的DAG。以习题6.1.2中的a)和b)为例:
a)
AST:
DAG:
这个DAG的叶节点有2个,内部节点有2个。
对应到三地址代码,是:
t1 = a + b t2 = t1 + t1
b)
AST:
DAG:
这个DAG的叶节点也是两个,但内部节点却有3个,比a)的多一个。
对应到三地址代码,则是:
t1 = a + b t2 = t1 + a t3 = t2 + b
问题是什么呢?习题里a)和b)的源码所代表的表达式的运算结果显然应该是一样的,但由于对应的AST的形状不同,导致生成的DAG也有所不同。
如果尝试对AST做等价变形然后再生成DAG,或许是可以选择出较优的版本,不过是否值得为了这个优化而使编译器变得复杂就是另一个问题了。对AST做了等价变形后,要比以某节点N1为根的子树与另一以N2为根的子树是否相同,就得专门写一个TreeComparer了。前面的简单算法是在生成节点的时候就做了比较,等于是做过了自底而上的比较,实现起来很简单。
===================================================================================
要写个简单的解析器来生成上面的图十分简单。
首先定义语言的语法,尽量定义得简单些:
E -> E '+' ID | ID | '(' E ')'
或者化简掉左递归后以EBNF表示:
E -> ID ( '+' ID )* | '(' E ')'
其中ID为单字符的英文字母。
那么可以简单的实现解析器如下:
using System; using System.Collections; using System.Collections.Generic; using System.IO; using System.Linq; public enum NodeKind { Add, Id } public abstract class Expression : IEquatable<Expression> { // DAG node cache static List<Expression> _cache; // lazily initialize the cache for creating DAG nodes protected static List<Expression> Cache { get { if ( null == _cache ) { _cache = new List<Expression>( ); } return _cache; } } public virtual NodeKind NodeKind { get { throw new NotSupportedException( ); } } // Create a BinaryExpression node representing an add operation public static BinaryExpression Add( Expression left, Expression right, bool useCache ) { var tempExpr = new BinaryExpression( left, right ); if ( useCache ) { return LookupCache( tempExpr ) as BinaryExpression; } else { return tempExpr; } } // Create an IdExpression representing an ID access public static IdExpression Id( char id, bool useCache ) { var tempExpr = new IdExpression( id ); if ( useCache ) { return LookupCache( tempExpr ) as IdExpression; } else { return tempExpr; } } static Expression LookupCache( Expression expr ) { var cachedExpr = Cache.FirstOrDefault( e => e.Equals( expr ) ); if ( null == cachedExpr ) { Cache.Add( expr ); cachedExpr = expr; } return cachedExpr; } #region IEquatable<Expression> members and related methods public override bool Equals( object other ) { if ( !( other is Expression ) ) return false; return Equals( other as Expression ); } public override int GetHashCode( ) { return GetHashCodeCore( ); } public abstract bool Equals( Expression other ); protected abstract int GetHashCodeCore( ); #endregion } public class BinaryExpression : Expression { Expression _left; Expression _right; public BinaryExpression( Expression left, Expression right ) { _left = left; _right = right; } public override NodeKind NodeKind { get { return NodeKind.Add; } } public Expression Left { get { return _left; } } public Expression Right { get { return _right; } } public override bool Equals( Expression other ) { if ( ! ( other is BinaryExpression ) ) return false; var otherExpr = other as BinaryExpression; return otherExpr.Left == _left && otherExpr.Right == _right; } protected override int GetHashCodeCore( ) { return _left.GetHashCode( ) * 37 + _right.GetHashCode( ) + 17; } public override string ToString( ) { return string.Format( "(+ {0} {1})", _left.ToString( ), _right.ToString( ) ); } } public class IdExpression : Expression { char _id; public IdExpression( char id ) { _id = id; } public override NodeKind NodeKind { get { return NodeKind.Id; } } public string IdString { get { return _id.ToString( ); } } public override bool Equals( Expression other ) { if ( ! ( other is IdExpression ) ) return false; return _id == ( other as IdExpression )._id; } protected override int GetHashCodeCore( ) { return _id.GetHashCode( ); } public override string ToString( ) { return IdString; } } public class SyntaxException : Exception { public SyntaxException( ) { } public SyntaxException( string message ) : base( message ) { } } public class Scanner : IEnumerable, IEnumerable<int> { public const int EOS = -1; string _input; public Scanner( string input ) { _input = input; } public IEnumerator GetEnumerator( ) { return ( this as IEnumerable<int> ).GetEnumerator( ); } IEnumerator<int> IEnumerable<int>.GetEnumerator( ) { return EnumerateChars( ).GetEnumerator( ); } static readonly int[ ] _punctuations = new int[ ] { '+', '(', ')' }; IEnumerable<int> EnumerateChars( ) { var reader = new StringReader( _input ); int intChar; while ( 0 < ( intChar = reader.Read( ) ) ) { var c = Convert.ToChar( intChar ); if ( Char.IsWhiteSpace( c ) ) continue; if ( _punctuations.Contains( intChar ) || Char.IsLetter( c ) ) { yield return intChar; } else { throw new SyntaxException( string.Format( "Invalid character: {0}", c.ToString( ) ) ); } } yield return EOS; } } public class Parser { Scanner _scanner; IEnumerator<int> _input; public Parser( Scanner scanner ) { _scanner = scanner; } public Expression ParseToDag( ) { _input = ( _scanner as IEnumerable<int> ).GetEnumerator( ); return Parse( true ); } public Expression ParseToAst( ) { _input = ( _scanner as IEnumerable<int> ).GetEnumerator( ); return Parse( false ); } Expression Parse( bool useCache ) { _input.MoveNext( ); var expr = ParseExpression( useCache ); Match( Scanner.EOS ); _input = null; return expr; } Expression ParseExpression( bool useCache ) { Expression expr = null; // E -> ID | '(' E ')' switch ( _input.Current ) { case '(': Match( '(' ); expr = ParseExpression( useCache ); Match( ')' ); break; case Scanner.EOS: throw new SyntaxException( "Unexpected end of string" ); default: expr = Expression.Id( Convert.ToChar( _input.Current ), useCache ); _input.MoveNext( ); break; } // ( '+' ( ID | '(' E ')' ) )* while ( _input.Current == '+' ) { Match( '+' ); Expression right = null; switch ( _input.Current ) { case '(': Match( '(' ); right = ParseExpression( useCache ); Match( ')' ); break; case Scanner.EOS: throw new SyntaxException( "Unexpected end of string" ); default: right = Expression.Id( Convert.ToChar( _input.Current ), useCache ); _input.MoveNext( ); break; } expr = Expression.Add( expr, right, useCache ); } return expr; } void Match( int charCodeToMatch ) { if ( _input.Current == charCodeToMatch ) { _input.MoveNext( ); } else { throw new SyntaxException( string.Format( "Expecting {0}, but found {1}", CharCodeToString( charCodeToMatch ), CharCodeToString( _input.Current ) ) ); } } string CharCodeToString( int charCode ) { return 0 < charCode ? Convert.ToChar( charCode ).ToString( ) : "End-Of-String"; } } class DotGenerator { Queue<Expression> _lastRank; Queue<Expression> _thisRank; TextWriter _writer; IEnumerator<string> _nameMaker; Dictionary<Expression, string> _nameMap; public DotGenerator( ) { _lastRank = new Queue<Expression>( ); _thisRank = new Queue<Expression>( ); } public string Generate( Expression root ) { _lastRank.Enqueue( root ); _nameMap = new Dictionary<Expression, string>( IdentityComparer<Expression>.Instance ); _nameMaker = GetNameMaker( ).GetEnumerator( ); _writer = new StringWriter( ); _writer.WriteLine( "digraph {" ); _writer.WriteLine( " node [fontsize=12, font=Courier, shape=plaintext]" ); GenerateCore( ); _writer.WriteLine( "}" ); var dot = _writer.ToString( ); _nameMap.Clear( ); _nameMap = null; _nameMaker = null; _writer = null; return dot; } // breadth-first traverse void GenerateCore( ) { while ( 0 < _lastRank.Count ) { /*if ( 1 < _lastRank.Count ) { string[ ] rank = _lastRank.Select( e => _nameMap[ e ] ).ToArray( ); _writer.WriteLine( " {0} [ordering=out, style=invis]", string.Join( " -> ", rank ) ); _writer.WriteLine( " {{rank=same; {0} }}", string.Join( " ", rank ) ); }*/ while ( 0 < _lastRank.Count ) { var expr = _lastRank.Dequeue( ); DeclareNode( expr ); switch ( expr.NodeKind ) { case NodeKind.Add: var addExpr = expr as BinaryExpression; var left = addExpr.Left; var right = addExpr.Right; if ( !_thisRank.Contains( left, IdentityComparer<Expression>.Instance ) ) { DeclareNode( addExpr.Left ); _thisRank.Enqueue( left ); } if ( !_thisRank.Contains( right, IdentityComparer<Expression>.Instance ) ) { DeclareNode( addExpr.Right ); _thisRank.Enqueue( right ); } _writer.WriteLine( " {0} -> {1}", _nameMap[ expr ], _nameMap[ left ] ); _writer.WriteLine( " {0} -> {1}", _nameMap[ expr ], _nameMap[ right ] ); break; case NodeKind.Id: // DO NOTHING break; } } // swap the two queues var tempQueue = _lastRank; _lastRank = _thisRank; _thisRank = tempQueue; } } void DeclareNode( Expression expr ) { if ( !_nameMap.ContainsKey( expr ) ) { _nameMaker.MoveNext( ); var name = _nameMaker.Current; _nameMap.Add( expr, name ); switch ( expr.NodeKind ) { case NodeKind.Add: _writer.WriteLine( " {0} [label=\"+\"]", name ); break; case NodeKind.Id: var idExpr = expr as IdExpression; _writer.WriteLine( " {0} [label=\"{1}\"]", name, idExpr.IdString ); break; } } } IEnumerable<string> GetNameMaker( ) { for ( var count = 0; ; ++count ) { yield return string.Format( "node_{0}", count.ToString( ) ); } } class IdentityComparer<T> : EqualityComparer<T> { static IdentityComparer<T> _instance; static IdentityComparer( ) { _instance = new IdentityComparer<T>( ); } public static IdentityComparer<T> Instance { get { return _instance; } } public override bool Equals( T first, T second ) { return object.ReferenceEquals( first, second ); } public override int GetHashCode( T obj ) { return obj.GetHashCode( ); } } } static class Program { static void Main( string[ ] args ) { string input = null; switch ( args.Length ) { case 0: Console.WriteLine( "Enter an expression on a line:" ); Console.WriteLine( "(or give the expression as " + "the first argument in command prompt)" ); input = Console.ReadLine( ); break; default: input = args[ 0 ]; break; } var scanner = new Scanner( input ); var parser = new Parser( scanner ); var dotGen = new DotGenerator( ); var ast = parser.ParseToAst( ); var astDot = dotGen.Generate( ast ); Console.WriteLine( "// DOT script for AST:" ); Console.WriteLine( astDot ); var dag = parser.ParseToDag( ); var dagDot = dotGen.Generate( dag ); Console.WriteLine( "// DOT script for DAG:" ); Console.WriteLine( dagDot ); } }
使用方法是直接运行该程序,然后在一行上输入一个符合前面语法规则的表达式,或者是在运行该程序的时候提供一个参数作为这个表达式。运行程序后,如果解析正常结束,那么会在标准输出上先后输出对应AST和DAG的DOT代码。
输出的DOT代码通过Graphviz的dot程序就能生成图片。
例如说运行程序后输入a + b + (a + b)回车,会看到:
// DOT script for AST: digraph { node [fontsize=12, font=Courier, shape=plaintext] node_0 [label="+"] node_1 [label="+"] node_2 [label="+"] node_0 -> node_1 node_0 -> node_2 node_3 [label="a"] node_4 [label="b"] node_1 -> node_3 node_1 -> node_4 node_5 [label="a"] node_6 [label="b"] node_2 -> node_5 node_2 -> node_6 }
和
// DOT script for DAG: digraph { node [fontsize=12, font=Courier, shape=plaintext] node_0 [label="+"] node_1 [label="+"] node_0 -> node_1 node_0 -> node_1 node_2 [label="a"] node_3 [label="b"] node_1 -> node_2 node_1 -> node_3 }
用dot把它们分别转换成图片即可。假如对应DAG的这段DOT代码被保存到名为dag.dot文件里,则:
dot -Tpng dag.dot -o dag.png
就可以得到名为dag.png的图片,跟本文顶上的第二张图是一样的。
Expression及其派生类是用来表示解析源码后得到的AST或DAG的节点。注意Expression类上的Add和Id这两个静态工厂方法中关于检查节点是否已经存在,并尽量返回已有节点的做法:这就是前面提到的简单DAG生成算法在上面这大堆代码里的实现。检测节点的相等性的代码主要是在BinaryExpression和IdExpression里实现的。
Cache本来我是想用HashSet的,不过.NET标准库里的HashSet在这里不好用:虽然很容易知道容器里是否已存在相同的节点,却没办法把那个节点迅速拿出来;要是最终还是得线性遍历的话,那还不如用线性容器。所以最后还是用了List。
Scanner和Parser分别最低限度的实现了词法分析器和递归下降语法分析器。只允许单字符变量名也就是为了方便Scanner的实现。不过这部分其实用ANTLR来生成更方便,也一样可以接上后面的程序运行。
DotGenerator用于根据AST或DAG生成DOT图,实现得有点乱。主要是原本为了保证生成的DOT代码中节点的顺序,而采用了广度优先的遍历顺序;可是后来用于强制指定顺序的代码反而带来了一些问题,所以注释掉了(第308行到第314行)。这样一来用两个Queue来记录着前一行与当前行的节点就不一定有必要了。不过懒得改,就这样吧……
编辑:嗯不行……前面的代码不改还是有问题。本来我是觉得DAG因为没有环所以只要记住“上一层”的节点就足以判断前面是否已经见过该节点,但熬夜写代码看来质量果然是不高啊,这想法是错的。还是乖乖的用一个HashSet来记着前面见到过的节点然后用深度优先遍历算了,免得麻烦。修改后的DotGenerator类如下:
class DotGenerator { HashSet<Expression> _seenNodes; TextWriter _writer; IEnumerator<string> _nameMaker; Dictionary<Expression, string> _nameMap; public DotGenerator( ) { _seenNodes = new HashSet<Expression>( IdentityComparer<Expression>.Instance ); _nameMap = new Dictionary<Expression, string>( IdentityComparer<Expression>.Instance ); } public string Generate( Expression root ) { _nameMaker = GetNameMaker( ).GetEnumerator( ); _writer = new StringWriter( ); _writer.WriteLine( "digraph {" ); _writer.WriteLine( " node [fontsize=12, font=Courier, shape=plaintext]" ); GenerateCore( root ); _writer.WriteLine( "}" ); var dot = _writer.ToString( ); _seenNodes.Clear( ); _nameMap.Clear( ); _nameMaker = null; _writer = null; return dot; } // depth-first traverse void GenerateCore( Expression expr ) { DeclareNode( expr ); _seenNodes.Add( expr ); switch ( expr.NodeKind ) { case NodeKind.Add: var addExpr = expr as BinaryExpression; var left = addExpr.Left; var right = addExpr.Right; if ( !_seenNodes.Contains( left ) ) { GenerateCore( left ); } if ( !_seenNodes.Contains( right ) ) { GenerateCore( right ); } _writer.WriteLine( " {0} -> {1}", _nameMap[ expr ], _nameMap[ left ] ); _writer.WriteLine( " {0} -> {1}", _nameMap[ expr ], _nameMap[ right ] ); break; case NodeKind.Id: // DO NOTHING break; } } void DeclareNode( Expression expr ) { if ( !_nameMap.ContainsKey( expr ) ) { _nameMaker.MoveNext( ); var name = _nameMaker.Current; _nameMap.Add( expr, name ); switch ( expr.NodeKind ) { case NodeKind.Add: _writer.WriteLine( " {0} [label=\"+\"]", name ); break; case NodeKind.Id: var idExpr = expr as IdExpression; _writer.WriteLine( " {0} [label=\"{1}\"]", name, idExpr.IdString ); break; } } } IEnumerable<string> GetNameMaker( ) { for ( var count = 0; ; ++count ) { yield return string.Format( "node_{0}", count.ToString( ) ); } } class IdentityComparer<T> : EqualityComparer<T> { static IdentityComparer<T> _instance; static IdentityComparer( ) { _instance = new IdentityComparer<T>( ); } public static IdentityComparer<T> Instance { get { return _instance; } } public override bool Equals( T first, T second ) { return object.ReferenceEquals( first, second ); } public override int GetHashCode( T obj ) { return obj.GetHashCode( ); } } }
对应习题里c)的DAG应该是:
上面的代码做出来的效果还有待改善就是了。对 a + b + (b + a) 这样的表达式,生成的DAG会是:
右侧中间的那个+下面的左节点与右节点的顺序反掉了。其实仔细留心的话,前面对习题的b)给出的DAG也有一个节点的左右关系是反了的。
要调整这个细节挺麻烦的,我还没想好怎么实现比较干净。不过暂时就这么凑合看看好了 = =
===================================================================================
顺带提一下.NET 3.5里的LINQ Expression Tree和DLR里的LINQ Expression Tree v2。
在LINQ与DLR的Expression tree(1):简介LINQ与Expression tree一帖的Expression tree与lambda表达式一节里,我简单的提到过“Expression Tree表示的是AST”这样的概念。当时只是为了说明方便,其实并不准确。
用那帖的例子来说,下面的lambda表达式:
x => -x
在那帖里我给出了这样的AST图:
也说明了图中虚线连接的两个节点实际上是一个节点。
但我们都知道,树这种数据结构的重要性质就是它的每个节点都只有一个父节点(根节点除外)。上述lambda表达式对应的Expression Tree中的节点情况实际上应该这样画:
这样就可以看得比较清楚了。实际上这个图并不是一棵树,而是一个DAG。Expression Tree实际表示的也应该说是DAG才准确。不过用AST的概念来解释它还是比DAG方便一些就是了……
===================================================================================
Hmm,用Sun的javac 1.6.x和.NET Framework 3.5 SP1的csc编译习题里的那3个表达式,得到的结果都是没有用DAG做过优化的,即便给csc设置/o开关(近来Sun的javac会忽略-O,所以也不用设了)。因为对运行时里的JIT的高度优化能力有信心,这些编译器都不再做多少优化了,直接留给拥有更多信息因而能做出更多优化的JIT来解决问题。
对现在流行的托管高级语言来说,有一个问题是:语言规范中规定了很多细节,以致许多东西无法被优化,否则就保证不了语义。
例如,如果在C#里,用户对自己的一个类型重载了加法运算符,然后里面有副作用;则如果优化后减少了加法运算符调用的次数,这个行为就能带来用户可见的影响。因而不可以随便优化这样的运算。改变求值顺序也是不允许的,像Java和C#都规定要遵循从左向右的求值顺序,实现时必须保证其语义的正确性。
微软的csc应该通过分析定义-使用关系做了至少一趟优化,因为这段代码:
static class TestDAG { static void Main(string[] args) { int a = 0x001001; int b = 0x010002; int i = a + b + (a + b); int j = a + b + a + b; int k = a + a + (a + a + a + (a + a + a + a)); } }
让csc编译过后就只剩下这么多了:
static class TestDAG { static void Main(string[] args) { int a = 0x001001; int b = 0x010002; } }
很明显如果继续用定义-使用关系来优化的话,整个Main()方法应该变成空的才对。
C#不允许用户对内建类型的运算符做重载,所以还好,至少System.Int32的加法运算符能保证没有可见的副作用,所以可以优化。不过试想一个这样的类:
public class Foo { int _value; public int Value { get { Console.WriteLine( _value ); return _value; } set { _value = value; } } }
然后要是foo是Foo的一个实例,我要是写:
1 + foo.Value + (1 + foo.Value)
要是被优化了的话,Console.WriteLine(_value)就只会发生一次,这就糟糕了。
GCC 4.3.0在编译这几个表达式的时候,使用-O2,对代码:
void foo(int a, int b) { int i = a + b + (a + b); int j = a + b + a + b; int k = a + a + (a + a + a + (a + a + a + a)); printf("%d, %d, %d, %d, %d\n", a, b, i, j, k); }
其中与i、j和k的初始化相关的表达式编译得到:
mov ecx,dword ptr ss:[ebp+8] ; ecx = a mov ebx,dword ptr ss:[ebp+C] ; ebx = b lea edx,dword ptr ds:[ebx+ecx] ; edx = a + b shl edx,1 ; edx = 2 * edx lea eax,dword ptr ds:[ecx+ecx*2] ; eax = a + 2 * a lea eax,dword ptr ds:[eax+eax*2] ; eax = eax + 2 * eax
优化得相当彻底。此时i和j都由edx表示。
事实上不加上输出语句的话,整个foo()就没了 = =
================================================
LLVM通过-reassociate和-instcombine可以对这里的问题做优化,但有种歪打正着的感觉。
例如说对:
a + b + c + a + b + c + a + b + c
LLVM可以通过reassociate变成:
tmp1 = a * 3 tmp2 = b * 3 tmp3 = c * 3 tmp4 = tmp1 + tmp2 tmp5 = tmp4 + tmp3
然后通过instcombine变成:
tmp1 = a + b tmp2 = tmp1 + c tmp3 = tmp2 * 3
然后在后面lower到底层IR时再把* 3转换为机器相关的更高效形式,例如lea。
original IR
; Function Attrs: nounwind ssp uwtable define void @foo(i32 %a, i32 %b, i32 %c) #0 { %1 = add i32 %a, %b %2 = add i32 %1, %c %3 = add i32 %2, %a %4 = add i32 %3, %b %5 = add i32 %4, %c %6 = add i32 %5, %a %7 = add i32 %6, %b %result = add i32 %7, %c %8 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([20 x i8]* @.str, i64 0, i64 0), i32 %a, i32 %b, i32 %result, i32 %result, i32 %result) #2 ret void }
after reassociate:
; Function Attrs: nounwind ssp uwtable define void @foo(i32 %a, i32 %b, i32 %c) #0 { %factor = mul i32 %c, 3 %factor1 = mul i32 %b, 3 %factor2 = mul i32 %a, 3 %1 = add i32 %factor1, %factor %result = add i32 %1, %factor2 %2 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([20 x i8]* @.str, i64 0, i64 0), i32 %a, i32 %b, i32 %result, i32 %result, i32 %result) #2 ret void }
after instcombine:
; Function Attrs: nounwind ssp uwtable define void @foo(i32 %a, i32 %b, i32 %c) #0 { %factor11 = add i32 %b, %c %1 = add i32 %factor11, %a %result = mul i32 %1, 3 %2 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([20 x i8]* @.str, i64 0, i64 0), i32 %a, i32 %b, i32 %result, i32 %result, i32 %result) #2 ret void }
-reassociate的相关部分是Reassociate::OptimizeAdd()做的。
http://www.opensource.apple.com/source/clang/clang-137/src/lib/Transforms/Scalar/Reassociate.cpp
Reassociate::ReassociateExpression() -> Reassociate::LinearizeExprTree() -> Reassociate::OptimizeExpression() -> Reassociate::OptimizeAdd()
话说这reassociate+instcombine的组合对纯加法还ok,但是对其它情况(例如说带有减法)就不太能行了。
看这个例子:
int foo(int a, int b) { return a - b + a - b + a - b; }
LLVM居然给生成出了:
foo: # @foo imul ecx, esi, -3 lea eax, [rdi + 2*rdi] add eax, ecx ret
================================================
拿HotSpot 22.0也试了试上面的习题b)。发现HotSpot Server Compiler也没对这种情况优化嘛,哈哈
还是有3个加在这里,而不是理想的2个加
评论
1 楼
RednaxelaFX
2009-04-15
昨晚回帖的时候少打了个标签就发了。然后想删了再发却怎么也删不掉。过了半个小时再看的时候删是删掉了但我不记得地址了…… OTL
正题:
这个课件里也讲到了生成DAG来完成CSE(Common Subexpression Elimination)的算法。看起来跟我上面写的没本质上的不同,毕竟它也是借鉴龙书的;只不过它对<op,l,r>做了hash而我只在List<Expression>里线性搜索。顺带,这课件里是把cse作为Common Subexpression的缩写。
hmm……
这课件里第25页的题目,画出下面的基本块的DAG并指出存在的问题:
存在的问题是这俩语句连不成一个DAG是吧,没有一个共同的根,于是没办法用单一的DAG来表示这个基本块。
正题:
这个课件里也讲到了生成DAG来完成CSE(Common Subexpression Elimination)的算法。看起来跟我上面写的没本质上的不同,毕竟它也是借鉴龙书的;只不过它对<op,l,r>做了hash而我只在List<Expression>里线性搜索。顺带,这课件里是把cse作为Common Subexpression的缩写。
引用
Building a DAG
node( < id > ) -> current DAG for < id >
1. set node(y) to undefined, for each symbol y
2. for each statement x <- y op z, repeat steps 3, 4 and 5
3. if node(y) is undefined,
create a leaf for y
set node(y) to the new node
do the same for z
4. if < op, node(y), node(z) > doesn't exist,
create it;
let n be the node found or newly created node
5. delete x from the list of labels for node(x)
append x to the list of labels for n
set node(x) to n
node( < id > ) -> current DAG for < id >
1. set node(y) to undefined, for each symbol y
2. for each statement x <- y op z, repeat steps 3, 4 and 5
3. if node(y) is undefined,
create a leaf for y
set node(y) to the new node
do the same for z
4. if < op, node(y), node(z) > doesn't exist,
create it;
let n be the node found or newly created node
5. delete x from the list of labels for node(x)
append x to the list of labels for n
set node(x) to n
hmm……
这课件里第25页的题目,画出下面的基本块的DAG并指出存在的问题:
a = c + 1 c = b + 2
存在的问题是这俩语句连不成一个DAG是吧,没有一个共同的根,于是没办法用单一的DAG来表示这个基本块。
发表评论
-
The Prehistory of Java, HotSpot and Train
2014-06-02 08:18 0http://cs.gmu.edu/cne/itcore/vi ... -
MSJVM and Sun 1.0.x/1.1.x
2014-05-20 18:50 0当年的survey paper: http://www.sym ... -
Sun JDK1.4.2_28有TieredCompilation
2014-05-12 08:48 0原来以前Sun的JDK 1.4.2 update 28就已经有 ... -
IBM JVM notes (2014 ver)
2014-05-11 07:16 0Sovereign JIT http://publib.bou ... -
class data sharing by Apple
2014-03-28 05:17 0class data sharing is implement ... -
Java 8与静态工具类
2014-03-19 08:43 16125以前要在Java里实现所谓“静态工具类”(static uti ... -
Java 8的default method与method resolution
2014-03-19 02:23 10324先看看下面这个代码例子, interface IFoo { ... -
HotSpot Server VM与Server Class Machine
2014-02-18 13:21 0HotSpot VM历来有Client VM与Server V ... -
Java 8的lambda表达式在OpenJDK8中的实现
2014-02-04 12:08 0三月份JDK8就要发布首发了,现在JDK8 release c ... -
GC stack map与deopt stack map的异同
2014-01-08 09:56 0两者之间不并存在包含关系。它们有交集,但也各自有特别的地方。 ... -
HotSpot Server Compiler与data-flow analysis
2014-01-07 17:41 0http://en.wikipedia.org/wiki/Da ... -
基于LLVM实现VM的JIT的一些痛点
2014-01-07 17:25 0同事Philip Reames Sanjoy Das http ... -
tailcall notes
2013-12-27 07:42 0http://blogs.msdn.com/b/clrcode ... -
《自制编程语言》的一些笔记
2013-11-24 00:20 0http://kmaebashi.com/programmer ... -
字符串的一般封装方式的内存布局 (1): 元数据与字符串内容,整体还是分离?
2013-11-07 17:44 22244(Disclaimer:未经许可请 ... -
字符串的一般封装方式的内存布局 (0): 拿在手上的是什么
2013-11-04 18:22 21361(Disclaimer:未经许可请 ... -
字符串的一般封装方式的内存布局
2013-11-01 12:55 0(Disclaimer:未经许可请 ... -
关于string,内存布局,C++ std::string,CoW
2013-10-30 20:45 0(Disclaimer:未经许可请 ... -
对C语义的for循环的基本代码生成模式
2013-10-19 23:12 21729之前有同学在做龙书(第二版)题目,做到8.4的练习,跟我对答案 ... -
Java的instanceof是如何实现的
2013-09-22 16:57 0Java语言规范,Java SE 7版 http://docs ...
相关推荐
网格环境下的有依赖关系的任务的调度算法(简称DAG图),并且在Simgrid 环境下运行成功。
Daggraph一个Android开发者的Dagger依赖关系图生成器
为此,首先分析讨论了一组多DAG共享云计算资源调度中的多DAG数量、属性结构分布特点与资源需求量之间的关系,并在此基础上提出了基于资源需求强度预测变异方法的进化算法EFRD,有效地解决了云计算环境下多DAG共享...
基于java进行的实现简单Dag图;附件中包含java根据配置的dagJson。1实现了filter过滤,返回指定的字段;2实现了按指定字段排序,返回指定的字段;可以自己添加mysql、Oracle、redis、hive、es、sparksql、clickhouse...
airflow触发器可以一个dag中同时触发一个或者多个子dag,也可在子触发了的dag中在触发一个或者多个dag。
云环境中dag调度算法的设计与实现.doc
云环境中DAG调度算法的设计与实现.doc
具有任务内并行性的任务多使用DAG有向无环图表示,联合调度方式解决该类任务调度问题。
算法实验:计算DAG图最长路径并输出。
提出了基于有向无环图的构图和绘图算法,可完成课程拓扑关系图的自动绘制,并以C#为编程语言实现了该算法,最后通过实例验证了算法能直观地表现课程及其间拓扑关系效果,且运行界面整齐美观。
以四元式的形式输入任意给定的基本块,即一个字符串,最左边和右边是两个括号(),四个符号之间用三个逗号相隔。 在系统输出,基本块对应的三地址代码时。用户应当告诉系统自己以后还要用哪个变量。 输出的形式 ...
该包还包含生成随机非传递 DAG 以及派生传递 DAG 作为算法测试用例的代码。 包括将生成的 DAG 写入图形文件格式 .sif 或 .dot 以进行可视化的函数。 代码是作为 GraphViz 工具 tred 的替代而开发的,它在一些中等...
为了实现任务执行效率与执行代价的同步优化,提出了一种云计算环境中的DAG任务多目标调度优化算法。算法将多目标最优化问题以满足Pareto最优的均衡最优解集合的形式进行建模,以启发式方式对模型进行求解。为了衡量...
创建了一个JUnit测试来测试有效的DAG图排序算法。 可以使用以下命令运行: java -cp .:junit.jar:hamcrest-core.jar org.junit.runner.JUnitCore DAGSortTest 这不会测试特定的输出,而是测试符合拓扑顺序的一般...
编译原理的课设,DAG的优化,内有源代码
针对并行程序结构产生任务计算量和通信量的随机性 ,提出了一种扩展的随机 DA G 模型 。 基于此模型对 DA G调度中常用调度算法关键路径 SCP ( Static Critical Path) 算法进行了详细的分析 ,提出了相应的扩展的随机 ...
dag-factory是一个用于从YAML配置文件动态生成 DAG的库。 安装 要安装dag-factory,请运行pip install dag-factory 。 它需要Python 3.6.0+和Apache Airflow 1.10+。 用法 在Airflow环境中安装dag-factory之后,有...
daggraph,面向android开发人员的匕首依赖图生成器.zip
DAG任务调度算法&优化现实_Java_下载.zip
比较、聚合和聚类有向无环图 (DAG)。 纸张代码: ... update_center_greedy.m DAG 聚合的贪心算法。 update_center_median.m DAG 聚合的中值算法。 graph_k_mean.m用于 DAG 聚类的 K-Means 方法。