OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 17 matching lines...) Expand all Loading... |
28 #include "hydrogen.h" | 28 #include "hydrogen.h" |
29 #include "hydrogen-gvn.h" | 29 #include "hydrogen-gvn.h" |
30 | 30 |
31 #include <algorithm> | 31 #include <algorithm> |
32 | 32 |
33 #include "v8.h" | 33 #include "v8.h" |
34 #include "codegen.h" | 34 #include "codegen.h" |
35 #include "full-codegen.h" | 35 #include "full-codegen.h" |
36 #include "hashmap.h" | 36 #include "hashmap.h" |
37 #include "hydrogen-environment-liveness.h" | 37 #include "hydrogen-environment-liveness.h" |
| 38 #include "hydrogen-infer-representation.h" |
38 #include "lithium-allocator.h" | 39 #include "lithium-allocator.h" |
39 #include "parser.h" | 40 #include "parser.h" |
40 #include "scopeinfo.h" | 41 #include "scopeinfo.h" |
41 #include "scopes.h" | 42 #include "scopes.h" |
42 #include "stub-cache.h" | 43 #include "stub-cache.h" |
43 #include "typing.h" | 44 #include "typing.h" |
44 | 45 |
45 #if V8_TARGET_ARCH_IA32 | 46 #if V8_TARGET_ARCH_IA32 |
46 #include "ia32/lithium-codegen-ia32.h" | 47 #include "ia32/lithium-codegen-ia32.h" |
47 #elif V8_TARGET_ARCH_X64 | 48 #elif V8_TARGET_ARCH_X64 |
(...skipping 2759 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2807 if (dominator == block) break; | 2808 if (dominator == block) break; |
2808 | 2809 |
2809 // Move up the dominator tree. | 2810 // Move up the dominator tree. |
2810 dominator = dominator->dominator(); | 2811 dominator = dominator->dominator(); |
2811 } | 2812 } |
2812 } | 2813 } |
2813 } | 2814 } |
2814 } | 2815 } |
2815 | 2816 |
2816 | 2817 |
2817 void HInferRepresentation::AddToWorklist(HValue* current) { | |
2818 if (current->representation().IsTagged()) return; | |
2819 if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return; | |
2820 if (in_worklist_.Contains(current->id())) return; | |
2821 worklist_.Add(current, zone()); | |
2822 in_worklist_.Add(current->id()); | |
2823 } | |
2824 | |
2825 | |
2826 void HInferRepresentation::Analyze() { | |
2827 HPhase phase("H_Infer representations", graph_); | |
2828 | |
2829 // (1) Initialize bit vectors and count real uses. Each phi gets a | |
2830 // bit-vector of length <number of phis>. | |
2831 const ZoneList<HPhi*>* phi_list = graph_->phi_list(); | |
2832 int phi_count = phi_list->length(); | |
2833 ZoneList<BitVector*> connected_phis(phi_count, graph_->zone()); | |
2834 for (int i = 0; i < phi_count; ++i) { | |
2835 phi_list->at(i)->InitRealUses(i); | |
2836 BitVector* connected_set = new(zone()) BitVector(phi_count, graph_->zone()); | |
2837 connected_set->Add(i); | |
2838 connected_phis.Add(connected_set, zone()); | |
2839 } | |
2840 | |
2841 // (2) Do a fixed point iteration to find the set of connected phis. A | |
2842 // phi is connected to another phi if its value is used either directly or | |
2843 // indirectly through a transitive closure of the def-use relation. | |
2844 bool change = true; | |
2845 while (change) { | |
2846 change = false; | |
2847 // We normally have far more "forward edges" than "backward edges", | |
2848 // so we terminate faster when we walk backwards. | |
2849 for (int i = phi_count - 1; i >= 0; --i) { | |
2850 HPhi* phi = phi_list->at(i); | |
2851 for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { | |
2852 HValue* use = it.value(); | |
2853 if (use->IsPhi()) { | |
2854 int id = HPhi::cast(use)->phi_id(); | |
2855 if (connected_phis[i]->UnionIsChanged(*connected_phis[id])) | |
2856 change = true; | |
2857 } | |
2858 } | |
2859 } | |
2860 } | |
2861 | |
2862 // Set truncation flags for groups of connected phis. This is a conservative | |
2863 // approximation; the flag will be properly re-computed after representations | |
2864 // have been determined. | |
2865 if (phi_count > 0) { | |
2866 BitVector* done = new(zone()) BitVector(phi_count, graph_->zone()); | |
2867 for (int i = 0; i < phi_count; ++i) { | |
2868 if (done->Contains(i)) continue; | |
2869 | |
2870 // Check if all uses of all connected phis in this group are truncating. | |
2871 bool all_uses_everywhere_truncating = true; | |
2872 for (BitVector::Iterator it(connected_phis.at(i)); | |
2873 !it.Done(); | |
2874 it.Advance()) { | |
2875 int index = it.Current(); | |
2876 all_uses_everywhere_truncating &= | |
2877 phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32); | |
2878 done->Add(index); | |
2879 } | |
2880 if (all_uses_everywhere_truncating) { | |
2881 continue; // Great, nothing to do. | |
2882 } | |
2883 // Clear truncation flag of this group of connected phis. | |
2884 for (BitVector::Iterator it(connected_phis.at(i)); | |
2885 !it.Done(); | |
2886 it.Advance()) { | |
2887 int index = it.Current(); | |
2888 phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32); | |
2889 } | |
2890 } | |
2891 } | |
2892 | |
2893 // Simplify constant phi inputs where possible. | |
2894 // This step uses kTruncatingToInt32 flags of phis. | |
2895 for (int i = 0; i < phi_count; ++i) { | |
2896 phi_list->at(i)->SimplifyConstantInputs(); | |
2897 } | |
2898 | |
2899 // Use the phi reachability information from step 2 to | |
2900 // sum up the non-phi use counts of all connected phis. | |
2901 for (int i = 0; i < phi_count; ++i) { | |
2902 HPhi* phi = phi_list->at(i); | |
2903 for (BitVector::Iterator it(connected_phis.at(i)); | |
2904 !it.Done(); | |
2905 it.Advance()) { | |
2906 int index = it.Current(); | |
2907 HPhi* it_use = phi_list->at(index); | |
2908 if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice. | |
2909 } | |
2910 } | |
2911 | |
2912 // Initialize work list | |
2913 for (int i = 0; i < graph_->blocks()->length(); ++i) { | |
2914 HBasicBlock* block = graph_->blocks()->at(i); | |
2915 const ZoneList<HPhi*>* phis = block->phis(); | |
2916 for (int j = 0; j < phis->length(); ++j) { | |
2917 AddToWorklist(phis->at(j)); | |
2918 } | |
2919 | |
2920 HInstruction* current = block->first(); | |
2921 while (current != NULL) { | |
2922 AddToWorklist(current); | |
2923 current = current->next(); | |
2924 } | |
2925 } | |
2926 | |
2927 // Do a fixed point iteration, trying to improve representations | |
2928 while (!worklist_.is_empty()) { | |
2929 HValue* current = worklist_.RemoveLast(); | |
2930 in_worklist_.Remove(current->id()); | |
2931 current->InferRepresentation(this); | |
2932 } | |
2933 | |
2934 // Lastly: any instruction that we don't have representation information | |
2935 // for defaults to Tagged. | |
2936 for (int i = 0; i < graph_->blocks()->length(); ++i) { | |
2937 HBasicBlock* block = graph_->blocks()->at(i); | |
2938 const ZoneList<HPhi*>* phis = block->phis(); | |
2939 for (int j = 0; j < phis->length(); ++j) { | |
2940 HPhi* phi = phis->at(j); | |
2941 if (phi->representation().IsNone()) { | |
2942 phi->ChangeRepresentation(Representation::Tagged()); | |
2943 } | |
2944 } | |
2945 for (HInstruction* current = block->first(); | |
2946 current != NULL; current = current->next()) { | |
2947 if (current->representation().IsNone() && | |
2948 current->CheckFlag(HInstruction::kFlexibleRepresentation)) { | |
2949 if (current->CheckFlag(HInstruction::kCannotBeTagged)) { | |
2950 current->ChangeRepresentation(Representation::Double()); | |
2951 } else { | |
2952 current->ChangeRepresentation(Representation::Tagged()); | |
2953 } | |
2954 } | |
2955 } | |
2956 } | |
2957 } | |
2958 | |
2959 | |
2960 void HGraph::MergeRemovableSimulates() { | 2818 void HGraph::MergeRemovableSimulates() { |
2961 HPhase phase("H_Merge removable simulates", this); | 2819 HPhase phase("H_Merge removable simulates", this); |
2962 ZoneList<HSimulate*> mergelist(2, zone()); | 2820 ZoneList<HSimulate*> mergelist(2, zone()); |
2963 for (int i = 0; i < blocks()->length(); ++i) { | 2821 for (int i = 0; i < blocks()->length(); ++i) { |
2964 HBasicBlock* block = blocks()->at(i); | 2822 HBasicBlock* block = blocks()->at(i); |
2965 // Make sure the merge list is empty at the start of a block. | 2823 // Make sure the merge list is empty at the start of a block. |
2966 ASSERT(mergelist.is_empty()); | 2824 ASSERT(mergelist.is_empty()); |
2967 // Nasty heuristic: Never remove the first simulate in a block. This | 2825 // Nasty heuristic: Never remove the first simulate in a block. This |
2968 // just so happens to have a beneficial effect on register allocation. | 2826 // just so happens to have a beneficial effect on register allocation. |
2969 bool first = true; | 2827 bool first = true; |
(...skipping 1009 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3979 CollectPhis(); | 3837 CollectPhis(); |
3980 | 3838 |
3981 if (has_osr_loop_entry()) { | 3839 if (has_osr_loop_entry()) { |
3982 const ZoneList<HPhi*>* phis = osr_loop_entry()->phis(); | 3840 const ZoneList<HPhi*>* phis = osr_loop_entry()->phis(); |
3983 for (int j = 0; j < phis->length(); j++) { | 3841 for (int j = 0; j < phis->length(); j++) { |
3984 HPhi* phi = phis->at(j); | 3842 HPhi* phi = phis->at(j); |
3985 osr_values()->at(phi->merged_index())->set_incoming_value(phi); | 3843 osr_values()->at(phi->merged_index())->set_incoming_value(phi); |
3986 } | 3844 } |
3987 } | 3845 } |
3988 | 3846 |
3989 HInferRepresentation rep(this); | 3847 Run<HInferRepresentationPhase>(); |
3990 rep.Analyze(); | |
3991 | 3848 |
3992 // Remove HSimulate instructions that have turned out not to be needed | 3849 // Remove HSimulate instructions that have turned out not to be needed |
3993 // after all by folding them into the following HSimulate. | 3850 // after all by folding them into the following HSimulate. |
3994 // This must happen after inferring representations. | 3851 // This must happen after inferring representations. |
3995 MergeRemovableSimulates(); | 3852 MergeRemovableSimulates(); |
3996 | 3853 |
3997 MarkDeoptimizeOnUndefined(); | 3854 MarkDeoptimizeOnUndefined(); |
3998 InsertRepresentationChanges(); | 3855 InsertRepresentationChanges(); |
3999 | 3856 |
4000 InitializeInferredTypes(); | 3857 InitializeInferredTypes(); |
(...skipping 7532 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11533 if (ShouldProduceTraceOutput()) { | 11390 if (ShouldProduceTraceOutput()) { |
11534 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); | 11391 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); |
11535 } | 11392 } |
11536 | 11393 |
11537 #ifdef DEBUG | 11394 #ifdef DEBUG |
11538 graph_->Verify(false); // No full verify. | 11395 graph_->Verify(false); // No full verify. |
11539 #endif | 11396 #endif |
11540 } | 11397 } |
11541 | 11398 |
11542 } } // namespace v8::internal | 11399 } } // namespace v8::internal |
OLD | NEW |