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 
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 
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.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