Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/IPO/IPConstantPropagation.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===//
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 pass implements an _extremely_ simple interprocedural constant
10
// propagation pass.  It could certainly be improved in many different ways,
11
// like using a worklist.  This pass makes arguments dead, but does not remove
12
// them.  The existing dead argument elimination pass should be run after this
13
// to clean up the mess.
14
//
15
//===----------------------------------------------------------------------===//
16
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/ADT/Statistic.h"
19
#include "llvm/Analysis/ValueTracking.h"
20
#include "llvm/IR/CallSite.h"
21
#include "llvm/IR/Constants.h"
22
#include "llvm/IR/Instructions.h"
23
#include "llvm/IR/Module.h"
24
#include "llvm/Pass.h"
25
#include "llvm/Transforms/IPO.h"
26
using namespace llvm;
27
28
#define DEBUG_TYPE "ipconstprop"
29
30
STATISTIC(NumArgumentsProped, "Number of args turned into constants");
31
STATISTIC(NumReturnValProped, "Number of return values turned into constants");
32
33
namespace {
34
  /// IPCP - The interprocedural constant propagation pass
35
  ///
36
  struct IPCP : public ModulePass {
37
    static char ID; // Pass identification, replacement for typeid
38
17
    IPCP() : ModulePass(ID) {
39
17
      initializeIPCPPass(*PassRegistry::getPassRegistry());
40
17
    }
41
42
    bool runOnModule(Module &M) override;
43
  };
44
}
45
46
/// PropagateConstantsIntoArguments - Look at all uses of the specified
47
/// function.  If all uses are direct call sites, and all pass a particular
48
/// constant in for an argument, propagate that constant in as the argument.
49
///
50
50
static bool PropagateConstantsIntoArguments(Function &F) {
51
50
  if (F.arg_empty() || 
F.use_empty()48
)
return false2
; // No arguments? Early exit.
52
48
53
48
  // For each argument, keep track of its constant value and whether it is a
54
48
  // constant or not.  The bool is driven to true when found to be non-constant.
55
48
  SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants;
56
48
  ArgumentConstants.resize(F.arg_size());
57
48
58
48
  unsigned NumNonconstant = 0;
59
73
  for (Use &U : F.uses()) {
60
73
    User *UR = U.getUser();
61
73
    // Ignore blockaddress uses.
62
73
    if (isa<BlockAddress>(UR)) 
continue0
;
63
73
64
73
    // If no abstract call site was created we did not understand the use, bail.
65
73
    AbstractCallSite ACS(&U);
66
73
    if (!ACS)
67
0
      return false;
68
73
69
73
    // Mismatched argument count is undefined behavior. Simply bail out to avoid
70
73
    // handling of such situations below (avoiding asserts/crashes).
71
73
    unsigned NumActualArgs = ACS.getNumArgOperands();
72
73
    if (F.isVarArg() ? 
ArgumentConstants.size() > NumActualArgs4
73
73
                     : 
ArgumentConstants.size() != NumActualArgs69
)
74
4
      return false;
75
69
76
69
    // Check out all of the potentially constant arguments.  Note that we don't
77
69
    // inspect varargs here.
78
69
    Function::arg_iterator Arg = F.arg_begin();
79
166
    for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 
++i, ++Arg97
) {
80
111
81
111
      // If this argument is known non-constant, ignore it.
82
111
      if (ArgumentConstants[i].second)
83
4
        continue;
84
107
85
107
      Value *V = ACS.getCallArgOperand(i);
86
107
      Constant *C = dyn_cast_or_null<Constant>(V);
87
107
88
107
      // Mismatched argument type is undefined behavior. Simply bail out to avoid
89
107
      // handling of such situations below (avoiding asserts/crashes).
90
107
      if (C && 
Arg->getType() != C->getType()71
)
91
1
        return false;
92
106
93
106
      // We can only propagate thread independent values through callbacks.
94
106
      // This is different to direct/indirect call sites because for them we
95
106
      // know the thread executing the caller and callee is the same. For
96
106
      // callbacks this is not guaranteed, thus a thread dependent value could
97
106
      // be different for the caller and callee, making it invalid to propagate.
98
106
      if (C && 
ACS.isCallbackCall()70
&&
C->isThreadDependent()54
) {
99
2
        // Argument became non-constant. If all arguments are non-constant now,
100
2
        // give up on this function.
101
2
        if (++NumNonconstant == ArgumentConstants.size())
102
0
          return false;
103
2
104
2
        ArgumentConstants[i].second = true;
105
2
        continue;
106
2
      }
107
104
108
104
      if (C && 
ArgumentConstants[i].first == nullptr68
) {
109
43
        ArgumentConstants[i].first = C;   // First constant seen.
110
61
      } else if (C && 
ArgumentConstants[i].first == C25
) {
111
15
        // Still the constant value we think it is.
112
46
      } else if (V == &*Arg) {
113
2
        // Ignore recursive calls passing argument down.
114
44
      } else {
115
44
        // Argument became non-constant.  If all arguments are non-constant now,
116
44
        // give up on this function.
117
44
        if (++NumNonconstant == ArgumentConstants.size())
118
13
          return false;
119
31
        ArgumentConstants[i].second = true;
120
31
      }
121
104
    }
122
69
  }
