ID #5690

简单DAG生成算法的一个性质

“简单”嘛说明肯定有更麻烦、效果可能更好的办法。这里提到的算法就是这样。

龙书第二版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))

(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个。

对应到三地址代码,是:

Three-address code代码

t1 = a + b
t2 = t1 + t1

b)

AST:

DAG:

这个DAG的叶节点也是两个,但内部节点却有3个,比a)的多一个。

对应到三地址代码,则是:

Three-address code代码

t1 = a + b
t2 = t1 + a
t3 = t2 + b

问题是什么呢?习题里a)和b)的源码所代表的表达式的运算结果显然应该是一样的,但由于对应的AST的形状不同,导致生成的DAG也有所不同。

如果尝试对AST做等价变形然后再生成DAG,或许是可以选择出较优的版本,不过是否值得为了这个优化而使编译器变得复杂就是另一个问题了。对AST做了等价变形后,要比以某节点N1为根的子树与另一以N2为根的子树是否相同,就得专门写一个TreeComparer了。前面的简单算法是在生成节点的时候就做了比较,等于是做过了自底而上的比较,实现起来很简单。

要写个简单的解析器来生成上面的图十分简单。

首先定义语言的语法,尽量定义得简单些:

Bnf代码

E ->
    E '+' ID
  | ID
  | '(' E ')'

或者化简掉左递归后以EBNF表示:

Ebnf代码

E ->
    ID ( '+' ID )*
  | '(' E ')'

其中ID为单字符的英文字母。

那么可以简单的实现解析器如下:

C#代码

