LCOV - code coverage report
Current view: top level - src/compiler - control-equivalence.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 101 105 96.2 %
Date: 2017-04-26 Functions: 12 12 100.0 %

          Line data    Source code
       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-equivalence.h"
       6             : #include "src/compiler/node-properties.h"
       7             : 
       8             : #define TRACE(...)                                 \
       9             :   do {                                             \
      10             :     if (FLAG_trace_turbo_ceq) PrintF(__VA_ARGS__); \
      11             :   } while (false)
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17      215041 : void ControlEquivalence::Run(Node* exit) {
      18      215043 :   if (!Participates(exit) || GetClass(exit) == kInvalidClass) {
      19      215039 :     DetermineParticipation(exit);
      20      215039 :     RunUndirectedDFS(exit);
      21             :   }
      22      215041 : }
      23             : 
      24             : 
      25             : // static
      26             : STATIC_CONST_MEMBER_DEFINITION const size_t ControlEquivalence::kInvalidClass;
      27             : 
      28             : 
      29     5423007 : void ControlEquivalence::VisitPre(Node* node) {
      30     5423007 :   TRACE("CEQ: Pre-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
      31     5423007 : }
      32             : 
      33             : 
      34     5422995 : void ControlEquivalence::VisitMid(Node* node, DFSDirection direction) {
      35     5422995 :   TRACE("CEQ: Mid-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
      36     5422999 :   BracketList& blist = GetBracketList(node);
      37             : 
      38             :   // Remove brackets pointing to this node [line:19].
      39     5422999 :   BracketListDelete(blist, node, direction);
      40             : 
      41             :   // Potentially introduce artificial dependency from start to end.
      42     5423008 :   if (blist.empty()) {
      43             :     DCHECK_EQ(kInputDirection, direction);
      44      268724 :     VisitBackedge(node, graph_->end(), kInputDirection);
      45             :   }
      46             : 
      47             :   // Potentially start a new equivalence class [line:37].
      48     5423008 :   BracketListTRACE(blist);
      49             :   Bracket* recent = &blist.back();
      50    10846018 :   if (recent->recent_size != blist.size()) {
      51     2616861 :     recent->recent_size = blist.size();
      52     2616861 :     recent->recent_class = NewClassNumber();
      53             :   }
      54             : 
      55             :   // Assign equivalence class to node.
      56     5423009 :   SetClass(node, recent->recent_class);
      57     5423002 :   TRACE("  Assigned class number is %zu\n", GetClass(node));
      58     5423002 : }
      59             : 
      60             : 
      61     5422996 : void ControlEquivalence::VisitPost(Node* node, Node* parent_node,
      62             :                                    DFSDirection direction) {
      63     5422996 :   TRACE("CEQ: Post-visit of #%d:%s\n", node->id(), node->op()->mnemonic());
      64     5422989 :   BracketList& blist = GetBracketList(node);
      65             : 
      66             :   // Remove brackets pointing to this node [line:19].
      67     5422989 :   BracketListDelete(blist, node, direction);
      68             : 
      69             :   // Propagate bracket list up the DFS tree [line:13].
      70     5423004 :   if (parent_node != nullptr) {
      71             :     BracketList& parent_blist = GetBracketList(parent_node);
      72    10415918 :     parent_blist.splice(parent_blist.end(), blist);
      73             :   }
      74     5422998 : }
      75             : 
      76             : 
      77     1349923 : void ControlEquivalence::VisitBackedge(Node* from, Node* to,
      78             :                                        DFSDirection direction) {
      79     1349923 :   TRACE("CEQ: Backedge from #%d:%s to #%d:%s\n", from->id(),
      80             :         from->op()->mnemonic(), to->id(), to->op()->mnemonic());
      81             : 
      82             :   // Push backedge onto the bracket list [line:25].
      83     1349923 :   Bracket bracket = {direction, kInvalidClass, 0, from, to};
      84     1349923 :   GetBracketList(from).push_back(bracket);
      85     1349923 : }
      86             : 
      87             : 
      88      215037 : void ControlEquivalence::RunUndirectedDFS(Node* exit) {
      89      215037 :   ZoneStack<DFSStackEntry> stack(zone_);
      90      215037 :   DFSPush(stack, exit, nullptr, kInputDirection);
      91      215037 :   VisitPre(exit);
      92             : 
      93    40138407 :   while (!stack.empty()) {  // Undirected depth-first backwards traversal.
      94             :     DFSStackEntry& entry = stack.top();
      95    39708288 :     Node* node = entry.node;
      96             : 
      97    39708288 :     if (entry.direction == kInputDirection) {
      98    18806528 :       if (entry.input != node->input_edges().end()) {
      99    13383537 :         Edge edge = *entry.input;
     100             :         Node* input = edge.to();
     101             :         ++(entry.input);
     102    13383537 :         if (NodeProperties::IsControlEdge(edge)) {
     103             :           // Visit next control input.
     104     6437121 :           if (!Participates(input)) continue;
     105     6437124 :           if (GetData(input)->visited) continue;
     106     5443534 :           if (GetData(input)->on_stack) {
     107             :             // Found backedge if input is on stack.
     108     2130262 :             if (input != entry.parent_node) {
     109      235569 :               VisitBackedge(node, input, kInputDirection);
     110             :             }
     111             :           } else {
     112             :             // Push input onto stack.
     113     3313285 :             DFSPush(stack, input, node, kInputDirection);
     114     3313289 :             VisitPre(input);
     115             :           }
     116             :         }
     117             :         continue;
     118             :       }
     119     5422991 :       if (entry.use != node->use_edges().end()) {
     120             :         // Switch direction to uses.
     121     3528317 :         entry.direction = kUseDirection;
     122     3528317 :         VisitMid(node, kInputDirection);
     123     3528319 :         continue;
     124             :       }
     125             :     }
     126             : 
     127    22796434 :     if (entry.direction == kUseDirection) {
     128    20902769 :       if (entry.use != node->use_edges().end()) {
     129    15479772 :         Edge edge = *entry.use;
     130             :         Node* use = edge.from();
     131             :         ++(entry.use);
     132    15479772 :         if (NodeProperties::IsControlEdge(edge)) {
     133             :           // Visit next control use.
     134    10654164 :           if (!Participates(use)) continue;
     135     6289161 :           if (GetData(use)->visited) continue;
     136     6053588 :           if (GetData(use)->on_stack) {
     137             :             // Found backedge if use is on stack.
     138     4158904 :             if (use != entry.parent_node) {
     139      845633 :               VisitBackedge(node, use, kUseDirection);
     140             :             }
     141             :           } else {
     142             :             // Push use onto stack.
     143     1894692 :             DFSPush(stack, use, node, kUseDirection);
     144     1894692 :             VisitPre(use);
     145             :           }
     146             :         }
     147             :         continue;
     148             :       }
     149     5422997 :       if (entry.input != node->input_edges().end()) {
     150             :         // Switch direction to inputs.
     151     1894693 :         entry.direction = kInputDirection;
     152     1894693 :         VisitMid(node, kUseDirection);
     153     1894695 :         continue;
     154             :       }
     155             :     }
     156             : 
     157             :     // Pop node from stack when done with all inputs and uses.
     158             :     DCHECK(entry.input == node->input_edges().end());
     159             :     DCHECK(entry.use == node->use_edges().end());
     160     5421969 :     DFSPop(stack, node);
     161     5422996 :     VisitPost(node, entry.parent_node, entry.direction);
     162             :   }
     163      215039 : }
     164             : 
     165     6652113 : void ControlEquivalence::DetermineParticipationEnqueue(ZoneQueue<Node*>& queue,
     166             :                                                        Node* node) {
     167    13304231 :   if (!Participates(node)) {
     168     5422980 :     AllocateData(node);
     169             :     queue.push(node);
     170             :   }
     171     6652113 : }
     172             : 
     173             : 
     174      215039 : void ControlEquivalence::DetermineParticipation(Node* exit) {
     175      215039 :   ZoneQueue<Node*> queue(zone_);
     176      215039 :   DetermineParticipationEnqueue(queue, exit);
     177     5853044 :   while (!queue.empty()) {  // Breadth-first backwards traversal.
     178     5422974 :     Node* node = queue.front();
     179             :     queue.pop();
     180     5422976 :     int max = NodeProperties::PastControlIndex(node);
     181    11860059 :     for (int i = NodeProperties::FirstControlIndex(node); i < max; i++) {
     182     6437077 :       DetermineParticipationEnqueue(queue, node->InputAt(i));
     183             :     }
     184             :   }
     185      215039 : }
     186             : 
     187             : 
     188     5423004 : void ControlEquivalence::DFSPush(DFSStack& stack, Node* node, Node* from,
     189             :                                  DFSDirection dir) {
     190             :   DCHECK(Participates(node));
     191             :   DCHECK(!GetData(node)->visited);
     192     5423004 :   GetData(node)->on_stack = true;
     193             :   Node::InputEdges::iterator input = node->input_edges().begin();
     194             :   Node::UseEdges::iterator use = node->use_edges().begin();
     195    16269022 :   stack.push({dir, input, use, from, node});
     196     5423006 : }
     197             : 
     198             : 
     199     5422995 : void ControlEquivalence::DFSPop(DFSStack& stack, Node* node) {
     200             :   DCHECK_EQ(stack.top().node, node);
     201     5422995 :   GetData(node)->on_stack = false;
     202     5422994 :   GetData(node)->visited = true;
     203             :   stack.pop();
     204     5423000 : }
     205             : 
     206             : 
     207    10845945 : void ControlEquivalence::BracketListDelete(BracketList& blist, Node* to,
     208             :                                            DFSDirection direction) {
     209             :   // TODO(mstarzinger): Optimize this to avoid linear search.
     210    59814815 :   for (BracketList::iterator i = blist.begin(); i != blist.end(); /*nop*/) {
     211    38122918 :     if (i->to == to && i->direction != direction) {
     212     1081176 :       TRACE("  BList erased: {%d->%d}\n", i->from->id(), i->to->id());
     213             :       i = blist.erase(i);
     214             :     } else {
     215             :       ++i;
     216             :     }
     217             :   }
     218    10845952 : }
     219             : 
     220             : 
     221     5423006 : void ControlEquivalence::BracketListTRACE(BracketList& blist) {
     222     5423006 :   if (FLAG_trace_turbo_ceq) {
     223           0 :     TRACE("  BList: ");
     224           0 :     for (Bracket bracket : blist) {
     225           0 :       TRACE("{%d->%d} ", bracket.from->id(), bracket.to->id());
     226             :     }
     227           0 :     TRACE("\n");
     228             :   }
     229     5423006 : }
     230             : 
     231             : }  // namespace compiler
     232             : }  // namespace internal
     233             : }  // namespace v8

Generated by: LCOV version 1.10