llvm.org GIT mirror llvm / c94da20 lib / Analysis / CFLAliasAnalysis.cpp
c94da20

Tree @c94da20 (Download .tar.gz)

CFLAliasAnalysis.cpp @c94da20raw · history · blame

   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
 137
 138
 139
 140
 141
 142
 143
 144
 145
 146
 147
 148
 149
 150
 151
 152
 153
 154
 155
 156
 157
 158
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179
 180
 181
 182
 183
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194
 195
 196
 197
 198
 199
 200
 201
 202
 203
 204
 205
 206
 207
 208
 209
 210
 211
 212
 213
 214
 215
 216
 217
 218
 219
 220
 221
 222
 223
 224
 225
 226
 227
 228
 229
 230
 231
 232
 233
 234
 235
 236
 237
 238
 239
 240
 241
 242
 243
 244
 245
 246
 247
 248
 249
 250
 251
 252
 253
 254
 255
 256
 257
 258
 259
 260
 261
 262
 263
 264
 265
 266
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277
 278
 279
 280
 281
 282
 283
 284
 285
 286
 287
 288
 289
 290
 291
 292
 293
 294
 295
 296
 297
 298
 299
 300
 301
 302
 303
 304
 305
 306
 307
 308
 309
 310
 311
 312
 313
 314
 315
 316
 317
 318
 319
 320
 321
 322
 323
 324
 325
 326
 327
 328
 329
 330
 331
 332
 333
 334
 335
 336
 337
 338
 339
 340
 341
 342
 343
 344
 345
 346
 347
 348
 349
 350
 351
 352
 353
 354
 355
 356
 357
 358
 359
 360
 361
 362
 363
 364
 365
 366
 367
 368
 369
 370
 371
 372
 373
 374
 375
 376
 377
 378
 379
 380
 381
 382
 383
 384
 385
 386
 387
 388
 389
 390
 391
 392
 393
 394
 395
 396
 397
 398
 399
 400
 401
 402
 403
 404
 405
 406
 407
 408
 409
 410
 411
 412
 413
 414
 415
 416
 417
 418
 419
 420
 421
 422
 423
 424
 425
 426
 427
 428
 429
 430
 431
 432
 433
 434
 435
 436
 437
 438
 439
 440
 441
 442
 443
 444
 445
 446
 447
 448
 449
 450
 451
 452
 453
 454
 455
 456
 457
 458
 459
 460
 461
 462
 463
 464
 465
 466
 467
 468
 469
 470
 471
 472
 473
 474
 475
 476
 477
 478
 479
 480
 481
 482
 483
 484
 485
 486
 487
 488
 489
 490
 491
 492
 493
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503
 504
 505
 506
 507
 508
 509
 510
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520
 521
 522
 523
 524
 525
 526
 527
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537
 538
 539
 540
 541
 542
 543
 544
 545
 546
 547
 548
 549
 550
 551
 552
 553
 554
 555
 556
 557
 558
 559
 560
 561
 562
 563
 564
 565
 566
 567
 568
 569
 570
 571
 572
 573
 574
 575
 576
 577
 578
 579
 580
 581
 582
 583
 584
 585
 586
 587
 588
 589
 590
 591
 592
 593
 594
 595
 596
 597
 598
 599
 600
 601
 602
 603
 604
 605
 606
 607
 608
 609
 610
 611
 612
 613
 614
 615
 616
 617
 618
 619
 620
 621
 622
 623
 624
 625
 626
 627
 628
 629
 630
 631
 632
 633
 634
 635
 636
 637
 638
 639
 640
 641
 642
 643
 644
 645
 646
 647
 648
 649
 650
 651
 652
 653
 654
 655
 656
 657
 658
 659
 660
 661
 662
 663
 664
 665
 666
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
//===- CFLAliasAnalysis.cpp - CFL-Based Alias Analysis Implementation ------==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements a CFL-based context-insensitive alias analysis
// algorithm. It does not depend on types. The algorithm is a mixture of the one
// described in "Demand-driven alias analysis for C" by Xin Zheng and Radu
// Rugina, and "Fast algorithms for Dyck-CFL-reachability with applications to
// Alias Analysis" by Zhang Q, Lyu M R, Yuan H, and Su Z. -- to summarize the
// papers, we build a graph of the uses of a variable, where each node is a
// memory location, and each edge is an action that happened on that memory
// location.  The "actions" can be one of Dereference, Reference, Assign, or
// Assign.
//
// Two variables are considered as aliasing iff you can reach one value's node
// from the other value's node and the language formed by concatenating all of
// the edge labels (actions) conforms to a context-free grammar.
//
// Because this algorithm requires a graph search on each query, we execute the
// algorithm outlined in "Fast algorithms..." (mentioned above)
// in order to transform the graph into sets of variables that may alias in
// ~nlogn time (n = number of variables.), which makes queries take constant
// time.
//===----------------------------------------------------------------------===//

#include "StratifiedSets.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/None.h"
#include "llvm/ADT/Optional.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/Passes.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/ValueHandle.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
#include <forward_list>
#include <tuple>

using namespace llvm;

#define DEBUG_TYPE "cfl-aa"