1.using System;
2.using System.Collections;
3.using System.Collections.Generic;
4.using System.IO;
5.using System.Linq;
6.
7.public enum NodeKind {
8.  Add,
9.  Id
10.}
11.
12.public abstract class Expression : IEquatable<Expression> {
13.  // DAG node cache
14.  static List<Expression> _cache;
15.
16.  // lazily initialize the cache for creating DAG nodes
17.  protected static List<Expression> Cache {
18.    get {
19.      if ( null == _cache ) {
20.        _cache = new List<Expression>( );
21.      }
22.      return _cache;
23.    }
24.  }
25.
26.  public virtual NodeKind NodeKind {
27.    get { throw new NotSupportedException( ); }
28.  }
29.
30.  // Create a BinaryExpression node representing an add operation
31.  public static BinaryExpression Add( Expression left, Expression right, bool useCache ) {
32.    var tempExpr = new BinaryExpression( left, right );
33.    if ( useCache ) {
34.      return LookupCache( tempExpr ) as BinaryExpression;
35.    } else {
36.      return tempExpr;
37.    }
38.  }
39.
40.  // Create an IdExpression representing an ID access
41.  public static IdExpression Id( char id, bool useCache ) {
42.    var tempExpr = new IdExpression( id );
43.    if ( useCache ) {
44.      return LookupCache( tempExpr ) as IdExpression;
45.    } else {
46.      return tempExpr;
47.    }
48.  }
49.
50.  static Expression LookupCache( Expression expr ) {
51.    var cachedExpr = Cache.FirstOrDefault( e => e.Equals( expr ) );
52.    if ( null == cachedExpr ) {
53.      Cache.Add( expr );
54.      cachedExpr = expr;
55.    }
56.    return cachedExpr;
57.  }
58.
59.  #region IEquatable<Expression> members and related methods
60.
61.  public override bool Equals( object other ) {
62.    if ( !( other is Expression ) ) return false;
63.    return Equals( other as Expression );
64.  }
65.
66.  public override int GetHashCode( ) {
67.    return GetHashCodeCore( );
68.  }
69.
70.  public abstract bool Equals( Expression other );
71.  protected abstract int GetHashCodeCore( );
72.
73.  #endregion
74.}
75.
76.public class BinaryExpression : Expression {
77.  Expression _left;
78.  Expression _right;
79.
80.  public BinaryExpression( Expression left, Expression right ) {
81.    _left = left;
82.    _right = right;
83.  }
84.
85.  public override NodeKind NodeKind {
86.    get { return NodeKind.Add; }
87.  }
88.
89.  public Expression Left {
90.    get { return _left; }
91.  }
92.
93.  public Expression Right {
94.    get { return _right; }
95.  }
96.
97.  public override bool Equals( Expression other ) {
98.    if ( ! ( other is BinaryExpression ) ) return false;
99.    var otherExpr = other as BinaryExpression;
100.    return otherExpr.Left == _left
101.      &&  otherExpr.Right == _right;
102.  }
103.
104.  protected override int GetHashCodeCore( ) {
105.    return _left.GetHashCode( ) * 37 + _right.GetHashCode( ) + 17;
106.  }
107.
108.  public override string ToString( ) {
109.    return string.Format( "(+ {0} {1})", _left.ToString( ), _right.ToString( ) );
110.  }
111.}
112.
113.public class IdExpression : Expression {
114.  char _id;
115.
116.  public IdExpression( char id ) {
117.    _id = id;
118.  }
119.
120.  public override NodeKind NodeKind {
121.    get { return NodeKind.Id; }
122.  }
123.
124.  public string IdString {
125.    get { return _id.ToString( ); }
126.  }
127.
128.  public override bool Equals( Expression other ) {
129.    if ( ! ( other is IdExpression ) ) return false;
130.    return _id == ( other as IdExpression )._id;
131.  }
132.
133.  protected override int GetHashCodeCore( ) {
134.    return _id.GetHashCode( );
135.  }
136.
137.  public override string ToString( ) {
138.    return IdString;
139.  }
140.}
141.
142.public class SyntaxException : Exception {
143.  public SyntaxException( ) {
144.  }
145.
146.  public SyntaxException( string message )
147.    : base( message ) {
148.  }
149.}
150.
151.public class Scanner : IEnumerable, IEnumerable<int> {
152.
153.  public const int EOS = -1;
154.
155.  string _input;
156.
157.  public Scanner( string input ) {
158.    _input = input;
159.  }
160.
161.  public IEnumerator GetEnumerator( ) {
162.    return ( this as IEnumerable<int> ).GetEnumerator( );
163.  }
164.
165.  IEnumerator<int> IEnumerable<int>.GetEnumerator( ) {
166.    return EnumerateChars( ).GetEnumerator( );
167.  }
168.
169.  static readonly int[ ] _punctuations = new int[ ] {
170.    '+', '(', ')'
171.  };
172.
173.  IEnumerable<int> EnumerateChars( ) {
174.    var reader = new StringReader( _input );
175.    int intChar;
176.    while ( 0 < ( intChar = reader.Read( ) ) ) {
177.      var c = Convert.ToChar( intChar );
178.      if ( Char.IsWhiteSpace( c ) ) continue;
179.      if ( _punctuations.Contains( intChar ) || Char.IsLetter( c ) ) {
180.        yield return intChar;
181.      } else {
182.        throw new SyntaxException(
183.          string.Format( "Invalid character: {0}", c.ToString( ) ) );
184.      }
185.    }
186.    yield return EOS;
187.  }
188.}
189.
190.public class Parser {
191.
192.  Scanner _scanner;
193.  IEnumerator<int> _input;
194.
195.  public Parser( Scanner scanner ) {
196.    _scanner = scanner;
197.  }
198.
199.  public Expression ParseToDag( ) {
200.    _input = ( _scanner as IEnumerable<int> ).GetEnumerator( );
201.    return Parse( true );
202.  }
203.
204.  public Expression ParseToAst( ) {
205.    _input = ( _scanner as IEnumerable<int> ).GetEnumerator( );
206.    return Parse( false );
207.  }
208.
209.  Expression Parse( bool useCache ) {
210.    _input.MoveNext( );
211.    var expr = ParseExpression( useCache );
212.    Match( Scanner.EOS );
213.    _input = null;
214.    return expr;
215.  }
216.
217.  Expression ParseExpression( bool useCache ) {
218.    Expression expr = null;
219.
220.    // E -> ID | '(' E ')'
221.    switch ( _input.Current ) {
222.    case '(':
223.      Match( '(' );
224.      expr = ParseExpression( useCache );
225.      Match( ')' );
226.      break;
227.    case Scanner.EOS:
228.      throw new SyntaxException( "Unexpected end of string" );
229.    default:
230.      expr = Expression.Id( Convert.ToChar( _input.Current ), useCache );
231.      _input.MoveNext( );
232.      break;
233.    }
234.
235.    // ( '+' ( ID | '(' E ')' ) )*
236.    while ( _input.Current == '+' ) {
237.      Match( '+' );
238.      Expression right = null;
239.      switch ( _input.Current ) {
240.      case '(':
241.        Match( '(' );
242.        right = ParseExpression( useCache );
243.        Match( ')' );
244.        break;
245.      case Scanner.EOS:
246.        throw new SyntaxException( "Unexpected end of string" );
247.      default:
248.        right = Expression.Id( Convert.ToChar( _input.Current ), useCache );
249.        _input.MoveNext( );
250.        break;
251.      }
252.      expr = Expression.Add( expr, right, useCache );
253.    }
254.
255.    return expr;
256.  }
257.
258.  void Match( int charCodeToMatch ) {
259.    if ( _input.Current == charCodeToMatch ) {
260.      _input.MoveNext( );
261.    } else {
262.      throw new SyntaxException(
263.        string.Format(
264.          "Expecting {0}, but found {1}",
265.          CharCodeToString( charCodeToMatch ),
266.          CharCodeToString( _input.Current ) ) );
267.    }
268.  }
269.
270.  string CharCodeToString( int charCode ) {
271.    return 0 < charCode ? Convert.ToChar( charCode ).ToString( ) : "End-Of-String";
272.  }
273.}
274.
275.class DotGenerator {
276.  Queue<Expression> _lastRank;
277.  Queue<Expression> _thisRank;
278.  TextWriter _writer;
279.  IEnumerator<string> _nameMaker;
280.  Dictionary<Expression, string> _nameMap;
281.
282.  public DotGenerator( ) {
283.    _lastRank = new Queue<Expression>( );
284.    _thisRank = new Queue<Expression>( );
285.  }
286.
287.  public string Generate( Expression root ) {
288.    _lastRank.Enqueue( root );
289.    _nameMap = new Dictionary<Expression, string>( IdentityComparer<Expression>.Instance );
290.    _nameMaker = GetNameMaker( ).GetEnumerator( );
291.    _writer = new StringWriter( );
292.    _writer.WriteLine( "digraph {" );
293.    _writer.WriteLine( "  node [fontsize=12, font=Courier, shape=plaintext]" );
294.    GenerateCore( );
295.    _writer.WriteLine( "}" );
296.    var dot = _writer.ToString( );
297.
298.    _nameMap.Clear( );
299.    _nameMap = null;
300.    _nameMaker = null;
301.    _writer = null;
302.    return dot;
303.  }
304.
305.  // breadth-first traverse
306.  void GenerateCore( ) {
307.    while ( 0 < _lastRank.Count ) {
308.      /*if ( 1 < _lastRank.Count ) {
309.        string[ ] rank = _lastRank.Select( e => _nameMap[ e ] ).ToArray( );
310.        _writer.WriteLine( "  {0} [ordering=out, style=invis]",
311.          string.Join( " -> ", rank ) );
312.        _writer.WriteLine( "  {{rank=same; {0} }}",
313.          string.Join( " ", rank ) );
314.      }*/
315.
316.      while ( 0 < _lastRank.Count ) {
317.        var expr = _lastRank.Dequeue( );
318.        DeclareNode( expr );
319.
320.        switch ( expr.NodeKind ) {
321.        case NodeKind.Add:
322.          var addExpr = expr as BinaryExpression;
323.          var left = addExpr.Left;
324.          var right = addExpr.Right;
325.
326.          if ( !_thisRank.Contains( left, IdentityComparer<Expression>.Instance ) ) {
327.            DeclareNode( addExpr.Left );
328.            _thisRank.Enqueue( left );
329.          }
330.          if ( !_thisRank.Contains( right, IdentityComparer<Expression>.Instance ) ) {
331.            DeclareNode( addExpr.Right );
332.            _thisRank.Enqueue( right );
333.          }
334.          _writer.WriteLine( "  {0} -> {1}",
335.            _nameMap[ expr ], _nameMap[ left ] );
336.          _writer.WriteLine( "  {0} -> {1}",
337.            _nameMap[ expr ], _nameMap[ right ] );
338.
339.          break;
340.        case NodeKind.Id:
341.          // DO NOTHING
342.          break;
343.        }
344.      }
345.
346.      // swap the two queues
347.      var tempQueue = _lastRank;
348.      _lastRank = _thisRank;
349.      _thisRank = tempQueue;
350.    }
351.  }
352.
353.  void DeclareNode( Expression expr ) {
354.    if ( !_nameMap.ContainsKey( expr ) ) {
355.      _nameMaker.MoveNext( );
356.      var name = _nameMaker.Current;
357.      _nameMap.Add( expr, name );
358.      switch ( expr.NodeKind ) {
359.      case NodeKind.Add:
360.        _writer.WriteLine( "  {0} [label=\"+\"]", name );
361.        break;
362.      case NodeKind.Id:
363.        var idExpr = expr as IdExpression;
364.        _writer.WriteLine( "  {0} [label=\"{1}\"]", name, idExpr.IdString );
365.        break;
366.      }
367.    }
368.  }
369.
370.  IEnumerable<string> GetNameMaker( ) {
371.    for ( var count = 0; ; ++count ) {
372.      yield return string.Format( "node_{0}", count.ToString( ) );
373.    }
374.  }
375.
376.  class IdentityComparer<T> : EqualityComparer<T> {
377.    static IdentityComparer<T> _instance;
378.
379.    static IdentityComparer( ) {
380.      _instance = new IdentityComparer<T>( );
381.    }
382.
383.    public static IdentityComparer<T> Instance {
384.      get { return _instance; }
385.    }
386.
387.    public override bool Equals( T first, T second ) {
388.      return object.ReferenceEquals( first, second );
389.    }
390.
391.    public override int GetHashCode( T obj ) {
392.      return obj.GetHashCode( );
393.    }
394.  }
395.}
396.
397.static class Program {
398.  static void Main( string[ ] args ) {
399.    string input = null;
400.    switch ( args.Length ) {
401.    case 0:
402.      Console.WriteLine( "Enter an expression on a line:" );
403.      Console.WriteLine( "(or give the expression as " +
404.                         "the first argument in command prompt)" );
405.      input = Console.ReadLine( );
406.      break;
407.    default:
408.      input = args[ 0 ];
409.      break;
410.    }
411.
412.    var scanner = new Scanner( input );
413.    var parser = new Parser( scanner );
414.    var dotGen = new DotGenerator( );
415.
416.    var ast = parser.ParseToAst( );
417.    var astDot = dotGen.Generate( ast );
418.    Console.WriteLine( "// DOT script for AST:" );
419.    Console.WriteLine( astDot );
420.
421.    var dag = parser.ParseToDag( );
422.    var dagDot = dotGen.Generate( dag );
423.    Console.WriteLine( "// DOT script for DAG:" );
424.    Console.WriteLine( dagDot );
425.  }
426.}

