Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/MachineLoopInfo.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
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
// This file defines the MachineLoopInfo class that is used to identify natural
10
// loops and determine the loop depth of various nodes of the CFG.  Note that
11
// the loops identified may actually be several natural loops that share the
12
// same header node... not just a single natural loop.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/CodeGen/MachineLoopInfo.h"
17
#include "llvm/Analysis/LoopInfoImpl.h"
18
#include "llvm/CodeGen/MachineDominators.h"
19
#include "llvm/CodeGen/Passes.h"
20
#include "llvm/Config/llvm-config.h"
21
#include "llvm/Support/Debug.h"
22
#include "llvm/Support/raw_ostream.h"
23
using namespace llvm;
24
25
// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
26
template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
27
template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
28
29
char MachineLoopInfo::ID = 0;
30
102k
INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
31
102k
                "Machine Natural Loop Construction", true, true)
32
102k
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
33
102k
INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
34
                "Machine Natural Loop Construction", true, true)
35
36
char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
37
38
2.12M
bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
39
2.12M
  releaseMemory();
40
2.12M
  LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
41
2.12M
  return false;
42
2.12M
}
43
44
157k
void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
45
157k
  AU.setPreservesAll();
46
157k
  AU.addRequired<MachineDominatorTree>();
47
157k
  MachineFunctionPass::getAnalysisUsage(AU);
48
157k
}
49
50
875
MachineBasicBlock *MachineLoop::getTopBlock() {
51
875
  MachineBasicBlock *TopMBB = getHeader();
52
875
  MachineFunction::iterator Begin = TopMBB->getParent()->begin();
53
875
  if (TopMBB->getIterator() != Begin) {
54
875
    MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
55
886
    while (contains(PriorMBB)) {
56
11
      TopMBB = PriorMBB;
57
11
      if (TopMBB->getIterator() == Begin)
58
0
        break;
59
11
      PriorMBB = &*std::prev(TopMBB->getIterator());
60
11
    }
61
875
  }
62
875
  return TopMBB;
63
875
}
64
65
335
MachineBasicBlock *MachineLoop::getBottomBlock() {
66
335
  MachineBasicBlock *BotMBB = getHeader();
67
335
  MachineFunction::iterator End = BotMBB->getParent()->end();
68
335
  if (BotMBB->getIterator() != std::prev(End)) {
69
303
    MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
70
303
    while (contains(NextMBB)) {
71
0
      BotMBB = NextMBB;
72
0
      if (BotMBB == &*std::next(BotMBB->getIterator()))
73
0
        break;
74
0
      NextMBB = &*std::next(BotMBB->getIterator());
75
0
    }
76
303
  }
77
335
  return BotMBB;
78
335
}
79
80
1.49k
MachineBasicBlock *MachineLoop::findLoopControlBlock() {
81
1.49k
  if (MachineBasicBlock *Latch = getLoopLatch()) {
82
1.48k
    if (isLoopExiting(Latch))
83
1.45k
      return Latch;
84
35
    else
85
35
      return getExitingBlock();
86
1
  }
87
1
  return nullptr;
88
1
}
89
90
25
DebugLoc MachineLoop::getStartLoc() const {
91
25
  // Try the pre-header first.
92
25
  if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
93
25
    if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
94
25
      if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
95
25
        return DL;
96
0
97
0
  // If we have no pre-header or there are no instructions with debug
98
0
  // info in it, try the header.
99
0
  if (MachineBasicBlock *HeadMBB = getHeader())
100
0
    if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
101
0
      return HeadBB->getTerminator()->getDebugLoc();
102
0
103
0
  return DebugLoc();
104
0
}
105
106
MachineBasicBlock *
107
MachineLoopInfo::findLoopPreheader(MachineLoop *L,
108
893
                                   bool SpeculativePreheader) const {
109
893
  if (MachineBasicBlock *PB = L->getLoopPreheader())
110
867
    return PB;
111
26
112
26
  if (!SpeculativePreheader)
113
22
    return nullptr;
114
4
115
4
  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
116
4
  if (HB->pred_size() != 2 || HB->hasAddressTaken())
117
0
    return nullptr;
118
4
  // Find the predecessor of the header that is not the latch block.
119
4
  MachineBasicBlock *Preheader = nullptr;
120
8
  for (MachineBasicBlock *P : HB->predecessors()) {
121
8
    if (P == LB)
122
4
      continue;
123
4
    // Sanity.
124
4
    if (Preheader)
125
0
      return nullptr;
126
4
    Preheader = P;
127
4
  }
128
4
129
4
  // Check if the preheader candidate is a successor of any other loop
130
4
  // headers. We want to avoid having two loop setups in the same block.
131
8
  
for (MachineBasicBlock *S : Preheader->successors())4
{
132
8
    if (S == HB)
133
4
      continue;
134
4
    MachineLoop *T = getLoopFor(S);
135
4
    if (T && 
T->getHeader() == S0
)
136
0
      return nullptr;
137
4
  }
138
4
  return Preheader;
139
4
}
140
141
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
142
LLVM_DUMP_METHOD void MachineLoop::dump() const {
143
  print(dbgs());
144
}
145
#endif