// Try to go from a Value* to a Function*. Never returns nullptr.
static Optional<Function *> parentFunctionOfValue(Value *);

// Returns possible functions called by the Inst* into the given
// SmallVectorImpl. Returns true if targets found, false otherwise.
// This is templated because InvokeInst/CallInst give us the same
// set of functions that we care about, and I don't like repeating
// myself.
template <typename Inst>
static bool getPossibleTargets(Inst *, SmallVectorImpl<Function *> &);

// Some instructions need to have their users tracked. Instructions like
// `add` require you to get the users of the Instruction* itself, other
// instructions like `store` require you to get the users of the first
// operand. This function gets the "proper" value to track for each
// type of instruction we support.
static Optional<Value *> getTargetValue(Instruction *);

// There are certain instructions (i.e. FenceInst, etc.) that we ignore.
// This notes that we should ignore those.
static bool hasUsefulEdges(Instruction *);

const StratifiedIndex StratifiedLink::SetSentinel =
  std::numeric_limits<StratifiedIndex>::max();

namespace {
// StratifiedInfo Attribute things.
typedef unsigned StratifiedAttr;
LLVM_CONSTEXPR unsigned MaxStratifiedAttrIndex = NumStratifiedAttrs;
LLVM_CONSTEXPR unsigned AttrAllIndex = 0;
LLVM_CONSTEXPR unsigned AttrGlobalIndex = 1;
LLVM_CONSTEXPR unsigned AttrFirstArgIndex = 2;
LLVM_CONSTEXPR unsigned AttrLastArgIndex = MaxStratifiedAttrIndex;
LLVM_CONSTEXPR unsigned AttrMaxNumArgs = AttrLastArgIndex - AttrFirstArgIndex;

LLVM_CONSTEXPR StratifiedAttr AttrNone = 0;
LLVM_CONSTEXPR StratifiedAttr AttrAll = ~AttrNone;

// \brief StratifiedSets call for knowledge of "direction", so this is how we
// represent that locally.
enum class Level { Same, Above, Below };

// \brief Edges can be one of four "weights" -- each weight must have an inverse
// weight (Assign has Assign; Reference has Dereference).
enum class EdgeType {
  // The weight assigned when assigning from or to a value. For example, in:
  // %b = getelementptr %a, 0
  // ...The relationships are %b assign %a, and %a assign %b. This used to be
  // two edges, but having a distinction bought us nothing.
  Assign,

  // The edge used when we have an edge going from some handle to a Value.
  // Examples of this include:
  // %b = load %a              (%b Dereference %a)
  // %b = extractelement %a, 0 (%a Dereference %b)
  Dereference,

  // The edge used when our edge goes from a value to a handle that may have
  // contained it at some point. Examples:
  // %b = load %a              (%a Reference %b)
  // %b = extractelement %a, 0 (%b Reference %a)
  Reference
};

// \brief Encodes the notion of a "use"
struct Edge {
  // \brief Which value the edge is coming from
  Value *From;

  // \brief Which value the edge is pointing to
  Value *To;

  // \brief Edge weight
  EdgeType Weight;

  // \brief Whether we aliased any external values along the way that may be
  // invisible to the analysis (i.e. landingpad for exceptions, calls for
  // interprocedural analysis, etc.)
  StratifiedAttrs AdditionalAttrs;

  Edge(Value *From, Value *To, EdgeType W, StratifiedAttrs A)
      : From(From), To(To), Weight(W), AdditionalAttrs(A) {}
};

// \brief Information we have about a function and would like to keep around
struct FunctionInfo {
  StratifiedSets<Value *> Sets;
  // Lots of functions have < 4 returns. Adjust as necessary.
  SmallVector<Value *, 4> ReturnedValues;

  FunctionInfo(StratifiedSets<Value *> &&S,
               SmallVector<Value *, 4> &&RV)
    : Sets(std::move(S)), ReturnedValues(std::move(RV)) {}
};

struct CFLAliasAnalysis;

struct FunctionHandle : public CallbackVH {
  FunctionHandle(Function *Fn, CFLAliasAnalysis *CFLAA)
      : CallbackVH(Fn), CFLAA(CFLAA) {
    assert(Fn != nullptr);
    assert(CFLAA != nullptr);
  }

  virtual ~FunctionHandle() {}

  void deleted() override { removeSelfFromCache(); }
  void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }

private:
  CFLAliasAnalysis *CFLAA;

  void removeSelfFromCache();
};

struct CFLAliasAnalysis : public ImmutablePass, public AliasAnalysis {
private:
  /// \brief Cached mapping of Functions to their StratifiedSets.
  /// If a function's sets are currently being built, it is marked
  /// in the cache as an Optional without a value. This way, if we
  /// have any kind of recursion, it is discernable from a function
  /// that simply has empty sets.
  DenseMap<Function *, Optional<FunctionInfo>> Cache;
  std::forward_list<FunctionHandle> Handles;

public:
  static char ID;

  CFLAliasAnalysis() : ImmutablePass(ID) {
    initializeCFLAliasAnalysisPass(*PassRegistry::getPassRegistry());
  }

