Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/IPO/Attributor.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Attributor.cpp - Module-wide attribute deduction -------------------===//
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 implements an inter procedural pass that deduces and/or propagating
10
// attributes. This is done in an abstract interpretation style fixpoint
11
// iteration. See the Attributor.h file comment and the class descriptions in
12
// that file for more information.
13
//
14
//===----------------------------------------------------------------------===//
15
16
#include "llvm/Transforms/IPO/Attributor.h"
17
18
#include "llvm/ADT/DepthFirstIterator.h"
19
#include "llvm/ADT/STLExtras.h"
20
#include "llvm/ADT/SetVector.h"
21
#include "llvm/ADT/SmallPtrSet.h"
22
#include "llvm/ADT/SmallVector.h"
23
#include "llvm/ADT/Statistic.h"
24
#include "llvm/Analysis/CaptureTracking.h"
25
#include "llvm/Analysis/GlobalsModRef.h"
26
#include "llvm/Analysis/Loads.h"
27
#include "llvm/Analysis/ValueTracking.h"
28
#include "llvm/IR/Argument.h"
29
#include "llvm/IR/Attributes.h"
30
#include "llvm/IR/CFG.h"
31
#include "llvm/IR/InstIterator.h"
32
#include "llvm/IR/IntrinsicInst.h"
33
#include "llvm/Support/CommandLine.h"
34
#include "llvm/Support/Debug.h"
35
#include "llvm/Support/raw_ostream.h"
36
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
37
#include "llvm/Transforms/Utils/Local.h"
38
39
#include <cassert>
40
41
using namespace llvm;
42
43
#define DEBUG_TYPE "attributor"
44
45
STATISTIC(NumFnWithExactDefinition,
46
          "Number of function with exact definitions");
47
STATISTIC(NumFnWithoutExactDefinition,
48
          "Number of function without exact definitions");
49
STATISTIC(NumAttributesTimedOut,
50
          "Number of abstract attributes timed out before fixpoint");
51
STATISTIC(NumAttributesValidFixpoint,
52
          "Number of abstract attributes in a valid fixpoint state");
53
STATISTIC(NumAttributesManifested,
54
          "Number of abstract attributes manifested in IR");
55
STATISTIC(NumFnNoUnwind, "Number of functions marked nounwind");
56
57
STATISTIC(NumFnUniqueReturned, "Number of function with unique return");
58
STATISTIC(NumFnKnownReturns, "Number of function with known return values");
59
STATISTIC(NumFnArgumentReturned,
60
          "Number of function arguments marked returned");
61
STATISTIC(NumFnNoSync, "Number of functions marked nosync");
62
STATISTIC(NumFnNoFree, "Number of functions marked nofree");
63
STATISTIC(NumFnReturnedNonNull,
64
          "Number of function return values marked nonnull");
65
STATISTIC(NumFnArgumentNonNull, "Number of function arguments marked nonnull");
66
STATISTIC(NumCSArgumentNonNull, "Number of call site arguments marked nonnull");
67
STATISTIC(NumFnWillReturn, "Number of functions marked willreturn");
68
STATISTIC(NumFnArgumentNoAlias, "Number of function arguments marked noalias");
69
STATISTIC(NumFnReturnedDereferenceable,
70
          "Number of function return values marked dereferenceable");
71
STATISTIC(NumFnArgumentDereferenceable,
72
          "Number of function arguments marked dereferenceable");
73
STATISTIC(NumCSArgumentDereferenceable,
74
          "Number of call site arguments marked dereferenceable");
75
76
// TODO: Determine a good default value.
77
//
78
// In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
79
// (when run with the first 5 abstract attributes). The results also indicate
80
// that we never reach 32 iterations but always find a fixpoint sooner.
81
//
82
// This will become more evolved once we perform two interleaved fixpoint
83
// iterations: bottom-up and top-down.
84
static cl::opt<unsigned>
85
    MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
86
                          cl::desc("Maximal number of fixpoint iterations."),
87
                          cl::init(32));
88
89
static cl::opt<bool> DisableAttributor(
90
    "attributor-disable", cl::Hidden,
91
    cl::desc("Disable the attributor inter-procedural deduction pass."),
92
    cl::init(true));
93
94
static cl::opt<bool> VerifyAttributor(
95
    "attributor-verify", cl::Hidden,
96
    cl::desc("Verify the Attributor deduction and "
97
             "manifestation of attributes -- may issue false-positive errors"),
98
    cl::init(false));
99
100
/// Logic operators for the change status enum class.
101
///
102
///{
103
1.43k
ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
104
1.43k
  return l == ChangeStatus::CHANGED ? 
l1.18k
:
r253
;
105
1.43k
}
106
0
ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
107
0
  return l == ChangeStatus::UNCHANGED ? l : r;
108
0
}
109
///}
110
111
/// Helper to adjust the statistics.
112
static void bookkeeping(AbstractAttribute::ManifestPosition MP,
113
588
                        const Attribute &Attr) {
114
588
  if (!AreStatisticsEnabled())
115
588
    return;
116
0
117
0
  switch (Attr.getKindAsEnum()) {
118
0
  case Attribute::Dereferenceable:
119
0
    switch (MP) {
120
0
    case AbstractAttribute::MP_RETURNED:
121
0
      NumFnReturnedDereferenceable++;
122
0
      break;
123
0
    case AbstractAttribute::MP_ARGUMENT:
124
0
      NumFnArgumentDereferenceable++;
125
0
      break;
126
0
    case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
127
0
      NumCSArgumentDereferenceable++;
128
0
      break;
129
0
    default:
130
0
      break;
131
0
    }
132
0
    break;
133
0
  case Attribute::NoUnwind:
134
0
    NumFnNoUnwind++;
135
0
    return;
136
0
  case Attribute::Returned:
137
0
    NumFnArgumentReturned++;
138
0
    return;
139
0
  case Attribute::NoSync:
140
0
    NumFnNoSync++;
141
0
    break;
142
0
  case Attribute::NoFree:
143
0
    NumFnNoFree++;
144
0
    break;
145
0
  case Attribute::NonNull:
146
0
    switch (MP) {
147
0
    case AbstractAttribute::MP_RETURNED:
148
0
      NumFnReturnedNonNull++;
149
0
      break;
150
0
    case AbstractAttribute::MP_ARGUMENT:
151
0
      NumFnArgumentNonNull++;
152
0
      break;
153
0
    case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
154
0
      NumCSArgumentNonNull++;
155
0
      break;
156
0
    default:
157
0
      break;
158
0
    }
159
0
    break;
160
0
  case Attribute::WillReturn:
161
0
    NumFnWillReturn++;
162
0
    break;
163
0
  case Attribute::NoAlias:
164
0
    NumFnArgumentNoAlias++;
165
0
    return;
166
0
  default:
167
0
    return;
168
0
  }
169
0
}
170
171
template <typename StateTy>
172
using followValueCB_t = std::function<bool(Value *, StateTy &State)>;
173
template <typename StateTy>
174
using visitValueCB_t = std::function<void(Value *, StateTy &State)>;
175
176
/// Recursively visit all values that might become \p InitV at some point. This
177
/// will be done by looking through cast instructions, selects, phis, and calls
178
/// with the "returned" attribute. The callback \p FollowValueCB is asked before
179
/// a potential origin value is looked at. If no \p FollowValueCB is passed, a
180
/// default one is used that will make sure we visit every value only once. Once
181
/// we cannot look through the value any further, the callback \p VisitValueCB
182
/// is invoked and passed the current value and the \p State. To limit how much
183
/// effort is invested, we will never visit more than \p MaxValues values.
184
template <typename StateTy>
185
static bool genericValueTraversal(
186
    Value *InitV, StateTy &State, visitValueCB_t<StateTy> &VisitValueCB,
187
425
    followValueCB_t<StateTy> *FollowValueCB = nullptr, int MaxValues = 8) {
188
425
189
425
  SmallPtrSet<Value *, 16> Visited;
190
592
  followValueCB_t<bool> DefaultFollowValueCB = [&](Value *Val, bool &) {
191
592
    return Visited.insert(Val).second;
192
592
  };
193
425
194
425
  if (!FollowValueCB)
195
425
    FollowValueCB = &DefaultFollowValueCB;
196
425
197
425
  SmallVector<Value *, 16> Worklist;
198
425
  Worklist.push_back(InitV);
199
425
200
425
  int Iteration = 0;
201
592
  do {
202
592
    Value *V = Worklist.pop_back_val();
203
592
204
592
    // Check if we should process the current value. To prevent endless
205
592
    // recursion keep a record of the values we followed!
206
592
    if (!(*FollowValueCB)(V, State))
207
12
      continue;
208
580
209
580
    // Make sure we limit the compile time for complex expressions.
210
580
    if (Iteration++ >= MaxValues)
211
0
      return false;
212
580
213
580
    // Explicitly look through calls with a "returned" attribute if we do
214
580
    // not have a pointer as stripPointerCasts only works on them.
215
580
    if (V->getType()->isPointerTy()) {
216
349
      V = V->stripPointerCasts();
217
349
    } else {
218
231
      CallSite CS(V);
219
231
      if (CS && 
CS.getCalledFunction()97
) {
220
97
        Value *NewV = nullptr;
221
97
        for (Argument &Arg : CS.getCalledFunction()->args())
222
165
          if (Arg.hasReturnedAttr()) {
223
2
            NewV = CS.getArgOperand(Arg.getArgNo());
224
2
            break;
225
2
          }
226
97
        if (NewV) {
227
2
          Worklist.push_back(NewV);
228
2
          continue;
229
2
        }
230
578
      }
231
231
    }
232
578
233
578
    // Look through select instructions, visit both potential values.
234
578
    if (auto *SI = dyn_cast<SelectInst>(V)) {
235
13
      Worklist.push_back(SI->getTrueValue());
236
13
      Worklist.push_back(SI->getFalseValue());
237
13
      continue;
238
13
    }
239
565
240
565
    // Look through phi nodes, visit all operands.
241
565
    if (auto *PHI = dyn_cast<PHINode>(V)) {
242
65
      Worklist.append(PHI->op_begin(), PHI->op_end());
243
65
      continue;
244
65
    }
245
500
246
500
    // Once a leaf is reached we inform the user through the callback.
247
500
    VisitValueCB(V, State);
248
592
  } while (!Worklist.empty());
249
425
250
425
  // All values have been visited.
251
425
  return true;
252
425
}
253
254
/// Helper to identify the correct offset into an attribute list.
255
static unsigned getAttrIndex(AbstractAttribute::ManifestPosition MP,
256
1.35k
                             unsigned ArgNo = 0) {
257
1.35k
  switch (MP) {
258
1.35k
  case AbstractAttribute::MP_ARGUMENT:
259
506
  case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
260
506
    return ArgNo + AttributeList::FirstArgIndex;
261
642
  case AbstractAttribute::MP_FUNCTION:
262
642
    return AttributeList::FunctionIndex;
263
506
  case AbstractAttribute::MP_RETURNED:
264
203
    return AttributeList::ReturnIndex;
265
0
  }
266
0
  llvm_unreachable("Unknown manifest position!");
267
0
}
268
269
/// Return true if \p New is equal or worse than \p Old.
270
364
static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
271
364
  if (!Old.isIntAttribute())
272
338
    return true;
273
26
274
26
  return Old.getValueAsInt() >= New.getValueAsInt();
