//===----------------------------------------------------------------------===//
#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);
}
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 {
}
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 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;
return AliasAnalysis::NoAlias;
}