123
48
124
48
  // If we got to this point, there is a constant argument!
125
48
  assert(NumNonconstant != ArgumentConstants.size());
126
30
  bool MadeChange = false;
127
30
  Function::arg_iterator AI = F.arg_begin();
128
90
  for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 
++i, ++AI60
) {
129
60
    // Do we have a constant argument?
130
60
    if (ArgumentConstants[i].second || 
AI->use_empty()30
||
131
60
        
AI->hasInAllocaAttr()15
||
(15
AI->hasByValAttr()15
&&
!F.onlyReadsMemory()0
))
132
45
      continue;
133
15
134
15
    Value *V = ArgumentConstants[i].first;
135
15
    if (!V) 
V = UndefValue::get(AI->getType())1
;
136
15
    AI->replaceAllUsesWith(V);
137
15
    ++NumArgumentsProped;
138
15
    MadeChange = true;
139
15
  }
140
30
  return MadeChange;
141
48
}
142
143
144
// Check to see if this function returns one or more constants. If so, replace
145
// all callers that use those return values with the constant value. This will
146
// leave in the actual return values and instructions, but deadargelim will
147
// clean that up.
148
//
149
// Additionally if a function always returns one of its arguments directly,
150
// callers will be updated to use the value they pass in directly instead of
151
// using the return value.
152
87
static bool PropagateConstantReturn(Function &F) {
153
87
  if (F.getReturnType()->isVoidTy())
154
34
    return false; // No return value.
155
53
156
53
  // We can infer and propagate the return value only when we know that the
157
53
  // definition we'll get at link time is *exactly* the definition we see now.
158
53
  // For more details, see GlobalValue::mayBeDerefined.
159
53
  if (!F.isDefinitionExact())
160
2
    return false;
161
51
162
51
  // Don't touch naked functions. The may contain asm returning
163
51
  // value we don't see, so we may end up interprocedurally propagating
164
51
  // the return value incorrectly.
165
51
  if (F.hasFnAttribute(Attribute::Naked))
166
1
    return false;
167
50
168
50
  // Check to see if this function returns a constant.
169
50
  SmallVector<Value *,4> RetVals;
170
50
  StructType *STy = dyn_cast<StructType>(F.getReturnType());
171
50
  if (STy)
172
12
    
for (unsigned i = 0, e = STy->getNumElements(); 4
i < e;
++i8
)
173
8
      RetVals.push_back(UndefValue::get(STy->getElementType(i)));
174
46
  else
175
46
    RetVals.push_back(UndefValue::get(F.getReturnType()));
176
50
177
50
  unsigned NumNonConstant = 0;
178
50
  for (BasicBlock &BB : F)
179
59
    if (ReturnInst *RI = dyn_cast<ReturnInst>(BB.getTerminator())) {
180
99
      for (unsigned i = 0, e = RetVals.size(); i != e; 
++i45
) {
181
60
        // Already found conflicting return values?
182
60
        Value *RV = RetVals[i];
183
60
        if (!RV)
184
0
          continue;
185
60
186
60
        // Find the returned value
187
60
        Value *V;
188
60
        if (!STy)
189
48
          V = RI->getOperand(0);
190
12
        else
191
12
          V = FindInsertedValue(RI->getOperand(0), i);
192
60
193
60
        if (V) {
194
58
          // Ignore undefs, we can change them into anything
195
58
          if (isa<UndefValue>(V))
196
0
            continue;
197
58
198
58
          // Try to see if all the rets return the same constant or argument.
199
58
          if (isa<Constant>(V) || 
isa<Argument>(V)29
) {
200
43
            if (isa<UndefValue>(RV)) {
201
37
              // No value found yet? Try the current one.
202
37
              RetVals[i] = V;
203
37
              continue;
204
37
            }
205
6
            // Returning the same value? Good.
206
6
            if (RV == V)
207
4
              continue;
208
19
          }
209
58
        }
210
19
        // Different or no known return value? Don't propagate this return
211
19
        // value.
212
19
        RetVals[i] = nullptr;
213
19
        // All values non-constant? Stop looking.
214
19
        if (++NumNonConstant == RetVals.size())
215
15
          return false;
216
19
      }
217
54
    }
218
50
219
50
  // If we got here, the function returns at least one constant value.  Loop
220
50
  // over all users, replacing any uses of the return value with the returned
221
50
  // constant.
222
50
  bool MadeChange = false;
223
57
  for (Use &U : F.uses()) {
224
57
    CallSite CS(U.getUser());
225
57
    Instruction* Call = CS.getInstruction();
226
57
227
57
    // Not a call instruction or a call instruction that's not calling F
228
57
    // directly?
229
57
    if (!Call || 
!CS.isCallee(&U)52
)
230
41
      continue;
231
16
232
16
    // Call result not used?
233
16
    if (Call->use_empty())
234
8
      continue;
235
8
236
8
    MadeChange = true;
237
8
238
8
    if (!STy) {
239
4
      Value* New = RetVals[0];
240
4
      if (Argument *A = dyn_cast<Argument>(New))
241
1
        // Was an argument returned? Then find the corresponding argument in
242
1
        // the call instruction and use that.
243
1
        New = CS.getArgument(A->getArgNo());
244
4
      Call->replaceAllUsesWith(New);
245
4
      continue;
246
4
    }
247
4
248
11
    
for (auto I = Call->user_begin(), E = Call->user_end(); 4
I != E;) {
249
7
      Instruction *Ins = cast<Instruction>(*I);
250
7
251
7
      // Increment now, so we can remove the use
252
7
      ++I;
253
7
254
7
      // Find the index of the retval to replace with
255
7
      int index = -1;
256
7
      if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins))
257
6
        if (EV->hasIndices())
258
6
          index = *EV->idx_begin();
259
7
260
7
      // If this use uses a specific return value, and we have a replacement,
261
7
      // replace it.
262
7
      if (index != -1) {
263
6
        Value *New = RetVals[index];
264
6
        if (New) {
265
4
          if (Argument *A = dyn_cast<Argument>(New))
266
2
            // Was an argument returned? Then find the corresponding argument in
267
2
            // the call instruction and use that.
268
2
            New = CS.getArgument(A->getArgNo());
269
4
          Ins->replaceAllUsesWith(New);
270
4
          Ins->eraseFromParent();
271
4
        }
272
6
      }
273
7
    }
274
4
  }
275
35
276
35
  if (MadeChange) 
++NumReturnValProped6
;
277
35
  return MadeChange;
278
50
}
279
280
char IPCP::ID = 0;
281
INITIALIZE_PASS(IPCP, "ipconstprop",
282
                "Interprocedural constant propagation", false, false)
283
284
0
ModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); }
285
286
17
bool IPCP::runOnModule(Module &M) {
287
17
  if (skipModule(M))
288
0
    return false;
289
17
290
17
  bool Changed = false;
291
17
  bool LocalChange = true;
292
17
293
17
  // FIXME: instead of using smart algorithms, we just iterate until we stop
294
17
  // making changes.
295
44
  while (LocalChange) {
296
27
    LocalChange = false;
297
27
    for (Function &F : M)
298
135
      if (!F.isDeclaration()) {
299
87
        // Delete any klingons.
300
87
        F.removeDeadConstantUsers();
301
87
        if (F.hasLocalLinkage())
302
50
          LocalChange |= PropagateConstantsIntoArguments(F);
303
87
        Changed |= PropagateConstantReturn(F);
304
87
      }
305
27
    Changed |= LocalChange;
306
27
  }
307
17
  return Changed;
308
17
}