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