使用方法是直接运行该程序,然后在一行上输入一个符合前面语法规则的表达式,或者是在运行该程序的时候提供一个参数作为这个表达式。运行程序后,如果解析正常结束,那么会在标准输出上先后输出对应AST和DAG的DOT代码。

输出的DOT代码通过Graphviz的dot程序就能生成图片。

例如说运行程序后输入a + b + (a + b)回车,会看到:

Dot代码

// 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代码

// 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文件里,则:

Command prompt代码

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类如下:

C#代码

1.class DotGenerator {
2.  HashSet<Expression> _seenNodes;
3.  TextWriter _writer;
4.  IEnumerator<string> _nameMaker;
5.  Dictionary<Expression, string> _nameMap;
6.
7.  public DotGenerator( ) {
8.    _seenNodes = new HashSet<Expression>(
9.      IdentityComparer<Expression>.Instance );
10.    _nameMap = new Dictionary<Expression, string>(
11.      IdentityComparer<Expression>.Instance );
12.  }
13.
14.  public string Generate( Expression root ) {
15.    _nameMaker = GetNameMaker( ).GetEnumerator( );
16.    _writer = new StringWriter( );
17.    _writer.WriteLine( "digraph {" );
18.    _writer.WriteLine( "  node [fontsize=12, font=Courier, shape=plaintext]" );
19.    GenerateCore( root );
20.    _writer.WriteLine( "}" );
21.    var dot = _writer.ToString( );
22.
23.    _seenNodes.Clear( );
24.    _nameMap.Clear( );
25.    _nameMaker = null;
26.    _writer = null;
27.    return dot;
28.  }
29.
30.  // depth-first traverse
31.  void GenerateCore( Expression expr ) {
32.    DeclareNode( expr );
33.    _seenNodes.Add( expr );
34.    switch ( expr.NodeKind ) {
35.    case NodeKind.Add:
36.      var addExpr = expr as BinaryExpression;
37.      var left = addExpr.Left;
38.      var right = addExpr.Right;
39.
40.      if ( !_seenNodes.Contains( left ) ) {
41.        GenerateCore( left );
42.      }
43.      if ( !_seenNodes.Contains( right ) ) {
44.        GenerateCore( right );
45.      }
46.      _writer.WriteLine( "  {0} -> {1}",
47.        _nameMap[ expr ], _nameMap[ left ] );
48.      _writer.WriteLine( "  {0} -> {1}",
49.        _nameMap[ expr ], _nameMap[ right ] );
50.
51.      break;
52.    case NodeKind.Id:
53.      // DO NOTHING
54.      break;
55.    }
56.  }
57.
58.
59.  void DeclareNode( Expression expr ) {
60.    if ( !_nameMap.ContainsKey( expr ) ) {
61.      _nameMaker.MoveNext( );
62.      var name = _nameMaker.Current;
63.      _nameMap.Add( expr, name );
64.      switch ( expr.NodeKind ) {
65.      case NodeKind.Add:
66.        _writer.WriteLine( "  {0} [label=\"+\"]", name );
67.        break;
68.      case NodeKind.Id:
69.        var idExpr = expr as IdExpression;
70.        _writer.WriteLine( "  {0} [label=\"{1}\"]", name, idExpr.IdString );
71.        break;
72.      }
73.    }
74.  }
75.
76.  IEnumerable<string> GetNameMaker( ) {
77.    for ( var count = 0; ; ++count ) {
78.      yield return string.Format( "node_{0}", count.ToString( ) );
79.    }
80.  }
81.
82.  class IdentityComparer<T> : EqualityComparer<T> {
83.    static IdentityComparer<T> _instance;
84.
85.    static IdentityComparer( ) {
86.      _instance = new IdentityComparer<T>( );
87.    }
88.
89.    public static IdentityComparer<T> Instance {
90.      get { return _instance; }
91.    }
92.
93.    public override bool Equals( T first, T second ) {
94.      return object.ReferenceEquals( first, second );
95.    }
96.
97.    public override int GetHashCode( T obj ) {
98.      return obj.GetHashCode( );
99.    }
100.  }
101.}

