Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/LoopAnalysisManager.cpp
Line
Count
Source
1
//===- LoopAnalysisManager.cpp - Loop analysis management -----------------===//
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/Analysis/LoopAnalysisManager.h"
10
#include "llvm/Analysis/BasicAliasAnalysis.h"
11
#include "llvm/Analysis/GlobalsModRef.h"
12
#include "llvm/Analysis/LoopInfo.h"
13
#include "llvm/Analysis/MemorySSA.h"
14
#include "llvm/Analysis/ScalarEvolution.h"
15
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
16
#include "llvm/IR/Dominators.h"
17
18
using namespace llvm;
19
20
namespace llvm {
21
// Explicit template instantiations and specialization definitions for core
22
// template typedefs.
23
template class AllAnalysesOn<Loop>;
24
template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
25
template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
26
template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
27
                                         LoopStandardAnalysisResults &>;
28
29
bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
30
    Function &F, const PreservedAnalyses &PA,
31
853
    FunctionAnalysisManager::Invalidator &Inv) {
32
853
  // First compute the sequence of IR units covered by this proxy. We will want
33
853
  // to visit this in postorder, but because this is a tree structure we can do
34
853
  // this by building a preorder sequence and walking it backwards. We also
35
853
  // want siblings in forward program order to match the LoopPassManager so we
36
853
  // get the preorder with siblings reversed.
37
853
  SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder();
38
853
39
853
  // If this proxy or the loop info is going to be invalidated, we also need
40
853
  // to clear all the keys coming from that analysis. We also completely blow
41
853
  // away the loop analyses if any of the standard analyses provided by the
42
853
  // loop pass manager go away so that loop analyses can freely use these
43
853
  // without worrying about declaring dependencies on them etc.
44
853
  // FIXME: It isn't clear if this is the right tradeoff. We could instead make
45
853
  // loop analyses declare any dependencies on these and use the more general
46
853
  // invalidation logic below to act on that.
47
853
  auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>();
48
853
  bool invalidateMemorySSAAnalysis = false;
49
853
  if (EnableMSSALoopDependency)
50
86
    invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
51
853
  if (!(PAC.preserved() || 
PAC.preservedSet<AllAnalysesOn<Function>>()136
) ||
52
853
      
Inv.invalidate<AAManager>(F, PA)734
||
53
853
      
Inv.invalidate<AssumptionAnalysis>(F, PA)721
||
54
853
      
Inv.invalidate<DominatorTreeAnalysis>(F, PA)721
||
55
853
      
Inv.invalidate<LoopAnalysis>(F, PA)720
||
56
853
      
Inv.invalidate<ScalarEvolutionAnalysis>(F, PA)713
||
57
853
      
invalidateMemorySSAAnalysis701
) {
58
152
    // Note that the LoopInfo may be stale at this point, however the loop
59
152
    // objects themselves remain the only viable keys that could be in the
60
152
    // analysis manager's cache. So we just walk the keys and forcibly clear
61
152
    // those results. Note that the order doesn't matter here as this will just
62
152
    // directly destroy the results without calling methods on them.
63
165
    for (Loop *L : PreOrderLoops) {
64
165
      // NB! `L` may not be in a good enough state to run Loop::getName.
65
165
      InnerAM->clear(*L, "<possibly invalidated loop>");
66
165
    }
67
152
68
152
    // We also need to null out the inner AM so that when the object gets
69
152
    // destroyed as invalid we don't try to clear the inner AM again. At that
70
152
    // point we won't be able to reliably walk the loops for this function and
71
152
    // only clear results associated with those loops the way we do here.
72
152
    // FIXME: Making InnerAM null at this point isn't very nice. Most analyses
73
152
    // try to remain valid during invalidation. Maybe we should add an
74
152
    // `IsClean` flag?
75
152
    InnerAM = nullptr;
76
152
77
152
    // Now return true to indicate this *is* invalid and a fresh proxy result
78
152
    // needs to be built. This is especially important given the null InnerAM.
79
152
    return true;
80
152
  }
81
701
82
701
  // Directly check if the relevant set is preserved so we can short circuit
83
701
  // invalidating loops.
84
701
  bool AreLoopAnalysesPreserved =
85
701
      PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>();
86
701
87
701
  // Since we have a valid LoopInfo we can actually leave the cached results in
88
701
  // the analysis manager associated with the Loop keys, but we need to
89
701
  // propagate any necessary invalidation logic into them. We'd like to
90
701
  // invalidate things in roughly the same order as they were put into the
91
701
  // cache and so we walk the preorder list in reverse to form a valid
92
701
  // postorder.
93
1.54k
  for (Loop *L : reverse(PreOrderLoops)) {
94
1.54k
    Optional<PreservedAnalyses> InnerPA;
95
1.54k
96
1.54k
    // Check to see whether the preserved set needs to be adjusted based on
97
1.54k
    // function-level analysis invalidation triggering deferred invalidation
98
1.54k
    // for this loop.
99
1.54k
    if (auto *OuterProxy =
100
640
            InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))
101
640
      for (const auto &OuterInvalidationPair :
102
640
           OuterProxy->getOuterInvalidations()) {
103
3
        AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
104
3
        const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
105
3
        if (Inv.invalidate(OuterAnalysisID, F, PA)) {
106
3
          if (!InnerPA)
107
3
            InnerPA = PA;
108
3
          for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
109
3
            InnerPA->abandon(InnerAnalysisID);
110
3
        }
111
3
      }
112
1.54k
113
1.54k
    // Check if we needed a custom PA set. If so we'll need to run the inner
114
1.54k
    // invalidation.
115
1.54k
    if (InnerPA) {
116
3
      InnerAM->invalidate(*L, *InnerPA);
117
3
      continue;
118
3
    }
119
1.54k
120
1.54k
    // Otherwise we only need to do invalidation if the original PA set didn't
121
1.54k
    // preserve all Loop analyses.
122
1.54k
    if (!AreLoopAnalysesPreserved)
123
22
      InnerAM->invalidate(*L, PA);
124
1.54k
  }
125
701
126
701
  // Return false to indicate that this result is still a valid proxy.
127
701
  return false;
128
701
}
129
130
template <>
131
LoopAnalysisManagerFunctionProxy::Result
132
LoopAnalysisManagerFunctionProxy::run(Function &F,
133
1.94k
                                      FunctionAnalysisManager &AM) {
134
1.94k
  return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
135
1.94k
}
136
}
137
138
1.45k
PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
139
1.45k
  PreservedAnalyses PA;
140
1.45k
  PA.preserve<DominatorTreeAnalysis>();
141
1.45k
  PA.preserve<LoopAnalysis>();
142
1.45k
  PA.preserve<LoopAnalysisManagerFunctionProxy>();
143
1.45k
  PA.preserve<ScalarEvolutionAnalysis>();
144
1.45k
  // FIXME: What we really want to do here is preserve an AA category, but that
145
1.45k
  // concept doesn't exist yet.
146
1.45k
  PA.preserve<AAManager>();
147
1.45k
  PA.preserve<BasicAA>();
148
1.45k
  PA.preserve<GlobalsAA>();
149
1.45k
  PA.preserve<SCEVAA>();
150
1.45k
  return PA;
151
1.45k
}