275
26
}
276
277
/// Return true if the information provided by \p Attr was added to the
278
/// attribute list \p Attrs. This is only the case if it was not already present
279
/// in \p Attrs at the position describe by \p MP and \p ArgNo.
280
static bool addIfNotExistent(LLVMContext &Ctx, const Attribute &Attr,
281
                             AttributeList &Attrs,
282
                             AbstractAttribute::ManifestPosition MP,
283
951
                             unsigned ArgNo = 0) {
284
951
  unsigned AttrIdx = getAttrIndex(MP, ArgNo);
285
951
286
951
  if (Attr.isEnumAttribute()) {
287
884
    Attribute::AttrKind Kind = Attr.getKindAsEnum();
288
884
    if (Attrs.hasAttribute(AttrIdx, Kind))
289
338
      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
290
338
        return false;
291
546
    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
292
546
    return true;
293
546
  }
294
67
  if (Attr.isStringAttribute()) {
295
0
    StringRef Kind = Attr.getKindAsString();
296
0
    if (Attrs.hasAttribute(AttrIdx, Kind))
297
0
      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
298
0
        return false;
299
0
    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
300
0
    return true;
301
0
  }
302
67
  if (Attr.isIntAttribute()) {
303
67
    Attribute::AttrKind Kind = Attr.getKindAsEnum();
304
67
    if (Attrs.hasAttribute(AttrIdx, Kind))
305
26
      if (isEqualOrWorse(Attr, Attrs.getAttribute(AttrIdx, Kind)))
306
25
        return false;
307
42
    Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
308
42
    Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
309
42
    return true;
310
42
  }
311
0
312
0
  llvm_unreachable("Expected enum or string attribute!");
313
0
}
314
315
5.74k
ChangeStatus AbstractAttribute::update(Attributor &A) {
316
5.74k
  ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
317
5.74k
  if (getState().isAtFixpoint())
318
2.24k
    return HasChanged;
319
3.50k
320
3.50k
  LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
321
3.50k
322
3.50k
  HasChanged = updateImpl(A);
323
3.50k
324
3.50k
  LLVM_DEBUG(dbgs() << "[Attributor] Update " << HasChanged << " " << *this
325
3.50k
                    << "\n");
326
3.50k
327
3.50k
  return HasChanged;
328
3.50k
}
329
330
947
ChangeStatus AbstractAttribute::manifest(Attributor &A) {
331
947
  assert(getState().isValidState() &&
332
947
         "Attempted to manifest an invalid state!");
333
947
  assert(getAssociatedValue() &&
334
947
         "Attempted to manifest an attribute without associated value!");
335
947
336
947
  ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
337
947
  SmallVector<Attribute, 4> DeducedAttrs;
338
947
  getDeducedAttributes(DeducedAttrs);
339
947
340
947
  Function &ScopeFn = getAnchorScope();
341
947
  LLVMContext &Ctx = ScopeFn.getContext();
342
947
  ManifestPosition MP = getManifestPosition();
343
947
344
947
  AttributeList Attrs;
345
947
  SmallVector<unsigned, 4> ArgNos;
346
947
347
947
  // In the following some generic code that will manifest attributes in
348
947
  // DeducedAttrs if they improve the current IR. Due to the different
349
947
  // annotation positions we use the underlying AttributeList interface.
350
947
  // Note that MP_CALL_SITE_ARGUMENT can annotate multiple locations.
351
947
352
947
  switch (MP) {
353
947
  case MP_ARGUMENT:
354
110
    ArgNos.push_back(cast<Argument>(getAssociatedValue())->getArgNo());
355
110
    Attrs = ScopeFn.getAttributes();
356
110
    break;
357
947
  case MP_FUNCTION:
358
704
  case MP_RETURNED:
359
704
    ArgNos.push_back(0);
360
704
    Attrs = ScopeFn.getAttributes();
361
704
    break;
362
704
  case MP_CALL_SITE_ARGUMENT: {
363
133
    CallSite CS(&getAnchoredValue());
364
326
    for (unsigned u = 0, e = CS.getNumArgOperands(); u != e; 
u++193
)
365
193
      if (CS.getArgOperand(u) == getAssociatedValue())
366
137
        ArgNos.push_back(u);
367
133
    Attrs = CS.getAttributes();
368
133
  }
369
947
  }
370
947
371
947
  for (const Attribute &Attr : DeducedAttrs) {
372
951
    for (unsigned ArgNo : ArgNos) {
373
951
      if (!addIfNotExistent(Ctx, Attr, Attrs, MP, ArgNo))
374
363
        continue;
375
588
376
588
      HasChanged = ChangeStatus::CHANGED;
377
588
      bookkeeping(MP, Attr);
378
588
    }
379
947
  }
380
947
381
947
  if (HasChanged == ChangeStatus::UNCHANGED)
382
361
    return HasChanged;
383
586
384
586
  switch (MP) {
385
586
  case MP_ARGUMENT:
386
494
  case MP_FUNCTION:
387
494
  case MP_RETURNED:
388
494
    ScopeFn.setAttributes(Attrs);
389
494
    break;
390
494
  case MP_CALL_SITE_ARGUMENT:
391
92
    CallSite(&getAnchoredValue()).setAttributes(Attrs);
392
586
  }
393
586
394
586
  return HasChanged;
395
586
}
396
397
5.57k
Function &AbstractAttribute::getAnchorScope() {
398
5.57k
  Value &V = getAnchoredValue();
399
5.57k
  if (isa<Function>(V))
400
3.55k
    return cast<Function>(V);
401
2.02k
  if (isa<Argument>(V))
402
725
    return *cast<Argument>(V).getParent();
403
1.30k
  if (isa<Instruction>(V))
404
1.30k
    return *cast<Instruction>(V).getFunction();
405
0
  llvm_unreachable("No scope for anchored value found!");
406
0
}
407
408
0
const Function &AbstractAttribute::getAnchorScope() const {
409
0
  return const_cast<AbstractAttribute *>(this)->getAnchorScope();
410
0
}
411
412
// Helper function that returns argument index of value.
413
// If the value is not an argument, this returns -1.
414
400
static int getArgNo(Value &V) {
415
400
  if (auto *Arg = dyn_cast<Argument>(&V))
416
259
    return Arg->getArgNo();
417
141
  return -1;
418
141
}
419
420
/// -----------------------NoUnwind Function Attribute--------------------------
421
422
struct AANoUnwindFunction : AANoUnwind, BooleanState {
423
424
  AANoUnwindFunction(Function &F, InformationCache &InfoCache)
425
248
      : AANoUnwind(F, InfoCache) {}
426
427
  /// See AbstractAttribute::getState()
428
  /// {
429
642
  AbstractState &getState() override { return *this; }
430
0
  const AbstractState &getState() const override { return *this; }
431
  /// }
432
433
  /// See AbstractAttribute::getManifestPosition().
434
217
  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
435
436
0
  const std::string getAsStr() const override {
437
0
    return getAssumed() ? "nounwind" : "may-unwind";
438
0
  }
439
440
  /// See AbstractAttribute::updateImpl(...).
441
  ChangeStatus updateImpl(Attributor &A) override;
442
443
  /// See AANoUnwind::isAssumedNoUnwind().
444
16
  bool isAssumedNoUnwind() const override { return getAssumed(); }
445
446
  /// See AANoUnwind::isKnownNoUnwind().
447
0
  bool isKnownNoUnwind() const override { return getKnown(); }
448
};
449
450
249
ChangeStatus AANoUnwindFunction::updateImpl(Attributor &A) {
451
249
  Function &F = getAnchorScope();
452
249
453
249
  // The map from instruction opcodes to those instructions in the function.
454
249
  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
455
249
  auto Opcodes = {
456
249
      (unsigned)Instruction::Invoke,      (unsigned)Instruction::CallBr,
457
249
      (unsigned)Instruction::Call,        (unsigned)Instruction::CleanupRet,
458
249
      (unsigned)Instruction::CatchSwitch, (unsigned)Instruction::Resume};
459
249
460
1.31k
  for (unsigned Opcode : Opcodes) {
461
1.31k
    for (Instruction *I : OpcodeInstMap[Opcode]) {
462
375
      if (!I->mayThrow())
463
300
        continue;
464
75
465
75
      auto *NoUnwindAA = A.getAAFor<AANoUnwind>(*this, *I);
466
75
467
75
      if (!NoUnwindAA || 
!NoUnwindAA->isAssumedNoUnwind()16
) {
468
59
        indicatePessimisticFixpoint();
469
59
        return ChangeStatus::CHANGED;
470
59
      }
471
75
    }
472
1.31k
  }
473
249
  
return ChangeStatus::UNCHANGED190
;
474
249
}
475
476
/// --------------------- Function Return Values -------------------------------
477
478
/// "Attribute" that collects all potential returned values and the return
479
/// instructions that they arise from.
480
///
481
/// If there is a unique returned value R, the manifest method will:
482
///   - mark R with the "returned" attribute, if R is an argument.
483
class AAReturnedValuesImpl final : public AAReturnedValues, AbstractState {
484
485
  /// Mapping of values potentially returned by the associated function to the
486
  /// return instructions that might return them.
487
  DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> ReturnedValues;
488
489
  /// State flags
490
  ///
491
  ///{
492
  bool IsFixed;
493
  bool IsValidState;
494
  bool HasOverdefinedReturnedCalls;
495
  ///}
496
497
  /// Collect values that could become \p V in the set \p Values, each mapped to
498
  /// \p ReturnInsts.
499
  void collectValuesRecursively(
500
      Attributor &A, Value *V, SmallPtrSetImpl<ReturnInst *> &ReturnInsts,
501
425
      DenseMap<Value *, SmallPtrSet<ReturnInst *, 2>> &Values) {
502
425
503
500
    visitValueCB_t<bool> VisitValueCB = [&](Value *Val, bool &) {
504
500
      assert(!isa<Instruction>(Val) ||
505
500
             &getAnchorScope() == cast<Instruction>(Val)->getFunction());
506
500
      Values[Val].insert(ReturnInsts.begin(), ReturnInsts.end());
507
500
    };
508
425
509
425
    bool UnusedBool;
510
425
    bool Success = genericValueTraversal(V, UnusedBool, VisitValueCB);
511
425
512
425
    // If we did abort the above traversal we haven't see all the values.
513
425
    // Consequently, we cannot know if the information we would derive is
514
425
    // accurate so we give up early.
515
425
    if (!Success)
516
0
      indicatePessimisticFixpoint();
517
425
  }
518
519
public:
520
  /// See AbstractAttribute::AbstractAttribute(...).
521
  AAReturnedValuesImpl(Function &F, InformationCache &InfoCache)
522
180
      : AAReturnedValues(F, InfoCache) {
523
180
    // We do not have an associated argument yet.
524
180
    AssociatedVal = nullptr;
525
180
  }
526
527
  /// See AbstractAttribute::initialize(...).
528
207
  void initialize(Attributor &A) override {
529
207
    // Reset the state.
530
207
    AssociatedVal = nullptr;
531
207
    IsFixed = false;
532
207
    IsValidState = true;
533
207
    HasOverdefinedReturnedCalls = false;
534
207
    ReturnedValues.clear();
535
207
536
207
    Function &F = cast<Function>(getAnchoredValue());
537
207
538
207
    // The map from instruction opcodes to those instructions in the function.
539
207
    auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
540
207
541
207
    // Look through all arguments, if one is marked as returned we are done.
542
274
    for (Argument &Arg : F.args()) {
543
274
      if (Arg.hasReturnedAttr()) {
544
32
545
32
        auto &ReturnInstSet = ReturnedValues[&Arg];
546
32
        for (Instruction *RI : OpcodeInstMap[Instruction::Ret])
547
32
          ReturnInstSet.insert(cast<ReturnInst>(RI));
548
32
549
32
        indicateOptimisticFixpoint();
550
32
        return;
551
32
      }
552
274
    }
553
207
554
207
    // If no argument was marked as returned we look at all return instructions
555
207
    // and collect potentially returned values.
556
207
    
for (Instruction *RI : OpcodeInstMap[Instruction::Ret])175
{
557
199
      SmallPtrSet<ReturnInst *, 1> RISet({cast<ReturnInst>(RI)});
558
199
      collectValuesRecursively(A, cast<ReturnInst>(RI)->getReturnValue(), RISet,
559
199
                               ReturnedValues);
560
199
    }
561
175
  }
562
563
  /// See AbstractAttribute::manifest(...).
564
  ChangeStatus manifest(Attributor &A) override;
565
566
  /// See AbstractAttribute::getState(...).
567
1.33k
  AbstractState &getState() override { return *this; }
568
569
  /// See AbstractAttribute::getState(...).
570
0
  const AbstractState &getState() const override { return *this; }
571
572
  /// See AbstractAttribute::getManifestPosition().
573
91
  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
574
575
  /// See AbstractAttribute::updateImpl(Attributor &A).
576
  ChangeStatus updateImpl(Attributor &A) override;
577
578
  /// Return the number of potential return values, -1 if unknown.
579
246
  size_t getNumReturnValues() const {
580
246
    return isValidState() ? ReturnedValues.size() : 
-10
;
581
246
  }
582
583
  /// Return an assumed unique return value if a single candidate is found. If
584
  /// there cannot be one, return a nullptr. If it is not clear yet, return the
585
  /// Optional::NoneType.
586
  Optional<Value *> getAssumedUniqueReturnValue() const;
587
588
  /// See AbstractState::checkForallReturnedValues(...).
589
  bool
590
  checkForallReturnedValues(std::function<bool(Value &)> &Pred) const override;
591
592
  /// Pretty print the attribute similar to the IR representation.
593
  const std::string getAsStr() const override;
594
595
  /// See AbstractState::isAtFixpoint().
596
562
  bool isAtFixpoint() const override { return IsFixed; }
597
598
  /// See AbstractState::isValidState().
599
2.20k
  bool isValidState() const override { return IsValidState; }
600
601
  /// See AbstractState::indicateOptimisticFixpoint(...).
602
207
  void indicateOptimisticFixpoint() override {
603
207
    IsFixed = true;
604
207
    IsValidState &= true;
605
207
  }
606
0
  void indicatePessimisticFixpoint() override {
607
0
    IsFixed = true;
608
0
    IsValidState = false;
609
0
  }
610
};
611
612
207
ChangeStatus AAReturnedValuesImpl::manifest(Attributor &A) {
613
207
  ChangeStatus Changed = ChangeStatus::UNCHANGED;
614
207
615
207
  // Bookkeeping.
616
207
  assert(isValidState());
617
207
  NumFnKnownReturns++;
618
207
619
207
  // Check if we have an assumed unique return value that we could manifest.
620
207
  Optional<Value *> UniqueRV = getAssumedUniqueReturnValue();
621
207
622
207
  if (!UniqueRV.hasValue() || 
!UniqueRV.getValue()193
)
623
51
    return Changed;
624
156
625
156
  // Bookkeeping.
626
156
  NumFnUniqueReturned++;
627
156
628
156
  // If the assumed unique return value is an argument, annotate it.
629
156
  if (auto *UniqueRVArg = dyn_cast<Argument>(UniqueRV.getValue())) {
630
91
    AssociatedVal = UniqueRVArg;
631
91
    Changed = AbstractAttribute::manifest(A) | Changed;
632
91
  }
633
156
634
156
  return Changed;
635
156
}
636
637
0
const std::string AAReturnedValuesImpl::getAsStr() const {
638
0
  return (isAtFixpoint() ? "returns(#" : "may-return(#") +
639
0
         (isValidState() ? std::to_string(getNumReturnValues()) : "?") + ")";
640
0
}
641
642
479
Optional<Value *> AAReturnedValuesImpl::getAssumedUniqueReturnValue() const {
643
479
  // If checkForallReturnedValues provides a unique value, ignoring potential
644
479
  // undef values that can also be present, it is assumed to be the actual
645
479
  // return value and forwarded to the caller of this method. If there are
646
479
  // multiple, a nullptr is returned indicating there cannot be a unique
647
479
  // returned value.
648
479
  Optional<Value *> UniqueRV;
649
479
650
488
  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
651
488
    // If we found a second returned value and neither the current nor the saved
652
488
    // one is an undef, there is no unique returned value. Undefs are special
653
488
    // since we can pretend they have any value.
654
488
    if (UniqueRV.hasValue() && 
UniqueRV != &RV48
&&
655
488
        
!(48
isa<UndefValue>(RV)48
||
isa<UndefValue>(UniqueRV.getValue())47
)) {
656
42
      UniqueRV = nullptr;
657
42
      return false;
658
42
    }
659
446
660
446
    // Do not overwrite a value with an undef.
661
446
    if (!UniqueRV.hasValue() || 
!isa<UndefValue>(RV)6
)
662
445
      UniqueRV = &RV;
663
446
664
446
    return true;
665
446
  };
