//===----------------------------------------------------------------------===//
#include "StratifiedSets.h"
-#include "llvm/Analysis/Passes.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/Optional.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/Instructions.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"
// 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;
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;
virtual ~FunctionHandle() {}
- virtual void deleted() override { removeSelfFromCache(); }
- virtual void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
+ void deleted() override { removeSelfFromCache(); }
+ void allUsesReplacedWith(Value *) override { removeSelfFromCache(); }
private:
CFLAliasAnalysis *CFLAA;
virtual ~CFLAliasAnalysis() {}
- void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AliasAnalysis::getAnalysisUsage(AU);
}
// Comparisons between global variables and other constants should be
// handled by BasicAA.
if (isa<Constant>(LocA.Ptr) && isa<Constant>(LocB.Ptr)) {
- return MayAlias;
+ return AliasAnalysis::alias(LocA, LocB);
}
+ AliasResult QueryResult = query(LocA, LocB);
+ if (QueryResult == MayAlias)
+ return AliasAnalysis::alias(LocA, LocB);
- return query(LocA, LocB);
+ return QueryResult;
}
void initializePass() override { InitializeAliasAnalysis(this); }
}
void visitSelectInst(SelectInst &Inst) {
- auto *Condition = Inst.getCondition();
- Output.push_back(Edge(&Inst, Condition, EdgeType::Assign, AttrNone));
+ // 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(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();
}
tryInterproceduralAnalysis(const SmallVectorImpl<Function *> &Fns,
Value *FuncValue,
const iterator_range<User::op_iterator> &Args) {
- LLVM_CONSTEXPR unsigned ExpectedMaxArgs = 8;
- LLVM_CONSTEXPR unsigned MaxSupportedArgs = 50;
+ 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()) > MaxSupportedArgs)
+ if (std::distance(Args.begin(), Args.end()) > (int) MaxSupportedArgs)
return false;
// Exit early if we'll fail anyway
}
}
if (AddEdge)
- Output.push_back({FuncValue, ArgVal, EdgeType::Assign,
- StratifiedAttrs().flip()});
+ Output.push_back(Edge(FuncValue, ArgVal, EdgeType::Assign,
+ StratifiedAttrs().flip()));
}
if (Parameters.size() != Arguments.size())
typedef std::size_t Node;
private:
- LLVM_CONSTEXPR static Node StartNode = Node(0);
+ 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;
}
// ----- Actual graph-related things ----- //
- WeightedBidirectionalGraph() = default;
+ WeightedBidirectionalGraph() {}
WeightedBidirectionalGraph(WeightedBidirectionalGraph<EdgeTypeT> &&Other)
: NodeImpls(std::move(Other.NodeImpls)) {}
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});
+ FromNode.Edges.push_back(Edge(Weight, To));
+ ToNode.Edges.push_back(Edge(ReverseWeight, From));
}
EdgeIterable edgesFor(const Node &N) const {
return AttrGlobalIndex;
if (auto *Arg = dyn_cast<Argument>(Val))
- if (!Arg->hasNoAliasAttr())
+ // 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)
+ if (ArgNum >= AttrMaxNumArgs)
return AttrAllIndex;
return ArgNum + AttrFirstArgIndex;
}
auto From = findOrInsertNode(E.From);
auto FlippedWeight = flipWeight(E.Weight);
auto Attrs = E.AdditionalAttrs;
- Graph.addEdge(From, To, {E.Weight, Attrs}, {FlippedWeight, Attrs});
+ Graph.addEdge(From, To, std::make_pair(E.Weight, Attrs),
+ std::make_pair(FlippedWeight, Attrs));
}
}
}
Builder.add(&Arg);
}
- return {Builder.build(), std::move(ReturnedValues)};
+ return FunctionInfo(Builder.build(), std::move(ReturnedValues));
}
void CFLAliasAnalysis::scan(Function *Fn) {
auto SetA = *MaybeA;
auto SetB = *MaybeB;
-
- if (SetA.Index == SetB.Index)
- return AliasAnalysis::PartialAlias;
-
auto AttrsA = Sets.getLink(SetA.Index).Attrs;
auto AttrsB = Sets.getLink(SetB.Index).Attrs;
- auto CombinedAttrs = AttrsA | AttrsB;
- if (CombinedAttrs.any())
- return AliasAnalysis::PartialAlias;
+ // 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;
}