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