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