Improve dominator computation to avoid worst-case quadratic time.
authorfschneider@chromium.org <fschneider@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Tue, 8 Nov 2011 10:18:25 +0000 (10:18 +0000)
committerfschneider@chromium.org <fschneider@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Tue, 8 Nov 2011 10:18:25 +0000 (10:18 +0000)
commit2a1f08a1c2b62c5986950ede9bba5fb3b9d9f060
treeece222377c9c0bb564155449ccedb66ad2a0d471
parent3628c9347cc22d8ad5124c654e714f988b245cc2
Improve dominator computation to avoid worst-case quadratic time.

In case of a degenerated CFG like in the example below processing
predecessors in the wrong order yields n^2 runtime.

  do {
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    if (x) break;
    // etc.
  } while (false);

Reversing iteration order avoids this.
Review URL: http://codereview.chromium.org/8502012

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@9905 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
src/hydrogen.cc