LCOV - code coverage report
Current view: top level - lib/CodeGen - LoopTraversal.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 30 30 100.0 %
Date: 2018-07-13 00:08:38 Functions: 2 2 100.0 %
Legend: Lines: hit not hit

          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     2065334 : bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
      17     2065334 :   unsigned MBBNumber = MBB->getNumber();
      18             :   assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
      19     5428160 :   return MBBInfos[MBBNumber].PrimaryCompleted &&
      20     1297492 :          MBBInfos[MBBNumber].IncomingCompleted ==
      21     4424226 :              MBBInfos[MBBNumber].PrimaryIncoming &&
      22     3126734 :          MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size();
      23             : }
      24             : 
      25      207015 : LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
      26             :   // Initialize the MMBInfos
      27      414030 :   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      681506 :   for (MachineBasicBlock *MBB : RPOT) {
      34             :     // N.B: IncomingProcessed and IncomingCompleted were already updated while
      35             :     // processing this block's predecessors.
      36      474491 :     unsigned MBBNumber = MBB->getNumber();
      37             :     assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
      38      948982 :     MBBInfos[MBBNumber].PrimaryCompleted = true;
      39      474491 :     MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
      40             :     bool Primary = true;
      41      474491 :     Workqueue.push_back(MBB);
      42     1602961 :     while (!Workqueue.empty()) {
      43      564235 :       MachineBasicBlock *ActiveMBB = &*Workqueue.back();
      44             :       Workqueue.pop_back();
      45      564235 :       bool Done = isBlockDone(ActiveMBB);
      46     1128470 :       MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
      47     1081875 :       for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
      48      517640 :         unsigned SuccNumber = Succ->getNumber();
      49             :         assert(SuccNumber < MBBInfos.size() &&
      50             :                "Unexpected basic block number.");
      51      517640 :         if (!isBlockDone(Succ)) {
      52      508968 :           if (Primary)
      53      765842 :             MBBInfos[SuccNumber].IncomingProcessed++;
      54      508968 :           if (Done)
      55      748494 :             MBBInfos[SuccNumber].IncomingCompleted++;
      56      508968 :           if (isBlockDone(Succ))
      57       89744 :             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      681506 :   for (MachineBasicBlock *MBB : RPOT) {
      68      474491 :     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      207015 :   return MBBTraversalOrder;
      77             : }

Generated by: LCOV version 1.13