Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2015 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/control-flow-optimizer.h"
      6 
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/graph.h"
      9 #include "src/compiler/node-matchers.h"
     10 #include "src/compiler/node-properties.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 ControlFlowOptimizer::ControlFlowOptimizer(Graph* graph,
     17                                            CommonOperatorBuilder* common,
     18                                            MachineOperatorBuilder* machine,
     19                                            Zone* zone)
     20     : graph_(graph),
     21       common_(common),
     22       machine_(machine),
     23       queue_(zone),
     24       queued_(graph, 2),
     25       zone_(zone) {}
     26 
     27 
     28 void ControlFlowOptimizer::Optimize() {
     29   Enqueue(graph()->start());
     30   while (!queue_.empty()) {
     31     Node* node = queue_.front();
     32     queue_.pop();
     33     if (node->IsDead()) continue;
     34     switch (node->opcode()) {
     35       case IrOpcode::kBranch:
     36         VisitBranch(node);
     37         break;
     38       default:
     39         VisitNode(node);
     40         break;
     41     }
     42   }
     43 }
     44 
     45 
     46 void ControlFlowOptimizer::Enqueue(Node* node) {
     47   DCHECK_NOT_NULL(node);
     48   if (node->IsDead() || queued_.Get(node)) return;
     49   queued_.Set(node, true);
     50   queue_.push(node);
     51 }
     52 
     53 
     54 void ControlFlowOptimizer::VisitNode(Node* node) {
     55   for (Edge edge : node->use_edges()) {
     56     if (NodeProperties::IsControlEdge(edge)) {
     57       Enqueue(edge.from());
     58     }
     59   }
     60 }
     61 
     62 
     63 void ControlFlowOptimizer::VisitBranch(Node* node) {
     64   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     65   if (TryBuildSwitch(node)) return;
     66   VisitNode(node);
     67 }
     68 
     69 
     70 bool ControlFlowOptimizer::TryBuildSwitch(Node* node) {
     71   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
     72 
     73   Node* branch = node;
     74   if (BranchHintOf(branch->op()) != BranchHint::kNone) return false;
     75   Node* cond = NodeProperties::GetValueInput(branch, 0);
     76   if (cond->opcode() != IrOpcode::kWord32Equal) return false;
     77   Int32BinopMatcher m(cond);
     78   Node* index = m.left().node();
     79   if (!m.right().HasValue()) return false;
     80   int32_t value = m.right().Value();
     81   ZoneSet<int32_t> values(zone());
     82   values.insert(value);
     83 
     84   Node* if_false;
     85   Node* if_true;
     86   while (true) {
     87     BranchMatcher matcher(branch);
     88     DCHECK(matcher.Matched());
     89 
     90     if_true = matcher.IfTrue();
     91     if_false = matcher.IfFalse();
     92 
     93     auto it = if_false->uses().begin();
     94     if (it == if_false->uses().end()) break;
     95     Node* branch1 = *it++;
     96     if (branch1->opcode() != IrOpcode::kBranch) break;
     97     if (BranchHintOf(branch1->op()) != BranchHint::kNone) break;
     98     if (it != if_false->uses().end()) break;
     99     Node* cond1 = branch1->InputAt(0);
    100     if (cond1->opcode() != IrOpcode::kWord32Equal) break;
    101     Int32BinopMatcher m1(cond1);
    102     if (m1.left().node() != index) break;
    103     if (!m1.right().HasValue()) break;
    104     int32_t value1 = m1.right().Value();
    105     if (values.find(value1) != values.end()) break;
    106     DCHECK_NE(value, value1);
    107 
    108     if (branch != node) {
    109       branch->NullAllInputs();
    110       if_true->ReplaceInput(0, node);
    111     }
    112     NodeProperties::ChangeOp(if_true, common()->IfValue(value));
    113     if_false->NullAllInputs();
    114     Enqueue(if_true);
    115 
    116     branch = branch1;
    117     value = value1;
    118     values.insert(value);
    119   }
    120 
    121   DCHECK_EQ(IrOpcode::kBranch, node->opcode());
    122   DCHECK_EQ(IrOpcode::kBranch, branch->opcode());
    123   if (branch == node) {
    124     DCHECK_EQ(1u, values.size());
    125     return false;
    126   }
    127   DCHECK_LT(1u, values.size());
    128   node->ReplaceInput(0, index);
    129   NodeProperties::ChangeOp(node, common()->Switch(values.size() + 1));
    130   if_true->ReplaceInput(0, node);
    131   NodeProperties::ChangeOp(if_true, common()->IfValue(value));
    132   Enqueue(if_true);
    133   if_false->ReplaceInput(0, node);
    134   NodeProperties::ChangeOp(if_false, common()->IfDefault());
    135   Enqueue(if_false);
    136   branch->NullAllInputs();
    137   return true;
    138 }
    139 
    140 }  // namespace compiler
    141 }  // namespace internal
    142 }  // namespace v8
    143