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 
13 using namespace llvm;
14 
isBlockDone(MachineBasicBlock * MBB)15 bool 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 
traverse(MachineFunction & MF)24 LoopTraversal::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.back();
43       Workqueue.pop_back();
44       bool Done = isBlockDone(ActiveMBB);
45       MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
46       for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
47         unsigned SuccNumber = Succ->getNumber();
48         assert(SuccNumber < MBBInfos.size() &&
49                "Unexpected basic block number.");
50         if (!isBlockDone(Succ)) {
51           if (Primary)
52             MBBInfos[SuccNumber].IncomingProcessed++;
53           if (Done)
54             MBBInfos[SuccNumber].IncomingCompleted++;
55           if (isBlockDone(Succ))
56             Workqueue.push_back(Succ);
57         }
58       }
59       Primary = false;
60     }
61   }
62 
63   // We need to go through again and finalize any blocks that are not done yet.
64   // This is possible if blocks have dead predecessors, so we didn't visit them
65   // above.
66   for (MachineBasicBlock *MBB : RPOT) {
67     if (!isBlockDone(MBB))
68       MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
69     // Don't update successors here. We'll get to them anyway through this
70     // loop.
71   }
72 
73   MBBInfos.clear();
74 
75   return MBBTraversalOrder;
76 }
77