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-phases.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 2766 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2814 if (dominator == block) break; | 2815 if (dominator == block) break; |
2815 | 2816 |
2816 // Move up the dominator tree. | 2817 // Move up the dominator tree. |
2817 dominator = dominator->dominator(); | 2818 dominator = dominator->dominator(); |
2818 } | 2819 } |
2819 } | 2820 } |
2820 } | 2821 } |
2821 } | 2822 } |
2822 | 2823 |
2823 | 2824 |
2824 void HInferRepresentation::AddToWorklist(HValue* current) { | |
2825 if (current->representation().IsTagged()) return; | |
2826 if (!current->CheckFlag(HValue::kFlexibleRepresentation)) return; | |
2827 if (in_worklist_.Contains(current->id())) return; | |
2828 worklist_.Add(current, zone()); | |
2829 in_worklist_.Add(current->id()); | |
2830 } | |
2831 | |
2832 | |
2833 void HInferRepresentation::Analyze() { | |
2834 HPhase phase("H_Infer representations", graph_); | |
2835 | |
2836 // (1) Initialize bit vectors and count real uses. Each phi gets a | |
2837 // bit-vector of length <number of phis>. | |
2838 const ZoneList<HPhi*>* phi_list = graph_->phi_list(); | |
2839 int phi_count = phi_list->length(); | |
2840 ZoneList<BitVector*> connected_phis(phi_count, graph_->zone()); | |
2841 for (int i = 0; i < phi_count; ++i) { | |
2842 phi_list->at(i)->InitRealUses(i); | |
2843 BitVector* connected_set = new(zone()) BitVector(phi_count, graph_->zone()); | |
2844 connected_set->Add(i); | |
2845 connected_phis.Add(connected_set, zone()); | |
2846 } | |
2847 | |
2848 // (2) Do a fixed point iteration to find the set of connected phis. A | |
2849 // phi is connected to another phi if its value is used either directly or | |
2850 // indirectly through a transitive closure of the def-use relation. | |
2851 bool change = true; | |
2852 while (change) { | |
2853 change = false; | |
2854 // We normally have far more "forward edges" than "backward edges", | |
2855 // so we terminate faster when we walk backwards. | |
2856 for (int i = phi_count - 1; i >= 0; --i) { | |
2857 HPhi* phi = phi_list->at(i); | |
2858 for (HUseIterator it(phi->uses()); !it.Done(); it.Advance()) { | |
2859 HValue* use = it.value(); | |
2860 if (use->IsPhi()) { | |
2861 int id = HPhi::cast(use)->phi_id(); | |
2862 if (connected_phis[i]->UnionIsChanged(*connected_phis[id])) | |
2863 change = true; | |
2864 } | |
2865 } | |
2866 } | |
2867 } | |
2868 | |
2869 // Set truncation flags for groups of connected phis. This is a conservative | |
2870 // approximation; the flag will be properly re-computed after representations | |
2871 // have been determined. | |
2872 if (phi_count > 0) { | |
2873 BitVector* done = new(zone()) BitVector(phi_count, graph_->zone()); | |
2874 for (int i = 0; i < phi_count; ++i) { | |
2875 if (done->Contains(i)) continue; | |
2876 | |
2877 // Check if all uses of all connected phis in this group are truncating. | |
2878 bool all_uses_everywhere_truncating = true; | |
2879 for (BitVector::Iterator it(connected_phis.at(i)); | |
2880 !it.Done(); | |
2881 it.Advance()) { | |
2882 int index = it.Current(); | |
2883 all_uses_everywhere_truncating &= | |
2884 phi_list->at(index)->CheckFlag(HInstruction::kTruncatingToInt32); | |
2885 done->Add(index); | |
2886 } | |
2887 if (all_uses_everywhere_truncating) { | |
2888 continue; // Great, nothing to do. | |
2889 } | |
2890 // Clear truncation flag of this group of connected phis. | |
2891 for (BitVector::Iterator it(connected_phis.at(i)); | |
2892 !it.Done(); | |
2893 it.Advance()) { | |
2894 int index = it.Current(); | |
2895 phi_list->at(index)->ClearFlag(HInstruction::kTruncatingToInt32); | |
2896 } | |
2897 } | |
2898 } | |
2899 | |
2900 // Simplify constant phi inputs where possible. | |
2901 // This step uses kTruncatingToInt32 flags of phis. | |
2902 for (int i = 0; i < phi_count; ++i) { | |
2903 phi_list->at(i)->SimplifyConstantInputs(); | |
2904 } | |
2905 | |
2906 // Use the phi reachability information from step 2 to | |
2907 // sum up the non-phi use counts of all connected phis. | |
2908 for (int i = 0; i < phi_count; ++i) { | |
2909 HPhi* phi = phi_list->at(i); | |
2910 for (BitVector::Iterator it(connected_phis.at(i)); | |
2911 !it.Done(); | |
2912 it.Advance()) { | |
2913 int index = it.Current(); | |
2914 HPhi* it_use = phi_list->at(index); | |
2915 if (index != i) phi->AddNonPhiUsesFrom(it_use); // Don't count twice. | |
2916 } | |
2917 } | |
2918 | |
2919 // Initialize work list | |
2920 for (int i = 0; i < graph_->blocks()->length(); ++i) { | |
2921 HBasicBlock* block = graph_->blocks()->at(i); | |
2922 const ZoneList<HPhi*>* phis = block->phis(); | |
2923 for (int j = 0; j < phis->length(); ++j) { | |
2924 AddToWorklist(phis->at(j)); | |
2925 } | |
2926 | |
2927 HInstruction* current = block->first(); | |
2928 while (current != NULL) { | |
2929 AddToWorklist(current); | |
2930 current = current->next(); | |
2931 } | |
2932 } | |
2933 | |
2934 // Do a fixed point iteration, trying to improve representations | |
2935 while (!worklist_.is_empty()) { | |
2936 HValue* current = worklist_.RemoveLast(); | |
2937 in_worklist_.Remove(current->id()); | |
2938 current->InferRepresentation(this); | |
2939 } | |
2940 | |
2941 // Lastly: any instruction that we don't have representation information | |
2942 // for defaults to Tagged. | |
2943 for (int i = 0; i < graph_->blocks()->length(); ++i) { | |
2944 HBasicBlock* block = graph_->blocks()->at(i); | |
2945 const ZoneList<HPhi*>* phis = block->phis(); | |
2946 for (int j = 0; j < phis->length(); ++j) { | |
2947 HPhi* phi = phis->at(j); | |
2948 if (phi->representation().IsNone()) { | |
2949 phi->ChangeRepresentation(Representation::Tagged()); | |
2950 } | |
2951 } | |
2952 for (HInstruction* current = block->first(); | |
2953 current != NULL; current = current->next()) { | |
2954 if (current->representation().IsNone() && | |
2955 current->CheckFlag(HInstruction::kFlexibleRepresentation)) { | |
2956 if (current->CheckFlag(HInstruction::kCannotBeTagged)) { | |
2957 current->ChangeRepresentation(Representation::Double()); | |
2958 } else { | |
2959 current->ChangeRepresentation(Representation::Tagged()); | |
2960 } | |
2961 } | |
2962 } | |
2963 } | |
2964 } | |
2965 | |
2966 | |
2967 void HGraph::MergeRemovableSimulates() { | 2825 void HGraph::MergeRemovableSimulates() { |
2968 HPhase phase("H_Merge removable simulates", this); | 2826 HPhase phase("H_Merge removable simulates", this); |
2969 ZoneList<HSimulate*> mergelist(2, zone()); | 2827 ZoneList<HSimulate*> mergelist(2, zone()); |
2970 for (int i = 0; i < blocks()->length(); ++i) { | 2828 for (int i = 0; i < blocks()->length(); ++i) { |
2971 HBasicBlock* block = blocks()->at(i); | 2829 HBasicBlock* block = blocks()->at(i); |
2972 // Make sure the merge list is empty at the start of a block. | 2830 // Make sure the merge list is empty at the start of a block. |
2973 ASSERT(mergelist.is_empty()); | 2831 ASSERT(mergelist.is_empty()); |
2974 // Nasty heuristic: Never remove the first simulate in a block. This | 2832 // Nasty heuristic: Never remove the first simulate in a block. This |
2975 // just so happens to have a beneficial effect on register allocation. | 2833 // just so happens to have a beneficial effect on register allocation. |
2976 bool first = true; | 2834 bool first = true; |
(...skipping 1009 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3986 CollectPhis(); | 3844 CollectPhis(); |
3987 | 3845 |
3988 if (has_osr_loop_entry()) { | 3846 if (has_osr_loop_entry()) { |
3989 const ZoneList<HPhi*>* phis = osr_loop_entry()->phis(); | 3847 const ZoneList<HPhi*>* phis = osr_loop_entry()->phis(); |
3990 for (int j = 0; j < phis->length(); j++) { | 3848 for (int j = 0; j < phis->length(); j++) { |
3991 HPhi* phi = phis->at(j); | 3849 HPhi* phi = phis->at(j); |
3992 osr_values()->at(phi->merged_index())->set_incoming_value(phi); | 3850 osr_values()->at(phi->merged_index())->set_incoming_value(phi); |
3993 } | 3851 } |
3994 } | 3852 } |
3995 | 3853 |
3996 HInferRepresentation rep(this); | 3854 Run<HInferRepresentationPhase>(); |
3997 rep.Analyze(); | |
3998 | 3855 |
3999 // Remove HSimulate instructions that have turned out not to be needed | 3856 // Remove HSimulate instructions that have turned out not to be needed |
4000 // after all by folding them into the following HSimulate. | 3857 // after all by folding them into the following HSimulate. |
4001 // This must happen after inferring representations. | 3858 // This must happen after inferring representations. |
4002 MergeRemovableSimulates(); | 3859 MergeRemovableSimulates(); |
4003 | 3860 |
4004 MarkDeoptimizeOnUndefined(); | 3861 MarkDeoptimizeOnUndefined(); |
4005 InsertRepresentationChanges(); | 3862 InsertRepresentationChanges(); |
4006 | 3863 |
4007 InitializeInferredTypes(); | 3864 InitializeInferredTypes(); |
(...skipping 7530 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11538 if (ShouldProduceTraceOutput()) { | 11395 if (ShouldProduceTraceOutput()) { |
11539 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); | 11396 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); |
11540 } | 11397 } |
11541 | 11398 |
11542 #ifdef DEBUG | 11399 #ifdef DEBUG |
11543 graph_->Verify(false); // No full verify. | 11400 graph_->Verify(false); // No full verify. |
11544 #endif | 11401 #endif |
11545 } | 11402 } |
11546 | 11403 |
11547 } } // namespace v8::internal | 11404 } } // namespace v8::internal |
OLD | NEW |