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/branch-elimination.h"
      6 
      7 #include "src/compiler/js-graph.h"
      8 #include "src/compiler/node-properties.h"
      9 #include "src/compiler/simplified-operator.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace compiler {
     14 
     15 BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
     16                                      Zone* zone)
     17     : AdvancedReducer(editor),
     18       jsgraph_(js_graph),
     19       node_conditions_(zone, js_graph->graph()->NodeCount()),
     20       zone_(zone),
     21       dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {
     22   NodeProperties::SetType(dead_, Type::None());
     23 }
     24 
     25 BranchElimination::~BranchElimination() {}
     26 
     27 
     28 Reduction BranchElimination::Reduce(Node* node) {
     29   switch (node->opcode()) {
     30     case IrOpcode::kDead:
     31       return NoChange();
     32     case IrOpcode::kDeoptimizeIf:
     33     case IrOpcode::kDeoptimizeUnless:
     34       return ReduceDeoptimizeConditional(node);
     35     case IrOpcode::kMerge:
     36       return ReduceMerge(node);
     37     case IrOpcode::kLoop:
     38       return ReduceLoop(node);
     39     case IrOpcode::kBranch:
     40       return ReduceBranch(node);
     41     case IrOpcode::kIfFalse:
     42       return ReduceIf(node, false);
     43     case IrOpcode::kIfTrue:
     44       return ReduceIf(node, true);
     45     case IrOpcode::kStart:
     46       return ReduceStart(node);
     47     default:
     48       if (node->op()->ControlOutputCount() > 0) {
     49         return ReduceOtherControl(node);
     50       }
     51       break;
     52   }
     53   return NoChange();
     54 }
     55 
     56 
     57 Reduction BranchElimination::ReduceBranch(Node* node) {
     58   Node* condition = node->InputAt(0);
     59   Node* control_input = NodeProperties::GetControlInput(node, 0);
     60   const ControlPathConditions* from_input = node_conditions_.Get(control_input);
     61   if (from_input != nullptr) {
     62     Maybe<bool> condition_value = from_input->LookupCondition(condition);
     63     // If we know the condition we can discard the branch.
     64     if (condition_value.IsJust()) {
     65       bool known_value = condition_value.FromJust();
     66       for (Node* const use : node->uses()) {
     67         switch (use->opcode()) {
     68           case IrOpcode::kIfTrue:
     69             Replace(use, known_value ? control_input : dead());
     70             break;
     71           case IrOpcode::kIfFalse:
     72             Replace(use, known_value ? dead() : control_input);
     73             break;
     74           default:
     75             UNREACHABLE();
     76         }
     77       }
     78       return Replace(dead());
     79     }
     80   }
     81   return TakeConditionsFromFirstControl(node);
     82 }
     83 
     84 Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
     85   DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
     86          node->opcode() == IrOpcode::kDeoptimizeUnless);
     87   bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
     88   DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
     89   Node* condition = NodeProperties::GetValueInput(node, 0);
     90   Node* frame_state = NodeProperties::GetValueInput(node, 1);
     91   Node* effect = NodeProperties::GetEffectInput(node);
     92   Node* control = NodeProperties::GetControlInput(node);
     93   ControlPathConditions const* conditions = node_conditions_.Get(control);
     94   // If we do not know anything about the predecessor, do not propagate just
     95   // yet because we will have to recompute anyway once we compute the
     96   // predecessor.
     97   if (conditions == nullptr) {
     98     return UpdateConditions(node, conditions);
     99   }
    100   Maybe<bool> condition_value = conditions->LookupCondition(condition);
    101   if (condition_value.IsJust()) {
    102     // If we know the condition we can discard the branch.
    103     if (condition_is_true == condition_value.FromJust()) {
    104       // We don't update the conditions here, because we're replacing {node}
    105       // with the {control} node that already contains the right information.
    106       ReplaceWithValue(node, dead(), effect, control);
    107     } else {
    108       control = graph()->NewNode(common()->Deoptimize(p.kind(), p.reason()),
    109                                  frame_state, effect, control);
    110       // TODO(bmeurer): This should be on the AdvancedReducer somehow.
    111       NodeProperties::MergeControlToEnd(graph(), common(), control);
    112       Revisit(graph()->end());
    113     }
    114     return Replace(dead());
    115   }
    116   return UpdateConditions(
    117       node, conditions->AddCondition(zone_, condition, condition_is_true));
    118 }
    119 
    120 Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
    121   // Add the condition to the list arriving from the input branch.
    122   Node* branch = NodeProperties::GetControlInput(node, 0);
    123   const ControlPathConditions* from_branch = node_conditions_.Get(branch);
    124   // If we do not know anything about the predecessor, do not propagate just
    125   // yet because we will have to recompute anyway once we compute the
    126   // predecessor.
    127   if (from_branch == nullptr) {
    128     return UpdateConditions(node, nullptr);
    129   }
    130   Node* condition = branch->InputAt(0);
    131   return UpdateConditions(
    132       node, from_branch->AddCondition(zone_, condition, is_true_branch));
    133 }
    134 
    135 
    136 Reduction BranchElimination::ReduceLoop(Node* node) {
    137   // Here we rely on having only reducible loops:
    138   // The loop entry edge always dominates the header, so we can just use
    139   // the information from the loop entry edge.
    140   return TakeConditionsFromFirstControl(node);
    141 }
    142 
    143 
    144 Reduction BranchElimination::ReduceMerge(Node* node) {
    145   // Shortcut for the case when we do not know anything about some
    146   // input.
    147   Node::Inputs inputs = node->inputs();
    148   for (Node* input : inputs) {
    149     if (node_conditions_.Get(input) == nullptr) {
    150       return UpdateConditions(node, nullptr);
    151     }
    152   }
    153 
    154   auto input_it = inputs.begin();
    155 
    156   DCHECK_GT(inputs.count(), 0);
    157 
    158   const ControlPathConditions* first = node_conditions_.Get(*input_it);
    159   ++input_it;
    160   // Make a copy of the first input's conditions and merge with the conditions
    161   // from other inputs.
    162   ControlPathConditions* conditions =
    163       new (zone_->New(sizeof(ControlPathConditions)))
    164           ControlPathConditions(*first);
    165   auto input_end = inputs.end();
    166   for (; input_it != input_end; ++input_it) {
    167     conditions->Merge(*(node_conditions_.Get(*input_it)));
    168   }
    169 
    170   return UpdateConditions(node, conditions);
    171 }
    172 
    173 
    174 Reduction BranchElimination::ReduceStart(Node* node) {
    175   return UpdateConditions(node, ControlPathConditions::Empty(zone_));
    176 }
    177 
    178 
    179 const BranchElimination::ControlPathConditions*
    180 BranchElimination::PathConditionsForControlNodes::Get(Node* node) {
    181   if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
    182     return info_for_node_[node->id()];
    183   }
    184   return nullptr;
    185 }
    186 
    187 
    188 void BranchElimination::PathConditionsForControlNodes::Set(
    189     Node* node, const ControlPathConditions* conditions) {
    190   size_t index = static_cast<size_t>(node->id());
    191   if (index >= info_for_node_.size()) {
    192     info_for_node_.resize(index + 1, nullptr);
    193   }
    194   info_for_node_[index] = conditions;
    195 }
    196 
    197 
    198 Reduction BranchElimination::ReduceOtherControl(Node* node) {
    199   DCHECK_EQ(1, node->op()->ControlInputCount());
    200   return TakeConditionsFromFirstControl(node);
    201 }
    202 
    203 
    204 Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
    205   // We just propagate the information from the control input (ideally,
    206   // we would only revisit control uses if there is change).
    207   const ControlPathConditions* from_input =
    208       node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
    209   return UpdateConditions(node, from_input);
    210 }
    211 
    212 
    213 Reduction BranchElimination::UpdateConditions(
    214     Node* node, const ControlPathConditions* conditions) {
    215   const ControlPathConditions* original = node_conditions_.Get(node);
    216   // Only signal that the node has Changed if the condition information has
    217   // changed.
    218   if (conditions != original) {
    219     if (conditions == nullptr || original == nullptr ||
    220         *conditions != *original) {
    221       node_conditions_.Set(node, conditions);
    222       return Changed(node);
    223     }
    224   }
    225   return NoChange();
    226 }
    227 
    228 
    229 // static
    230 const BranchElimination::ControlPathConditions*
    231 BranchElimination::ControlPathConditions::Empty(Zone* zone) {
    232   return new (zone->New(sizeof(ControlPathConditions)))
    233       ControlPathConditions(nullptr, 0);
    234 }
    235 
    236 
    237 void BranchElimination::ControlPathConditions::Merge(
    238     const ControlPathConditions& other) {
    239   // Change the current condition list to a longest common tail
    240   // of this condition list and the other list. (The common tail
    241   // should correspond to the list from the common dominator.)
    242 
    243   // First, we throw away the prefix of the longer list, so that
    244   // we have lists of the same length.
    245   size_t other_size = other.condition_count_;
    246   BranchCondition* other_condition = other.head_;
    247   while (other_size > condition_count_) {
    248     other_condition = other_condition->next;
    249     other_size--;
    250   }
    251   while (condition_count_ > other_size) {
    252     head_ = head_->next;
    253     condition_count_--;
    254   }
    255 
    256   // Then we go through both lists in lock-step until we find
    257   // the common tail.
    258   while (head_ != other_condition) {
    259     DCHECK(condition_count_ > 0);
    260     condition_count_--;
    261     other_condition = other_condition->next;
    262     head_ = head_->next;
    263   }
    264 }
    265 
    266 
    267 const BranchElimination::ControlPathConditions*
    268 BranchElimination::ControlPathConditions::AddCondition(Zone* zone,
    269                                                        Node* condition,
    270                                                        bool is_true) const {
    271   DCHECK(LookupCondition(condition).IsNothing());
    272 
    273   BranchCondition* new_head = new (zone->New(sizeof(BranchCondition)))
    274       BranchCondition(condition, is_true, head_);
    275 
    276   ControlPathConditions* conditions =
    277       new (zone->New(sizeof(ControlPathConditions)))
    278           ControlPathConditions(new_head, condition_count_ + 1);
    279   return conditions;
    280 }
    281 
    282 
    283 Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
    284     Node* condition) const {
    285   for (BranchCondition* current = head_; current != nullptr;
    286        current = current->next) {
    287     if (current->condition == condition) {
    288       return Just<bool>(current->is_true);
    289     }
    290   }
    291   return Nothing<bool>();
    292 }
    293 
    294 
    295 bool BranchElimination::ControlPathConditions::operator==(
    296     const ControlPathConditions& other) const {
    297   if (condition_count_ != other.condition_count_) return false;
    298   BranchCondition* this_condition = head_;
    299   BranchCondition* other_condition = other.head_;
    300   while (true) {
    301     if (this_condition == other_condition) return true;
    302     if (this_condition->condition != other_condition->condition ||
    303         this_condition->is_true != other_condition->is_true) {
    304       return false;
    305     }
    306     this_condition = this_condition->next;
    307     other_condition = other_condition->next;
    308   }
    309   UNREACHABLE();
    310   return false;
    311 }
    312 
    313 Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
    314 
    315 CommonOperatorBuilder* BranchElimination::common() const {
    316   return jsgraph()->common();
    317 }
    318 
    319 }  // namespace compiler
    320 }  // namespace internal
    321 }  // namespace v8
    322