  virtual ~CFLAliasAnalysis() {}

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AliasAnalysis::getAnalysisUsage(AU);
  }

  void *getAdjustedAnalysisPointer(const void *ID) override {
    if (ID == &AliasAnalysis::ID)
      return (AliasAnalysis *)this;
    return this;
  }

  /// \brief Inserts the given Function into the cache.
  void scan(Function *Fn);

  void evict(Function *Fn) { Cache.erase(Fn); }

  /// \brief Ensures that the given function is available in the cache.
  /// Returns the appropriate entry from the cache.
  const Optional<FunctionInfo> &ensureCached(Function *Fn) {
    auto Iter = Cache.find(Fn);
    if (Iter == Cache.end()) {
      scan(Fn);
      Iter = Cache.find(Fn);
      assert(Iter != Cache.end());
      assert(Iter->second.hasValue());
    }
    return Iter->second;
  }

  AliasResult query(const Location &LocA, const Location &LocB);

  AliasResult alias(const Location &LocA, const Location &LocB) override {
    if (LocA.Ptr == LocB.Ptr) {
      if (LocA.Size == LocB.Size) {
        return MustAlias;
      } else {
        return PartialAlias;
      }
    }

    // Comparisons between global variables and other constants should be
    // handled by BasicAA.
    if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
      return AliasAnalysis::alias(LocA, LocB);
    }

    AliasResult QueryResult = query(LocA, LocB);
    if (QueryResult == MayAlias)
      return AliasAnalysis::alias(LocA, LocB);

    return QueryResult;
  }

  bool doInitialization(Module &M) override;
};

void FunctionHandle::removeSelfFromCache() {
  assert(CFLAA != nullptr);
  auto *Val = getValPtr();
  CFLAA->evict(cast<Function>(Val));
  setValPtr(nullptr);
}

// \brief Gets the edges our graph should have, based on an Instruction*
class GetEdgesVisitor : public InstVisitor<GetEdgesVisitor, void> {
  CFLAliasAnalysis &AA;
  SmallVectorImpl<Edge> &Output;

public:
  GetEdgesVisitor(CFLAliasAnalysis &AA, SmallVectorImpl<Edge> &Output)
      : AA(AA), Output(Output) {}

  void visitInstruction(Instruction &) {
    llvm_unreachable("Unsupported instruction encountered");
  }

  void visitCastInst(CastInst &Inst) {
    Output.push_back(Edge(&Inst, Inst.getOperand(0), EdgeType::Assign,
                          AttrNone));
  }

  void visitBinaryOperator(BinaryOperator &Inst) {
    auto *Op1 = Inst.getOperand(0);
    auto *Op2 = Inst.getOperand(1);
    Output.push_back(Edge(&Inst, Op1, EdgeType::Assign, AttrNone));
    Output.push_back(Edge(&Inst, Op2, EdgeType::Assign, AttrNone));
  }

