Line data    Source code

       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     3259216 : bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
      17     3259216 :   unsigned MBBNumber = MBB->getNumber();
      18             :   assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
      19     3259216 :   return MBBInfos[MBBNumber].PrimaryCompleted &&
      20     1925100 :          MBBInfos[MBBNumber].IncomingCompleted ==
      21     3259216 :              MBBInfos[MBBNumber].PrimaryIncoming &&
      22     1556268 :          MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
      23             : }
      24             : 
      25      222428 : LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
      26             :   // Initialize the MMBInfos
      27      444856 :   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      915656 :   for (MachineBasicBlock *MBB : RPOT) {
      34             :     // N.B: IncomingProcessed and IncomingCompleted were already updated while
      35             :     // processing this block's predecessors.
      36      693228 :     unsigned MBBNumber = MBB->getNumber();
      37             :     assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
      38      693228 :     MBBInfos[MBBNumber].PrimaryCompleted = true;
      39      693228 :     MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
      40             :     bool Primary = true;
      41      693228 :     Workqueue.push_back(MBB);
      42     1527854 :     while (!Workqueue.empty()) {
      43      834626 :       MachineBasicBlock *ActiveMBB = &*Workqueue.back();
      44             :       Workqueue.pop_back();
      45      834626 :       bool Done = isBlockDone(ActiveMBB);
      46     1669252 :       MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
      47     1705869 :       for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
      48      871243 :         unsigned SuccNumber = Succ->getNumber();
      49             :         assert(SuccNumber < MBBInfos.size() &&
      50             :                "Unexpected basic block number.");
      51      871243 :         if (!isBlockDone(Succ)) {
      52      860119 :           if (Primary)
      53     1326332 :             MBBInfos[SuccNumber].IncomingProcessed++;
      54      860119 :           if (Done)
      55     1304080 :             MBBInfos[SuccNumber].IncomingCompleted++;
      56      860119 :           if (isBlockDone(Succ))
      57      141398 :             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      915656 :   for (MachineBasicBlock *MBB : RPOT) {
      68      693228 :     if (!isBlockDone(MBB))
      69           4 :       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      222428 :   return MBBTraversalOrder;
      77             : }