Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(79)

Side by Side Diff: src/hydrogen.cc

Issue 18054002: Refactor HInferRepresentation into an HPhase and use the phase zone. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
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
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
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
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
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
OLDNEW
« no previous file with comments | « src/hydrogen.h ('k') | src/hydrogen-instructions.h » ('j') | src/hydrogen-phases.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698