  void visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
    auto *Ptr = Inst.getPointerOperand();
    auto *Val = Inst.getNewValOperand();
    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
  }

  void visitAtomicRMWInst(AtomicRMWInst &Inst) {
    auto *Ptr = Inst.getPointerOperand();
    auto *Val = Inst.getValOperand();
    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
  }

  void visitPHINode(PHINode &Inst) {
    for (unsigned I = 0, E = Inst.getNumIncomingValues(); I != E; ++I) {
      Value *Val = Inst.getIncomingValue(I);
      Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone));
    }
  }

  void visitGetElementPtrInst(GetElementPtrInst &Inst) {
    auto *Op = Inst.getPointerOperand();
    Output.push_back(Edge(&Inst, Op, EdgeType::Assign, AttrNone));
    for (auto I = Inst.idx_begin(), E = Inst.idx_end(); I != E; ++I)
      Output.push_back(Edge(&Inst, *I, EdgeType::Assign, AttrNone));
  }

  void visitSelectInst(SelectInst &Inst) {
    // Condition is not processed here (The actual statement producing
    // the condition result is processed elsewhere). For select, the
    // condition is evaluated, but not loaded, stored, or assigned
    // simply as a result of being the condition of a select.

    auto *TrueVal = Inst.getTrueValue();
    Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone));
    auto *FalseVal = Inst.getFalseValue();
    Output.push_back(Edge(&Inst, FalseVal, EdgeType::Assign, AttrNone));
  }

  void visitAllocaInst(AllocaInst &) {}

  void visitLoadInst(LoadInst &Inst) {
    auto *Ptr = Inst.getPointerOperand();
    auto *Val = &Inst;
    Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone));
  }

  void visitStoreInst(StoreInst &Inst) {
    auto *Ptr = Inst.getPointerOperand();
    auto *Val = Inst.getValueOperand();
    Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
  }

  void visitVAArgInst(VAArgInst &Inst) {
    // We can't fully model va_arg here. For *Ptr = Inst.getOperand(0), it does
    // two things:
    //  1. Loads a value from *((T*)*Ptr).
    //  2. Increments (stores to) *Ptr by some target-specific amount.
    // For now, we'll handle this like a landingpad instruction (by placing the
    // result in its own group, and having that group alias externals).
    auto *Val = &Inst;
    Output.push_back(Edge(Val, Val, EdgeType::Assign, AttrAll));
  }

  static bool isFunctionExternal(Function *Fn) {
    return Fn->isDeclaration() || !Fn->hasLocalLinkage();
  }

  // Gets whether the sets at Index1 above, below, or equal to the sets at
  // Index2. Returns None if they are not in the same set chain.
  static Optional<Level> getIndexRelation(const StratifiedSets<Value *> &Sets,
                                          StratifiedIndex Index1,
                                          StratifiedIndex Index2) {
    if (Index1 == Index2)
      return Level::Same;

    const auto *Current = &Sets.getLink(Index1);
    while (Current->hasBelow()) {
      if (Current->Below == Index2)
        return Level::Below;
      Current = &Sets.getLink(Current->Below);
    }

    Current = &Sets.getLink(Index1);
    while (Current->hasAbove()) {
      if (Current->Above == Index2)
        return Level::Above;
      Current = &Sets.getLink(Current->Above);
    }

    return NoneType();
  }

  bool
  tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
                             Value *FuncValue,
                             const iterator_range<User::op_iterator> &Args) {
    const unsigned ExpectedMaxArgs = 8;
    const unsigned MaxSupportedArgs = 50;
    assert(Fns.size() > 0);

    // I put this here to give us an upper bound on time taken by IPA. Is it
    // really (realistically) needed? Keep in mind that we do have an n^2 algo.
    if (std::distance(Args.begin(), Args.end()) > (int) MaxSupportedArgs)
      return false;

    // Exit early if we'll fail anyway
    for (auto *Fn : Fns) {
      if (isFunctionExternal(Fn) || Fn->isVarArg())
        return false;
      auto &MaybeInfo = AA.ensureCached(Fn);
      if (!MaybeInfo.hasValue())
        return false;
    }

    SmallVector<Value *, ExpectedMaxArgs> Arguments(Args.begin(), Args.end());
    SmallVector<StratifiedInfo, ExpectedMaxArgs> Parameters;
    for (auto *Fn : Fns) {
      auto &Info = *AA.ensureCached(Fn);
      auto &Sets = Info.Sets;
      auto &RetVals = Info.ReturnedValues;

      Parameters.clear();
      for (auto &Param : Fn->args()) {
        auto MaybeInfo = Sets.find(&Param);
        // Did a new parameter somehow get added to the function/slip by?
        if (!MaybeInfo.hasValue())
          return false;
        Parameters.push_back(*MaybeInfo);
      }

      // Adding an edge from argument -> return value for each parameter that
      // may alias the return value
      for (unsigned I = 0, E = Parameters.size(); I != E; ++I) {
        auto &ParamInfo = Parameters[I];
        auto &ArgVal = Arguments[I];
        bool AddEdge = false;
        StratifiedAttrs Externals;
        for (unsigned X = 0, XE = RetVals.size(); X != XE; ++X) {
          auto MaybeInfo = Sets.find(RetVals[X]);
          if (!MaybeInfo.hasValue())
            return false;

          auto &RetInfo = *MaybeInfo;
          auto RetAttrs = Sets.getLink(RetInfo.Index).Attrs;
          auto ParamAttrs = Sets.getLink(ParamInfo.Index).Attrs;
          auto MaybeRelation =
              getIndexRelation(Sets, ParamInfo.Index, RetInfo.Index);
          if (MaybeRelation.hasValue()) {
            AddEdge = true;
            Externals |= RetAttrs | ParamAttrs;
          }
        }
        if (AddEdge)
          Output.push_back(Edge(FuncValue, ArgVal, EdgeType::Assign,
                            StratifiedAttrs().flip()));
      }

      if (Parameters.size() != Arguments.size())
        return false;

      // Adding edges between arguments for arguments that may end up aliasing
      // each other. This is necessary for functions such as
      // void foo(int** a, int** b) { *a = *b; }
      // (Technically, the proper sets for this would be those below
      // Arguments[I] and Arguments[X], but our algorithm will produce
      // extremely similar, and equally correct, results either way)
      for (unsigned I = 0, E = Arguments.size(); I != E; ++I) {
        auto &MainVal = Arguments[I];
        auto &MainInfo = Parameters[I];
        auto &MainAttrs = Sets.getLink(MainInfo.Index).Attrs;
        for (unsigned X = I + 1; X != E; ++X) {
          auto &SubInfo = Parameters[X];
          auto &SubVal = Arguments[X];
          auto &SubAttrs = Sets.getLink(SubInfo.Index).Attrs;
          auto MaybeRelation =
              getIndexRelation(Sets, MainInfo.Index, SubInfo.Index);

          if (!MaybeRelation.hasValue())
            continue;

          auto NewAttrs = SubAttrs | MainAttrs;
          Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs));
        }
      }
    }
    return true;
  }

  template <typename InstT> void visitCallLikeInst(InstT &Inst) {
    SmallVector<Function *, 4> Targets;
    if (getPossibleTargets(&Inst, Targets)) {
      if (tryInterproceduralAnalysis(Targets, &Inst, Inst.arg_operands()))
        return;
      // Cleanup from interprocedural analysis
      Output.clear();
    }

    for (Value *V : Inst.arg_operands())
      Output.push_back(Edge(&Inst, V, EdgeType::Assign, AttrAll));
  }

  void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); }

  void visitInvokeInst(InvokeInst &Inst) { visitCallLikeInst(Inst); }

  // Because vectors/aggregates are immutable and unaddressable,
  // there's nothing we can do to coax a value out of them, other
  // than calling Extract{Element,Value}. We can effectively treat
  // them as pointers to arbitrary memory locations we can store in
  // and load from.
  void visitExtractElementInst(ExtractElementInst &Inst) {
    auto *Ptr = Inst.getVectorOperand();
    auto *Val = &Inst;
    Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone));
  }

  void visitInsertElementInst(InsertElementInst &Inst) {
    auto *Vec = Inst.getOperand(0);
    auto *Val = Inst.getOperand(1);
    Output.push_back(Edge(&Inst, Vec, EdgeType::Assign, AttrNone));
    Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone));
  }

  void visitLandingPadInst(LandingPadInst &Inst) {
    // Exceptions come from "nowhere", from our analysis' perspective.
    // So we place the instruction its own group, noting that said group may
    // alias externals
    Output.push_back(Edge(&Inst, &Inst, EdgeType::Assign, AttrAll));
  }

  void visitInsertValueInst(InsertValueInst &Inst) {
    auto *Agg = Inst.getOperand(0);
    auto *Val = Inst.getOperand(1);
    Output.push_back(Edge(&Inst, Agg, EdgeType::Assign, AttrNone));
    Output.push_back(Edge(&Inst, Val, EdgeType::Dereference, AttrNone));
  }

  void visitExtractValueInst(ExtractValueInst &Inst) {
    auto *Ptr = Inst.getAggregateOperand();
    Output.push_back(Edge(&Inst, Ptr, EdgeType::Reference, AttrNone));
  }

  void visitShuffleVectorInst(ShuffleVectorInst &Inst) {
    auto *From1 = Inst.getOperand(0);
    auto *From2 = Inst.getOperand(1);
    Output.push_back(Edge(&Inst, From1, EdgeType::Assign, AttrNone));
    Output.push_back(Edge(&Inst, From2, EdgeType::Assign, AttrNone));
  }
};

