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 |