666
479
667
479
  if (!checkForallReturnedValues(Pred))
668
42
    UniqueRV = nullptr;
669
479
670
479
  return UniqueRV;
671
479
}
672
673
bool AAReturnedValuesImpl::checkForallReturnedValues(
674
981
    std::function<bool(Value &)> &Pred) const {
675
981
  if (!isValidState())
676
0
    return false;
677
981
678
981
  // Check all returned values but ignore call sites as long as we have not
679
981
  // encountered an overdefined one during an update.
680
1.98k
  
for (auto &It : ReturnedValues)981
{
681
1.98k
    Value *RV = It.first;
682
1.98k
683
1.98k
    ImmutableCallSite ICS(RV);
684
1.98k
    if (ICS && 
!HasOverdefinedReturnedCalls1.09k
)
685
979
      continue;
686
1.00k
687
1.00k
    if (!Pred(*RV))
688
346
      return false;
689
1.00k
  }
690
981
691
981
  
return true635
;
692
981
}
693
694
246
ChangeStatus AAReturnedValuesImpl::updateImpl(Attributor &A) {
695
246
696
246
  // Check if we know of any values returned by the associated function,
697
246
  // if not, we are done.
698
246
  if (getNumReturnValues() == 0) {
699
3
    indicateOptimisticFixpoint();
700
3
    return ChangeStatus::UNCHANGED;
701
3
  }
702
243
703
243
  // Check if any of the returned values is a call site we can refine.
704
243
  decltype(ReturnedValues) AddRVs;
705
243
  bool HasCallSite = false;
706
243
707
243
  // Look at all returned call sites.
708
518
  for (auto &It : ReturnedValues) {
709
518
    SmallPtrSet<ReturnInst *, 2> &ReturnInsts = It.second;
710
518
    Value *RV = It.first;
711
518
    LLVM_DEBUG(dbgs() << "[AAReturnedValues] Potentially returned value " << *RV
712
518
                      << "\n");
713
518
714
518
    // Only call sites can change during an update, ignore the rest.
715
518
    CallSite RetCS(RV);
716
518
    if (!RetCS)
717
210
      continue;
718
308
719
308
    // For now, any call site we see will prevent us from directly fixing the
720
308
    // state. However, if the information on the callees is fixed, the call
721
308
    // sites will be removed and we will fix the information for this state.
722
308
    HasCallSite = true;
723
308
724
308
    // Try to find a assumed unique return value for the called function.
725
308
    auto *RetCSAA = A.getAAFor<AAReturnedValuesImpl>(*this, *RV);
726
308
    if (!RetCSAA) {
727
36
      HasOverdefinedReturnedCalls = true;
728
36
      LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site (" << *RV
729
36
                        << ") with " << (RetCSAA ? "invalid" : "no")
730
36
                        << " associated state\n");
731
36
      continue;
732
36
    }
733
272
734
272
    // Try to find a assumed unique return value for the called function.
735
272
    Optional<Value *> AssumedUniqueRV = RetCSAA->getAssumedUniqueReturnValue();
736
272
737
272
    // If no assumed unique return value was found due to the lack of
738
272
    // candidates, we may need to resolve more calls (through more update
739
272
    // iterations) or the called function will not return. Either way, we simply
740
272
    // stick with the call sites as return values. Because there were not
741
272
    // multiple possibilities, we do not treat it as overdefined.
742
272
    if (!AssumedUniqueRV.hasValue())
743
25
      continue;
744
247
745
247
    // If multiple, non-refinable values were found, there cannot be a unique
746
247
    // return value for the called function. The returned call is overdefined!
747
247
    if (!AssumedUniqueRV.getValue()) {
748
5
      HasOverdefinedReturnedCalls = true;
749
5
      LLVM_DEBUG(dbgs() << "[AAReturnedValues] Returned call site has multiple "
750
5
                           "potentially returned values\n");
751
5
      continue;
752
5
    }
753
242
754
242
    LLVM_DEBUG({
755
242
      bool UniqueRVIsKnown = RetCSAA->isAtFixpoint();
756
242
      dbgs() << "[AAReturnedValues] Returned call site "
757
242
             << (UniqueRVIsKnown ? "known" : "assumed")
758
242
             << " unique return value: " << *AssumedUniqueRV << "\n";
759
242
    });
760
242
761
242
    // The assumed unique return value.
762
242
    Value *AssumedRetVal = AssumedUniqueRV.getValue();
763
242
764
242
    // If the assumed unique return value is an argument, lookup the matching
765
242
    // call site operand and recursively collect new returned values.
766
242
    // If it is not an argument, it is just put into the set of returned values
767
242
    // as we would have already looked through casts, phis, and similar values.
768
242
    if (Argument *AssumedRetArg = dyn_cast<Argument>(AssumedRetVal))
769
226
      collectValuesRecursively(A,
770
226
                               RetCS.getArgOperand(AssumedRetArg->getArgNo()),
771
226
                               ReturnInsts, AddRVs);
772
16
    else
773
16
      AddRVs[AssumedRetVal].insert(ReturnInsts.begin(), ReturnInsts.end());
774
242
  }
775
243
776
243
  // Keep track of any change to trigger updates on dependent attributes.
777
243
  ChangeStatus Changed = ChangeStatus::UNCHANGED;
778
243
779
243
  for (auto &It : AddRVs) {
780
222
    assert(!It.second.empty() && "Entry does not add anything.");
781
222
    auto &ReturnInsts = ReturnedValues[It.first];
782
222
    for (ReturnInst *RI : It.second)
783
222
      if (ReturnInsts.insert(RI).second) {
784
59
        LLVM_DEBUG(dbgs() << "[AAReturnedValues] Add new returned value "
785
59
                          << *It.first << " => " << *RI << "\n");
786
59
        Changed = ChangeStatus::CHANGED;
787
59
      }
788
222
  }
789
243
790
243
  // If there is no call site in the returned values we are done.
791
243
  if (!HasCallSite) {
792
77
    indicateOptimisticFixpoint();
793
77
    return ChangeStatus::CHANGED;
794
77
  }
795
166
796
166
  return Changed;
797
166
}
798
799
/// ------------------------ NoSync Function Attribute -------------------------
800
801
struct AANoSyncFunction : AANoSync, BooleanState {
802
803
  AANoSyncFunction(Function &F, InformationCache &InfoCache)
804
248
      : AANoSync(F, InfoCache) {}
805
806
  /// See AbstractAttribute::getState()
807
  /// {
808
852
  AbstractState &getState() override { return *this; }
809
0
  const AbstractState &getState() const override { return *this; }
810
  /// }
811
812
  /// See AbstractAttribute::getManifestPosition().
813
174
  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
814
815
0
  const std::string getAsStr() const override {
816
0
    return getAssumed() ? "nosync" : "may-sync";
817
0
  }
818
819
  /// See AbstractAttribute::updateImpl(...).
820
  ChangeStatus updateImpl(Attributor &A) override;
821
822
  /// See AANoSync::isAssumedNoSync()
823
180
  bool isAssumedNoSync() const override { return getAssumed(); }
824
825
  /// See AANoSync::isKnownNoSync()
826
0
  bool isKnownNoSync() const override { return getKnown(); }
827
828
  /// Helper function used to determine whether an instruction is non-relaxed
829
  /// atomic. In other words, if an atomic instruction does not have unordered
830
  /// or monotonic ordering
831
  static bool isNonRelaxedAtomic(Instruction *I);
832
833
  /// Helper function used to determine whether an instruction is volatile.
834
  static bool isVolatile(Instruction *I);
835
836
  /// Helper function uset to check if intrinsic is volatile (memcpy, memmove,
837
  /// memset).
838
  static bool isNoSyncIntrinsic(Instruction *I);
839
};
840
841
63
bool AANoSyncFunction::isNonRelaxedAtomic(Instruction *I) {
842
63
  if (!I->isAtomic())
843
53
    return false;
844
10
845
10
  AtomicOrdering Ordering;
846
10
  switch (I->getOpcode()) {
847
10
  case Instruction::AtomicRMW:
848
0
    Ordering = cast<AtomicRMWInst>(I)->getOrdering();
849
0
    break;
850
10
  case Instruction::Store:
851
2
    Ordering = cast<StoreInst>(I)->getOrdering();
852
2
    break;
853
10
  case Instruction::Load:
854
4
    Ordering = cast<LoadInst>(I)->getOrdering();
855
4
    break;
856
10
  case Instruction::Fence: {
857
4
    auto *FI = cast<FenceInst>(I);
858
4
    if (FI->getSyncScopeID() == SyncScope::SingleThread)
859
2
      return false;
860
2
    Ordering = FI->getOrdering();
861
2
    break;
862
2
  }
863
2
  case Instruction::AtomicCmpXchg: {
864
0
    AtomicOrdering Success = cast<AtomicCmpXchgInst>(I)->getSuccessOrdering();
865
0
    AtomicOrdering Failure = cast<AtomicCmpXchgInst>(I)->getFailureOrdering();
866
0
    // Only if both are relaxed, than it can be treated as relaxed.
867
0
    // Otherwise it is non-relaxed.
868
0
    if (Success != AtomicOrdering::Unordered &&
869
0
        Success != AtomicOrdering::Monotonic)
870
0
      return true;
871
0
    if (Failure != AtomicOrdering::Unordered &&
872
0
        Failure != AtomicOrdering::Monotonic)
873
0
      return true;
874
0
    return false;
875
0
  }
876
0
  default:
877
0
    llvm_unreachable(
878
8
        "New atomic operations need to be known in the attributor.");
879
8
  }
880
8
881
8
  // Relaxed.
882
8
  if (Ordering == AtomicOrdering::Unordered ||
883
8
      Ordering == AtomicOrdering::Monotonic)
884
5
    return false;
885
3
  return true;
886
3
}
887
888
/// Checks if an intrinsic is nosync. Currently only checks mem* intrinsics.
889
/// FIXME: We should ipmrove the handling of intrinsics.
890
5
bool AANoSyncFunction::isNoSyncIntrinsic(Instruction *I) {
891
5
  if (auto *II = dyn_cast<IntrinsicInst>(I)) {
892
5
    switch (II->getIntrinsicID()) {
893
5
    /// Element wise atomic memory intrinsics are can only be unordered,
894
5
    /// therefore nosync.
895
5
    case Intrinsic::memset_element_unordered_atomic:
896
0
    case Intrinsic::memmove_element_unordered_atomic:
897
0
    case Intrinsic::memcpy_element_unordered_atomic:
898
0
      return true;
899
2
    case Intrinsic::memset:
900
2
    case Intrinsic::memmove:
901
2
    case Intrinsic::memcpy:
902
2
      if (!cast<MemIntrinsic>(II)->isVolatile())
903
1
        return true;
904
1
      return false;
905
3
    default:
906
3
      return false;
907
0
    }
908
0
  }
909
0
  return false;
910
0
}
911
912
68
bool AANoSyncFunction::isVolatile(Instruction *I) {
913
68
  assert(!ImmutableCallSite(I) && !isa<CallBase>(I) &&
914
68
         "Calls should not be checked here");
915
68
916
68
  switch (I->getOpcode()) {
917
68
  case Instruction::AtomicRMW:
918
0
    return cast<AtomicRMWInst>(I)->isVolatile();
919
68
  case Instruction::Store:
920
36
    return cast<StoreInst>(I)->isVolatile();
921
68
  case Instruction::Load:
922
28
    return cast<LoadInst>(I)->isVolatile();
923
68
  case Instruction::AtomicCmpXchg:
924
0
    return cast<AtomicCmpXchgInst>(I)->isVolatile();
925
68
  default:
926
4
    return false;
927
68
  }
928
68
}
929
930
250
ChangeStatus AANoSyncFunction::updateImpl(Attributor &A) {
931
250
  Function &F = getAnchorScope();
932
250
933
250
  /// We are looking for volatile instructions or Non-Relaxed atomics.
934
250
  /// FIXME: We should ipmrove the handling of intrinsics.
935
340
  for (Instruction *I : InfoCache.getReadOrWriteInstsForFunction(F)) {
936
340
    ImmutableCallSite ICS(I);
937
340
    auto *NoSyncAA = A.getAAFor<AANoSyncFunction>(*this, *I);
938
340
939
340
    if (isa<IntrinsicInst>(I) && 
isNoSyncIntrinsic(I)5
)
940
1
      continue;
941
339
942
339
    if (ICS && 
(271
!NoSyncAA271
||
!NoSyncAA->isAssumedNoSync()180
) &&
943
339
        
!ICS.hasFnAttr(Attribute::NoSync)91
) {
944
90
      indicatePessimisticFixpoint();
945
90
      return ChangeStatus::CHANGED;
946
90
    }
947
249
948
249
    if (ICS)
949
181
      continue;
950
68
951
68
    if (!isVolatile(I) && 
!isNonRelaxedAtomic(I)63
)
952
60
      continue;
953
8
954
8
    indicatePessimisticFixpoint();
955
8
    return ChangeStatus::CHANGED;
956
8
  }
957
250
958
250
  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
959
152
  auto Opcodes = {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
960
152
                  (unsigned)Instruction::Call};
961
152
962
456
  for (unsigned Opcode : Opcodes) {
963
456
    for (Instruction *I : OpcodeInstMap[Opcode]) {
964
276
      // At this point we handled all read/write effects and they are all
965
276
      // nosync, so they can be skipped.
966
276
      if (I->mayReadOrWriteMemory())
967
178
        continue;
968
98
969
98
      ImmutableCallSite ICS(I);
970
98
971
98
      // non-convergent and readnone imply nosync.
972
98
      if (!ICS.isConvergent())
973
97
        continue;
974
1
975
1
      indicatePessimisticFixpoint();
976
1
      return ChangeStatus::CHANGED;
977
1
    }
978
456
  }
979
152
980
152
  
return ChangeStatus::UNCHANGED151
;
981
152
}
982
983
/// ------------------------ No-Free Attributes ----------------------------
984
985
struct AANoFreeFunction : AbstractAttribute, BooleanState {
986
987
  /// See AbstractAttribute::AbstractAttribute(...).
988
  AANoFreeFunction(Function &F, InformationCache &InfoCache)
989
248
      : AbstractAttribute(F, InfoCache) {}
990
991
  /// See AbstractAttribute::getState()
992
  ///{
993
940
  AbstractState &getState() override { return *this; }
994
0
  const AbstractState &getState() const override { return *this; }
995
  ///}
996
997
  /// See AbstractAttribute::getManifestPosition().
998
178
  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
999
1000
  /// See AbstractAttribute::getAsStr().
1001
0
  const std::string getAsStr() const override {
1002
0
    return getAssumed() ? "nofree" : "may-free";
1003
0
  }
1004
1005
  /// See AbstractAttribute::updateImpl(...).
1006
  ChangeStatus updateImpl(Attributor &A) override;
1007
1008
  /// See AbstractAttribute::getAttrKind().
1009
178
  Attribute::AttrKind getAttrKind() const override { return ID; }
1010
1011
  /// Return true if "nofree" is assumed.
1012
274
  bool isAssumedNoFree() const { return getAssumed(); }
1013
1014
  /// Return true if "nofree" is known.
1015
0
  bool isKnownNoFree() const { return getKnown(); }
1016
1017
  /// The identifier used by the Attributor for this class of attributes.
1018
  static constexpr Attribute::AttrKind ID = Attribute::NoFree;
1019
};
1020
1021
250
ChangeStatus AANoFreeFunction::updateImpl(Attributor &A) {
1022
250
  Function &F = getAnchorScope();
1023
250
1024
250
  // The map from instruction opcodes to those instructions in the function.
1025
250
  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1026
250
1027
250
  for (unsigned Opcode :
1028
250
       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1029
742
        (unsigned)Instruction::Call}) {
1030
742
    for (Instruction *I : OpcodeInstMap[Opcode]) {
1031
371
1032
371
      auto ICS = ImmutableCallSite(I);
1033
371
      auto *NoFreeAA = A.getAAFor<AANoFreeFunction>(*this, *I);
1034
371
1035
371
      if ((!NoFreeAA || 
!NoFreeAA->isAssumedNoFree()274
) &&
1036
371
          
!ICS.hasFnAttr(Attribute::NoFree)97
) {
1037
95
        indicatePessimisticFixpoint();
1038
95
        return ChangeStatus::CHANGED;
1039
95
      }
1040
371
    }
1041
742
  }