// For a given instruction, we need to know which Value* to get the
// users of in order to build our graph. In some cases (i.e. add),
// we simply need the Instruction*. In other cases (i.e. store),
// finding the users of the Instruction* is useless; we need to find
// the users of the first operand. This handles determining which
// value to follow for us.
//
// Note: we *need* to keep this in sync with GetEdgesVisitor. Add
// something to GetEdgesVisitor, add it here -- remove something from
// GetEdgesVisitor, remove it here.
class GetTargetValueVisitor
    : public InstVisitor<GetTargetValueVisitor, Value *> {
public:
  Value *visitInstruction(Instruction &Inst) { return &Inst; }

  Value *visitStoreInst(StoreInst &Inst) { return Inst.getPointerOperand(); }

  Value *visitAtomicCmpXchgInst(AtomicCmpXchgInst &Inst) {
    return Inst.getPointerOperand();
  }

  Value *visitAtomicRMWInst(AtomicRMWInst &Inst) {
    return Inst.getPointerOperand();
  }

  Value *visitInsertElementInst(InsertElementInst &Inst) {
    return Inst.getOperand(0);
  }

  Value *visitInsertValueInst(InsertValueInst &Inst) {
    return Inst.getAggregateOperand();
  }
};

// Set building requires a weighted bidirectional graph.
template <typename EdgeTypeT> class WeightedBidirectionalGraph {
public:
  typedef std::size_t Node;

private:
  const static Node StartNode = Node(0);

  struct Edge {
    EdgeTypeT Weight;
    Node Other;

    Edge(const EdgeTypeT &W, const Node &N)
      : Weight(W), Other(N) {}

    bool operator==(const Edge &E) const {
      return Weight == E.Weight && Other == E.Other;
    }

    bool operator!=(const Edge &E) const { return !operator==(E); }
  };

  struct NodeImpl {
    std::vector<Edge> Edges;
  };

  std::vector<NodeImpl> NodeImpls;

  bool inbounds(Node NodeIndex) const { return NodeIndex < NodeImpls.size(); }

  const NodeImpl &getNode(Node N) const { return NodeImpls[N]; }
  NodeImpl &getNode(Node N) { return NodeImpls[N]; }

public:
  // ----- Various Edge iterators for the graph ----- //

  // \brief Iterator for edges. Because this graph is bidirected, we don't
  // allow modificaiton of the edges using this iterator. Additionally, the
  // iterator becomes invalid if you add edges to or from the node you're
  // getting the edges of.
  struct EdgeIterator : public std::iterator<std::forward_iterator_tag,
                                             std::tuple<EdgeTypeT, Node *>> {
    EdgeIterator(const typename std::vector<Edge>::const_iterator &Iter)
        : Current(Iter) {}

    EdgeIterator(NodeImpl &Impl) : Current(Impl.begin()) {}

    EdgeIterator &operator++() {
      ++Current;
      return *this;
    }

    EdgeIterator operator++(int) {
      EdgeIterator Copy(Current);
      operator++();
      return Copy;
    }

    std::tuple<EdgeTypeT, Node> &operator*() {
      Store = std::make_tuple(Current->Weight, Current->Other);
      return Store;
    }

    bool operator==(const EdgeIterator &Other) const {
      return Current == Other.Current;
    }

    bool operator!=(const EdgeIterator &Other) const {
      return !operator==(Other);
    }

  private:
    typename std::vector<Edge>::const_iterator Current;
    std::tuple<EdgeTypeT, Node> Store;
  };

  // Wrapper for EdgeIterator with begin()/end() calls.
  struct EdgeIterable {
    EdgeIterable(const std::vector<Edge> &Edges)
        : BeginIter(Edges.begin()), EndIter(Edges.end()) {}

    EdgeIterator begin() { return EdgeIterator(BeginIter); }

    EdgeIterator end() { return EdgeIterator(EndIter); }

  private:
    typename std::vector<Edge>::const_iterator BeginIter;
    typename std::vector<Edge>::const_iterator EndIter;
  };

  // ----- Actual graph-related things ----- //

  WeightedBidirectionalGraph() {}

  WeightedBidirectionalGraph(WeightedBidirectionalGraph<EdgeTypeT> &&Other)
      : NodeImpls(std::move(Other.NodeImpls)) {}

  WeightedBidirectionalGraph<EdgeTypeT> &
  operator=(WeightedBidirectionalGraph<EdgeTypeT> &&Other) {
    NodeImpls = std::move(Other.NodeImpls);
    return *this;
  }

  Node addNode() {
    auto Index = NodeImpls.size();
    auto NewNode = Node(Index);
    NodeImpls.push_back(NodeImpl());
    return NewNode;
  }

  void addEdge(Node From, Node To, const EdgeTypeT &Weight,
               const EdgeTypeT &ReverseWeight) {
    assert(inbounds(From));
    assert(inbounds(To));
    auto &FromNode = getNode(From);
    auto &ToNode = getNode(To);
    FromNode.Edges.push_back(Edge(Weight, To));
    ToNode.Edges.push_back(Edge(ReverseWeight, From));
  }

  EdgeIterable edgesFor(const Node &N) const {
    const auto &Node = getNode(N);
    return EdgeIterable(Node.Edges);
  }

  bool empty() const { return NodeImpls.empty(); }
  std::size_t size() const { return NodeImpls.size(); }

  // \brief Gets an arbitrary node in the graph as a starting point for
  // traversal.
  Node getEntryNode() {
    assert(inbounds(StartNode));
    return StartNode;
  }
};

