Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/ScalarEvolutionAliasAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ScalarEvolutionAliasAnalysis.cpp - SCEV-based Alias Analysis -------===//
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 ScalarEvolutionAliasAnalysis pass, which implements a
10
// simple alias analysis implemented in terms of ScalarEvolution queries.
11
//
12
// This differs from traditional loop dependence analysis in that it tests
13
// for dependencies within a single iteration of a loop, rather than
14
// dependencies between different iterations.
15
//
16
// ScalarEvolution has a more complete understanding of pointer arithmetic
17
// than BasicAliasAnalysis' collection of ad-hoc analyses.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
22
using namespace llvm;
23
24
AliasResult SCEVAAResult::alias(const MemoryLocation &LocA,
25
180
                                const MemoryLocation &LocB, AAQueryInfo &AAQI) {
26
180
  // If either of the memory references is empty, it doesn't matter what the
27
180
  // pointer values are. This allows the code below to ignore this special
28
180
  // case.
29
180
  if (LocA.Size.isZero() || LocB.Size.isZero())
30
0
    return NoAlias;
31
180
32
180
  // This is SCEVAAResult. Get the SCEVs!
33
180
  const SCEV *AS = SE.getSCEV(const_cast<Value *>(LocA.Ptr));
34
180
  const SCEV *BS = SE.getSCEV(const_cast<Value *>(LocB.Ptr));
35
180
36
180
  // If they evaluate to the same expression, it's a MustAlias.
37
180
  if (AS == BS)
38
88
    return MustAlias;
39
92
40
92
  // If something is known about the difference between the two addresses,
41
92
  // see if it's enough to prove a NoAlias.
42
92
  if (SE.getEffectiveSCEVType(AS->getType()) ==
43
92
      SE.getEffectiveSCEVType(BS->getType())) {
44
92
    unsigned BitWidth = SE.getTypeSizeInBits(AS->getType());
45
92
    APInt ASizeInt(BitWidth, LocA.Size.hasValue()
46
92
                                 ? 
LocA.Size.getValue()80
47
92
                                 : 
MemoryLocation::UnknownSize12
);
48
92
    APInt BSizeInt(BitWidth, LocB.Size.hasValue()
49
92
                                 ? 
LocB.Size.getValue()80
50
92
                                 : 
MemoryLocation::UnknownSize12
);
51
92
52
92
    // Compute the difference between the two pointers.
53
92
    const SCEV *BA = SE.getMinusSCEV(BS, AS);
54
92
55
92
    // Test whether the difference is known to be great enough that memory of
56
92
    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
57
92
    // are non-zero, which is special-cased above.
58
92
    if (ASizeInt.ule(SE.getUnsignedRange(BA).getUnsignedMin()) &&
59
92
        
(-BSizeInt).uge(SE.getUnsignedRange(BA).getUnsignedMax())58
)
60
26
      return NoAlias;
61
66
62
66
    // Folding the subtraction while preserving range information can be tricky
63
66
    // (because of INT_MIN, etc.); if the prior test failed, swap AS and BS
64
66
    // and try again to see if things fold better that way.
65
66
66
66
    // Compute the difference between the two pointers.
67
66
    const SCEV *AB = SE.getMinusSCEV(AS, BS);
68
66
69
66
    // Test whether the difference is known to be great enough that memory of
70
66
    // the given sizes don't overlap. This assumes that ASizeInt and BSizeInt
71
66
    // are non-zero, which is special-cased above.
72
66
    if (BSizeInt.ule(SE.getUnsignedRange(AB).getUnsignedMin()) &&
73
66
        
(-ASizeInt).uge(SE.getUnsignedRange(AB).getUnsignedMax())2
)
74
2
      return NoAlias;
75
64
  }
76
64
77
64
  // If ScalarEvolution can find an underlying object, form a new query.
78
64
  // The correctness of this depends on ScalarEvolution not recognizing
79
64
  // inttoptr and ptrtoint operators.
80
64
  Value *AO = GetBaseValue(AS);
81
64
  Value *BO = GetBaseValue(BS);
82
64
  if ((AO && AO != LocA.Ptr) || 
(8
BO8
&&
BO != LocB.Ptr8
))
83
56
    if (alias(MemoryLocation(AO ? AO : 
LocA.Ptr0
,
84
56
                             AO ? LocationSize::unknown() : 
LocA.Size0
,
85
56
                             AO ? AAMDNodes() : 
LocA.AATags0
),
86
56
              MemoryLocation(BO ? BO : 
LocB.Ptr0
,
87
56
                             BO ? LocationSize::unknown() : 
LocB.Size0
,
88
56
                             BO ? AAMDNodes() : 
LocB.AATags0
),
89
56
              AAQI) == NoAlias)
90
0
      return NoAlias;
91
64
92
64
  // Forward the query to the next analysis.
93
64
  return AAResultBase::alias(LocA, LocB, AAQI);
94
64
}
95
96
/// Given an expression, try to find a base value.
97
///
98
/// Returns null if none was found.
99
228
Value *SCEVAAResult::GetBaseValue(const SCEV *S) {
100
228
  if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
101
44
    // In an addrec, assume that the base will be in the start, rather
102
44
    // than the step.
103
44
    return GetBaseValue(AR->getStart());
104
184
  } else if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
105
56
    // If there's a pointer operand, it'll be sorted at the end of the list.
106
56
    const SCEV *Last = A->getOperand(A->getNumOperands() - 1);
107
56
    if (Last->getType()->isPointerTy())
108
56
      return GetBaseValue(Last);
109
128
  } else if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
110
128
    // This is a leaf node.
111
128
    return U->getValue();
112
128
  }
113
0
  // No Identified object found.
114
0
  return nullptr;
115
0
}
116
117
AnalysisKey SCEVAA::Key;
118
119
6
SCEVAAResult SCEVAA::run(Function &F, FunctionAnalysisManager &AM) {
120
6
  return SCEVAAResult(AM.getResult<ScalarEvolutionAnalysis>(F));
121
6
}
122
123
char SCEVAAWrapperPass::ID = 0;
124
102k
INITIALIZE_PASS_BEGIN(SCEVAAWrapperPass, "scev-aa",
125
102k
                      "ScalarEvolution-based Alias Analysis", false, true)
126
102k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
127
102k
INITIALIZE_PASS_END(SCEVAAWrapperPass, "scev-aa",
128
                    "ScalarEvolution-based Alias Analysis", false, true)
129
130
0
FunctionPass *llvm::createSCEVAAWrapperPass() {
131
0
  return new SCEVAAWrapperPass();
132
0
}
133
134
5
SCEVAAWrapperPass::SCEVAAWrapperPass() : FunctionPass(ID) {
135
5
  initializeSCEVAAWrapperPassPass(*PassRegistry::getPassRegistry());
136
5
}
137
138
10
bool SCEVAAWrapperPass::runOnFunction(Function &F) {
139
10
  Result.reset(
140
10
      new SCEVAAResult(getAnalysis<ScalarEvolutionWrapperPass>().getSE()));
141
10
  return false;
142
10
}
143
144
5
void SCEVAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
145
5
  AU.setPreservesAll();
146
5
  AU.addRequired<ScalarEvolutionWrapperPass>();
147
5
}