Home | History | Annotate | Download | only in compiler
      1 // Copyright 2014 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/loop-analysis.h"
      6 
      7 #include "src/compiler/graph.h"
      8 #include "src/compiler/node.h"
      9 #include "src/compiler/node-marker.h"
     10 #include "src/compiler/node-properties.h"
     11 #include "src/zone.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 namespace compiler {
     16 
     17 #define OFFSET(x) ((x)&0x1f)
     18 #define BIT(x) (1u << OFFSET(x))
     19 #define INDEX(x) ((x) >> 5)
     20 
     21 // Temporary information for each node during marking.
     22 struct NodeInfo {
     23   Node* node;
     24   NodeInfo* next;       // link in chaining loop members
     25 };
     26 
     27 
     28 // Temporary loop info needed during traversal and building the loop tree.
     29 struct LoopInfo {
     30   Node* header;
     31   NodeInfo* header_list;
     32   NodeInfo* body_list;
     33   LoopTree::Loop* loop;
     34 };
     35 
     36 
     37 // Encapsulation of the loop finding algorithm.
     38 // -----------------------------------------------------------------------------
     39 // Conceptually, the contents of a loop are those nodes that are "between" the
     40 // loop header and the backedges of the loop. Graphs in the soup of nodes can
     41 // form improper cycles, so standard loop finding algorithms that work on CFGs
     42 // aren't sufficient. However, in valid TurboFan graphs, all cycles involve
     43 // either a {Loop} node or a phi. The {Loop} node itself and its accompanying
     44 // phis are treated together as a set referred to here as the loop header.
     45 // This loop finding algorithm works by traversing the graph in two directions,
     46 // first from nodes to their inputs, starting at {end}, then in the reverse
     47 // direction, from nodes to their uses, starting at loop headers.
     48 // 1 bit per loop per node per direction are required during the marking phase.
     49 // To handle nested loops correctly, the algorithm must filter some reachability
     50 // marks on edges into/out-of the loop header nodes.
     51 class LoopFinderImpl {
     52  public:
     53   LoopFinderImpl(Graph* graph, LoopTree* loop_tree, Zone* zone)
     54       : zone_(zone),
     55         end_(graph->end()),
     56         queue_(zone),
     57         queued_(graph, 2),
     58         info_(graph->NodeCount(), {nullptr, nullptr}, zone),
     59         loops_(zone),
     60         loop_num_(graph->NodeCount(), -1, zone),
     61         loop_tree_(loop_tree),
     62         loops_found_(0),
     63         width_(0),
     64         backward_(nullptr),
     65         forward_(nullptr) {}
     66 
     67   void Run() {
     68     PropagateBackward();
     69     PropagateForward();
     70     FinishLoopTree();
     71   }
     72 
     73   void Print() {
     74     // Print out the results.
     75     for (NodeInfo& ni : info_) {
     76       if (ni.node == nullptr) continue;
     77       for (int i = 1; i <= loops_found_; i++) {
     78         int index = ni.node->id() * width_ + INDEX(i);
     79         bool marked_forward = forward_[index] & BIT(i);
     80         bool marked_backward = backward_[index] & BIT(i);
     81         if (marked_forward && marked_backward) {
     82           PrintF("X");
     83         } else if (marked_forward) {
     84           PrintF("/");
     85         } else if (marked_backward) {
     86           PrintF("\\");
     87         } else {
     88           PrintF(" ");
     89         }
     90       }
     91       PrintF(" #%d:%s\n", ni.node->id(), ni.node->op()->mnemonic());
     92     }
     93 
     94     int i = 0;
     95     for (LoopInfo& li : loops_) {
     96       PrintF("Loop %d headed at #%d\n", i, li.header->id());
     97       i++;
     98     }
     99 
    100     for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
    101       PrintLoop(loop);
    102     }
    103   }
    104 
    105  private:
    106   Zone* zone_;
    107   Node* end_;
    108   NodeDeque queue_;
    109   NodeMarker<bool> queued_;
    110   ZoneVector<NodeInfo> info_;
    111   ZoneVector<LoopInfo> loops_;
    112   ZoneVector<int> loop_num_;
    113   LoopTree* loop_tree_;
    114   int loops_found_;
    115   int width_;
    116   uint32_t* backward_;
    117   uint32_t* forward_;
    118 
    119   int num_nodes() {
    120     return static_cast<int>(loop_tree_->node_to_loop_num_.size());
    121   }
    122 
    123   // Tb = Tb | (Fb - loop_filter)
    124   bool PropagateBackwardMarks(Node* from, Node* to, int loop_filter) {
    125     if (from == to) return false;
    126     uint32_t* fp = &backward_[from->id() * width_];
    127     uint32_t* tp = &backward_[to->id() * width_];
    128     bool change = false;
    129     for (int i = 0; i < width_; i++) {
    130       uint32_t mask = i == INDEX(loop_filter) ? ~BIT(loop_filter) : 0xFFFFFFFF;
    131       uint32_t prev = tp[i];
    132       uint32_t next = prev | (fp[i] & mask);
    133       tp[i] = next;
    134       if (!change && (prev != next)) change = true;
    135     }
    136     return change;
    137   }
    138 
    139   // Tb = Tb | B
    140   bool SetBackwardMark(Node* to, int loop_num) {
    141     uint32_t* tp = &backward_[to->id() * width_ + INDEX(loop_num)];
    142     uint32_t prev = tp[0];
    143     uint32_t next = prev | BIT(loop_num);
    144     tp[0] = next;
    145     return next != prev;
    146   }
    147 
    148   // Tf = Tf | B
    149   bool SetForwardMark(Node* to, int loop_num) {
    150     uint32_t* tp = &forward_[to->id() * width_ + INDEX(loop_num)];
    151     uint32_t prev = tp[0];
    152     uint32_t next = prev | BIT(loop_num);
    153     tp[0] = next;
    154     return next != prev;
    155   }
    156 
    157   // Tf = Tf | (Ff & Tb)
    158   bool PropagateForwardMarks(Node* from, Node* to) {
    159     if (from == to) return false;
    160     bool change = false;
    161     int findex = from->id() * width_;
    162     int tindex = to->id() * width_;
    163     for (int i = 0; i < width_; i++) {
    164       uint32_t marks = backward_[tindex + i] & forward_[findex + i];
    165       uint32_t prev = forward_[tindex + i];
    166       uint32_t next = prev | marks;
    167       forward_[tindex + i] = next;
    168       if (!change && (prev != next)) change = true;
    169     }
    170     return change;
    171   }
    172 
    173   bool IsInLoop(Node* node, int loop_num) {
    174     int offset = node->id() * width_ + INDEX(loop_num);
    175     return backward_[offset] & forward_[offset] & BIT(loop_num);
    176   }
    177 
    178   // Propagate marks backward from loop headers.
    179   void PropagateBackward() {
    180     ResizeBackwardMarks();
    181     SetBackwardMark(end_, 0);
    182     Queue(end_);
    183 
    184     while (!queue_.empty()) {
    185       Node* node = queue_.front();
    186       info(node);
    187       queue_.pop_front();
    188       queued_.Set(node, false);
    189 
    190       int loop_num = -1;
    191       // Setup loop headers first.
    192       if (node->opcode() == IrOpcode::kLoop) {
    193         // found the loop node first.
    194         loop_num = CreateLoopInfo(node);
    195       } else if (NodeProperties::IsPhi(node)) {
    196         // found a phi first.
    197         Node* merge = node->InputAt(node->InputCount() - 1);
    198         if (merge->opcode() == IrOpcode::kLoop) {
    199           loop_num = CreateLoopInfo(merge);
    200         }
    201       }
    202 
    203       // Propagate marks backwards from this node.
    204       for (int i = 0; i < node->InputCount(); i++) {
    205         Node* input = node->InputAt(i);
    206         if (loop_num > 0 && i != kAssumedLoopEntryIndex) {
    207           // Only propagate the loop mark on backedges.
    208           if (SetBackwardMark(input, loop_num)) Queue(input);
    209         } else {
    210           // Entry or normal edge. Propagate all marks except loop_num.
    211           if (PropagateBackwardMarks(node, input, loop_num)) Queue(input);
    212         }
    213       }
    214     }
    215   }
    216 
    217   // Make a new loop if necessary for the given node.
    218   int CreateLoopInfo(Node* node) {
    219     int loop_num = LoopNum(node);
    220     if (loop_num > 0) return loop_num;
    221 
    222     loop_num = ++loops_found_;
    223     if (INDEX(loop_num) >= width_) ResizeBackwardMarks();
    224 
    225     // Create a new loop.
    226     loops_.push_back({node, nullptr, nullptr, nullptr});
    227     loop_tree_->NewLoop();
    228     SetBackwardMark(node, loop_num);
    229     loop_tree_->node_to_loop_num_[node->id()] = loop_num;
    230 
    231     // Setup loop mark for phis attached to loop header.
    232     for (Node* use : node->uses()) {
    233       if (NodeProperties::IsPhi(use)) {
    234         info(use);  // create the NodeInfo
    235         SetBackwardMark(use, loop_num);
    236         loop_tree_->node_to_loop_num_[use->id()] = loop_num;
    237       }
    238     }
    239 
    240     return loop_num;
    241   }
    242 
    243   void ResizeBackwardMarks() {
    244     int new_width = width_ + 1;
    245     int max = num_nodes();
    246     uint32_t* new_backward = zone_->NewArray<uint32_t>(new_width * max);
    247     memset(new_backward, 0, new_width * max * sizeof(uint32_t));
    248     if (width_ > 0) {  // copy old matrix data.
    249       for (int i = 0; i < max; i++) {
    250         uint32_t* np = &new_backward[i * new_width];
    251         uint32_t* op = &backward_[i * width_];
    252         for (int j = 0; j < width_; j++) np[j] = op[j];
    253       }
    254     }
    255     width_ = new_width;
    256     backward_ = new_backward;
    257   }
    258 
    259   void ResizeForwardMarks() {
    260     int max = num_nodes();
    261     forward_ = zone_->NewArray<uint32_t>(width_ * max);
    262     memset(forward_, 0, width_ * max * sizeof(uint32_t));
    263   }
    264 
    265   // Propagate marks forward from loops.
    266   void PropagateForward() {
    267     ResizeForwardMarks();
    268     for (LoopInfo& li : loops_) {
    269       SetForwardMark(li.header, LoopNum(li.header));
    270       Queue(li.header);
    271     }
    272     // Propagate forward on paths that were backward reachable from backedges.
    273     while (!queue_.empty()) {
    274       Node* node = queue_.front();
    275       queue_.pop_front();
    276       queued_.Set(node, false);
    277       for (Edge edge : node->use_edges()) {
    278         Node* use = edge.from();
    279         if (!IsBackedge(use, edge)) {
    280           if (PropagateForwardMarks(node, use)) Queue(use);
    281         }
    282       }
    283     }
    284   }
    285 
    286   bool IsBackedge(Node* use, Edge& edge) {
    287     if (LoopNum(use) <= 0) return false;
    288     if (edge.index() == kAssumedLoopEntryIndex) return false;
    289     if (NodeProperties::IsPhi(use)) {
    290       return !NodeProperties::IsControlEdge(edge);
    291     }
    292     return true;
    293   }
    294 
    295   int LoopNum(Node* node) { return loop_tree_->node_to_loop_num_[node->id()]; }
    296 
    297   NodeInfo& info(Node* node) {
    298     NodeInfo& i = info_[node->id()];
    299     if (i.node == nullptr) i.node = node;
    300     return i;
    301   }
    302 
    303   void Queue(Node* node) {
    304     if (!queued_.Get(node)) {
    305       queue_.push_back(node);
    306       queued_.Set(node, true);
    307     }
    308   }
    309 
    310   void FinishLoopTree() {
    311     DCHECK(loops_found_ == static_cast<int>(loops_.size()));
    312     DCHECK(loops_found_ == static_cast<int>(loop_tree_->all_loops_.size()));
    313 
    314     // Degenerate cases.
    315     if (loops_found_ == 0) return;
    316     if (loops_found_ == 1) return FinishSingleLoop();
    317 
    318     for (int i = 1; i <= loops_found_; i++) ConnectLoopTree(i);
    319 
    320     size_t count = 0;
    321     // Place the node into the innermost nested loop of which it is a member.
    322     for (NodeInfo& ni : info_) {
    323       if (ni.node == nullptr) continue;
    324 
    325       LoopInfo* innermost = nullptr;
    326       int innermost_index = 0;
    327       int pos = ni.node->id() * width_;
    328       // Search the marks word by word.
    329       for (int i = 0; i < width_; i++) {
    330         uint32_t marks = backward_[pos + i] & forward_[pos + i];
    331         for (int j = 0; j < 32; j++) {
    332           if (marks & (1u << j)) {
    333             int loop_num = i * 32 + j;
    334             if (loop_num == 0) continue;
    335             LoopInfo* loop = &loops_[loop_num - 1];
    336             if (innermost == nullptr ||
    337                 loop->loop->depth_ > innermost->loop->depth_) {
    338               innermost = loop;
    339               innermost_index = loop_num;
    340             }
    341           }
    342         }
    343       }
    344       if (innermost == nullptr) continue;
    345       if (LoopNum(ni.node) == innermost_index) {
    346         ni.next = innermost->header_list;
    347         innermost->header_list = &ni;
    348       } else {
    349         ni.next = innermost->body_list;
    350         innermost->body_list = &ni;
    351       }
    352       count++;
    353     }
    354 
    355     // Serialize the node lists for loops into the loop tree.
    356     loop_tree_->loop_nodes_.reserve(count);
    357     for (LoopTree::Loop* loop : loop_tree_->outer_loops_) {
    358       SerializeLoop(loop);
    359     }
    360   }
    361 
    362   // Handle the simpler case of a single loop (no checks for nesting necessary).
    363   void FinishSingleLoop() {
    364     // Place nodes into the loop header and body.
    365     LoopInfo* li = &loops_[0];
    366     li->loop = &loop_tree_->all_loops_[0];
    367     loop_tree_->SetParent(nullptr, li->loop);
    368     size_t count = 0;
    369     for (NodeInfo& ni : info_) {
    370       if (ni.node == nullptr || !IsInLoop(ni.node, 1)) continue;
    371       if (LoopNum(ni.node) == 1) {
    372         ni.next = li->header_list;
    373         li->header_list = &ni;
    374       } else {
    375         ni.next = li->body_list;
    376         li->body_list = &ni;
    377       }
    378       count++;
    379     }
    380 
    381     // Serialize the node lists for the loop into the loop tree.
    382     loop_tree_->loop_nodes_.reserve(count);
    383     SerializeLoop(li->loop);
    384   }
    385 
    386   // Recursively serialize the list of header nodes and body nodes
    387   // so that nested loops occupy nested intervals.
    388   void SerializeLoop(LoopTree::Loop* loop) {
    389     int loop_num = loop_tree_->LoopNum(loop);
    390     LoopInfo& li = loops_[loop_num - 1];
    391 
    392     // Serialize the header.
    393     loop->header_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
    394     for (NodeInfo* ni = li.header_list; ni != nullptr; ni = ni->next) {
    395       loop_tree_->loop_nodes_.push_back(ni->node);
    396       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
    397     }
    398 
    399     // Serialize the body.
    400     loop->body_start_ = static_cast<int>(loop_tree_->loop_nodes_.size());
    401     for (NodeInfo* ni = li.body_list; ni != nullptr; ni = ni->next) {
    402       loop_tree_->loop_nodes_.push_back(ni->node);
    403       loop_tree_->node_to_loop_num_[ni->node->id()] = loop_num;
    404     }
    405 
    406     // Serialize nested loops.
    407     for (LoopTree::Loop* child : loop->children_) SerializeLoop(child);
    408 
    409     loop->body_end_ = static_cast<int>(loop_tree_->loop_nodes_.size());
    410   }
    411 
    412   // Connect the LoopTree loops to their parents recursively.
    413   LoopTree::Loop* ConnectLoopTree(int loop_num) {
    414     LoopInfo& li = loops_[loop_num - 1];
    415     if (li.loop != nullptr) return li.loop;
    416 
    417     NodeInfo& ni = info(li.header);
    418     LoopTree::Loop* parent = nullptr;
    419     for (int i = 1; i <= loops_found_; i++) {
    420       if (i == loop_num) continue;
    421       if (IsInLoop(ni.node, i)) {
    422         // recursively create potential parent loops first.
    423         LoopTree::Loop* upper = ConnectLoopTree(i);
    424         if (parent == nullptr || upper->depth_ > parent->depth_) {
    425           parent = upper;
    426         }
    427       }
    428     }
    429     li.loop = &loop_tree_->all_loops_[loop_num - 1];
    430     loop_tree_->SetParent(parent, li.loop);
    431     return li.loop;
    432   }
    433 
    434   void PrintLoop(LoopTree::Loop* loop) {
    435     for (int i = 0; i < loop->depth_; i++) PrintF("  ");
    436     PrintF("Loop depth = %d ", loop->depth_);
    437     int i = loop->header_start_;
    438     while (i < loop->body_start_) {
    439       PrintF(" H#%d", loop_tree_->loop_nodes_[i++]->id());
    440     }
    441     while (i < loop->body_end_) {
    442       PrintF(" B#%d", loop_tree_->loop_nodes_[i++]->id());
    443     }
    444     PrintF("\n");
    445     for (LoopTree::Loop* child : loop->children_) PrintLoop(child);
    446   }
    447 };
    448 
    449 
    450 LoopTree* LoopFinder::BuildLoopTree(Graph* graph, Zone* zone) {
    451   LoopTree* loop_tree =
    452       new (graph->zone()) LoopTree(graph->NodeCount(), graph->zone());
    453   LoopFinderImpl finder(graph, loop_tree, zone);
    454   finder.Run();
    455   if (FLAG_trace_turbo_graph) {
    456     finder.Print();
    457   }
    458   return loop_tree;
    459 }
    460 
    461 
    462 Node* LoopTree::HeaderNode(Loop* loop) {
    463   Node* first = *HeaderNodes(loop).begin();
    464   if (first->opcode() == IrOpcode::kLoop) return first;
    465   DCHECK(IrOpcode::IsPhiOpcode(first->opcode()));
    466   Node* header = NodeProperties::GetControlInput(first);
    467   DCHECK_EQ(IrOpcode::kLoop, header->opcode());
    468   return header;
    469 }
    470 
    471 }  // namespace compiler
    472 }  // namespace internal
    473 }  // namespace v8
    474