1042
250
  
return ChangeStatus::UNCHANGED155
;
1043
250
}
1044
1045
/// ------------------------ NonNull Argument Attribute ------------------------
1046
struct AANonNullImpl : AANonNull, BooleanState {
1047
1048
  AANonNullImpl(Value &V, InformationCache &InfoCache)
1049
336
      : AANonNull(V, InfoCache) {}
1050
1051
  AANonNullImpl(Value *AssociatedVal, Value &AnchoredValue,
1052
                InformationCache &InfoCache)
1053
375
      : AANonNull(AssociatedVal, AnchoredValue, InfoCache) {}
1054
1055
  /// See AbstractAttribute::getState()
1056
  /// {
1057
4.71k
  AbstractState &getState() override { return *this; }
1058
0
  const AbstractState &getState() const override { return *this; }
1059
  /// }
1060
1061
  /// See AbstractAttribute::getAsStr().
1062
0
  const std::string getAsStr() const override {
1063
0
    return getAssumed() ? "nonnull" : "may-null";
1064
0
  }
1065
1066
  /// See AANonNull::isAssumedNonNull().
1067
559
  bool isAssumedNonNull() const override { return getAssumed(); }
1068
1069
  /// See AANonNull::isKnownNonNull().
1070
437
  bool isKnownNonNull() const override { return getKnown(); }
1071
1072
  /// Generate a predicate that checks if a given value is assumed nonnull.
1073
  /// The generated function returns true if a value satisfies any of
1074
  /// following conditions.
1075
  /// (i) A value is known nonZero(=nonnull).
1076
  /// (ii) A value is associated with AANonNull and its isAssumedNonNull() is
1077
  /// true.
1078
  std::function<bool(Value &)> generatePredicate(Attributor &);
1079
};
1080
1081
182
std::function<bool(Value &)> AANonNullImpl::generatePredicate(Attributor &A) {
1082
182
  // FIXME: The `AAReturnedValues` should provide the predicate with the
1083
182
  // `ReturnInst` vector as well such that we can use the control flow sensitive
1084
182
  // version of `isKnownNonZero`. This should fix `test11` in
1085
182
  // `test/Transforms/FunctionAttrs/nonnull.ll`
1086
182
1087
192
  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1088
192
    if (isKnownNonZero(&RV, getAnchorScope().getParent()->getDataLayout()))
1089
36
      return true;
1090
156
1091
156
    auto *NonNullAA = A.getAAFor<AANonNull>(*this, RV);
1092
156
1093
156
    ImmutableCallSite ICS(&RV);
1094
156
1095
156
    if ((!NonNullAA || 
!NonNullAA->isAssumedNonNull()62
) &&
1096
156
        
(94
!ICS94
||
!ICS.hasRetAttr(Attribute::NonNull)21
))
1097
94
      return false;
1098
62
1099
62
    return true;
1100
62
  };
1101
182
1102
182
  return Pred;
1103
182
}
1104
1105
/// NonNull attribute for function return value.
1106
struct AANonNullReturned : AANonNullImpl {
1107
1108
  AANonNullReturned(Function &F, InformationCache &InfoCache)
1109
120
      : AANonNullImpl(F, InfoCache) {}
1110
1111
  /// See AbstractAttribute::getManifestPosition().
1112
29
  ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1113
1114
  /// See AbstractAttriubute::initialize(...).
1115
141
  void initialize(Attributor &A) override {
1116
141
    Function &F = getAnchorScope();
1117
141
1118
141
    // Already nonnull.
1119
141
    if (F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1120
141
                                       Attribute::NonNull) ||
1121
141
        F.getAttributes().hasAttribute(AttributeList::ReturnIndex,
1122
132
                                       Attribute::Dereferenceable))
1123
10
      indicateOptimisticFixpoint();
1124
141
  }
1125
1126
  /// See AbstractAttribute::updateImpl(...).
1127
  ChangeStatus updateImpl(Attributor &A) override;
1128
};
1129
1130
182
ChangeStatus AANonNullReturned::updateImpl(Attributor &A) {
1131
182
  Function &F = getAnchorScope();
1132
182
1133
182
  auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1134
182
  if (!AARetVal) {
1135
0
    indicatePessimisticFixpoint();
1136
0
    return ChangeStatus::CHANGED;
1137
0
  }
1138
182
1139
182
  std::function<bool(Value &)> Pred = this->generatePredicate(A);
1140
182
  if (!AARetVal->checkForallReturnedValues(Pred)) {
1141
94
    indicatePessimisticFixpoint();
1142
94
    return ChangeStatus::CHANGED;
1143
94
  }
1144
88
  return ChangeStatus::UNCHANGED;
1145
88
}
1146
1147
/// NonNull attribute for function argument.
1148
struct AANonNullArgument : AANonNullImpl {
1149
1150
  AANonNullArgument(Argument &A, InformationCache &InfoCache)
1151
216
      : AANonNullImpl(A, InfoCache) {}
1152
1153
  /// See AbstractAttribute::getManifestPosition().
1154
10
  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1155
1156
  /// See AbstractAttriubute::initialize(...).
1157
259
  void initialize(Attributor &A) override {
1158
259
    Argument *Arg = cast<Argument>(getAssociatedValue());
1159
259
    if (Arg->hasNonNullAttr())
1160
9
      indicateOptimisticFixpoint();
1161
259
  }
1162
1163
  /// See AbstractAttribute::updateImpl(...).
1164
  ChangeStatus updateImpl(Attributor &A) override;
1165
};
1166
1167
/// NonNull attribute for a call site argument.
1168
struct AANonNullCallSiteArgument : AANonNullImpl {
1169
1170
  /// See AANonNullImpl::AANonNullImpl(...).
1171
  AANonNullCallSiteArgument(CallSite CS, unsigned ArgNo,
1172
                            InformationCache &InfoCache)
1173
      : AANonNullImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(), InfoCache),
1174
375
        ArgNo(ArgNo) {}
1175
1176
  /// See AbstractAttribute::initialize(...).
1177
488
  void initialize(Attributor &A) override {
1178
488
    CallSite CS(&getAnchoredValue());
1179
488
    if (CS.paramHasAttr(ArgNo, getAttrKind()) ||
1180
488
        
CS.paramHasAttr(ArgNo, Attribute::Dereferenceable)450
||
1181
488
        isKnownNonZero(getAssociatedValue(),
1182
449
                       getAnchorScope().getParent()->getDataLayout()))
1183
88
      indicateOptimisticFixpoint();
1184
488
  }
1185
1186
  /// See AbstractAttribute::updateImpl(Attributor &A).
1187
  ChangeStatus updateImpl(Attributor &A) override;
1188
1189
  /// See AbstractAttribute::getManifestPosition().
1190
88
  ManifestPosition getManifestPosition() const override {
1191
88
    return MP_CALL_SITE_ARGUMENT;
1192
88
  };
1193
1194
  // Return argument index of associated value.
1195
0
  int getArgNo() const { return ArgNo; }
1196
1197
private:
1198
  unsigned ArgNo;
1199
};
1200
209
ChangeStatus AANonNullArgument::updateImpl(Attributor &A) {
1201
209
  Function &F = getAnchorScope();
1202
209
  Argument &Arg = cast<Argument>(getAnchoredValue());
1203
209
1204
209
  unsigned ArgNo = Arg.getArgNo();
1205
209
1206
209
  // Callback function
1207
209
  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) {
1208
58
    assert(CS && "Sanity check: Call site was not initialized properly!");
1209
58
1210
58
    auto *NonNullAA = A.getAAFor<AANonNull>(*this, *CS.getInstruction(), ArgNo);
1211
58
1212
58
    // Check that NonNullAA is AANonNullCallSiteArgument.
1213
58
    if (NonNullAA) {
1214
58
      ImmutableCallSite ICS(&NonNullAA->getAnchoredValue());
1215
58
      if (ICS && 
CS.getInstruction() == ICS.getInstruction()40
)
1216
40
        return NonNullAA->isAssumedNonNull();
1217
18
      return false;
1218
18
    }
1219
0
1220
0
    if (CS.paramHasAttr(ArgNo, Attribute::NonNull))
1221
0
      return true;
1222
0
1223
0
    Value *V = CS.getArgOperand(ArgNo);
1224
0
    if (isKnownNonZero(V, getAnchorScope().getParent()->getDataLayout()))
1225
0
      return true;
1226
0
1227
0
    return false;
1228
0
  };
1229
209
  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1230
206
    indicatePessimisticFixpoint();
1231
206
    return ChangeStatus::CHANGED;
1232
206
  }
1233
3
  return ChangeStatus::UNCHANGED;