typedef WeightedBidirectionalGraph<std::pair<EdgeType, StratifiedAttrs>> GraphT;
typedef DenseMap<Value *, GraphT::Node> NodeMapT;
}

// -- Setting up/registering CFLAA pass -- //
char CFLAliasAnalysis::ID = 0;

INITIALIZE_AG_PASS(CFLAliasAnalysis, AliasAnalysis, "cfl-aa",
                   "CFL-Based AA implementation", false, true, false)

ImmutablePass *llvm::createCFLAliasAnalysisPass() {
  return new CFLAliasAnalysis();
}

//===----------------------------------------------------------------------===//
// Function declarations that require types defined in the namespace above
//===----------------------------------------------------------------------===//

// Given an argument number, returns the appropriate Attr index to set.
static StratifiedAttr argNumberToAttrIndex(StratifiedAttr);

// Given a Value, potentially return which AttrIndex it maps to.
static Optional<StratifiedAttr> valueToAttrIndex(Value *Val);

// Gets the inverse of a given EdgeType.
static EdgeType flipWeight(EdgeType);

// Gets edges of the given Instruction*, writing them to the SmallVector*.
static void argsToEdges(CFLAliasAnalysis &, Instruction *,
                        SmallVectorImpl<Edge> &);

// Gets the "Level" that one should travel in StratifiedSets
// given an EdgeType.
static Level directionOfEdgeType(EdgeType);

// Builds the graph needed for constructing the StratifiedSets for the
// given function
static void buildGraphFrom(CFLAliasAnalysis &, Function *,
                           SmallVectorImpl<Value *> &, NodeMapT &, GraphT &);

// Builds the graph + StratifiedSets for a function.
static FunctionInfo buildSetsFrom(CFLAliasAnalysis &, Function *);

static Optional<Function *> parentFunctionOfValue(Value *Val) {
  if (auto *Inst = dyn_cast<Instruction>(Val)) {
    auto *Bb = Inst->getParent();
    return Bb->getParent();
  }

  if (auto *Arg = dyn_cast<Argument>(Val))
    return Arg->getParent();
  return NoneType();
}

template <typename Inst>
static bool getPossibleTargets(Inst *Call,
                               SmallVectorImpl<Function *> &Output) {
  if (auto *Fn = Call->getCalledFunction()) {
    Output.push_back(Fn);
    return true;
  }

  // TODO: If the call is indirect, we might be able to enumerate all potential
  // targets of the call and return them, rather than just failing.
  return false;
}

static Optional<Value *> getTargetValue(Instruction *Inst) {
  GetTargetValueVisitor V;
  return V.visit(Inst);
}

