Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/LoopTraversal.cpp
Line
Count
Source
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
4.43M
bool LoopTraversal::isBlockDone(MachineBasicBlock *MBB) {
16
4.43M
  unsigned MBBNumber = MBB->getNumber();
17
4.43M
  assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
18
4.43M
  return MBBInfos[MBBNumber].PrimaryCompleted &&
19
4.43M
         MBBInfos[MBBNumber].IncomingCompleted ==
20
2.42M
             MBBInfos[MBBNumber].PrimaryIncoming &&
21
4.43M
         
MBBInfos[MBBNumber].IncomingProcessed == MBB->pred_size()2.10M
;
22
4.43M
}
23
24
288k
LoopTraversal::TraversalOrder LoopTraversal::traverse(MachineFunction &MF) {
25
288k
  // Initialize the MMBInfos
26
288k
  MBBInfos.assign(MF.getNumBlockIDs(), MBBInfo());
27
288k
28
288k
  MachineBasicBlock *Entry = &*MF.begin();
29
288k
  ReversePostOrderTraversal<MachineBasicBlock *> RPOT(Entry);
30
288k
  SmallVector<MachineBasicBlock *, 4> Workqueue;
31
288k
  SmallVector<TraversedMBBInfo, 4> MBBTraversalOrder;
32
936k
  for (MachineBasicBlock *MBB : RPOT) {
33
936k
    // N.B: IncomingProcessed and IncomingCompleted were already updated while
34
936k
    // processing this block's predecessors.
35
936k
    unsigned MBBNumber = MBB->getNumber();
36
936k
    assert(MBBNumber < MBBInfos.size() && "Unexpected basic block number.");
37
936k
    MBBInfos[MBBNumber].PrimaryCompleted = true;
38
936k
    MBBInfos[MBBNumber].PrimaryIncoming = MBBInfos[MBBNumber].IncomingProcessed;
39
936k
    bool Primary = true;
40
936k
    Workqueue.push_back(MBB);
41
2.00M
    while (!Workqueue.empty()) {
42
1.06M
      MachineBasicBlock *ActiveMBB = &*Workqueue.back();
43
1.06M
      Workqueue.pop_back();
44
1.06M
      bool Done = isBlockDone(ActiveMBB);
45
1.06M
      MBBTraversalOrder.push_back(TraversedMBBInfo(ActiveMBB, Primary, Done));
46
1.23M
      for (MachineBasicBlock *Succ : ActiveMBB->successors()) {
47
1.23M
        unsigned SuccNumber = Succ->getNumber();
48
1.23M
        assert(SuccNumber < MBBInfos.size() &&
49
1.23M
               "Unexpected basic block number.");
50
1.23M
        if (!isBlockDone(Succ)) {
51
1.19M
          if (Primary)
52
1.00M
            MBBInfos[SuccNumber].IncomingProcessed++;
53
1.19M
          if (Done)
54
968k
            MBBInfos[SuccNumber].IncomingCompleted++;
55
1.19M
          if (isBlockDone(Succ))
56
131k
            Workqueue.push_back(Succ);
57
1.19M
        }
58
1.23M
      }
59
1.06M
      Primary = false;
60
1.06M
    }
61
936k
  }
62
288k
63
288k
  // We need to go through again and finalize any blocks that are not done yet.
64
288k
  // This is possible if blocks have dead predecessors, so we didn't visit them
65
288k
  // above.
66
936k
  for (MachineBasicBlock *MBB : RPOT) {
67
936k
    if (!isBlockDone(MBB))
68
2
      MBBTraversalOrder.push_back(TraversedMBBInfo(MBB, false, true));
69
936k
    // Don't update successors here. We'll get to them anyway through this
70
936k
    // loop.
71
936k
  }
72
288k
73
288k
  MBBInfos.clear();
74
288k
75
288k
  return MBBTraversalOrder;
76
288k
}