| OLD | NEW |
| 1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "src/compiler/access-builder.h" | 5 #include "src/compiler/access-builder.h" |
| 6 #include "src/compiler/common-operator.h" | 6 #include "src/compiler/common-operator.h" |
| 7 #include "src/compiler/graph.h" | 7 #include "src/compiler/graph.h" |
| 8 #include "src/compiler/graph-visualizer.h" | 8 #include "src/compiler/graph-visualizer.h" |
| 9 #include "src/compiler/js-graph.h" | 9 #include "src/compiler/js-graph.h" |
| 10 #include "src/compiler/js-operator.h" | 10 #include "src/compiler/js-operator.h" |
| (...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 109 } | 109 } |
| 110 return node; | 110 return node; |
| 111 } | 111 } |
| 112 | 112 |
| 113 const Operator* op(int count, bool effect) { | 113 const Operator* op(int count, bool effect) { |
| 114 return effect ? common.EffectPhi(count) | 114 return effect ? common.EffectPhi(count) |
| 115 : common.Phi(MachineRepresentation::kTagged, count); | 115 : common.Phi(MachineRepresentation::kTagged, count); |
| 116 } | 116 } |
| 117 | 117 |
| 118 Node* Return(Node* val, Node* effect, Node* control) { | 118 Node* Return(Node* val, Node* effect, Node* control) { |
| 119 Node* ret = graph.NewNode(common.Return(), val, effect, control); | 119 Node* zero = graph.NewNode(common.Int32Constant(0)); |
| 120 Node* ret = graph.NewNode(common.Return(), zero, val, effect, control); |
| 120 end->ReplaceInput(0, ret); | 121 end->ReplaceInput(0, ret); |
| 121 return ret; | 122 return ret; |
| 122 } | 123 } |
| 123 | 124 |
| 124 LoopTree* GetLoopTree() { | 125 LoopTree* GetLoopTree() { |
| 125 if (loop_tree == NULL) { | 126 if (loop_tree == NULL) { |
| 126 if (FLAG_trace_turbo_graph) { | 127 if (FLAG_trace_turbo_graph) { |
| 127 OFStream os(stdout); | 128 OFStream os(stdout); |
| 128 os << AsRPO(graph); | 129 os << AsRPO(graph); |
| 129 } | 130 } |
| (...skipping 559 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 689 Node* p3 = t.jsgraph.Int32Constant(33); | 690 Node* p3 = t.jsgraph.Int32Constant(33); |
| 690 | 691 |
| 691 Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); | 692 Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
| 692 Node* phi = t.graph.NewNode( | 693 Node* phi = t.graph.NewNode( |
| 693 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop); | 694 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop); |
| 694 Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); | 695 Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); |
| 695 Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); | 696 Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
| 696 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); | 697 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 697 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); | 698 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 698 loop->ReplaceInput(1, if_true); | 699 loop->ReplaceInput(1, if_true); |
| 699 Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit); | 700 Node* zero = t.graph.NewNode(t.common.Int32Constant(0)); |
| 701 Node* ret = t.graph.NewNode(t.common.Return(), zero, p3, t.start, exit); |
| 700 t.graph.SetEnd(ret); | 702 t.graph.SetEnd(ret); |
| 701 | 703 |
| 702 Node* choices[] = {p1, phi, cond}; | 704 Node* choices[] = {p1, phi, cond}; |
| 703 p1->ReplaceUses(choices[i]); | 705 p1->ReplaceUses(choices[i]); |
| 704 p2->ReplaceUses(choices[j]); | 706 p2->ReplaceUses(choices[j]); |
| 705 p3->ReplaceUses(choices[k]); | 707 p3->ReplaceUses(choices[k]); |
| 706 | 708 |
| 707 Node* header[] = {loop, phi}; | 709 Node* header[] = {loop, phi}; |
| 708 Node* body[] = {cond, branch, if_true}; | 710 Node* body[] = {cond, branch, if_true}; |
| 709 t.CheckLoop(header, 2, body, 3); | 711 t.CheckLoop(header, 2, body, 3); |
| (...skipping 26 matching lines...) Expand all Loading... |
| 736 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); | 738 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
| 737 Node* phi2 = t.graph.NewNode( | 739 Node* phi2 = t.graph.NewNode( |
| 738 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p2, loop2); | 740 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p2, loop2); |
| 739 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); | 741 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); |
| 740 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); | 742 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
| 741 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); | 743 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
| 742 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); | 744 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
| 743 loop2->ReplaceInput(1, if_true2); | 745 loop2->ReplaceInput(1, if_true2); |
| 744 loop1->ReplaceInput(1, exit2); | 746 loop1->ReplaceInput(1, exit2); |
| 745 | 747 |
| 746 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); | 748 Node* zero = t.graph.NewNode(t.common.Int32Constant(0)); |
| 749 Node* ret = |
| 750 t.graph.NewNode(t.common.Return(), zero, phi1, t.start, exit1); |
| 747 t.graph.SetEnd(ret); | 751 t.graph.SetEnd(ret); |
| 748 | 752 |
| 749 Node* choices[] = {p1, phi1, cond1, phi2, cond2}; | 753 Node* choices[] = {p1, phi1, cond1, phi2, cond2}; |
| 750 p1->ReplaceUses(choices[i]); | 754 p1->ReplaceUses(choices[i]); |
| 751 p2->ReplaceUses(choices[j]); | 755 p2->ReplaceUses(choices[j]); |
| 752 p3->ReplaceUses(choices[k]); | 756 p3->ReplaceUses(choices[k]); |
| 753 | 757 |
| 754 Node* header1[] = {loop1, phi1}; | 758 Node* header1[] = {loop1, phi1}; |
| 755 Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, | 759 Node* body1[] = {cond1, branch1, if_true1, exit2, loop2, |
| 756 phi2, cond2, branch2, if_true2}; | 760 phi2, cond2, branch2, if_true2}; |
| (...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 823 p3a, p3c, loop3); | 827 p3a, p3c, loop3); |
| 824 Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); | 828 Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); |
| 825 Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); | 829 Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); |
| 826 Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); | 830 Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); |
| 827 Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); | 831 Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); |
| 828 | 832 |
| 829 loop3->ReplaceInput(1, if_true3); | 833 loop3->ReplaceInput(1, if_true3); |
| 830 loop2->ReplaceInput(1, exit3); | 834 loop2->ReplaceInput(1, exit3); |
| 831 loop1->ReplaceInput(1, exit2); | 835 loop1->ReplaceInput(1, exit2); |
| 832 | 836 |
| 833 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); | 837 Node* zero = t.graph.NewNode(t.common.Int32Constant(0)); |
| 838 Node* ret = t.graph.NewNode(t.common.Return(), zero, phi1, t.start, exit1); |
| 834 t.graph.SetEnd(ret); | 839 t.graph.SetEnd(ret); |
| 835 | 840 |
| 836 // Mutate the graph according to the edge choices. | 841 // Mutate the graph according to the edge choices. |
| 837 | 842 |
| 838 Node* o1[] = {t.one}; | 843 Node* o1[] = {t.one}; |
| 839 Node* o2[] = {t.one, phi1, cond1}; | 844 Node* o2[] = {t.one, phi1, cond1}; |
| 840 Node* o3[] = {t.one, phi1, cond1, phi2, cond2}; | 845 Node* o3[] = {t.one, phi1, cond1, phi2, cond2}; |
| 841 | 846 |
| 842 p1a->ReplaceUses(o1[c1a]); | 847 p1a->ReplaceUses(o1[c1a]); |
| 843 p1b->ReplaceUses(o1[c1b]); | 848 p1b->ReplaceUses(o1[c1b]); |
| (...skipping 92 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 936 loop->ReplaceInput(1, if_true); | 941 loop->ReplaceInput(1, if_true); |
| 937 | 942 |
| 938 nodes[i * 4 + 0] = loop; | 943 nodes[i * 4 + 0] = loop; |
| 939 nodes[i * 4 + 1] = phi; | 944 nodes[i * 4 + 1] = phi; |
| 940 nodes[i * 4 + 2] = branch; | 945 nodes[i * 4 + 2] = branch; |
| 941 nodes[i * 4 + 3] = if_true; | 946 nodes[i * 4 + 3] = if_true; |
| 942 | 947 |
| 943 last = exit; | 948 last = exit; |
| 944 } | 949 } |
| 945 | 950 |
| 946 Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, last); | 951 Node* zero = t.graph.NewNode(t.common.Int32Constant(0)); |
| 952 Node* ret = t.graph.NewNode(t.common.Return(), zero, t.p0, t.start, last); |
| 947 t.graph.SetEnd(ret); | 953 t.graph.SetEnd(ret); |
| 948 | 954 |
| 949 // Verify loops. | 955 // Verify loops. |
| 950 for (int i = 0; i < count; i++) { | 956 for (int i = 0; i < count; i++) { |
| 951 t.CheckLoop(nodes + i * 4, 2, nodes + i * 4 + 2, 2); | 957 t.CheckLoop(nodes + i * 4, 2, nodes + i * 4 + 2, 2); |
| 952 } | 958 } |
| 953 } | 959 } |
| 954 | 960 |
| 955 | 961 |
| 956 static void RunManyNestedLoops_i(int count) { | 962 static void RunManyNestedLoops_i(int count) { |
| 957 LoopFinderTester t; | 963 LoopFinderTester t; |
| 958 Node** nodes = t.zone()->NewArray<Node*>(count * 5); | 964 Node** nodes = t.zone()->NewArray<Node*>(count * 5); |
| 959 Node* k11 = t.jsgraph.Int32Constant(11); | 965 Node* k11 = t.jsgraph.Int32Constant(11); |
| 960 Node* k12 = t.jsgraph.Int32Constant(12); | 966 Node* k12 = t.jsgraph.Int32Constant(12); |
| 961 Node* outer = nullptr; | 967 Node* outer = nullptr; |
| 962 Node* entry = t.start; | 968 Node* entry = t.start; |
| 963 | 969 |
| 964 // Build loops. | 970 // Build loops. |
| 971 Node* zero = t.graph.NewNode(t.common.Int32Constant(0)); |
| 965 for (int i = 0; i < count; i++) { | 972 for (int i = 0; i < count; i++) { |
| 966 Node* loop = t.graph.NewNode(t.common.Loop(2), entry, t.start); | 973 Node* loop = t.graph.NewNode(t.common.Loop(2), entry, t.start); |
| 967 Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), | 974 Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 968 k11, k12, loop); | 975 k11, k12, loop); |
| 969 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); | 976 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); |
| 970 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); | 977 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
| 971 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); | 978 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
| 972 | 979 |
| 973 nodes[i * 5 + 0] = exit; // outside | 980 nodes[i * 5 + 0] = exit; // outside |
| 974 nodes[i * 5 + 1] = loop; // header | 981 nodes[i * 5 + 1] = loop; // header |
| 975 nodes[i * 5 + 2] = phi; // header | 982 nodes[i * 5 + 2] = phi; // header |
| 976 nodes[i * 5 + 3] = branch; // body | 983 nodes[i * 5 + 3] = branch; // body |
| 977 nodes[i * 5 + 4] = if_true; // body | 984 nodes[i * 5 + 4] = if_true; // body |
| 978 | 985 |
| 979 if (outer != nullptr) { | 986 if (outer != nullptr) { |
| 980 // inner loop. | 987 // inner loop. |
| 981 outer->ReplaceInput(1, exit); | 988 outer->ReplaceInput(1, exit); |
| 982 } else { | 989 } else { |
| 983 // outer loop. | 990 // outer loop. |
| 984 Node* ret = t.graph.NewNode(t.common.Return(), t.p0, t.start, exit); | 991 Node* ret = t.graph.NewNode(t.common.Return(), zero, t.p0, t.start, exit); |
| 985 t.graph.SetEnd(ret); | 992 t.graph.SetEnd(ret); |
| 986 } | 993 } |
| 987 outer = loop; | 994 outer = loop; |
| 988 entry = if_true; | 995 entry = if_true; |
| 989 } | 996 } |
| 990 outer->ReplaceInput(1, entry); // innermost loop. | 997 outer->ReplaceInput(1, entry); // innermost loop. |
| 991 | 998 |
| 992 // Verify loops. | 999 // Verify loops. |
| 993 for (int i = 0; i < count; i++) { | 1000 for (int i = 0; i < count; i++) { |
| 994 int k = i * 5; | 1001 int k = i * 5; |
| (...skipping 19 matching lines...) Expand all Loading... |
| 1014 TEST(LaManyNested_62) { RunManyNestedLoops_i(62); } | 1021 TEST(LaManyNested_62) { RunManyNestedLoops_i(62); } |
| 1015 TEST(LaManyNested_63) { RunManyNestedLoops_i(63); } | 1022 TEST(LaManyNested_63) { RunManyNestedLoops_i(63); } |
| 1016 TEST(LaManyNested_64) { RunManyNestedLoops_i(64); } | 1023 TEST(LaManyNested_64) { RunManyNestedLoops_i(64); } |
| 1017 | 1024 |
| 1018 | 1025 |
| 1019 TEST(LaPhiTangle) { LoopFinderTester t; } | 1026 TEST(LaPhiTangle) { LoopFinderTester t; } |
| 1020 | 1027 |
| 1021 } // namespace compiler | 1028 } // namespace compiler |
| 1022 } // namespace internal | 1029 } // namespace internal |
| 1023 } // namespace v8 | 1030 } // namespace v8 |
| OLD | NEW |