static bool hasUsefulEdges(Instruction *Inst) {
  bool IsNonInvokeTerminator =
      isa<TerminatorInst>(Inst) && !isa<InvokeInst>(Inst);
  return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) && !IsNonInvokeTerminator;
}

static Optional<StratifiedAttr> valueToAttrIndex(Value *Val) {
  if (isa<GlobalValue>(Val))
    return AttrGlobalIndex;

  if (auto *Arg = dyn_cast<Argument>(Val))
    // Only pointer arguments should have the argument attribute,
    // because things can't escape through scalars without us seeing a
    // cast, and thus, interaction with them doesn't matter.
    if (!Arg->hasNoAliasAttr() && Arg->getType()->isPointerTy())
      return argNumberToAttrIndex(Arg->getArgNo());
  return NoneType();
}

static StratifiedAttr argNumberToAttrIndex(unsigned ArgNum) {
  if (ArgNum >= AttrMaxNumArgs)
    return AttrAllIndex;
  return ArgNum + AttrFirstArgIndex;
}

static EdgeType flipWeight(EdgeType Initial) {
  switch (Initial) {
  case EdgeType::Assign:
    return EdgeType::Assign;
  case EdgeType::Dereference:
    return EdgeType::Reference;
  case EdgeType::Reference:
    return EdgeType::Dereference;
  }
  llvm_unreachable("Incomplete coverage of EdgeType enum");
}

static void argsToEdges(CFLAliasAnalysis &Analysis, Instruction *Inst,
                        SmallVectorImpl<Edge> &Output) {
  GetEdgesVisitor v(Analysis, Output);
  v.visit(Inst);
}

static Level directionOfEdgeType(EdgeType Weight) {
  switch (Weight) {
  case EdgeType::Reference:
    return Level::Above;
  case EdgeType::Dereference:
    return Level::Below;
  case EdgeType::Assign:
    return Level::Same;
  }
  llvm_unreachable("Incomplete switch coverage");
}

// Aside: We may remove graph construction entirely, because it doesn't really
// buy us much that we don't already have. I'd like to add interprocedural
// analysis prior to this however, in case that somehow requires the graph
// produced by this for efficient execution
static void buildGraphFrom(CFLAliasAnalysis &Analysis, Function *Fn,
                           SmallVectorImpl<Value *> &ReturnedValues,
                           NodeMapT &Map, GraphT &Graph) {
  const auto findOrInsertNode = [&Map, &Graph](Value *Val) {
    auto Pair = Map.insert(std::make_pair(Val, GraphT::Node()));
    auto &Iter = Pair.first;
    if (Pair.second) {
      auto NewNode = Graph.addNode();
      Iter->second = NewNode;
    }
    return Iter->second;
  };

  SmallVector<Edge, 8> Edges;
  for (auto &Bb : Fn->getBasicBlockList()) {
    for (auto &Inst : Bb.getInstList()) {
      // We don't want the edges of most "return" instructions, but we *do* want
      // to know what can be returned.
      if (auto *Ret = dyn_cast<ReturnInst>(&Inst))
        ReturnedValues.push_back(Ret);

      if (!hasUsefulEdges(&Inst))
        continue;

      Edges.clear();
      argsToEdges(Analysis, &Inst, Edges);

      // In the case of an unused alloca (or similar), edges may be empty. Note
      // that it exists so we can potentially answer NoAlias.
      if (Edges.empty()) {
        auto MaybeVal = getTargetValue(&Inst);
        assert(MaybeVal.hasValue());
        auto *Target = *MaybeVal;
        findOrInsertNode(Target);
        continue;
      }

      for (const Edge &E : Edges) {
        auto To = findOrInsertNode(E.To);
        auto From = findOrInsertNode(E.From);
        auto FlippedWeight = flipWeight(E.Weight);
        auto Attrs = E.AdditionalAttrs;
        Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs),
                                std::make_pair(FlippedWeight, Attrs));
      }
    }
  }
}

