Enable polymorphic inlining of StringBase [] and StringBase codeUnitAt

Enable polymorphic inlining of StringBase [] and StringBase codeUnitAt.

R=fschneider@google.com

Committed: https://code.google.com/p/dart/source/detail?r=32749

[Cutch, 2014-02-12 23:00:00]

With this CL the below benchmark is sped up:

test1 is sped up ~4x
test2 is sped up ~12x

---

test2(String a, String b) {
  if (a.length != b.length) {
    return false;
  }
  for (var i = 0; i < a.length; i++) {
    if (a[i] != b[i]) {
      return false;
    }
  }
  return true;
}

test1(String a, String b) {
  return a == b;
}

var LEN = 500;

var ITER = 10000000 / LEN;

measure(fn, a, b) {
  for (var i = 0; i < ITER; i++) {
    if (!fn(a, b)) throw 123;
  }
}  

main() {
  var n = LEN;
  StringBuffer s = new StringBuffer();
  for (var i=0; i < n; ++i) s.write("A");
  String t = s.toString();
  String u = s.toString();
  String v = s.toString() + "\u1234";
  String w = s.toString() + "\u1234";
  Stopwatch stopwatch = new Stopwatch()..start();
  for (var i=0; i<10; i++) measure(test1, t, u);
  print(stopwatch.elapsed);
  stopwatch.reset();
  for (var i=0; i<10; i++) measure(test1, v, w);
  print(stopwatch.elapsed);
}

[Florian Schneider, 2014-02-13 11:57:46]

Looks almost good - My only comment is about removing the bit of old code.

Also, make sure that unit tests cover the newly added code.

https://codereview.chromium.org/161853002/diff/1/runtime/vm/flow_graph_optimi...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/161853002/diff/1/runtime/vm/flow_graph_optimi...
runtime/vm/flow_graph_optimizer.cc:2392: bool skip_check = false;
I'm pretty sure that constant propagation handles bounds checks properly by now.
You can remove the skip_check variable and the code below and always emit the
bounds check. It will be eliminated later on.

https://codereview.chromium.org/161853002/diff/1/runtime/vm/flow_graph_optimi...
runtime/vm/flow_graph_optimizer.cc:2473: LoadIndexedInstr*
FlowGraphOptimizer::BuildStringCodeUnitAt(
I think you should be able to use your newly introduced builder function instead
of this one.

https://codereview.chromium.org/161853002/diff/1/runtime/vm/flow_graph_optimi...
runtime/vm/flow_graph_optimizer.cc:2603: if ((class_ids[0] == kOneByteStringCid)
&& (ic_data.NumberOfChecks() == 1)) {
Here you should use the newly added builder functions instead of the old ones.
As as positive side-effect you also get 2-byte strings handled for free.

[Cutch, 2014-02-13 18:15:46]

I ended up adding a generic routine for replacing an InstanceCallInstr with
inlined code. It would be nice if all inlining was moved into
TryInlineRecognizedMethod so we don't distinguish between monomorphic and
polymorphic inlining.

[Cutch, 2014-02-13 18:44:57]

Note, I had to disable inlining of [] on two byte strings. It was leading to
crashes (and the instruction StringFromCharCode had a foreboding ASSERT that the
source string has to be a one byte string.)

[Florian Schneider, 2014-02-17 11:50:54]

On 2014/02/13 18:44:57, Cutch wrote:
> Note, I had to disable inlining of [] on two byte strings. It was leading to
> crashes (and the instruction StringFromCharCode had a foreboding ASSERT that
the
> source string has to be a one byte string.)

Oh yes - that's expected. The optimized version of StringFromCharCode only
supports 1-byte strings because it uses a lookup in the 256 entry table.

[Florian Schneider, 2014-02-17 11:56:12]

LGTM.

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:2508: if
(RawObject::IsExternalStringClassId(cid)) {
Add a TODO for handling external strings in the same way.

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:2530: if
(RawObject::IsExternalStringClassId(cid) || cid != kOneByteStringCid) {
Add a TODO for handling external strings in the same way.

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:185: #define POLYMORPHIC_TARGET_LIST(V)      
                                      \
dbc: For now it's ok, but it's kind of tedious to keep these different lists. I
hope once all recognized methods are supported with polymorphic inlining we can
get rid of this subset of RECOGNIZED_LIST.

https://codereview.chromium.org/161853002/diff/140001/tests/language/vm/strin...
File tests/language/vm/string_polymorphic_test.dart (right):

https://codereview.chromium.org/161853002/diff/140001/tests/language/vm/strin...
tests/language/vm/string_polymorphic_test.dart:15: var ITER = 10000000 / LEN;
The iteration count can probably be lower if you already use
optimization-counter-threshold=10.

[Cutch, 2014-02-18 17:00:30]

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
File runtime/vm/flow_graph_optimizer.cc (right):

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:2508: if
(RawObject::IsExternalStringClassId(cid)) {
On 2014/02/17 11:56:12, Florian Schneider wrote:
> Add a TODO for handling external strings in the same way.

Done.

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/flow_graph_o...
runtime/vm/flow_graph_optimizer.cc:2530: if
(RawObject::IsExternalStringClassId(cid) || cid != kOneByteStringCid) {
On 2014/02/17 11:56:12, Florian Schneider wrote:
> Add a TODO for handling external strings in the same way.

Done.

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/intermediate...
File runtime/vm/intermediate_language.h (right):

https://codereview.chromium.org/161853002/diff/140001/runtime/vm/intermediate...
runtime/vm/intermediate_language.h:185: #define POLYMORPHIC_TARGET_LIST(V)      
                                      \
On 2014/02/17 11:56:12, Florian Schneider wrote:
> dbc: For now it's ok, but it's kind of tedious to keep these different lists.
I
> hope once all recognized methods are supported with polymorphic inlining we
can
> get rid of this subset of RECOGNIZED_LIST.

I'd like to see this removed too. We need to teach the polymorphic inliner how
to do polymorphic inlining of multiple receivers with the same target function
(see flow_graph_optimizer.cc:3624).

https://codereview.chromium.org/161853002/diff/140001/tests/language/vm/strin...
File tests/language/vm/string_polymorphic_test.dart (right):

https://codereview.chromium.org/161853002/diff/140001/tests/language/vm/strin...
tests/language/vm/string_polymorphic_test.dart:15: var ITER = 10000000 / LEN;
On 2014/02/17 11:56:12, Florian Schneider wrote:
> The iteration count can probably be lower if you already use
> optimization-counter-threshold=10.

Done.

[Cutch, 2014-02-18 17:41:19]

Committed patchset #5 manually as r32749 (presubmit successful).