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 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
104 } | 104 } |
105 | 105 |
106 Node* SetSelfReferences(Node* node) { | 106 Node* SetSelfReferences(Node* node) { |
107 for (Edge edge : node->input_edges()) { | 107 for (Edge edge : node->input_edges()) { |
108 if (edge.to() == self) node->ReplaceInput(edge.index(), node); | 108 if (edge.to() == self) node->ReplaceInput(edge.index(), node); |
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) : common.Phi(kMachAnyTagged, count); | 114 return effect ? common.EffectPhi(count) |
| 115 : common.Phi(MachineRepresentation::kTagged, count); |
115 } | 116 } |
116 | 117 |
117 Node* Return(Node* val, Node* effect, Node* control) { | 118 Node* Return(Node* val, Node* effect, Node* control) { |
118 Node* ret = graph.NewNode(common.Return(), val, effect, control); | 119 Node* ret = graph.NewNode(common.Return(), val, effect, control); |
119 end->ReplaceInput(0, ret); | 120 end->ReplaceInput(0, ret); |
120 return ret; | 121 return ret; |
121 } | 122 } |
122 | 123 |
123 LoopTree* GetLoopTree() { | 124 LoopTree* GetLoopTree() { |
124 if (loop_tree == NULL) { | 125 if (loop_tree == NULL) { |
(...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
259 Node* header[] = {w.loop}; | 260 Node* header[] = {w.loop}; |
260 Node* body[] = {w.branch, w.if_true}; | 261 Node* body[] = {w.branch, w.if_true}; |
261 t.CheckLoop(header, 1, body, 2); | 262 t.CheckLoop(header, 1, body, 2); |
262 } | 263 } |
263 | 264 |
264 | 265 |
265 TEST(LaLoop1phi) { | 266 TEST(LaLoop1phi) { |
266 // One loop with a simple phi. | 267 // One loop with a simple phi. |
267 LoopFinderTester t; | 268 LoopFinderTester t; |
268 While w(t, t.p0); | 269 While w(t, t.p0); |
269 Node* phi = | 270 Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kTagged, 2), |
270 t.graph.NewNode(t.common.Phi(kMachAnyTagged, 2), t.zero, t.one, w.loop); | 271 t.zero, t.one, w.loop); |
271 t.Return(phi, t.start, w.exit); | 272 t.Return(phi, t.start, w.exit); |
272 | 273 |
273 Node* chain[] = {w.loop}; | 274 Node* chain[] = {w.loop}; |
274 t.CheckNestedLoops(chain, 1); | 275 t.CheckNestedLoops(chain, 1); |
275 | 276 |
276 Node* header[] = {w.loop, phi}; | 277 Node* header[] = {w.loop, phi}; |
277 Node* body[] = {w.branch, w.if_true}; | 278 Node* body[] = {w.branch, w.if_true}; |
278 t.CheckLoop(header, 2, body, 2); | 279 t.CheckLoop(header, 2, body, 2); |
279 } | 280 } |
280 | 281 |
(...skipping 187 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
468 } | 469 } |
469 | 470 |
470 | 471 |
471 TEST(LaNestedLoop1x) { | 472 TEST(LaNestedLoop1x) { |
472 // One loop nested in another. | 473 // One loop nested in another. |
473 LoopFinderTester t; | 474 LoopFinderTester t; |
474 While w1(t, t.p0); | 475 While w1(t, t.p0); |
475 While w2(t, t.p0); | 476 While w2(t, t.p0); |
476 w2.nest(w1); | 477 w2.nest(w1); |
477 | 478 |
478 const Operator* op = t.common.Phi(kMachInt32, 2); | 479 const Operator* op = t.common.Phi(MachineRepresentation::kWord32, 2); |
479 Node* p1a = t.graph.NewNode(op, t.p0, t.p0, w1.loop); | 480 Node* p1a = t.graph.NewNode(op, t.p0, t.p0, w1.loop); |
480 Node* p1b = t.graph.NewNode(op, t.p0, t.p0, w1.loop); | 481 Node* p1b = t.graph.NewNode(op, t.p0, t.p0, w1.loop); |
481 Node* p2a = t.graph.NewNode(op, p1a, t.p0, w2.loop); | 482 Node* p2a = t.graph.NewNode(op, p1a, t.p0, w2.loop); |
482 Node* p2b = t.graph.NewNode(op, p1b, t.p0, w2.loop); | 483 Node* p2b = t.graph.NewNode(op, p1b, t.p0, w2.loop); |
483 | 484 |
484 p1a->ReplaceInput(1, p2b); | 485 p1a->ReplaceInput(1, p2b); |
485 p1b->ReplaceInput(1, p2a); | 486 p1b->ReplaceInput(1, p2a); |
486 | 487 |
487 p2a->ReplaceInput(1, p2b); | 488 p2a->ReplaceInput(1, p2b); |
488 p2b->ReplaceInput(1, p2a); | 489 p2b->ReplaceInput(1, p2a); |
(...skipping 192 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
681 for (int i = 0; i < 3; i++) { | 682 for (int i = 0; i < 3; i++) { |
682 for (int j = 0; j < 3; j++) { | 683 for (int j = 0; j < 3; j++) { |
683 for (int k = 0; k < 3; k++) { | 684 for (int k = 0; k < 3; k++) { |
684 LoopFinderTester t; | 685 LoopFinderTester t; |
685 | 686 |
686 Node* p1 = t.jsgraph.Int32Constant(11); | 687 Node* p1 = t.jsgraph.Int32Constant(11); |
687 Node* p2 = t.jsgraph.Int32Constant(22); | 688 Node* p2 = t.jsgraph.Int32Constant(22); |
688 Node* p3 = t.jsgraph.Int32Constant(33); | 689 Node* p3 = t.jsgraph.Int32Constant(33); |
689 | 690 |
690 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); |
691 Node* phi = | 692 Node* phi = t.graph.NewNode( |
692 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop); | 693 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop); |
693 Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); | 694 Node* cond = t.graph.NewNode(&kIntAdd, phi, p2); |
694 Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); | 695 Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop); |
695 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); | 696 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
696 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); | 697 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
697 loop->ReplaceInput(1, if_true); | 698 loop->ReplaceInput(1, if_true); |
698 Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit); | 699 Node* ret = t.graph.NewNode(t.common.Return(), p3, t.start, exit); |
699 t.graph.SetEnd(ret); | 700 t.graph.SetEnd(ret); |
700 | 701 |
701 Node* choices[] = {p1, phi, cond}; | 702 Node* choices[] = {p1, phi, cond}; |
702 p1->ReplaceUses(choices[i]); | 703 p1->ReplaceUses(choices[i]); |
(...skipping 14 matching lines...) Expand all Loading... |
717 for (int j = 0; j < 5; j++) { | 718 for (int j = 0; j < 5; j++) { |
718 for (int k = 0; k < 5; k++) { | 719 for (int k = 0; k < 5; k++) { |
719 LoopFinderTester t; | 720 LoopFinderTester t; |
720 | 721 |
721 Node* p1 = t.jsgraph.Int32Constant(11); | 722 Node* p1 = t.jsgraph.Int32Constant(11); |
722 Node* p2 = t.jsgraph.Int32Constant(22); | 723 Node* p2 = t.jsgraph.Int32Constant(22); |
723 Node* p3 = t.jsgraph.Int32Constant(33); | 724 Node* p3 = t.jsgraph.Int32Constant(33); |
724 | 725 |
725 // outer loop. | 726 // outer loop. |
726 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); | 727 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
727 Node* phi1 = | 728 Node* phi1 = t.graph.NewNode( |
728 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p1, loop1); | 729 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop1); |
729 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one); | 730 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one); |
730 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); | 731 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
731 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); | 732 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
732 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); | 733 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
733 | 734 |
734 // inner loop. | 735 // inner loop. |
735 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); |
736 Node* phi2 = | 737 Node* phi2 = t.graph.NewNode( |
737 t.graph.NewNode(t.common.Phi(kMachInt32, 2), t.one, p2, loop2); | 738 t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p2, loop2); |
738 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); | 739 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3); |
739 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); | 740 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
740 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); | 741 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
741 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); | 742 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
742 loop2->ReplaceInput(1, if_true2); | 743 loop2->ReplaceInput(1, if_true2); |
743 loop1->ReplaceInput(1, exit2); | 744 loop1->ReplaceInput(1, exit2); |
744 | 745 |
745 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); | 746 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
746 t.graph.SetEnd(ret); | 747 t.graph.SetEnd(ret); |
747 | 748 |
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
793 Node* p1c = t.jsgraph.Int32Constant(33); | 794 Node* p1c = t.jsgraph.Int32Constant(33); |
794 Node* p2a = t.jsgraph.Int32Constant(44); | 795 Node* p2a = t.jsgraph.Int32Constant(44); |
795 Node* p2b = t.jsgraph.Int32Constant(55); | 796 Node* p2b = t.jsgraph.Int32Constant(55); |
796 Node* p2c = t.jsgraph.Int32Constant(66); | 797 Node* p2c = t.jsgraph.Int32Constant(66); |
797 Node* p3a = t.jsgraph.Int32Constant(77); | 798 Node* p3a = t.jsgraph.Int32Constant(77); |
798 Node* p3b = t.jsgraph.Int32Constant(88); | 799 Node* p3b = t.jsgraph.Int32Constant(88); |
799 Node* p3c = t.jsgraph.Int32Constant(99); | 800 Node* p3c = t.jsgraph.Int32Constant(99); |
800 | 801 |
801 // L1 depth = 0 | 802 // L1 depth = 0 |
802 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); | 803 Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start); |
803 Node* phi1 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p1a, p1c, loop1); | 804 Node* phi1 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 805 p1a, p1c, loop1); |
804 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b); | 806 Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b); |
805 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); | 807 Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1); |
806 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); | 808 Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1); |
807 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); | 809 Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1); |
808 | 810 |
809 // L2 depth = 1 | 811 // L2 depth = 1 |
810 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); | 812 Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start); |
811 Node* phi2 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p2a, p2c, loop2); | 813 Node* phi2 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 814 p2a, p2c, loop2); |
812 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b); | 815 Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b); |
813 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); | 816 Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2); |
814 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); | 817 Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2); |
815 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); | 818 Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2); |
816 | 819 |
817 // L3 depth = 2 | 820 // L3 depth = 2 |
818 Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start); | 821 Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start); |
819 Node* phi3 = t.graph.NewNode(t.common.Phi(kMachInt32, 2), p3a, p3c, loop3); | 822 Node* phi3 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 823 p3a, p3c, loop3); |
820 Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); | 824 Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b); |
821 Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); | 825 Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3); |
822 Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); | 826 Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3); |
823 Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); | 827 Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3); |
824 | 828 |
825 loop3->ReplaceInput(1, if_true3); | 829 loop3->ReplaceInput(1, if_true3); |
826 loop2->ReplaceInput(1, exit3); | 830 loop2->ReplaceInput(1, exit3); |
827 loop1->ReplaceInput(1, exit2); | 831 loop1->ReplaceInput(1, exit2); |
828 | 832 |
829 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); | 833 Node* ret = t.graph.NewNode(t.common.Return(), phi1, t.start, exit1); |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
917 static void RunManyChainedLoops_i(int count) { | 921 static void RunManyChainedLoops_i(int count) { |
918 LoopFinderTester t; | 922 LoopFinderTester t; |
919 Node** nodes = t.zone()->NewArray<Node*>(count * 4); | 923 Node** nodes = t.zone()->NewArray<Node*>(count * 4); |
920 Node* k11 = t.jsgraph.Int32Constant(11); | 924 Node* k11 = t.jsgraph.Int32Constant(11); |
921 Node* k12 = t.jsgraph.Int32Constant(12); | 925 Node* k12 = t.jsgraph.Int32Constant(12); |
922 Node* last = t.start; | 926 Node* last = t.start; |
923 | 927 |
924 // Build loops. | 928 // Build loops. |
925 for (int i = 0; i < count; i++) { | 929 for (int i = 0; i < count; i++) { |
926 Node* loop = t.graph.NewNode(t.common.Loop(2), last, t.start); | 930 Node* loop = t.graph.NewNode(t.common.Loop(2), last, t.start); |
927 Node* phi = t.graph.NewNode(t.common.Phi(kMachInt32, 2), k11, k12, loop); | 931 Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 932 k11, k12, loop); |
928 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); | 933 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); |
929 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); | 934 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
930 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); | 935 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
931 loop->ReplaceInput(1, if_true); | 936 loop->ReplaceInput(1, if_true); |
932 | 937 |
933 nodes[i * 4 + 0] = loop; | 938 nodes[i * 4 + 0] = loop; |
934 nodes[i * 4 + 1] = phi; | 939 nodes[i * 4 + 1] = phi; |
935 nodes[i * 4 + 2] = branch; | 940 nodes[i * 4 + 2] = branch; |
936 nodes[i * 4 + 3] = if_true; | 941 nodes[i * 4 + 3] = if_true; |
937 | 942 |
(...skipping 14 matching lines...) Expand all Loading... |
952 LoopFinderTester t; | 957 LoopFinderTester t; |
953 Node** nodes = t.zone()->NewArray<Node*>(count * 5); | 958 Node** nodes = t.zone()->NewArray<Node*>(count * 5); |
954 Node* k11 = t.jsgraph.Int32Constant(11); | 959 Node* k11 = t.jsgraph.Int32Constant(11); |
955 Node* k12 = t.jsgraph.Int32Constant(12); | 960 Node* k12 = t.jsgraph.Int32Constant(12); |
956 Node* outer = nullptr; | 961 Node* outer = nullptr; |
957 Node* entry = t.start; | 962 Node* entry = t.start; |
958 | 963 |
959 // Build loops. | 964 // Build loops. |
960 for (int i = 0; i < count; i++) { | 965 for (int i = 0; i < count; i++) { |
961 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); |
962 Node* phi = t.graph.NewNode(t.common.Phi(kMachInt32, 2), k11, k12, loop); | 967 Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2), |
| 968 k11, k12, loop); |
963 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); | 969 Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop); |
964 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); | 970 Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch); |
965 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); | 971 Node* exit = t.graph.NewNode(t.common.IfFalse(), branch); |
966 | 972 |
967 nodes[i * 5 + 0] = exit; // outside | 973 nodes[i * 5 + 0] = exit; // outside |
968 nodes[i * 5 + 1] = loop; // header | 974 nodes[i * 5 + 1] = loop; // header |
969 nodes[i * 5 + 2] = phi; // header | 975 nodes[i * 5 + 2] = phi; // header |
970 nodes[i * 5 + 3] = branch; // body | 976 nodes[i * 5 + 3] = branch; // body |
971 nodes[i * 5 + 4] = if_true; // body | 977 nodes[i * 5 + 4] = if_true; // body |
972 | 978 |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1008 TEST(LaManyNested_62) { RunManyNestedLoops_i(62); } | 1014 TEST(LaManyNested_62) { RunManyNestedLoops_i(62); } |
1009 TEST(LaManyNested_63) { RunManyNestedLoops_i(63); } | 1015 TEST(LaManyNested_63) { RunManyNestedLoops_i(63); } |
1010 TEST(LaManyNested_64) { RunManyNestedLoops_i(64); } | 1016 TEST(LaManyNested_64) { RunManyNestedLoops_i(64); } |
1011 | 1017 |
1012 | 1018 |
1013 TEST(LaPhiTangle) { LoopFinderTester t; } | 1019 TEST(LaPhiTangle) { LoopFinderTester t; } |
1014 | 1020 |
1015 } // namespace compiler | 1021 } // namespace compiler |
1016 } // namespace internal | 1022 } // namespace internal |
1017 } // namespace v8 | 1023 } // namespace v8 |
OLD | NEW |