1234
3
}
1235
1236
328
ChangeStatus AANonNullCallSiteArgument::updateImpl(Attributor &A) {
1237
328
  // NOTE: Never look at the argument of the callee in this method.
1238
328
  //       If we do this, "nonnull" is always deduced because of the assumption.
1239
328
1240
328
  Value &V = *getAssociatedValue();
1241
328
1242
328
  auto *NonNullAA = A.getAAFor<AANonNull>(*this, V);
1243
328
1244
328
  if (!NonNullAA || 
!NonNullAA->isAssumedNonNull()20
) {
1245
308
    indicatePessimisticFixpoint();
1246
308
    return ChangeStatus::CHANGED;
1247
308
  }
1248
20
1249
20
  return ChangeStatus::UNCHANGED;
1250
20
}
1251
1252
/// ------------------------ Will-Return Attributes ----------------------------
1253
1254
struct AAWillReturnImpl : public AAWillReturn, BooleanState {
1255
1256
  /// See AbstractAttribute::AbstractAttribute(...).
1257
  AAWillReturnImpl(Function &F, InformationCache &InfoCache)
1258
248
      : AAWillReturn(F, InfoCache) {}
1259
1260
  /// See AAWillReturn::isKnownWillReturn().
1261
0
  bool isKnownWillReturn() const override { return getKnown(); }
1262
1263
  /// See AAWillReturn::isAssumedWillReturn().
1264
49
  bool isAssumedWillReturn() const override { return getAssumed(); }
1265
1266
  /// See AbstractAttribute::getState(...).
1267
759
  AbstractState &getState() override { return *this; }
1268
1269
  /// See AbstractAttribute::getState(...).
1270
0
  const AbstractState &getState() const override { return *this; }
1271
1272
  /// See AbstractAttribute::getAsStr()
1273
0
  const std::string getAsStr() const override {
1274
0
    return getAssumed() ? "willreturn" : "may-noreturn";
1275
0
  }
1276
};
1277
1278
struct AAWillReturnFunction final : AAWillReturnImpl {
1279
1280
  /// See AbstractAttribute::AbstractAttribute(...).
1281
  AAWillReturnFunction(Function &F, InformationCache &InfoCache)
1282
248
      : AAWillReturnImpl(F, InfoCache) {}
1283
1284
  /// See AbstractAttribute::getManifestPosition().
1285
73
  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
1286
1287
  /// See AbstractAttribute::initialize(...).
1288
  void initialize(Attributor &A) override;
1289
1290
  /// See AbstractAttribute::updateImpl(...).
1291
  ChangeStatus updateImpl(Attributor &A) override;
1292
};
1293
1294
// Helper function that checks whether a function has any cycle.
1295
// TODO: Replace with more efficent code
1296
282
bool containsCycle(Function &F) {
1297
282
  SmallPtrSet<BasicBlock *, 32> Visited;
1298
282
1299
282
  // Traverse BB by dfs and check whether successor is already visited.
1300
542
  for (BasicBlock *BB : depth_first(&F)) {
1301
542
    Visited.insert(BB);
1302
542
    for (auto *SuccBB : successors(BB)) {
1303
351
      if (Visited.count(SuccBB))
1304
68
        return true;
1305
351
    }
1306
542
  }
1307
282
  
return false214
;
1308
282
}
1309
1310
// Helper function that checks the function have a loop which might become an
1311
// endless loop
1312
// FIXME: Any cycle is regarded as endless loop for now.
1313
//        We have to allow some patterns.
1314
282
bool containsPossiblyEndlessLoop(Function &F) { return containsCycle(F); }
1315
1316
282
void AAWillReturnFunction::initialize(Attributor &A) {
1317
282
  Function &F = getAnchorScope();
1318
282
1319
282
  if (containsPossiblyEndlessLoop(F))
1320
68
    indicatePessimisticFixpoint();
1321
282
}
1322
1323
192
ChangeStatus AAWillReturnFunction::updateImpl(Attributor &A) {
1324
192
  Function &F = getAnchorScope();
1325
192
1326
192
  // The map from instruction opcodes to those instructions in the function.
1327
192
  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(F);
1328
192
1329
192
  for (unsigned Opcode :
1330
192
       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
1331
572
        (unsigned)Instruction::Call}) {
1332
572
    for (Instruction *I : OpcodeInstMap[Opcode]) {
1333
142
      auto ICS = ImmutableCallSite(I);
1334
142
1335
142
      if (ICS.hasFnAttr(Attribute::WillReturn))
1336
3
        continue;
1337
139
1338
139
      auto *WillReturnAA = A.getAAFor<AAWillReturn>(*this, *I);
1339
139
      if (!WillReturnAA || 
!WillReturnAA->isAssumedWillReturn()49
) {
1340
90
        indicatePessimisticFixpoint();
1341
90
        return ChangeStatus::CHANGED;
1342
90
      }
1343
49
1344
49
      auto *NoRecurseAA = A.getAAFor<AANoRecurse>(*this, *I);
1345
49
1346
49
      // FIXME: (i) Prohibit any recursion for now.
1347
49
      //        (ii) AANoRecurse isn't implemented yet so currently any call is
1348
49
      //        regarded as having recursion.
1349
49
      //       Code below should be
1350
49
      //       if ((!NoRecurseAA || !NoRecurseAA->isAssumedNoRecurse()) &&
1351
49
      if (!NoRecurseAA && !ICS.hasFnAttr(Attribute::NoRecurse)) {
1352
37
        indicatePessimisticFixpoint();
1353
37
        return ChangeStatus::CHANGED;
1354
37
      }
1355
49
    }
1356
572
  }
1357
192
1358
192
  
return ChangeStatus::UNCHANGED65
;
1359
192
}
1360
1361
/// ------------------------ NoAlias Argument Attribute ------------------------
1362
1363
struct AANoAliasImpl : AANoAlias, BooleanState {
1364
1365
  AANoAliasImpl(Value &V, InformationCache &InfoCache)
1366
120
      : AANoAlias(V, InfoCache) {}
1367
1368
  /// See AbstractAttribute::getState()
1369
  /// {
1370
404
  AbstractState &getState() override { return *this; }
1371
0
  const AbstractState &getState() const override { return *this; }
1372
  /// }
1373
1374
0
  const std::string getAsStr() const override {
1375
0
    return getAssumed() ? "noalias" : "may-alias";
1376
0
  }
1377
1378
  /// See AANoAlias::isAssumedNoAlias().
1379
0
  bool isAssumedNoAlias() const override { return getAssumed(); }
1380
1381
  /// See AANoAlias::isKnowndNoAlias().
1382
0
  bool isKnownNoAlias() const override { return getKnown(); }
1383
};
1384
1385
/// NoAlias attribute for function return value.
1386
struct AANoAliasReturned : AANoAliasImpl {
1387
1388
  AANoAliasReturned(Function &F, InformationCache &InfoCache)
1389
120
      : AANoAliasImpl(F, InfoCache) {}
1390
1391
  /// See AbstractAttribute::getManifestPosition().
1392
20
  virtual ManifestPosition getManifestPosition() const override {
1393
20
    return MP_RETURNED;
1394
20
  }
1395
1396
  /// See AbstractAttriubute::initialize(...).
1397
141
  void initialize(Attributor &A) override {
1398
141
    Function &F = getAnchorScope();
1399
141
1400
141
    // Already noalias.
1401
141
    if (F.returnDoesNotAlias()) {
1402
8
      indicateOptimisticFixpoint();
1403
8
      return;
1404
8
    }
1405
141
  }
1406
1407
  /// See AbstractAttribute::updateImpl(...).
1408
  virtual ChangeStatus updateImpl(Attributor &A) override;
1409
};
1410
1411
121
ChangeStatus AANoAliasReturned::updateImpl(Attributor &A) {
1412
121
  Function &F = getAnchorScope();
1413
121
1414
121
  auto *AARetValImpl = A.getAAFor<AAReturnedValuesImpl>(*this, F);
1415
121
  if (!AARetValImpl) {
1416
0
    indicatePessimisticFixpoint();
1417
0
    return ChangeStatus::CHANGED;
1418
0
  }
1419
121
1420
121
  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1421
121
    if (Constant *C = dyn_cast<Constant>(&RV))
1422
19
      if (C->isNullValue() || 
isa<UndefValue>(C)12
)
1423
14
        return true;
1424
107
1425
107
    /// For now, we can only deduce noalias if we have call sites.
1426
107
    /// FIXME: add more support.
1427
107
    ImmutableCallSite ICS(&RV);
1428
107
    if (!ICS)
1429
89
      return false;
1430
18
1431
18
    auto *NoAliasAA = A.getAAFor<AANoAlias>(*this, RV);
1432
18
1433
18
    if (!ICS.returnDoesNotAlias() &&
1434
18
        
(12
!NoAliasAA12
||
!NoAliasAA->isAssumedNoAlias()0
))
1435
12
      return false;
1436
6
1437
6
    /// FIXME: We can improve capture check in two ways:
1438
6
    /// 1. Use the AANoCapture facilities.
1439
6
    /// 2. Use the location of return insts for escape queries.
1440
6
    if (PointerMayBeCaptured(&RV, /* ReturnCaptures */ false,
1441
6
                             /* StoreCaptures */ true))
1442
1
      return false;
1443
5
1444
5
    return true;
1445
5
  };
1446
121
1447
121
  if (!AARetValImpl->checkForallReturnedValues(Pred)) {
1448
102
    indicatePessimisticFixpoint();
1449
102
    return ChangeStatus::CHANGED;
1450
102
  }
1451
19
1452
19
  return ChangeStatus::UNCHANGED;
