Instruction::GetBlock has quadradic time complexity

[DartBot]

This issue was originally filed by zerny...@google.com

---

The VMs Instruction::GetBlock has quadradic time complexity which can cause excessive slowdown in large blocks with repeated variable uses. See for example tests/corelib/regexp/global_test.dart

[floitschG]

Added Triaged label.

[DartBot]

This comment was originally written by zerny...@google.com

---

Set owner to @fsc8000.

[iposva-google]

Added Accepted label.

[ErikCorryGoogle]

This is still an issue. Example stack trace from pcre_test:

#0 0x0000000000d6b877 in dart::Instruction::IsBlockEntry (this=0x1f88a00) at ../../runtime/vm/compiler/backend/il.h:791
#1 0x0000000000e1ea03 in dart::Instruction::GetBlock (this=) at ../../runtime/vm/compiler/backend/il.cc:681
#2 0x0000000000e0a21e in dart::IsDominatedUse (dom=0x6c84790, use=0x46bb380) at ../../runtime/vm/compiler/backend/flow_graph.cc:2025
#3 0x0000000000e080e6 in dart::FlowGraph::RenameDominatedUses (def=, dom=0x6c84790, other=0x6c84790) at ../../runtime/vm/compiler/backend/flow_graph.cc:2045
#4 0x0000000000e07feb in dart::FlowGraph::EnsureRedefinition (this=0x5df5c78, prev=0x30a14d8, original=, compile_type=...) at ../../runtime/vm/compiler/backend/flow_graph.cc:1321
#5 0x0000000000e85c2e in dart::FlowGraphTypePropagator::EnsureMoreAccurateRedefinition (this=0x7fffffffab68, prev=0x46bb380, original=0x6c84790, new_type=...) at ../../runtime/vm/compiler/backend/type_propagator.cc:214

Reproduce with:

./tools/test.py -c dartkp --strong --time -m debug -a x64 corelib_2/regexp/pcre_test