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