llvm/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.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 }