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 19 matching lines...) Expand all Loading... |
30 #include <algorithm> | 30 #include <algorithm> |
31 | 31 |
32 #include "v8.h" | 32 #include "v8.h" |
33 #include "codegen.h" | 33 #include "codegen.h" |
34 #include "full-codegen.h" | 34 #include "full-codegen.h" |
35 #include "hashmap.h" | 35 #include "hashmap.h" |
36 #include "hydrogen-environment-liveness.h" | 36 #include "hydrogen-environment-liveness.h" |
37 #include "hydrogen-escape-analysis.h" | 37 #include "hydrogen-escape-analysis.h" |
38 #include "hydrogen-infer-representation.h" | 38 #include "hydrogen-infer-representation.h" |
39 #include "hydrogen-gvn.h" | 39 #include "hydrogen-gvn.h" |
| 40 #include "hydrogen-range-analysis.h" |
40 #include "hydrogen-uint32-analysis.h" | 41 #include "hydrogen-uint32-analysis.h" |
41 #include "lithium-allocator.h" | 42 #include "lithium-allocator.h" |
42 #include "parser.h" | 43 #include "parser.h" |
43 #include "scopeinfo.h" | 44 #include "scopeinfo.h" |
44 #include "scopes.h" | 45 #include "scopes.h" |
45 #include "stub-cache.h" | 46 #include "stub-cache.h" |
46 #include "typing.h" | 47 #include "typing.h" |
47 | 48 |
48 #if V8_TARGET_ARCH_IA32 | 49 #if V8_TARGET_ARCH_IA32 |
49 #include "ia32/lithium-codegen-ia32.h" | 50 #include "ia32/lithium-codegen-ia32.h" |
(...skipping 2519 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2569 if (!in_worklist.Contains(use->id())) { | 2570 if (!in_worklist.Contains(use->id())) { |
2570 in_worklist.Add(use->id()); | 2571 in_worklist.Add(use->id()); |
2571 worklist->Add(use, zone()); | 2572 worklist->Add(use, zone()); |
2572 } | 2573 } |
2573 } | 2574 } |
2574 } | 2575 } |
2575 } | 2576 } |
2576 } | 2577 } |
2577 | 2578 |
2578 | 2579 |
2579 class HRangeAnalysis BASE_EMBEDDED { | |
2580 public: | |
2581 explicit HRangeAnalysis(HGraph* graph) : | |
2582 graph_(graph), zone_(graph->zone()), changed_ranges_(16, zone_) { } | |
2583 | |
2584 void Analyze(); | |
2585 | |
2586 private: | |
2587 void TraceRange(const char* msg, ...); | |
2588 void Analyze(HBasicBlock* block); | |
2589 void InferControlFlowRange(HCompareIDAndBranch* test, HBasicBlock* dest); | |
2590 void UpdateControlFlowRange(Token::Value op, HValue* value, HValue* other); | |
2591 void InferRange(HValue* value); | |
2592 void RollBackTo(int index); | |
2593 void AddRange(HValue* value, Range* range); | |
2594 | |
2595 HGraph* graph_; | |
2596 Zone* zone_; | |
2597 ZoneList<HValue*> changed_ranges_; | |
2598 }; | |
2599 | |
2600 | |
2601 void HRangeAnalysis::TraceRange(const char* msg, ...) { | |
2602 if (FLAG_trace_range) { | |
2603 va_list arguments; | |
2604 va_start(arguments, msg); | |
2605 OS::VPrint(msg, arguments); | |
2606 va_end(arguments); | |
2607 } | |
2608 } | |
2609 | |
2610 | |
2611 void HRangeAnalysis::Analyze() { | |
2612 HPhase phase("H_Range analysis", graph_); | |
2613 Analyze(graph_->entry_block()); | |
2614 } | |
2615 | |
2616 | |
2617 void HRangeAnalysis::Analyze(HBasicBlock* block) { | |
2618 TraceRange("Analyzing block B%d\n", block->block_id()); | |
2619 | |
2620 int last_changed_range = changed_ranges_.length() - 1; | |
2621 | |
2622 // Infer range based on control flow. | |
2623 if (block->predecessors()->length() == 1) { | |
2624 HBasicBlock* pred = block->predecessors()->first(); | |
2625 if (pred->end()->IsCompareIDAndBranch()) { | |
2626 InferControlFlowRange(HCompareIDAndBranch::cast(pred->end()), block); | |
2627 } | |
2628 } | |
2629 | |
2630 // Process phi instructions. | |
2631 for (int i = 0; i < block->phis()->length(); ++i) { | |
2632 HPhi* phi = block->phis()->at(i); | |
2633 InferRange(phi); | |
2634 } | |
2635 | |
2636 // Go through all instructions of the current block. | |
2637 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { | |
2638 InferRange(it.Current()); | |
2639 } | |
2640 | |
2641 // Continue analysis in all dominated blocks. | |
2642 for (int i = 0; i < block->dominated_blocks()->length(); ++i) { | |
2643 Analyze(block->dominated_blocks()->at(i)); | |
2644 } | |
2645 | |
2646 RollBackTo(last_changed_range); | |
2647 } | |
2648 | |
2649 | |
2650 void HRangeAnalysis::InferControlFlowRange(HCompareIDAndBranch* test, | |
2651 HBasicBlock* dest) { | |
2652 ASSERT((test->FirstSuccessor() == dest) == (test->SecondSuccessor() != dest)); | |
2653 if (test->representation().IsSmiOrInteger32()) { | |
2654 Token::Value op = test->token(); | |
2655 if (test->SecondSuccessor() == dest) { | |
2656 op = Token::NegateCompareOp(op); | |
2657 } | |
2658 Token::Value inverted_op = Token::ReverseCompareOp(op); | |
2659 UpdateControlFlowRange(op, test->left(), test->right()); | |
2660 UpdateControlFlowRange(inverted_op, test->right(), test->left()); | |
2661 } | |
2662 } | |
2663 | |
2664 | |
2665 // We know that value [op] other. Use this information to update the range on | |
2666 // value. | |
2667 void HRangeAnalysis::UpdateControlFlowRange(Token::Value op, | |
2668 HValue* value, | |
2669 HValue* other) { | |
2670 Range temp_range; | |
2671 Range* range = other->range() != NULL ? other->range() : &temp_range; | |
2672 Range* new_range = NULL; | |
2673 | |
2674 TraceRange("Control flow range infer %d %s %d\n", | |
2675 value->id(), | |
2676 Token::Name(op), | |
2677 other->id()); | |
2678 | |
2679 if (op == Token::EQ || op == Token::EQ_STRICT) { | |
2680 // The same range has to apply for value. | |
2681 new_range = range->Copy(zone_); | |
2682 } else if (op == Token::LT || op == Token::LTE) { | |
2683 new_range = range->CopyClearLower(zone_); | |
2684 if (op == Token::LT) { | |
2685 new_range->AddConstant(-1); | |
2686 } | |
2687 } else if (op == Token::GT || op == Token::GTE) { | |
2688 new_range = range->CopyClearUpper(zone_); | |
2689 if (op == Token::GT) { | |
2690 new_range->AddConstant(1); | |
2691 } | |
2692 } | |
2693 | |
2694 if (new_range != NULL && !new_range->IsMostGeneric()) { | |
2695 AddRange(value, new_range); | |
2696 } | |
2697 } | |
2698 | |
2699 | |
2700 void HRangeAnalysis::InferRange(HValue* value) { | |
2701 ASSERT(!value->HasRange()); | |
2702 if (!value->representation().IsNone()) { | |
2703 value->ComputeInitialRange(zone_); | |
2704 Range* range = value->range(); | |
2705 TraceRange("Initial inferred range of %d (%s) set to [%d,%d]\n", | |
2706 value->id(), | |
2707 value->Mnemonic(), | |
2708 range->lower(), | |
2709 range->upper()); | |
2710 } | |
2711 } | |
2712 | |
2713 | |
2714 void HRangeAnalysis::RollBackTo(int index) { | |
2715 for (int i = index + 1; i < changed_ranges_.length(); ++i) { | |
2716 changed_ranges_[i]->RemoveLastAddedRange(); | |
2717 } | |
2718 changed_ranges_.Rewind(index + 1); | |
2719 } | |
2720 | |
2721 | |
2722 void HRangeAnalysis::AddRange(HValue* value, Range* range) { | |
2723 Range* original_range = value->range(); | |
2724 value->AddNewRange(range, zone_); | |
2725 changed_ranges_.Add(value, zone_); | |
2726 Range* new_range = value->range(); | |
2727 TraceRange("Updated range of %d set to [%d,%d]\n", | |
2728 value->id(), | |
2729 new_range->lower(), | |
2730 new_range->upper()); | |
2731 if (original_range != NULL) { | |
2732 TraceRange("Original range was [%d,%d]\n", | |
2733 original_range->lower(), | |
2734 original_range->upper()); | |
2735 } | |
2736 TraceRange("New information was [%d,%d]\n", | |
2737 range->lower(), | |
2738 range->upper()); | |
2739 } | |
2740 | |
2741 | |
2742 class HStackCheckEliminator BASE_EMBEDDED { | 2580 class HStackCheckEliminator BASE_EMBEDDED { |
2743 public: | 2581 public: |
2744 explicit HStackCheckEliminator(HGraph* graph) : graph_(graph) { } | 2582 explicit HStackCheckEliminator(HGraph* graph) : graph_(graph) { } |
2745 | 2583 |
2746 void Process(); | 2584 void Process(); |
2747 | 2585 |
2748 private: | 2586 private: |
2749 HGraph* graph_; | 2587 HGraph* graph_; |
2750 }; | 2588 }; |
2751 | 2589 |
(...skipping 847 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3599 // will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with | 3437 // will not remove semantically meaningful ToInt32 operations e.g. BIT_OR with |
3600 // zero. | 3438 // zero. |
3601 if (FLAG_opt_safe_uint32_operations) Run<HUint32AnalysisPhase>(); | 3439 if (FLAG_opt_safe_uint32_operations) Run<HUint32AnalysisPhase>(); |
3602 | 3440 |
3603 if (FLAG_use_canonicalizing) Canonicalize(); | 3441 if (FLAG_use_canonicalizing) Canonicalize(); |
3604 | 3442 |
3605 if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>(); | 3443 if (FLAG_use_escape_analysis) Run<HEscapeAnalysisPhase>(); |
3606 | 3444 |
3607 if (FLAG_use_gvn) Run<HGlobalValueNumberingPhase>(); | 3445 if (FLAG_use_gvn) Run<HGlobalValueNumberingPhase>(); |
3608 | 3446 |
3609 if (FLAG_use_range) { | 3447 if (FLAG_use_range) Run<HRangeAnalysisPhase>(); |
3610 HRangeAnalysis range_analysis(this); | 3448 |
3611 range_analysis.Analyze(); | |
3612 } | |
3613 ComputeMinusZeroChecks(); | 3449 ComputeMinusZeroChecks(); |
3614 | 3450 |
3615 // Eliminate redundant stack checks on backwards branches. | 3451 // Eliminate redundant stack checks on backwards branches. |
3616 HStackCheckEliminator sce(this); | 3452 HStackCheckEliminator sce(this); |
3617 sce.Process(); | 3453 sce.Process(); |
3618 | 3454 |
3619 if (FLAG_idefs) SetupInformativeDefinitions(); | 3455 if (FLAG_idefs) SetupInformativeDefinitions(); |
3620 if (FLAG_array_bounds_checks_elimination && !FLAG_idefs) { | 3456 if (FLAG_array_bounds_checks_elimination && !FLAG_idefs) { |
3621 EliminateRedundantBoundsChecks(); | 3457 EliminateRedundantBoundsChecks(); |
3622 } | 3458 } |
(...skipping 7415 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
11038 if (ShouldProduceTraceOutput()) { | 10874 if (ShouldProduceTraceOutput()) { |
11039 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); | 10875 isolate()->GetHTracer()->TraceHydrogen(name(), graph_); |
11040 } | 10876 } |
11041 | 10877 |
11042 #ifdef DEBUG | 10878 #ifdef DEBUG |
11043 graph_->Verify(false); // No full verify. | 10879 graph_->Verify(false); // No full verify. |
11044 #endif | 10880 #endif |
11045 } | 10881 } |
11046 | 10882 |
11047 } } // namespace v8::internal | 10883 } } // namespace v8::internal |
OLD | NEW |