76 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/CodeGen/LoopTraversal.h"10#include "llvm/ADT/PostOrderIterator.h"11#include "llvm/CodeGen/MachineFunction.h"12 13using namespace llvm;14 15bool 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 24LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {25 // Initialize the MMBInfos26 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 while34 // 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 them64 // 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 this69 // loop.70 }71 72 MBBInfos.clear();73 74 return MBBTraversalOrder;75}76