OLD | NEW |
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 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 304 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
315 #undef DEF_VISIT | 315 #undef DEF_VISIT |
316 | 316 |
317 // Only allow fast-case switch if the range of labels is at most | 317 // Only allow fast-case switch if the range of labels is at most |
318 // this factor times the number of case labels. | 318 // this factor times the number of case labels. |
319 // Value is derived from comparing the size of code generated by the normal | 319 // Value is derived from comparing the size of code generated by the normal |
320 // switch code for Smi-labels to the size of a single pointer. If code | 320 // switch code for Smi-labels to the size of a single pointer. If code |
321 // quality increases this number should be decreased to match. | 321 // quality increases this number should be decreased to match. |
322 static const int kFastSwitchMaxOverheadFactor = 5; | 322 static const int kFastSwitchMaxOverheadFactor = 5; |
323 | 323 |
324 // Minimal number of switch cases required before we allow jump-table | 324 // Minimal number of switch cases required before we allow jump-table |
325 // optimization. | 325 // optimization. |
326 static const int kFastSwitchMinCaseCount = 5; | 326 static const int kFastSwitchMinCaseCount = 5; |
327 | 327 |
328 // Create fast switch implementation if all labels are small integers | 328 // Create fast switch implementation if all labels are small integers |
329 // in a limited range. Returns false if this is not the case, and no | 329 // in a limited range. Returns false if this is not the case, and no |
330 // code has been generated (i.e., the default implementation should be used). | 330 // code has been generated (i.e., the default implementation should be used). |
331 bool TryFastCaseSwitchStatement(SwitchStatement *switchStmt); | 331 bool TryFastCaseSwitchStatement(SwitchStatement *switchStmt); |
332 | 332 |
333 // Generate a computed jump with an empty jump table. | 333 // Generate a computed jump with an empty jump table. |
334 // Binds a label to the start of the jump table. This table must | 334 // Binds a label to the start of the jump table. This table must |
335 // be populated later when the adresses of the targets are known. | 335 // be populated later when the adresses of the targets are known. |
(...skipping 2596 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2932 // Update context local. | 2932 // Update context local. |
2933 __ mov(Operand(ebp, StandardFrameConstants::kContextOffset), esi); | 2933 __ mov(Operand(ebp, StandardFrameConstants::kContextOffset), esi); |
2934 } | 2934 } |
2935 | 2935 |
2936 | 2936 |
2937 // Generate a computed jump with an empty jump table. | 2937 // Generate a computed jump with an empty jump table. |
2938 // Returns a label pointing to the start of the jump table. This must | 2938 // Returns a label pointing to the start of the jump table. This must |
2939 // be populated later when the adresses of the targets are known | 2939 // be populated later when the adresses of the targets are known |
2940 void Ia32CodeGenerator::GenerateFastCaseSwitchJumpTable( | 2940 void Ia32CodeGenerator::GenerateFastCaseSwitchJumpTable( |
2941 int min_index, int range, Label *fail_label, Label &table_start) { | 2941 int min_index, int range, Label *fail_label, Label &table_start) { |
2942 // Notice: Internal references, used by both the jmp instruction and the | 2942 // Notice: Internal references, used by both the jmp instruction and |
2943 // table entries, need to be relocated if the buffer grows. This prevents | 2943 // the table entries, need to be relocated if the buffer grows. This |
2944 // the forward use of Labels, since a displacement cannot survive relocation, | 2944 // prevents the forward use of Labels, since a displacement cannot |
2945 // and it also cannot safely be distinguished from a real address. | 2945 // survive relocation, and it also cannot safely be distinguished |
2946 // Instead we put in zero-values as placeholders, and fill in the adresses aft
er | 2946 // from a real address. Instead we put in zero-values as |
2947 // the labels have been bound. | 2947 // placeholders, and fill in the adresses after the labels have been |
| 2948 // bound. |
2948 | 2949 |
2949 __ pop(eax); // supposed Smi | 2950 __ pop(eax); // supposed smi |
2950 // check range of value, if outside [0..length-1] jump to default/end label. | 2951 // check range of value, if outside [0..length-1] jump to default/end label. |
2951 ASSERT(kSmiTagSize == 1 && kSmiTag == 0); | 2952 ASSERT(kSmiTagSize == 1 && kSmiTag == 0); |
2952 if (min_index != 0) { | 2953 if (min_index != 0) { |
2953 __ sub(Operand(eax), Immediate(min_index * 2)); // Smi subtraction | 2954 __ sub(Operand(eax), Immediate(min_index * 2)); // smi subtraction |
2954 } | 2955 } |
2955 __ test(eax, Immediate(0x80000000 | kSmiTagMask)); // negative or not Smi | 2956 __ test(eax, Immediate(0x80000000 | kSmiTagMask)); // negative or not smi |
2956 __ j(not_equal, fail_label, not_taken); | 2957 __ j(not_equal, fail_label, not_taken); |
2957 __ cmp(eax, range * 2); | 2958 __ cmp(eax, range * 2); |
2958 __ j(greater_equal, fail_label, not_taken); | 2959 __ j(greater_equal, fail_label, not_taken); |
2959 | 2960 |
2960 __ jmp(Operand(eax, times_2, 0x0, internal_reference)); // 0 is placeholder | 2961 __ jmp(Operand(eax, times_2, 0x0, internal_reference)); // 0 is placeholder |
2961 // calculate address to overwrite later with actual address of table. | 2962 // calculate address to overwrite later with actual address of table. |
2962 int32_t jump_table_ref = __ pc_offset() - sizeof(int32_t); | 2963 int32_t jump_table_ref = __ pc_offset() - sizeof(int32_t); |
2963 | 2964 |
2964 __ Align(4); | 2965 __ Align(4); |
2965 __ bind(&table_start); | 2966 __ bind(&table_start); |
2966 __ WriteInternalReference(jump_table_ref, table_start); | 2967 __ WriteInternalReference(jump_table_ref, table_start); |
2967 | 2968 |
2968 for (int i = 0; i < range; i++) { | 2969 for (int i = 0; i < range; i++) { |
2969 __ dd(0x0, internal_reference); // table entry, 0 is placeholder | 2970 __ dd(0x0, internal_reference); // table entry, 0 is placeholder |
2970 } | 2971 } |
2971 } | 2972 } |
2972 | 2973 |
2973 | 2974 |
2974 // Populate an empty jump table with the adresses of bound labels. | 2975 // Populate an empty jump table with the adresses of bound labels. |
2975 void Ia32CodeGenerator::PopulateFastCaseSwitchJumpTable( | 2976 void Ia32CodeGenerator::PopulateFastCaseSwitchJumpTable( |
2976 Label &table_start, SmartPointer<Label*> &case_targets, int table_size) { | 2977 Label &table_start, SmartPointer<Label*> &case_targets, int table_size) { |
2977 for (int i = 0; i < table_size; i++) { | 2978 for (int i = 0; i < table_size; i++) { |
2978 int table_entry_pos = table_start.pos() + i * sizeof(uint32_t); | 2979 int table_entry_pos = table_start.pos() + i * sizeof(uint32_t); |
2979 __ WriteInternalReference(table_entry_pos, *case_targets[i]); | 2980 __ WriteInternalReference(table_entry_pos, *case_targets[i]); |
2980 } | 2981 } |
2981 } | 2982 } |
2982 | 2983 |
2983 | 2984 |
2984 // Generates a fast-case switch statement for a switch with all-Smi labels | 2985 // Generates a fast-case switch statement for a switch with all-Smi labels |
2985 // in a limited range. | 2986 // in a limited range. |
2986 void Ia32CodeGenerator::GenerateFastCaseSwitchStatement( | 2987 void Ia32CodeGenerator::GenerateFastCaseSwitchStatement( |
2987 SwitchStatement *node, int min_index, int range, int default_index) { | 2988 SwitchStatement *node, int min_index, int range, int default_index) { |
2988 ZoneList<CaseClause*>* cases = node->cases(); | 2989 ZoneList<CaseClause*>* cases = node->cases(); |
2989 int length = cases->length(); | 2990 int length = cases->length(); |
2990 | 2991 |
2991 SmartPointer<Label*> case_targets(NewArray<Label*>(range)); | 2992 SmartPointer<Label*> case_targets(NewArray<Label*>(range)); |
2992 SmartPointer<Label> case_labels(NewArray<Label>(length)); | 2993 SmartPointer<Label> case_labels(NewArray<Label>(length)); |
2993 | 2994 |
2994 Label* fail_label = (default_index >= 0 ? &(case_labels[default_index]) | 2995 Label* fail_label = (default_index >= 0 ? &(case_labels[default_index]) |
2995 : node->break_target()); | 2996 : node->break_target()); |
2996 | 2997 |
2997 // create array of labels to jump to by index. | 2998 // Create array of labels to jump to by index and set default jump |
2998 // set default jump targets everywhere | 2999 // targets everywhere. |
2999 for (int i = 0; i < range; i++) { | 3000 for (int i = 0; i < range; i++) { |
3000 // length => end label | 3001 // length => end label |
3001 case_targets[i] = fail_label; | 3002 case_targets[i] = fail_label; |
3002 } | 3003 } |
3003 // overwrite for values of cases: | 3004 |
3004 // (reverse order, so that if same label twice, the first one wins) | 3005 // Overwrite for values of cases: |
| 3006 // (reverse order, so that if same label twice, the first one wins). |
3005 for (int i = length-1; i >= 0 ; i--) { | 3007 for (int i = length-1; i >= 0 ; i--) { |
3006 CaseClause* clause = cases->at(i); | 3008 CaseClause* clause = cases->at(i); |
3007 if (!clause->is_default()) { | 3009 if (!clause->is_default()) { |
3008 Object* label_value = *(clause->label()->AsLiteral()->handle()); | 3010 Object* label_value = *(clause->label()->AsLiteral()->handle()); |
3009 int case_value = Smi::cast(label_value)->value(); | 3011 int case_value = Smi::cast(label_value)->value(); |
3010 case_targets[case_value - min_index] = &(case_labels[i]); | 3012 case_targets[case_value - min_index] = &(case_labels[i]); |
3011 } | 3013 } |
3012 } | 3014 } |
3013 | 3015 |
3014 // Generate the jump table and code for all cases. | 3016 // Generate the jump table and code for all cases. |
3015 Label table_start; | 3017 Label table_start; |
3016 | 3018 |
3017 GenerateFastCaseSwitchJumpTable(min_index, range, fail_label, table_start); | 3019 GenerateFastCaseSwitchJumpTable(min_index, range, fail_label, table_start); |
3018 | 3020 |
3019 for (int i = 0; i < length; i++) { | 3021 for (int i = 0; i < length; i++) { |
3020 Comment cmnt(masm_, "[ case clause"); | 3022 Comment cmnt(masm_, "[ case clause"); |
3021 __ bind(&(case_labels[i])); | 3023 __ bind(&(case_labels[i])); |
3022 VisitStatements(cases->at(i)->statements()); | 3024 VisitStatements(cases->at(i)->statements()); |
3023 } | 3025 } |
3024 | 3026 |
3025 __ bind(node->break_target()); | 3027 __ bind(node->break_target()); |
3026 | 3028 |
3027 // all labels bound now, so we can populate the table with the | 3029 // All labels bound now, so we can populate the table with the |
3028 // correct addresses. | 3030 // correct addresses. |
3029 PopulateFastCaseSwitchJumpTable(table_start, case_targets, range); | 3031 PopulateFastCaseSwitchJumpTable(table_start, case_targets, range); |
3030 } | 3032 } |
3031 | 3033 |
3032 | 3034 |
3033 bool Ia32CodeGenerator::TryFastCaseSwitchStatement(SwitchStatement *node) { | 3035 bool Ia32CodeGenerator::TryFastCaseSwitchStatement(SwitchStatement *node) { |
3034 ZoneList<CaseClause*>* cases = node->cases(); | 3036 ZoneList<CaseClause*>* cases = node->cases(); |
3035 int length = cases->length(); | 3037 int length = cases->length(); |
3036 | 3038 |
3037 if (length < kFastSwitchMinCaseCount) { | 3039 if (length < kFastSwitchMinCaseCount) { |
3038 return false; | 3040 return false; |
3039 } | 3041 } |
3040 » » | 3042 |
3041 // Test whether fast-case should be used. | 3043 // Test whether fast-case should be used. |
3042 int default_index = -1; | 3044 int default_index = -1; |
3043 int min_index = Smi::kMaxValue; | 3045 int min_index = Smi::kMaxValue; |
3044 int max_index = Smi::kMinValue; | 3046 int max_index = Smi::kMinValue; |
3045 for (int i = 0; i < length; i++) { | 3047 for (int i = 0; i < length; i++) { |
3046 CaseClause* clause = cases->at(i); | 3048 CaseClause* clause = cases->at(i); |
3047 if (clause->is_default()) { | 3049 if (clause->is_default()) { |
3048 if (default_index >= 0) { | 3050 if (default_index >= 0) { |
3049 return false; // More than one default label: | 3051 return false; // More than one default label: |
3050 // Defer to normal case for error. | 3052 // Defer to normal case for error. |
3051 } | 3053 } |
3052 default_index = i; | 3054 default_index = i; |
3053 } else { | 3055 } else { |
3054 Expression* label = clause->label(); | 3056 Expression* label = clause->label(); |
3055 Literal* literal = label->AsLiteral(); | 3057 Literal* literal = label->AsLiteral(); |
3056 if (literal == NULL) { | 3058 if (literal == NULL) { |
3057 return false; // fail fast case | 3059 return false; // fail fast case |
3058 } | 3060 } |
3059 Object* value = *(literal->handle()); | 3061 Object* value = *(literal->handle()); |
3060 if (!value->IsSmi()) { | 3062 if (!value->IsSmi()) { |
3061 return false; | 3063 return false; |
3062 } | 3064 } |
3063 int smi = Smi::cast(value)->value(); | 3065 int smi = Smi::cast(value)->value(); |
3064 if (smi < min_index) { min_index = smi; } | 3066 if (smi < min_index) { min_index = smi; } |
3065 if (smi > max_index) { max_index = smi; } | 3067 if (smi > max_index) { max_index = smi; } |
3066 } | 3068 } |
3067 } | 3069 } |
3068 // all labels are Smi. | 3070 |
| 3071 // After this all labels are smis. |
3069 int range = max_index - min_index + 1; // |min..max| inclusive | 3072 int range = max_index - min_index + 1; // |min..max| inclusive |
3070 if (range / kFastSwitchMaxOverheadFactor > length) { | 3073 if (range / kFastSwitchMaxOverheadFactor > length) { |
3071 return false; // range of labels is too sparse | 3074 return false; // range of labels is too sparse |
3072 } | 3075 } |
3073 | 3076 |
3074 // Optimization accepted, generate code. | 3077 // Optimization accepted, generate code. |
3075 GenerateFastCaseSwitchStatement(node, min_index, range, default_index); | 3078 GenerateFastCaseSwitchStatement(node, min_index, range, default_index); |
3076 return true; | 3079 return true; |
3077 } | 3080 } |
3078 | 3081 |
(...skipping 2501 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
5580 bool is_eval) { | 5583 bool is_eval) { |
5581 Handle<Code> code = Ia32CodeGenerator::MakeCode(fun, script, is_eval); | 5584 Handle<Code> code = Ia32CodeGenerator::MakeCode(fun, script, is_eval); |
5582 if (!code.is_null()) { | 5585 if (!code.is_null()) { |
5583 Counters::total_compiled_code_size.Increment(code->instruction_size()); | 5586 Counters::total_compiled_code_size.Increment(code->instruction_size()); |
5584 } | 5587 } |
5585 return code; | 5588 return code; |
5586 } | 5589 } |
5587 | 5590 |
5588 | 5591 |
5589 } } // namespace v8::internal | 5592 } } // namespace v8::internal |
OLD | NEW |