1453
19
}
1454
1455
/// -------------------AAIsDead Function Attribute-----------------------
1456
1457
struct AAIsDeadFunction : AAIsDead, BooleanState {
1458
1459
  AAIsDeadFunction(Function &F, InformationCache &InfoCache)
1460
248
      : AAIsDead(F, InfoCache) {}
1461
1462
  /// See AbstractAttribute::getState()
1463
  /// {
1464
564
  AbstractState &getState() override { return *this; }
1465
0
  const AbstractState &getState() const override { return *this; }
1466
  /// }
1467
1468
  /// See AbstractAttribute::getManifestPosition().
1469
0
  ManifestPosition getManifestPosition() const override { return MP_FUNCTION; }
1470
1471
282
  void initialize(Attributor &A) override {
1472
282
    Function &F = getAnchorScope();
1473
282
1474
282
    ToBeExploredPaths.insert(&(F.getEntryBlock().front()));
1475
282
    AssumedLiveBlocks.insert(&(F.getEntryBlock()));
1476
853
    for (size_t i = 0; i < ToBeExploredPaths.size(); 
++i571
)
1477
571
      explorePath(A, ToBeExploredPaths[i]);
1478
282
  }
1479
1480
  /// Explores new instructions starting from \p I. If instruction is dead, stop
1481
  /// and return true if it discovered a new instruction.
1482
  bool explorePath(Attributor &A, Instruction *I);
1483
1484
0
  const std::string getAsStr() const override {
1485
0
    return "LiveBBs(" + std::to_string(AssumedLiveBlocks.size()) + "/" +
1486
0
           std::to_string(getAnchorScope().size()) + ")";
1487
0
  }
1488
1489
  /// See AbstractAttribute::manifest(...).
1490
282
  ChangeStatus manifest(Attributor &A) override {
1491
282
    assert(getState().isValidState() &&
1492
282
           "Attempted to manifest an invalid state!");
1493
282
1494
282
    ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
1495
282
1496
282
    for (Instruction *I : NoReturnCalls) {
1497
11
      BasicBlock *BB = I->getParent();
1498
11
1499
11
      /// Invoke is replaced with a call and unreachable is placed after it.
1500
11
      if (auto *II = dyn_cast<InvokeInst>(I)) {
1501
1
        changeToCall(II);
1502
1
        changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1503
1
        LLVM_DEBUG(dbgs() << "[AAIsDead] Replaced invoke with call inst\n");
1504
1
        continue;
1505
1
      }
1506
10
1507
10
      SplitBlock(BB, I->getNextNode());
1508
10
      changeToUnreachable(BB->getTerminator(), /* UseLLVMTrap */ false);
1509
10
      HasChanged = ChangeStatus::CHANGED;
1510
10
    }
1511
282
1512
282
    return HasChanged;
1513
282
  }
1514
1515
  /// See AbstractAttribute::updateImpl(...).
1516
  ChangeStatus updateImpl(Attributor &A) override;
1517
1518
  /// See AAIsDead::isAssumedDead().
1519
0
  bool isAssumedDead(BasicBlock *BB) const override {
1520
0
    if (!getAssumed())
1521
0
      return false;
1522
0
    return !AssumedLiveBlocks.count(BB);
1523
0
  }
1524
1525
  /// See AAIsDead::isKnownDead().
1526
0
  bool isKnownDead(BasicBlock *BB) const override {
1527
0
    if (!getKnown())
1528
0
      return false;
1529
0
    return !AssumedLiveBlocks.count(BB);
1530
0
  }
1531
1532
  /// Collection of to be explored paths.
1533
  SmallSetVector<Instruction *, 8> ToBeExploredPaths;
1534
1535
  /// Collection of all assumed live BasicBlocks.
1536
  DenseSet<BasicBlock *> AssumedLiveBlocks;
1537
1538
  /// Collection of calls with noreturn attribute, assumed or knwon.
1539
  SmallSetVector<Instruction *, 4> NoReturnCalls;
1540
};
1541
1542
582
bool AAIsDeadFunction::explorePath(Attributor &A, Instruction *I) {
1543
582
  BasicBlock *BB = I->getParent();
1544
582
1545
2.05k
  while (I) {
1546
1.49k
    ImmutableCallSite ICS(I);
1547
1.49k
1548
1.49k
    if (ICS) {
1549
490
      auto *NoReturnAA = A.getAAFor<AANoReturn>(*this, *I);
1550
490
1551
490
      if (NoReturnAA && 
NoReturnAA->isAssumedNoReturn()0
) {
1552
0
        if (!NoReturnCalls.insert(I))
1553
0
          // If I is already in the NoReturnCalls set, then it stayed noreturn
1554
0
          // and we didn't discover any new instructions.
1555
0
          return false;
1556
0
1557
0
        // Discovered new noreturn call, return true to indicate that I is not
1558
0
        // noreturn anymore and should be deleted from NoReturnCalls.
1559
0
        return true;
1560
0
      }
1561
490
1562
490
      if (ICS.hasFnAttr(Attribute::NoReturn)) {
1563
22
        if (!NoReturnCalls.insert(I))
1564
11
          return false;
1565
11
1566
11
        return true;
1567
11
      }
1568
490
    }
1569
1.47k
1570
1.47k
    I = I->getNextNode();
1571
1.47k
  }
1572
582
1573
582
  // get new paths (reachable blocks).
1574
582
  
for (BasicBlock *SuccBB : successors(BB))560
{
1575
387
    Instruction *Inst = &(SuccBB->front());
1576
387
    AssumedLiveBlocks.insert(SuccBB);
1577
387
    ToBeExploredPaths.insert(Inst);
1578
387
  }
1579
560
1580
560
  return true;
1581
582
}
1582
1583
248
ChangeStatus AAIsDeadFunction::updateImpl(Attributor &A) {
1584
248
  // Temporary collection to iterate over existing noreturn instructions. This
1585
248
  // will alow easier modification of NoReturnCalls collection
1586
248
  SmallVector<Instruction *, 8> NoReturnChanged;
1587
248
  ChangeStatus Status = ChangeStatus::UNCHANGED;
1588
248
1589
248
  for (Instruction *I : NoReturnCalls)
1590
11
    NoReturnChanged.push_back(I);
1591
248
1592
248
  for (Instruction *I : NoReturnChanged) {
1593
11
    size_t Size = ToBeExploredPaths.size();
1594
11
1595
11
    // Still noreturn.
1596
11
    if (!explorePath(A, I))
1597
11
      continue;
1598
0
1599
0
    NoReturnCalls.remove(I);
1600
0
1601
0
    // No new paths.
1602
0
    if (Size == ToBeExploredPaths.size())
1603
0
      continue;
1604
0
1605
0
    // At least one new path.
1606
0
    Status = ChangeStatus::CHANGED;
1607
0
1608
0
    // explore new paths.
1609
0
    while (Size != ToBeExploredPaths.size())
1610
0
      explorePath(A, ToBeExploredPaths[Size++]);
1611
0
  }
1612
248
1613
248
  LLVM_DEBUG(
1614
248
      dbgs() << "[AAIsDead] AssumedLiveBlocks: " << AssumedLiveBlocks.size()
1615
248
             << "Total number of blocks: " << getAnchorScope().size() << "\n");
1616
248
1617
248
  return Status;
1618
248
}
1619
1620
/// -------------------- Dereferenceable Argument Attribute --------------------
1621
1622
struct DerefState : AbstractState {
1623
1624
  /// State representing for dereferenceable bytes.
1625
  IntegerState DerefBytesState;
1626
1627
  /// State representing that whether the value is nonnull or global.
1628
  IntegerState NonNullGlobalState;
1629
1630
  /// Bits encoding for NonNullGlobalState.
1631
  enum {
1632
    DEREF_NONNULL = 1 << 0,
1633
    DEREF_GLOBAL = 1 << 1,
1634
  };
1635
1636
  /// See AbstractState::isValidState()
1637
2.85k
  bool isValidState() const override { return DerefBytesState.isValidState(); }
1638
1639
  // See AbstractState::isAtFixpoint()
1640
2.62k
  bool isAtFixpoint() const override {
1641
2.62k
    return DerefBytesState.isAtFixpoint() && 
NonNullGlobalState.isAtFixpoint()1.71k
;
1642
2.62k
  }
1643
1644
  /// See AbstractState::indicateOptimisticFixpoint(...)
1645
387
  void indicateOptimisticFixpoint() override {
1646
387
    DerefBytesState.indicateOptimisticFixpoint();
1647
387
    NonNullGlobalState.indicateOptimisticFixpoint();
1648
387
  }
1649
1650
  /// See AbstractState::indicatePessimisticFixpoint(...)
1651
324
  void indicatePessimisticFixpoint() override {
1652
324
    DerefBytesState.indicatePessimisticFixpoint();
1653
324
    NonNullGlobalState.indicatePessimisticFixpoint();
1654
324
  }
1655
1656
  /// Update known dereferenceable bytes.
1657
27
  void takeKnownDerefBytesMaximum(uint64_t Bytes) {
1658
27
    DerefBytesState.takeKnownMaximum(Bytes);
1659
27
  }
1660
1661
  /// Update assumed dereferenceable bytes.
1662
1.06k
  void takeAssumedDerefBytesMinimum(uint64_t Bytes) {
1663
1.06k
    DerefBytesState.takeAssumedMinimum(Bytes);
1664
1.06k
  }
1665
1666
  /// Update assumed NonNullGlobalState
1667
902
  void updateAssumedNonNullGlobalState(bool IsNonNull, bool IsGlobal) {
1668
902
    if (!IsNonNull)
1669
720
      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1670
902
    if (!IsGlobal)
1671
891
      NonNullGlobalState.removeAssumedBits(DEREF_GLOBAL);
1672
902
  }
1673
1674
  /// Equality for DerefState.
1675
902
  bool operator==(const DerefState &R) {
1676
902
    return this->DerefBytesState == R.DerefBytesState &&
1677
902
           
this->NonNullGlobalState == R.NonNullGlobalState538
;
1678
902
  }
1679
};
1680
struct AADereferenceableImpl : AADereferenceable, DerefState {
1681
1682
  AADereferenceableImpl(Value &V, InformationCache &InfoCache)
1683
336
      : AADereferenceable(V, InfoCache) {}
1684
1685
  AADereferenceableImpl(Value *AssociatedVal, Value &AnchoredValue,
1686
                        InformationCache &InfoCache)
1687
375
      : AADereferenceable(AssociatedVal, AnchoredValue, InfoCache) {}
1688
1689
  /// See AbstractAttribute::getState()
1690
  /// {
1691
4.32k
  AbstractState &getState() override { return *this; }
1692
0
  const AbstractState &getState() const override { return *this; }
1693
  /// }
1694
1695
  /// See AADereferenceable::getAssumedDereferenceableBytes().
1696
299
  uint32_t getAssumedDereferenceableBytes() const override {
1697
299
    return DerefBytesState.getAssumed();
1698
299
  }
1699
1700
  /// See AADereferenceable::getKnownDereferenceableBytes().
1701
0
  uint32_t getKnownDereferenceableBytes() const override {
1702
0
    return DerefBytesState.getKnown();
1703
0
  }
1704
1705
  // Helper function for syncing nonnull state.
1706
1.22k
  void syncNonNull(const AANonNull *NonNullAA) {
1707
1.22k
    if (!NonNullAA) {
1708
789
      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1709
789
      return;
1710
789
    }
1711
437
1712
437
    if (NonNullAA->isKnownNonNull())
1713
160
      NonNullGlobalState.addKnownBits(DEREF_NONNULL);
1714
437
1715
437
    if (!NonNullAA->isAssumedNonNull())
1716
0
      NonNullGlobalState.removeAssumedBits(DEREF_NONNULL);
1717
437
  }
1718
1719
  /// See AADereferenceable::isAssumedGlobal().
1720
452
  bool isAssumedGlobal() const override {
1721
452
    return NonNullGlobalState.isAssumed(DEREF_GLOBAL);
1722
452
  }
1723
1724
  /// See AADereferenceable::isKnownGlobal().
1725
808
  bool isKnownGlobal() const override {
1726
808
    return NonNullGlobalState.isKnown(DEREF_GLOBAL);
1727
808
  }
1728
1729
  /// See AADereferenceable::isAssumedNonNull().
1730
1.50k
  bool isAssumedNonNull() const override {
1731
1.50k
    return NonNullGlobalState.isAssumed(DEREF_NONNULL);
1732
1.50k
  }
1733
1734
  /// See AADereferenceable::isKnownNonNull().
1735
0
  bool isKnownNonNull() const override {
1736
0
    return NonNullGlobalState.isKnown(DEREF_NONNULL);
1737
0
  }
1738
1739
67
  void getDeducedAttributes(SmallVectorImpl<Attribute> &Attrs) const override {
1740
67
    LLVMContext &Ctx = AnchoredVal.getContext();
1741
67
1742
67
    // TODO: Add *_globally support
1743
67
    if (isAssumedNonNull())
1744
64
      Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
1745
64
          Ctx, getAssumedDereferenceableBytes()));
1746
3
    else
1747
3
      Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
1748
3
          Ctx, getAssumedDereferenceableBytes()));
1749
67
  }
1750
  uint64_t computeAssumedDerefenceableBytes(Attributor &A, Value &V,
1751
                                            bool &IsNonNull, bool &IsGlobal);
1752
1753
400
  void initialize(Attributor &A) override {
1754
400
    Function &F = getAnchorScope();
1755
400
    unsigned AttrIdx =
1756
400
        getAttrIndex(getManifestPosition(), getArgNo(getAnchoredValue()));
1757
400
1758
400
    for (Attribute::AttrKind AK :
1759
400
         {Attribute::Dereferenceable, Attribute::DereferenceableOrNull})
1760
800
      if (F.getAttributes().hasAttribute(AttrIdx, AK))
1761
11
        takeKnownDerefBytesMaximum(F.getAttribute(AttrIdx, AK).getValueAsInt());
1762
400
  }
1763
1764
  /// See AbstractAttribute::getAsStr().
1765
0
  const std::string getAsStr() const override {
1766
0
    if (!getAssumedDereferenceableBytes())
1767
0
      return "unknown-dereferenceable";
1768
0
    return std::string("dereferenceable") +
1769
0
           (isAssumedNonNull() ? "" : "_or_null") +
1770
0
           (isAssumedGlobal() ? "_globally" : "") + "<" +
1771
0
           std::to_string(getKnownDereferenceableBytes()) + "-" +
1772
0
           std::to_string(getAssumedDereferenceableBytes()) + ">";
1773
0
  }
