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