static FunctionInfo buildSetsFrom(CFLAliasAnalysis &Analysis, Function *Fn) {
  NodeMapT Map;
  GraphT Graph;
  SmallVector<Value *, 4> ReturnedValues;

  buildGraphFrom(Analysis, Fn, ReturnedValues, Map, Graph);

  DenseMap<GraphT::Node, Value *> NodeValueMap;
  NodeValueMap.resize(Map.size());
  for (const auto &Pair : Map)
    NodeValueMap.insert(std::make_pair(Pair.second, Pair.first));

  const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) {
    auto ValIter = NodeValueMap.find(Node);
    assert(ValIter != NodeValueMap.end());
    return ValIter->second;
  };

  StratifiedSetsBuilder<Value *> Builder;

  SmallVector<GraphT::Node, 16> Worklist;
  for (auto &Pair : Map) {
    Worklist.clear();

    auto *Value = Pair.first;
    Builder.add(Value);
    auto InitialNode = Pair.second;
    Worklist.push_back(InitialNode);
    while (!Worklist.empty()) {
      auto Node = Worklist.pop_back_val();
      auto *CurValue = findValueOrDie(Node);
      if (isa<Constant>(CurValue) && !isa<GlobalValue>(CurValue))
        continue;

      for (const auto &EdgeTuple : Graph.edgesFor(Node)) {
        auto Weight = std::get<0>(EdgeTuple);
        auto Label = Weight.first;
        auto &OtherNode = std::get<1>(EdgeTuple);
        auto *OtherValue = findValueOrDie(OtherNode);

        if (isa<Constant>(OtherValue) && !isa<GlobalValue>(OtherValue))
          continue;

        bool Added;
        switch (directionOfEdgeType(Label)) {
        case Level::Above:
          Added = Builder.addAbove(CurValue, OtherValue);
          break;
        case Level::Below:
          Added = Builder.addBelow(CurValue, OtherValue);
          break;
        case Level::Same:
          Added = Builder.addWith(CurValue, OtherValue);
          break;
        }

        if (Added) {
          auto Aliasing = Weight.second;
          if (auto MaybeCurIndex = valueToAttrIndex(CurValue))
            Aliasing.set(*MaybeCurIndex);
          if (auto MaybeOtherIndex = valueToAttrIndex(OtherValue))
            Aliasing.set(*MaybeOtherIndex);
          Builder.noteAttributes(CurValue, Aliasing);
          Builder.noteAttributes(OtherValue, Aliasing);
          Worklist.push_back(OtherNode);
        }
      }
    }
  }

  // There are times when we end up with parameters not in our graph (i.e. if
  // it's only used as the condition of a branch). Other bits of code depend on
  // things that were present during construction being present in the graph.
  // So, we add all present arguments here.
  for (auto &Arg : Fn->args()) {
    Builder.add(&Arg);
  }

  return FunctionInfo(Builder.build(), std::move(ReturnedValues));
}

void CFLAliasAnalysis::scan(Function *Fn) {
  auto InsertPair = Cache.insert(std::make_pair(Fn, Optional<FunctionInfo>()));
  (void)InsertPair;
  assert(InsertPair.second &&
         "Trying to scan a function that has already been cached");

  FunctionInfo Info(buildSetsFrom(*this, Fn));
  Cache[Fn] = std::move(Info);
  Handles.push_front(FunctionHandle(Fn, this));
}

AliasAnalysis::AliasResult
CFLAliasAnalysis::query(const AliasAnalysis::Location &LocA,
                        const AliasAnalysis::Location &LocB) {
  auto *ValA = const_cast<Value *>(LocA.Ptr);
  auto *ValB = const_cast<Value *>(LocB.Ptr);

  Function *Fn = nullptr;
  auto MaybeFnA = parentFunctionOfValue(ValA);
  auto MaybeFnB = parentFunctionOfValue(ValB);
  if (!MaybeFnA.hasValue() && !MaybeFnB.hasValue()) {
    // The only times this is known to happen are when globals + InlineAsm
    // are involved
    DEBUG(dbgs() << "CFLAA: could not extract parent function information.\n");
    return AliasAnalysis::MayAlias;
  }

  if (MaybeFnA.hasValue()) {
    Fn = *MaybeFnA;
    assert((!MaybeFnB.hasValue() || *MaybeFnB == *MaybeFnA) &&
           "Interprocedural queries not supported");
  } else {
    Fn = *MaybeFnB;
  }

  assert(Fn != nullptr);
  auto &MaybeInfo = ensureCached(Fn);
  assert(MaybeInfo.hasValue());

  auto &Sets = MaybeInfo->Sets;
  auto MaybeA = Sets.find(ValA);
  if (!MaybeA.hasValue())
    return AliasAnalysis::MayAlias;

  auto MaybeB = Sets.find(ValB);
  if (!MaybeB.hasValue())
    return AliasAnalysis::MayAlias;

  auto SetA = *MaybeA;
  auto SetB = *MaybeB;
  auto AttrsA = Sets.getLink(SetA.Index).Attrs;
  auto AttrsB = Sets.getLink(SetB.Index).Attrs;

  // Stratified set attributes are used as markets to signify whether a member
  // of a StratifiedSet (or a member of a set above the current set) has
  // interacted with either arguments or globals. "Interacted with" meaning
  // its value may be different depending on the value of an argument or
  // global. The thought behind this is that, because arguments and globals
  // may alias each other, if AttrsA and AttrsB have touched args/globals,
  // we must conservatively say that they alias. However, if at least one of
  // the sets has no values that could legally be altered by changing the value
  // of an argument or global, then we don't have to be as conservative.
  if (AttrsA.any() && AttrsB.any())
    return AliasAnalysis::MayAlias;

  // We currently unify things even if the accesses to them may not be in
  // bounds, so we can't return partial alias here because we don't
  // know whether the pointer is really within the object or not.
  // IE Given an out of bounds GEP and an alloca'd pointer, we may
  // unify the two. We can't return partial alias for this case.
  // Since we do not currently track enough information to
  // differentiate

  if (SetA.Index == SetB.Index)
    return AliasAnalysis::MayAlias;

  return AliasAnalysis::NoAlias;
}

bool CFLAliasAnalysis::doInitialization(Module &M) {
  InitializeAliasAnalysis(this, &M.getDataLayout());
  return true;
}