Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Utils/GlobalStatus.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- GlobalStatus.cpp - Compute status info for globals -----------------==//
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/Transforms/Utils/GlobalStatus.h"
10
#include "llvm/ADT/SmallPtrSet.h"
11
#include "llvm/IR/BasicBlock.h"
12
#include "llvm/IR/CallSite.h"
13
#include "llvm/IR/Constant.h"
14
#include "llvm/IR/Constants.h"
15
#include "llvm/IR/GlobalValue.h"
16
#include "llvm/IR/GlobalVariable.h"
17
#include "llvm/IR/InstrTypes.h"
18
#include "llvm/IR/Instruction.h"
19
#include "llvm/IR/Instructions.h"
20
#include "llvm/IR/IntrinsicInst.h"
21
#include "llvm/IR/Use.h"
22
#include "llvm/IR/User.h"
23
#include "llvm/IR/Value.h"
24
#include "llvm/Support/AtomicOrdering.h"
25
#include "llvm/Support/Casting.h"
26
#include <algorithm>
27
#include <cassert>
28
29
using namespace llvm;
30
31
/// Return the stronger of the two ordering. If the two orderings are acquire
32
/// and release, then return AcquireRelease.
33
///
34
1.20M
static AtomicOrdering strongerOrdering(AtomicOrdering X, AtomicOrdering Y) {
35
1.20M
  if ((X == AtomicOrdering::Acquire && 
Y == AtomicOrdering::Release1
) ||
36
1.20M
      (Y == AtomicOrdering::Acquire && 
X == AtomicOrdering::Release3
))
37
0
    return AtomicOrdering::AcquireRelease;
38
1.20M
  return (AtomicOrdering)std::max((unsigned)X, (unsigned)Y);
39
1.20M
}
40
41
/// It is safe to destroy a constant iff it is only used by constants itself.
42
/// Note that constants cannot be cyclic, so this test is pretty easy to
43
/// implement recursively.
44
///
45
730k
bool llvm::isSafeToDestroyConstant(const Constant *C) {
46
730k
  if (isa<GlobalValue>(C))
47
328k
    return false;
48
401k
49
401k
  if (isa<ConstantData>(C))
50
86
    return false;
51
401k
52
401k
  for (const User *U : C->users())
53
401k
    if (const Constant *CU = dyn_cast<Constant>(U)) {
54
401k
      if (!isSafeToDestroyConstant(CU))
55
401k
        return false;
56
19
    } else
57
19
      return false;
58
401k
  
return true555
;
59
401k
}
60
61
static bool analyzeGlobalAux(const Value *V, GlobalStatus &GS,
62
5.55M
                             SmallPtrSetImpl<const Value *> &VisitedUsers) {
63
5.55M
  if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
64
1.73M
    if (GV->isExternallyInitialized())
65
467
      GS.StoredType = GlobalStatus::StoredOnce;
66
5.55M
67
11.0M
  for (const Use &U : V->uses()) {
68
11.0M
    const User *UR = U.getUser();
69
11.0M
    if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(UR)) {
70
1.68M
      GS.HasNonInstructionUser = true;
71
1.68M
72
1.68M
      // If the result of the constantexpr isn't pointer type, then we won't
73
1.68M
      // know to expect it in various places.  Just reject early.
74
1.68M
      if (!isa<PointerType>(CE->getType()))
75
58.0k
        return true;
76
1.63M
77
1.63M
      // FIXME: Do we need to add constexpr selects to VisitedUsers?
78
1.63M
      if (analyzeGlobalAux(CE, GS, VisitedUsers))
79
1.49M
        return true;
80
9.33M
    } else if (const Instruction *I = dyn_cast<Instruction>(UR)) {
81
9.01M
      if (!GS.HasMultipleAccessingFunctions) {
82
4.58M
        const Function *F = I->getParent()->getParent();
83
4.58M
        if (!GS.AccessingFunction)
84
2.83M
          GS.AccessingFunction = F;
85
1.75M
        else if (GS.AccessingFunction != F)
86
588k
          GS.HasMultipleAccessingFunctions = true;
87
4.58M
      }
88
9.01M
      if (const LoadInst *LI = dyn_cast<LoadInst>(I)) {
89
775k
        GS.IsLoaded = true;
90
775k
        // Don't hack on volatile loads.
91
775k
        if (LI->isVolatile())
92
1.53k
          return true;
93
774k
        GS.Ordering = strongerOrdering(GS.Ordering, LI->getOrdering());
94
8.23M
      } else if (const StoreInst *SI = dyn_cast<StoreInst>(I)) {
95
456k
        // Don't allow a store OF the address, only stores TO the address.
96
456k
        if (SI->getOperand(0) == V)
97
27.7k
          return true;
98
428k
99
428k
        // Don't hack on volatile stores.
100
428k
        if (SI->isVolatile())
101
638
          return true;
102
428k
103
428k
        GS.Ordering = strongerOrdering(GS.Ordering, SI->getOrdering());
104
428k
105
428k
        // If this is a direct store to the global (i.e., the global is a scalar
106
428k
        // value, not an aggregate), keep more specific information about
107
428k
        // stores.
108
428k
        if (GS.StoredType != GlobalStatus::Stored) {
109
259k
          if (const GlobalVariable *GV =
110
224k
                  dyn_cast<GlobalVariable>(SI->getOperand(1))) {
111
224k
            Value *StoredVal = SI->getOperand(0);
112
224k
113
224k
            if (Constant *C = dyn_cast<Constant>(StoredVal)) {
114
119k
              if (C->isThreadDependent()) {
115
16
                // The stored value changes between threads; don't track it.
116
16
                return true;
117
16
              }
118
224k
            }
119
224k
120
224k
            if (GV->hasInitializer() && 
StoredVal == GV->getInitializer()212k
) {
121
33.0k
              if (GS.StoredType < GlobalStatus::InitializerStored)
122
30.1k
                GS.StoredType = GlobalStatus::InitializerStored;
123
191k
            } else if (isa<LoadInst>(StoredVal) &&
124
191k
                       
cast<LoadInst>(StoredVal)->getOperand(0) == GV2.77k
) {
125
86
              if (GS.StoredType < GlobalStatus::InitializerStored)
126
36
                GS.StoredType = GlobalStatus::InitializerStored;
127
191k
            } else if (GS.StoredType < GlobalStatus::StoredOnce) {
128
121k
              GS.StoredType = GlobalStatus::StoredOnce;
129
121k
              GS.StoredOnceValue = StoredVal;
130
121k
            } else 
if (70.1k
GS.StoredType == GlobalStatus::StoredOnce70.1k
&&
131
70.1k
                       GS.StoredOnceValue == StoredVal) {
132
51.6k
              // noop.
133
51.6k
            } else {
134
18.4k
              GS.StoredType = GlobalStatus::Stored;
135
18.4k
            }
136
224k
          } else {
137
35.5k
            GS.StoredType = GlobalStatus::Stored;
138
35.5k
          }
139
259k
        }
140
7.77M
      } else if (isa<BitCastInst>(I) || 
isa<GetElementPtrInst>(I)7.75M
) {
141
146k
        // Skip over bitcasts and GEPs; we don't care about the type or offset
142
146k
        // of the pointer.
143
146k
        if (analyzeGlobalAux(I, GS, VisitedUsers))
144
2.71k
          return true;
145
7.63M
      } else if (isa<SelectInst>(I) || 
isa<PHINode>(I)7.62M
) {
146
26.8k
        // Look through selects and PHIs to find if the pointer is
147
26.8k
        // conditionally accessed. Make sure we only visit an instruction
148
26.8k
        // once; otherwise, we can get infinite recursion or exponential
149
26.8k
        // compile time.
150
26.8k
        if (VisitedUsers.insert(I).second)
151
21.9k
          if (analyzeGlobalAux(I, GS, VisitedUsers))
152
17.8k
            return true;
153
7.60M
      } else if (isa<CmpInst>(I)) {
154
1.05k
        GS.IsCompared = true;
155
7.60M
      } else if (const MemTransferInst *MTI = dyn_cast<MemTransferInst>(I)) {
156
14.9k
        if (MTI->isVolatile())
157
0
          return true;
158
14.9k
        if (MTI->getArgOperand(0) == V)
159
6.00k
          GS.StoredType = GlobalStatus::Stored;
160
14.9k
        if (MTI->getArgOperand(1) == V)
161
8.96k
          GS.IsLoaded = true;
162
7.58M
      } else if (const MemSetInst *MSI = dyn_cast<MemSetInst>(I)) {
163
928
        assert(MSI->getArgOperand(0) == V && "Memset only takes one pointer!");
164
928
        if (MSI->isVolatile())
165
0
          return true;
166
928
        GS.StoredType = GlobalStatus::Stored;
167
7.58M
      } else if (auto C = ImmutableCallSite(I)) {
168
7.54M
        if (!C.isCallee(&U))
169
1.24M
          return true;
170
6.30M
        GS.IsLoaded = true;
171
6.30M
      } else {
172
40.4k
        return true; // Any other non-load instruction might take address!
173
40.4k
      }
174
328k
    } else if (const Constant *C = dyn_cast<Constant>(UR)) {
175
328k
      GS.HasNonInstructionUser = true;
176
328k
      // We might have a dead and dangling constant hanging off of here.
177
328k
      if (!isSafeToDestroyConstant(C))
178
328k
        return true;
179
0
    } else {
180
0
      GS.HasNonInstructionUser = true;
181
0
      // Otherwise must be some other user.
182
0
      return true;
183
0
    }
184
11.0M
  }
185
5.55M
186
5.55M
  
return false2.33M
;
187
5.55M
}
188
189
3.75M
GlobalStatus::GlobalStatus() = default;
190
191
3.75M
bool GlobalStatus::analyzeGlobal(const Value *V, GlobalStatus &GS) {
192
3.75M
  SmallPtrSet<const Value *, 16> VisitedUsers;
193
3.75M
  return analyzeGlobalAux(V, GS, VisitedUsers);
194
3.75M
}