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