lib/CodeGen/LoopTraversal.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-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 }