index da0264ec1df02d9fcb6f44b0f926fb8ab9aac1f0..9783671b09a3ff4337f297dff06244c7b28ce20d 100644 (file)
//===----------------------------------------------------------------------===//
#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);
}
}
void visitCastInst(CastInst &Inst) {
- Output.push_back({&Inst, Inst.getOperand(0), EdgeType::Assign, AttrNone});
+ 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({&Inst, Op1, EdgeType::Assign, AttrNone});
- Output.push_back({&Inst, Op2, EdgeType::Assign, AttrNone});
+ 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({Ptr, Val, EdgeType::Dereference, AttrNone});
+ Output.push_back(Edge(Ptr, Val, EdgeType::Dereference, AttrNone));
}
void visitAtomicRMWInst(AtomicRMWInst &Inst) {
auto *Ptr = Inst.getPointerOperand();
auto *Val = Inst.getValOperand();
- Output.push_back({Ptr, Val, EdgeType::Dereference, AttrNone});
+ 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({&Inst, Val, EdgeType::Assign, AttrNone});
+ Output.push_back(Edge(&Inst, Val, EdgeType::Assign, AttrNone));
}
}
void visitGetElementPtrInst(GetElementPtrInst &Inst) {
auto *Op = Inst.getPointerOperand();
- Output.push_back({&Inst, Op, EdgeType::Assign, AttrNone});
+ 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({&Inst, *I, EdgeType::Assign, AttrNone});
+ Output.push_back(Edge(&Inst, *I, EdgeType::Assign, AttrNone));
}
void visitSelectInst(SelectInst &Inst) {
auto *Condition = Inst.getCondition();
- Output.push_back({&Inst, Condition, EdgeType::Assign, AttrNone});
+ Output.push_back(Edge(&Inst, Condition, EdgeType::Assign, AttrNone));
auto *TrueVal = Inst.getTrueValue();
- Output.push_back({&Inst, TrueVal, EdgeType::Assign, AttrNone});
+ Output.push_back(Edge(&Inst, TrueVal, EdgeType::Assign, AttrNone));
auto *FalseVal = Inst.getFalseValue();
- Output.push_back({&Inst, FalseVal, EdgeType::Assign, AttrNone});
+ 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({Val, Ptr, EdgeType::Reference, AttrNone});
+ Output.push_back(Edge(Val, Ptr, EdgeType::Reference, AttrNone));
}
void visitStoreInst(StoreInst &Inst) {
auto *Ptr = Inst.getPointerOperand();
auto *Val = Inst.getValueOperand();
- Output.push_back({Ptr, Val, EdgeType::Dereference, AttrNone});
+ 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) {
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())
continue;
auto NewAttrs = SubAttrs | MainAttrs;
- Output.push_back({MainVal, SubVal, EdgeType::Assign, NewAttrs});
+ Output.push_back(Edge(MainVal, SubVal, EdgeType::Assign, NewAttrs));
}
}
}
}
for (Value *V : Inst.arg_operands())
- Output.push_back({&Inst, V, EdgeType::Assign, AttrAll});
+ Output.push_back(Edge(&Inst, V, EdgeType::Assign, AttrAll));
}
void visitCallInst(CallInst &Inst) { visitCallLikeInst(Inst); }
void visitExtractElementInst(ExtractElementInst &Inst) {
auto *Ptr = Inst.getVectorOperand();
auto *Val = &Inst;
- Output.push_back({Val, Ptr, EdgeType::Reference, AttrNone});
+ 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({&Inst, Vec, EdgeType::Assign, AttrNone});
- Output.push_back({&Inst, Val, EdgeType::Dereference, AttrNone});
+ 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({&Inst, &Inst, EdgeType::Assign, AttrAll});
+ 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({&Inst, Agg, EdgeType::Assign, AttrNone});
- Output.push_back({&Inst, Val, EdgeType::Dereference, AttrNone});
+ 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({&Inst, Ptr, EdgeType::Reference, AttrNone});
+ 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({&Inst, From1, EdgeType::Assign, AttrNone});
- Output.push_back({&Inst, From2, EdgeType::Assign, AttrNone});
+ Output.push_back(Edge(&Inst, From1, EdgeType::Assign, AttrNone));
+ Output.push_back(Edge(&Inst, From2, EdgeType::Assign, AttrNone));
}
};
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));
}
}
}
DenseMap<GraphT::Node, Value *> NodeValueMap;
NodeValueMap.resize(Map.size());
for (const auto &Pair : Map)
- NodeValueMap.insert({Pair.second, Pair.first});
+ NodeValueMap.insert(std::make_pair(Pair.second, Pair.first));
const auto findValueOrDie = [&NodeValueMap](GraphT::Node Node) {
auto ValIter = NodeValueMap.find(Node);
Builder.add(&Arg);
}
- return {Builder.build(), std::move(ReturnedValues)};
+ return FunctionInfo(Builder.build(), std::move(ReturnedValues));
}
void CFLAliasAnalysis::scan(Function *Fn) {
- auto InsertPair = Cache.insert({Fn, Optional<FunctionInfo>()});
+ 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");
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;
}