对应习题里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表达式:

C#代码

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应该通过分析定义-使用关系做了至少一趟优化,因为这段代码:

C#代码

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编译过后就只剩下这么多了:

C#代码

static class TestDAG {
    static void Main(string[] args) {
        int a = 0x001001;
        int b = 0x010002;
    }
}

很明显如果继续用定义-使用关系来优化的话,整个Main()方法应该变成空的才对。

C#不允许用户对内建类型的运算符做重载,所以还好,至少System.Int32的加法运算符能保证没有可见的副作用,所以可以优化。不过试想一个这样的类:

C#代码

public class Foo {
    int _value;
    public int Value {
        get {
            Console.WriteLine( _value );
            return _value;
        }
        set { _value = value; }
    }
}

然后要是foo是Foo的一个实例,我要是写:

C#代码

1 + foo.Value + (1 + foo.Value)

要是被优化了的话,Console.WriteLine(_value)就只会发生一次,这就糟糕了。

GCC 4.3.0在编译这几个表达式的时候,使用-O2,对代码:

C代码

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的初始化相关的表达式编译得到:

X86 assembler代码

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()就没了 = =


2011-07-01 18:28
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

递归的应用 - 最简单分形图形实现

根据前序和中序序列生成二叉树

数据结构在游戏中的简单应用

C语言实现UUID生成算法(WIN32版本)

一个简单有效的洗牌算法