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(NumElts: MF.getNumBlockIDs(), Elt: 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(Elt: MBB);
41 while (!Workqueue.empty()) {
42 MachineBasicBlock *ActiveMBB = Workqueue.pop_back_val();
43 bool Done = isBlockDone(MBB: ActiveMBB);
44 MBBTraversalOrder.push_back(Elt: 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(MBB: Succ)) {
50 if (Primary)
51 MBBInfos[SuccNumber].IncomingProcessed++;
52 if (Done)
53 MBBInfos[SuccNumber].IncomingCompleted++;
54 if (isBlockDone(MBB: Succ))
55 Workqueue.push_back(Elt: 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(Elt: 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