1774
};
1775
1776
struct AADereferenceableReturned : AADereferenceableImpl {
1777
  AADereferenceableReturned(Function &F, InformationCache &InfoCache)
1778
120
      : AADereferenceableImpl(F, InfoCache) {}
1779
1780
  /// See AbstractAttribute::getManifestPosition().
1781
154
  ManifestPosition getManifestPosition() const override { return MP_RETURNED; }
1782
1783
  /// See AbstractAttribute::updateImpl(...).
1784
  ChangeStatus updateImpl(Attributor &A) override;
1785
};
1786
1787
// Helper function that returns dereferenceable bytes.
1788
static uint64_t calcDifferenceIfBaseIsNonNull(int64_t DerefBytes,
1789
37
                                              int64_t Offset, bool IsNonNull) {
1790
37
  if (!IsNonNull)
1791
0
    return 0;
1792
37
  return std::max((int64_t)0, DerefBytes - Offset);
1793
37
}
1794
1795
uint64_t AADereferenceableImpl::computeAssumedDerefenceableBytes(
1796
1.03k
    Attributor &A, Value &V, bool &IsNonNull, bool &IsGlobal) {
1797
1.03k
  // TODO: Tracking the globally flag.
1798
1.03k
  IsGlobal = false;
1799
1.03k
1800
1.03k
  // First, we try to get information about V from Attributor.
1801
1.03k
  if (auto *DerefAA = A.getAAFor<AADereferenceable>(*this, V)) {
1802
165
    IsNonNull &= DerefAA->isAssumedNonNull();
1803
165
    return DerefAA->getAssumedDereferenceableBytes();
1804
165
  }
1805
868
1806
868
  // Otherwise, we try to compute assumed bytes from base pointer.
1807
868
  const DataLayout &DL = getAnchorScope().getParent()->getDataLayout();
1808
868
  unsigned IdxWidth =
1809
868
      DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
1810
868
  APInt Offset(IdxWidth, 0);
1811
868
  Value *Base = V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1812
868
1813
868
  if (auto *BaseDerefAA = A.getAAFor<AADereferenceable>(*this, *Base)) {
1814
33
    IsNonNull &= Offset != 0;
1815
33
    return calcDifferenceIfBaseIsNonNull(
1816
33
        BaseDerefAA->getAssumedDereferenceableBytes(), Offset.getSExtValue(),
1817
33
        Offset != 0 || 
BaseDerefAA->isAssumedNonNull()12
);
1818
33
  }
1819
835
1820
835
  // Then, use IR information.
1821
835
1822
835
  if (isDereferenceablePointer(Base, Base->getType(), DL))
1823
4
    return calcDifferenceIfBaseIsNonNull(
1824
4
        DL.getTypeStoreSize(Base->getType()->getPointerElementType()),
1825
4
        Offset.getSExtValue(),
1826
4
        !NullPointerIsDefined(&getAnchorScope(),
1827
4
                              V.getType()->getPointerAddressSpace()));
1828
831
1829
831
  IsNonNull = false;
1830
831
  return 0;
1831
831
}
1832
199
ChangeStatus AADereferenceableReturned::updateImpl(Attributor &A) {
1833
199
  Function &F = getAnchorScope();
1834
199
  auto BeforeState = static_cast<DerefState>(*this);
1835
199
1836
199
  syncNonNull(A.getAAFor<AANonNull>(*this, F));
1837
199
1838
199
  auto *AARetVal = A.getAAFor<AAReturnedValues>(*this, F);
1839
199
  if (!AARetVal) {
1840
0
    indicatePessimisticFixpoint();
1841
0
    return ChangeStatus::CHANGED;
1842
0
  }
1843
199
1844
199
  bool IsNonNull = isAssumedNonNull();
1845
199
  bool IsGlobal = isAssumedGlobal();
1846
199
1847
206
  std::function<bool(Value &)> Pred = [&](Value &RV) -> bool {
1848
206
    takeAssumedDerefBytesMinimum(
1849
206
        computeAssumedDerefenceableBytes(A, RV, IsNonNull, IsGlobal));
1850
206
    return isValidState();
1851
206
  };
1852
199
1853
199
  if (AARetVal->checkForallReturnedValues(Pred)) {
1854
91
    updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1855
91
    return BeforeState == static_cast<DerefState>(*this)
1856
91
               ? 
ChangeStatus::UNCHANGED16
1857
91
               : 
ChangeStatus::CHANGED75
;
1858
91
  }
1859
108
  indicatePessimisticFixpoint();
1860
108
  return ChangeStatus::CHANGED;
1861
108
}
1862
1863
struct AADereferenceableArgument : AADereferenceableImpl {
1864
  AADereferenceableArgument(Argument &A, InformationCache &InfoCache)
1865
216
      : AADereferenceableImpl(A, InfoCache) {}
1866
1867
  /// See AbstractAttribute::getManifestPosition().
1868
268
  ManifestPosition getManifestPosition() const override { return MP_ARGUMENT; }
1869
1870
  /// See AbstractAttribute::updateImpl(...).
1871
  ChangeStatus updateImpl(Attributor &A) override;
1872
};
1873
1874
219
ChangeStatus AADereferenceableArgument::updateImpl(Attributor &A) {
1875
219
  Function &F = getAnchorScope();
1876
219
  Argument &Arg = cast<Argument>(getAnchoredValue());
1877
219
1878
219
  auto BeforeState = static_cast<DerefState>(*this);
1879
219
1880
219
  unsigned ArgNo = Arg.getArgNo();
1881
219
1882
219
  syncNonNull(A.getAAFor<AANonNull>(*this, F, ArgNo));
1883
219
1884
219
  bool IsNonNull = isAssumedNonNull();
1885
219
  bool IsGlobal = isAssumedGlobal();
1886
219
1887
219
  // Callback function
1888
219
  std::function<bool(CallSite)> CallSiteCheck = [&](CallSite CS) -> bool {
1889
53
    assert(CS && "Sanity check: Call site was not initialized properly!");
1890
53
1891
53
    // Check that DereferenceableAA is AADereferenceableCallSiteArgument.
1892
53
    if (auto *DereferenceableAA =
1893
53
            A.getAAFor<AADereferenceable>(*this, *CS.getInstruction(), ArgNo)) {
1894
53
      ImmutableCallSite ICS(&DereferenceableAA->getAnchoredValue());
1895
53
      if (ICS && 
CS.getInstruction() == ICS.getInstruction()34
) {
1896
34
        takeAssumedDerefBytesMinimum(
1897
34
            DereferenceableAA->getAssumedDereferenceableBytes());
1898
34
        IsNonNull &= DereferenceableAA->isAssumedNonNull();
1899
34
        IsGlobal &= DereferenceableAA->isAssumedGlobal();
1900
34
        return isValidState();
1901
34
      }
1902
19
    }
1903
19
1904
19
    takeAssumedDerefBytesMinimum(computeAssumedDerefenceableBytes(
1905
19
        A, *CS.getArgOperand(ArgNo), IsNonNull, IsGlobal));
1906
19
1907
19
    return isValidState();
1908
19
  };
1909
219
1910
219
  if (!A.checkForAllCallSites(F, CallSiteCheck, true)) {
1911
216
    indicatePessimisticFixpoint();
1912
216
    return ChangeStatus::CHANGED;
1913
216
  }
1914
3
1915
3
  updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1916
3
1917
3
  return BeforeState == static_cast<DerefState>(*this) ? 
ChangeStatus::UNCHANGED2
1918
3
                                                       : 
ChangeStatus::CHANGED1
;
1919
3
}
1920
1921
/// Dereferenceable attribute for a call site argument.
1922
struct AADereferenceableCallSiteArgument : AADereferenceableImpl {
1923
1924
  /// See AADereferenceableImpl::AADereferenceableImpl(...).
1925
  AADereferenceableCallSiteArgument(CallSite CS, unsigned ArgNo,
1926
                                    InformationCache &InfoCache)
1927
      : AADereferenceableImpl(CS.getArgOperand(ArgNo), *CS.getInstruction(),
1928
                              InfoCache),
1929
375
        ArgNo(ArgNo) {}
1930
1931
  /// See AbstractAttribute::initialize(...).
1932
488
  void initialize(Attributor &A) override {
1933
488
    CallSite CS(&getAnchoredValue());
1934
488
    if (CS.paramHasAttr(ArgNo, Attribute::Dereferenceable))
1935
16
      takeKnownDerefBytesMaximum(CS.getDereferenceableBytes(ArgNo));
1936
488
1937
488
    if (CS.paramHasAttr(ArgNo, Attribute::DereferenceableOrNull))
1938
0
      takeKnownDerefBytesMaximum(CS.getDereferenceableOrNullBytes(ArgNo));
1939
488
  }
1940
1941
  /// See AbstractAttribute::updateImpl(Attributor &A).
1942
  ChangeStatus updateImpl(Attributor &A) override;
1943
1944
  /// See AbstractAttribute::getManifestPosition().
1945
45
  ManifestPosition getManifestPosition() const override {
1946
45
    return MP_CALL_SITE_ARGUMENT;
1947
45
  };
1948
1949
  // Return argument index of associated value.
1950
0
  int getArgNo() const { return ArgNo; }
1951
1952
private:
1953
  unsigned ArgNo;
1954
};
1955
1956
808
ChangeStatus AADereferenceableCallSiteArgument::updateImpl(Attributor &A) {
1957
808
  // NOTE: Never look at the argument of the callee in this method.
1958
808
  //       If we do this, "dereferenceable" is always deduced because of the
1959
808
  //       assumption.
1960
808
1961
808
  Value &V = *getAssociatedValue();
1962
808
1963
808
  auto BeforeState = static_cast<DerefState>(*this);
1964
808
1965
808
  syncNonNull(A.getAAFor<AANonNull>(*this, getAnchoredValue(), ArgNo));
1966
808
  bool IsNonNull = isAssumedNonNull();
1967
808
  bool IsGlobal = isKnownGlobal();
1968
808
1969
808
  takeAssumedDerefBytesMinimum(
1970
808
      computeAssumedDerefenceableBytes(A, V, IsNonNull, IsGlobal));
1971
808
  updateAssumedNonNullGlobalState(IsNonNull, IsGlobal);
1972
808
1973
808
  return BeforeState == static_cast<DerefState>(*this) ? 
ChangeStatus::UNCHANGED402
1974
808
                                                       : 
ChangeStatus::CHANGED406
;
1975
808
}
1976
1977
/// ----------------------------------------------------------------------------
1978
///                               Attributor
1979
/// ----------------------------------------------------------------------------
1980
1981
bool Attributor::checkForAllCallSites(Function &F,
1982
                                      std::function<bool(CallSite)> &Pred,
1983
428
                                      bool RequireAllCallSites) {
1984
428
  // We can try to determine information from
1985
428
  // the call sites. However, this is only possible all call sites are known,
1986
428
  // hence the function has internal linkage.
1987
428
  if (RequireAllCallSites && !F.hasInternalLinkage()) {
1988
385
    LLVM_DEBUG(
1989
385
        dbgs()
1990
385
        << "Attributor: Function " << F.getName()
1991
385
        << " has no internal linkage, hence not all call sites are known\n");
1992
385
    return false;
1993
385
  }
1994
43
1995
111
  
for (const Use &U : F.uses())43
{
1996
111
1997
111
    CallSite CS(U.getUser());
1998
111
    if (!CS || !CS.isCallee(&U) || !CS.getCaller()->hasExactDefinition()) {
1999
0
      if (!RequireAllCallSites)
2000
0
        continue;
2001
0
2002
0
      LLVM_DEBUG(dbgs() << "Attributor: User " << *U.getUser()
2003
0
                        << " is an invalid use of " << F.getName() << "\n");
2004
0
      return false;
2005
0
    }
2006
111
2007
111
    if (Pred(CS))
2008
74
      continue;
2009
37
2010
37
    LLVM_DEBUG(dbgs() << "Attributor: Call site callback failed for "
2011
37
                      << *CS.getInstruction() << "\n");
2012
37
    return false;
2013
37
  }
2014
43
2015
43
  
return true6
;
2016
43
}
2017
2018
19
ChangeStatus Attributor::run() {
2019
19
  // Initialize all abstract attributes.
2020
19
  for (AbstractAttribute *AA : AllAbstractAttributes)
2021
3.53k
    AA->initialize(*this);
2022
19
2023
19
  LLVM_DEBUG(dbgs() << "[Attributor] Identified and initialized "
2024
19
                    << AllAbstractAttributes.size()
2025
19
                    << " abstract attributes.\n");
2026
19
2027
19
  // Now that all abstract attributes are collected and initialized we start
2028
19
  // the abstract analysis.
2029
19
2030
19
  unsigned IterationCounter = 1;
2031
19
2032
19
  SmallVector<AbstractAttribute *, 64> ChangedAAs;
2033
19
  SetVector<AbstractAttribute *> Worklist;
2034
19
  Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
2035
19
2036
55
  do {
2037
55
    LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
2038
55
                      << ", Worklist size: " << Worklist.size() << "\n");
2039
55
2040
55
    // Add all abstract attributes that are potentially dependent on one that
2041
55
    // changed to the work list.
2042
2.03k
    for (AbstractAttribute *ChangedAA : ChangedAAs) {
2043
2.03k
      auto &QuerriedAAs = QueryMap[ChangedAA];
2044
2.03k
      Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
2045
2.03k
    }
2046
55
2047
55
    // Reset the changed set.
2048
55
    ChangedAAs.clear();
2049
55
2050
55
    // Update all abstract attribute in the work list and record the ones that
2051
55
    // changed.
2052
55
    for (AbstractAttribute *AA : Worklist)
2053
5.74k
      if (AA->update(*this) == ChangeStatus::CHANGED)
2054
2.03k
        ChangedAAs.push_back(AA);
2055
55
2056
55
    // Reset the work list and repopulate with the changed abstract attributes.
2057
55
    // Note that dependent ones are added above.
2058
55
    Worklist.clear();
2059
55
    Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
2060
55
2061
55
  } while (!Worklist.empty() && 
++IterationCounter < MaxFixpointIterations36
);
2062
19
2063
19
  LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
2064
19
                    << IterationCounter << "/" << MaxFixpointIterations
2065
19
                    << " iterations\n");
2066
19
2067
19
  bool FinishedAtFixpoint = Worklist.empty();
2068
19
2069
19
  // Reset abstract arguments not settled in a sound fixpoint by now. This
2070
19
  // happens when we stopped the fixpoint iteration early. Note that only the
2071
19
  // ones marked as "changed" *and* the ones transitively depending on them
2072
19
  // need to be reverted to a pessimistic state. Others might not be in a
2073
19
  // fixpoint state but we can use the optimistic results for them anyway.
2074
19
  SmallPtrSet<AbstractAttribute *, 32> Visited;
2075
19
  for (unsigned u = 0; u < ChangedAAs.size(); 
u++0
) {
2076
0
    AbstractAttribute *ChangedAA = ChangedAAs[u];
2077
0
    if (!Visited.insert(ChangedAA).second)
2078
0
      continue;
2079
0
2080
0
    AbstractState &State = ChangedAA->getState();
2081
0
    if (!State.isAtFixpoint()) {
2082
0
      State.indicatePessimisticFixpoint();
2083
0
2084
0
      NumAttributesTimedOut++;
2085
0
    }
2086
0
2087
0
    auto &QuerriedAAs = QueryMap[ChangedAA];
2088
0
    ChangedAAs.append(QuerriedAAs.begin(), QuerriedAAs.end());
2089
0
  }
2090
19
2091
19
  LLVM_DEBUG({
2092
19
    if (!Visited.empty())
2093
19
      dbgs() << "\n[Attributor] Finalized " << Visited.size()
2094
19
             << " abstract attributes.\n";
2095
19
  });
2096
19
2097
19
  unsigned NumManifested = 0;
2098
19
  unsigned NumAtFixpoint = 0;
2099
19
  ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
