1//===- LoopTraversal.cpp - Optimal basic block traversal order --*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/CodeGen/LoopTraversal.h"
10#include "llvm/ADT/PostOrderIterator.h"
11#include "llvm/CodeGen/MachineFunction.h"
12
13using namespace llvm;
14
15bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
16  unsigned MBBNumber = MBB->getNumber();
17  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
18  return MBBInfos[MBBNumber].PrimaryCompleted &&
19         MBBInfos[MBBNumber].IncomingCompleted ==
20             MBBInfos[MBBNumber].PrimaryIncoming &&
21         MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
22}
23
24LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
25  // Initialize the MMBInfos
26  MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo());
27
28  MachineBasicBlock *Entry = &*MF.begin();
29  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(Entry);
30  SmallVector<MachineBasicBlock *, 4> Workqueue;
31  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
32  for (MachineBasicBlock *MBB : RPOT) {
33    // N.B: IncomingProcessed and IncomingCompleted were already updated while
34    // processing this block's predecessors.
35    unsigned MBBNumber = MBB->getNumber();
36    assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
37    MBBInfos[MBBNumber].PrimaryCompleted = true;
38    MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
39    bool Primary = true;
40    Workqueue.push_back(MBB);
41    while (!Workqueue.empty()) {
42      MachineBasicBlock *ActiveMBB = Workqueue.pop_back_val();
43      bool Done = isBlockDone(ActiveMBB);
44      MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
45      for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
46        unsigned SuccNumber = Succ->getNumber();
47        assert(SuccNumber < MBBInfos.size() &&
48               "Unexpected basic block number.");
49        if (!isBlockDone(Succ)) {
50          if (Primary)
51            MBBInfos[SuccNumber].IncomingProcessed++;
52          if (Done)
53            MBBInfos[SuccNumber].IncomingCompleted++;
54          if (isBlockDone(Succ))
55            Workqueue.push_back(Succ);
56        }
57      }
58      Primary = false;
59    }
60  }
61
62  // We need to go through again and finalize any blocks that are not done yet.
63  // This is possible if blocks have dead predecessors, so we didn't visit them
64  // above.
65  for (MachineBasicBlock *MBB : RPOT) {
66    if (!isBlockDone(MBB))
67      MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
68    // Don't update successors here. We'll get to them anyway through this
69    // loop.
70  }
71
72  MBBInfos.clear();
73
74  return MBBTraversalOrder;
75}
76