lib/CodeGen/LoopTraversal.cpp

   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
  16 bool 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
  25 LoopTraversal::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 }