2100
3.53k
  for (AbstractAttribute *AA : AllAbstractAttributes) {
2101
3.53k
    AbstractState &State = AA->getState();
2102
3.53k
2103
3.53k
    // If there is not already a fixpoint reached, we can now take the
2104
3.53k
    // optimistic state. This is correct because we enforced a pessimistic one
2105
3.53k
    // on abstract attributes that were transitively dependent on a changed one
2106
3.53k
    // already above.
2107
3.53k
    if (!State.isAtFixpoint())
2108
1.31k
      State.indicateOptimisticFixpoint();
2109
3.53k
2110
3.53k
    // If the state is invalid, we do not try to manifest it.
2111
3.53k
    if (!State.isValidState())
2112
2.18k
      continue;
2113
1.34k
2114
1.34k
    // Manifest the state and record if we changed the IR.
2115
1.34k
    ChangeStatus LocalChange = AA->manifest(*this);
2116
1.34k
    ManifestChange = ManifestChange | LocalChange;
2117
1.34k
2118
1.34k
    NumAtFixpoint++;
2119
1.34k
    NumManifested += (LocalChange == ChangeStatus::CHANGED);
2120
1.34k
  }
2121
19
2122
19
  (void)NumManifested;
2123
19
  (void)NumAtFixpoint;
2124
19
  LLVM_DEBUG(dbgs() << "\n[Attributor] Manifested " << NumManifested
2125
19
                    << " arguments while " << NumAtFixpoint
2126
19
                    << " were in a valid fixpoint state\n");
2127
19
2128
19
  // If verification is requested, we finished this run at a fixpoint, and the
2129
19
  // IR was changed, we re-run the whole fixpoint analysis, starting at
2130
19
  // re-initialization of the arguments. This re-run should not result in an IR
2131
19
  // change. Though, the (virtual) state of attributes at the end of the re-run
2132
19
  // might be more optimistic than the known state or the IR state if the better
2133
19
  // state cannot be manifested.
2134
19
  if (VerifyAttributor && 
FinishedAtFixpoint3
&&
2135
19
      
ManifestChange == ChangeStatus::CHANGED3
) {
2136
3
    VerifyAttributor = false;
2137
3
    ChangeStatus VerifyStatus = run();
2138
3
    if (VerifyStatus != ChangeStatus::UNCHANGED)
2139
3
      
llvm_unreachable0
(
2140
3
          "Attributor verification failed, re-run did result in an IR change "
2141
3
          "even after a fixpoint was reached in the original run. (False "
2142
3
          "positives possible!)");
2143
3
    VerifyAttributor = true;
2144
3
  }
2145
19
2146
19
  NumAttributesManifested += NumManifested;
2147
19
  NumAttributesValidFixpoint += NumAtFixpoint;
2148
19
2149
19
  return ManifestChange;
2150
19
}
2151
2152
void Attributor::identifyDefaultAbstractAttributes(
2153
    Function &F, InformationCache &InfoCache,
2154
248
    DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
2155
248
2156
248
  // Every function can be nounwind.
2157
248
  registerAA(*new AANoUnwindFunction(F, InfoCache));
2158
248
2159
248
  // Every function might be marked "nosync"
2160
248
  registerAA(*new AANoSyncFunction(F, InfoCache));
2161
248
2162
248
  // Every function might be "no-free".
2163
248
  registerAA(*new AANoFreeFunction(F, InfoCache));
2164
248
2165
248
  // Return attributes are only appropriate if the return type is non void.
2166
248
  Type *ReturnType = F.getReturnType();
2167
248
  if (!ReturnType->isVoidTy()) {
2168
180
    // Argument attribute "returned" --- Create only one per function even
2169
180
    // though it is an argument attribute.
2170
180
    if (!Whitelist || 
Whitelist->count(AAReturnedValues::ID)0
)
2171
180
      registerAA(*new AAReturnedValuesImpl(F, InfoCache));
2172
180
2173
180
    if (ReturnType->isPointerTy()) {
2174
120
      // Every function with pointer return type might be marked nonnull.
2175
120
      if (!Whitelist || 
Whitelist->count(AANonNullReturned::ID)0
)
2176
120
        registerAA(*new AANonNullReturned(F, InfoCache));
2177
120
2178
120
      // Every function with pointer return type might be marked noalias.
2179
120
      if (!Whitelist || 
Whitelist->count(AANoAliasReturned::ID)0
)
2180
120
        registerAA(*new AANoAliasReturned(F, InfoCache));
2181
120
2182
120
      // Every function with pointer return type might be marked
2183
120
      // dereferenceable.
2184
120
      if (ReturnType->isPointerTy() &&
2185
120
          (!Whitelist || 
Whitelist->count(AADereferenceableReturned::ID)0
))
2186
120
        registerAA(*new AADereferenceableReturned(F, InfoCache));
2187
120
    }
2188
180
  }
2189
248
2190
291
  for (Argument &Arg : F.args()) {
2191
291
    if (Arg.getType()->isPointerTy()) {
2192
216
      // Every argument with pointer type might be marked nonnull.
2193
216
      if (!Whitelist || 
Whitelist->count(AANonNullArgument::ID)0
)
2194
216
        registerAA(*new AANonNullArgument(Arg, InfoCache));
2195
216
2196
216
      // Every argument with pointer type might be marked dereferenceable.
2197
216
      if (!Whitelist || 
Whitelist->count(AADereferenceableArgument::ID)0
)
2198
216
        registerAA(*new AADereferenceableArgument(Arg, InfoCache));
2199
216
    }
2200
291
  }
2201
248
2202
248
  // Every function might be "will-return".
2203
248
  registerAA(*new AAWillReturnFunction(F, InfoCache));
2204
248
2205
248
  // Check for dead BasicBlocks in every function.
2206
248
  registerAA(*new AAIsDeadFunction(F, InfoCache));
2207
248
2208
248
  // Walk all instructions to find more attribute opportunities and also
2209
248
  // interesting instructions that might be queried by abstract attributes
2210
248
  // during their initialization or update.
2211
248
  auto &ReadOrWriteInsts = InfoCache.FuncRWInstsMap[&F];
2212
248
  auto &InstOpcodeMap = InfoCache.FuncInstOpcodeMap[&F];
2213
248
2214
1.31k
  for (Instruction &I : instructions(&F)) {
2215
1.31k
    bool IsInterestingOpcode = false;
2216
1.31k
2217
1.31k
    // To allow easy access to all instructions in a function with a given
2218
1.31k
    // opcode we store them in the InfoCache. As not all opcodes are interesting
2219
1.31k
    // to concrete attributes we only cache the ones that are as identified in
2220
1.31k
    // the following switch.
2221
1.31k
    // Note: There are no concrete attributes now so this is initially empty.
2222
1.31k
    switch (I.getOpcode()) {
2223
1.31k
    default:
2224
633
      assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
2225
633
             "New call site/base instruction type needs to be known int the "
2226
633
             "attributor.");
2227
633
      break;
2228
1.31k
    case Instruction::Call:
2229
679
    case Instruction::CallBr:
2230
679
    case Instruction::Invoke:
2231
679
    case Instruction::CleanupRet:
2232
679
    case Instruction::CatchSwitch:
2233
679
    case Instruction::Resume:
2234
679
    case Instruction::Ret:
2235
679
      IsInterestingOpcode = true;
2236
1.31k
    }
2237
1.31k
    if (IsInterestingOpcode)
2238
679
      InstOpcodeMap[I.getOpcode()].push_back(&I);
2239
1.31k
    if (I.mayReadOrWriteMemory())
2240
383
      ReadOrWriteInsts.push_back(&I);
2241
1.31k
2242
1.31k
    CallSite CS(&I);
2243
1.31k
    if (CS && 
CS.getCalledFunction()409
) {
2244
980
      for (int i = 0, e = CS.getCalledFunction()->arg_size(); i < e; 
i++572
) {
2245
572
        if (!CS.getArgument(i)->getType()->isPointerTy())
2246
197
          continue;
2247
375
2248
375
        // Call site argument attribute "non-null".
2249
375
        if (!Whitelist || 
Whitelist->count(AANonNullCallSiteArgument::ID)0
)
2250
375
          registerAA(*new AANonNullCallSiteArgument(CS, i, InfoCache), i);
2251
375
2252
375
        // Call site argument attribute "dereferenceable".
2253
375
        if (!Whitelist ||
2254
375
            
Whitelist->count(AADereferenceableCallSiteArgument::ID)0
)
2255
375
          registerAA(*new AADereferenceableCallSiteArgument(CS, i, InfoCache),
2256
375
                     i);
2257
375
      }
2258
408
    }
2259
1.31k
  }
2260
248
}
2261
2262
/// Helpers to ease debugging through output streams and print calls.
2263
///
2264
///{
2265
0
raw_ostream &llvm::operator<<(raw_ostream &OS, ChangeStatus S) {
2266
0
  return OS << (S == ChangeStatus::CHANGED ? "changed" : "unchanged");
2267
0
}
2268
2269
raw_ostream &llvm::operator<<(raw_ostream &OS,
2270
0
                              AbstractAttribute::ManifestPosition AP) {
2271
0
  switch (AP) {
2272
0
  case AbstractAttribute::MP_ARGUMENT:
2273
0
    return OS << "arg";
2274
0
  case AbstractAttribute::MP_CALL_SITE_ARGUMENT:
2275
0
    return OS << "cs_arg";
2276
0
  case AbstractAttribute::MP_FUNCTION:
2277
0
    return OS << "fn";
2278
0
  case AbstractAttribute::MP_RETURNED:
2279
0
    return OS << "fn_ret";
2280
0
  }
2281
0
  llvm_unreachable("Unknown attribute position!");
2282
0
}
2283
2284
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractState &S) {
2285
0
  return OS << (!S.isValidState() ? "top" : (S.isAtFixpoint() ? "fix" : ""));
2286
0
}
2287
2288
0
raw_ostream &llvm::operator<<(raw_ostream &OS, const AbstractAttribute &AA) {
2289
0
  AA.print(OS);
2290
0
  return OS;
2291
0
}
2292
2293
0
void AbstractAttribute::print(raw_ostream &OS) const {
2294
0
  OS << "[" << getManifestPosition() << "][" << getAsStr() << "]["
2295
0
     << AnchoredVal.getName() << "]";
2296
0
}
2297
///}
2298
2299
/// ----------------------------------------------------------------------------
2300
///                       Pass (Manager) Boilerplate
2301
/// ----------------------------------------------------------------------------
2302
2303
13.4k
static bool runAttributorOnModule(Module &M) {
2304
13.4k
  if (DisableAttributor)
2305
13.4k
    return false;
2306
15
2307
15
  LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
2308
15
                    << " functions.\n");
2309
15
2310
15
  // Create an Attributor and initially empty information cache that is filled
2311
15
  // while we identify default attribute opportunities.
2312
15
  Attributor A;
2313
15
  InformationCache InfoCache;
2314
15
2315
318
  for (Function &F : M) {
2316
318
    // TODO: Not all attributes require an exact definition. Find a way to
2317
318
    //       enable deduction for some but not all attributes in case the
2318
318
    //       definition might be changed at runtime, see also
2319
318
    //       http://lists.llvm.org/pipermail/llvm-dev/2018-February/121275.html.
2320
318
    // TODO: We could always determine abstract attributes and if sufficient
2321
318
    //       information was found we could duplicate the functions that do not
2322
318
    //       have an exact definition.
2323
318
    if (!F.hasExactDefinition()) {
2324
70
      NumFnWithoutExactDefinition++;
2325
70
      continue;
2326
70
    }
2327
248
2328
248
    // For now we ignore naked and optnone functions.
2329
248
    if (F.hasFnAttribute(Attribute::Naked) ||
2330
248
        F.hasFnAttribute(Attribute::OptimizeNone))
2331
0
      continue;
2332
248
2333
248
    NumFnWithExactDefinition++;
2334
248
2335
248
    // Populate the Attributor with abstract attribute opportunities in the
2336
248
    // function and the information cache with IR information.
2337
248
    A.identifyDefaultAbstractAttributes(F, InfoCache);
2338
248
  }
2339
15
2340
15
  return A.run() == ChangeStatus::CHANGED;
2341
15
}
2342
2343
0
PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
2344
0
  if (runAttributorOnModule(M)) {
2345
0
    // FIXME: Think about passes we will preserve and add them here.
2346
0
    return PreservedAnalyses::none();
2347
0
  }
2348
0
  return PreservedAnalyses::all();
2349
0
}
2350
2351
namespace {
2352
2353
struct AttributorLegacyPass : public ModulePass {
2354
  static char ID;
2355
2356
13.4k
  AttributorLegacyPass() : ModulePass(ID) {
2357
13.4k
    initializeAttributorLegacyPassPass(*PassRegistry::getPassRegistry());
2358
13.4k
  }
2359
2360
13.4k
  bool runOnModule(Module &M) override {
2361
13.4k
    if (skipModule(M))
2362
2
      return false;
2363
13.4k
    return runAttributorOnModule(M);
2364
13.4k
  }
2365
2366
13.4k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
2367
13.4k
    // FIXME: Think about passes we will preserve and add them here.
2368
13.4k
    AU.setPreservesCFG();
2369
13.4k
  }
2370
};
2371
2372
} // end anonymous namespace
2373
2374
13.4k
Pass *llvm::createAttributorLegacyPass() { return new AttributorLegacyPass(); }
2375
2376
char AttributorLegacyPass::ID = 0;
2377
23.9k
INITIALIZE_PASS_BEGIN(AttributorLegacyPass, "attributor",
2378
23.9k
                      "Deduce and propagate attributes", false, false)
2379
23.9k
INITIALIZE_PASS_END(AttributorLegacyPass, "attributor",
2380
                    "Deduce and propagate attributes", false, false)