aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDan Gohman <gohman@apple.com>2010-08-02 23:11:01 +0000
committerDan Gohman <gohman@apple.com>2010-08-02 23:11:01 +0000
commitc182cb5784cfe557f3c8fa6cfb208c02d2ed42d5 (patch)
treed5cb8821bf0fc46ee3cb26e27b5fab8ad47ff217
parentdacfc5d37f649fb15aaa339eaf1b010c4f44c803 (diff)
downloadexternal_llvm-c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5.zip
external_llvm-c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5.tar.gz
external_llvm-c182cb5784cfe557f3c8fa6cfb208c02d2ed42d5.tar.bz2
Sketch up a preliminary Type-Based Alias Analysis implementation.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@110077 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r--include/llvm/Analysis/Passes.h7
-rw-r--r--include/llvm/LinkAllPasses.h1
-rw-r--r--lib/Analysis/TypeBasedAliasAnalysis.cpp191
3 files changed, 199 insertions, 0 deletions
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index 38bba77..e8e7796 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -81,6 +81,13 @@ namespace llvm {
//===--------------------------------------------------------------------===//
//
+ // createTypeBasedAliasAnalysisPass - This pass implements metadata-based
+ // type-based alias analysis.
+ //
+ ImmutablePass *createTypeBasedAliasAnalysisPass();
+
+ //===--------------------------------------------------------------------===//
+ //
// createProfileLoaderPass - This pass loads information from a profile dump
// file.
//
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index 4f3a019..4068772 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -53,6 +53,7 @@ namespace {
(void) llvm::createBasicAliasAnalysisPass();
(void) llvm::createLibCallAliasAnalysisPass(0);
(void) llvm::createScalarEvolutionAliasAnalysisPass();
+ (void) llvm::createTypeBasedAliasAnalysisPass();
(void) llvm::createBlockPlacementPass();
(void) llvm::createBreakCriticalEdgesPass();
(void) llvm::createCFGSimplificationPass();
diff --git a/lib/Analysis/TypeBasedAliasAnalysis.cpp b/lib/Analysis/TypeBasedAliasAnalysis.cpp
new file mode 100644
index 0000000..cab266b
--- /dev/null
+++ b/lib/Analysis/TypeBasedAliasAnalysis.cpp
@@ -0,0 +1,191 @@
+//===- TypeBasedAliasAnalysis.cpp - Type-Based Alias Analysis -------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the TypeBasedAliasAnalysis pass, which implements
+// metadata-based TBAA.
+//
+// In LLVM IR, memory does not have types, so LLVM's own type system is not
+// suitable for doing TBAA. Instead, metadata is added to the IR to describe
+// a type system of a higher level language.
+//
+// This pass is language-independent. The type system is encoded in
+// metadata. This allows this pass to support typical C and C++ TBAA, but
+// it can also support custom aliasing behavior for other languages.
+//
+// This is a work-in-progress. It doesn't work yet, and the metadata
+// format isn't stable.
+//
+// TODO: getModRefBehavior. The AliasAnalysis infrastructure will need to
+// be extended.
+// TODO: AA chaining
+// TODO: struct fields
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Module.h"
+#include "llvm/Metadata.h"
+#include "llvm/Pass.h"
+using namespace llvm;
+
+namespace {
+ /// TBAANode - This is a simple wrapper around an MDNode which provides a
+ /// higher-level interface by hiding the details of how alias analysis
+ /// information is encoded in its operands.
+ class TBAANode {
+ const MDNode *Node;
+
+ public:
+ TBAANode() : Node(0) {}
+ explicit TBAANode(MDNode *N) : Node(N) {}
+
+ /// getNode - Get the MDNode for this TBAANode.
+ const MDNode *getNode() const { return Node; }
+
+ /// getParent - Get this TBAANode's Alias DAG parent.
+ TBAANode getParent() const {
+ if (Node->getNumOperands() < 2)
+ return TBAANode();
+ MDNode *P = dyn_cast<MDNode>(Node->getOperand(1));
+ if (!P)
+ return TBAANode();
+ // Ok, this node has a valid parent. Return it.
+ return TBAANode(P);
+ }
+
+ /// TypeIsImmutable - Test if this TBAANode represents a type for objects
+ /// which are not modified (by any means) in the context where this
+ /// AliasAnalysis is relevant.
+ bool TypeIsImmutable() const {
+ if (Node->getNumOperands() < 3)
+ return false;
+ ConstantInt *CI = dyn_cast<ConstantInt>(Node->getOperand(2));
+ if (!CI)
+ return false;
+ // TODO: Think about the encoding.
+ return CI->isOne();
+ }
+ };
+}
+
+namespace {
+ /// TypeBasedAliasAnalysis - This is a simple alias analysis
+ /// implementation that uses TypeBased to answer queries.
+ class TypeBasedAliasAnalysis : public ImmutablePass,
+ public AliasAnalysis {
+ public:
+ static char ID; // Class identification, replacement for typeinfo
+ TypeBasedAliasAnalysis() : ImmutablePass(&ID) {}
+
+ /// getAdjustedAnalysisPointer - This method is used when a pass implements
+ /// an analysis interface through multiple inheritance. If needed, it
+ /// should override this to adjust the this pointer as needed for the
+ /// specified pass info.
+ virtual void *getAdjustedAnalysisPointer(const PassInfo *PI) {
+ if (PI->isPassID(&AliasAnalysis::ID))
+ return (AliasAnalysis*)this;
+ return this;
+ }
+
+ private:
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ virtual AliasResult alias(const Value *V1, unsigned V1Size,
+ const Value *V2, unsigned V2Size);
+ virtual bool pointsToConstantMemory(const Value *P);
+ };
+} // End of anonymous namespace
+
+// Register this pass...
+char TypeBasedAliasAnalysis::ID = 0;
+INITIALIZE_AG_PASS(TypeBasedAliasAnalysis, AliasAnalysis, "tbaa",
+ "Type-Based Alias Analysis", false, true, false);
+
+ImmutablePass *llvm::createTypeBasedAliasAnalysisPass() {
+ return new TypeBasedAliasAnalysis();
+}
+
+void
+TypeBasedAliasAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ AliasAnalysis::getAnalysisUsage(AU);
+}
+
+AliasAnalysis::AliasResult
+TypeBasedAliasAnalysis::alias(const Value *A, unsigned ASize,
+ const Value *B, unsigned BSize) {
+ // Currently, metadata can only be attached to Instructions.
+ const Instruction *AI = dyn_cast<Instruction>(A);
+ if (!AI) return MayAlias;
+ const Instruction *BI = dyn_cast<Instruction>(B);
+ if (!BI) return MayAlias;
+
+ // Get the attached MDNodes. If either value lacks a tbaa MDNode, we must
+ // be conservative.
+ MDNode *AM =
+ AI->getMetadata(AI->getParent()->getParent()->getParent()
+ ->getMDKindID("tbaa"));
+ if (!AM) return MayAlias;
+ MDNode *BM =
+ AI->getMetadata(BI->getParent()->getParent()->getParent()
+ ->getMDKindID("tbaa"));
+ if (!BM) return MayAlias;
+
+ // Keep track of the root node for A and B.
+ TBAANode RootA, RootB;
+
+ // Climb the DAG from A to see if we reach B.
+ for (TBAANode T(AM); ; ) {
+ if (T.getNode() == BM)
+ // B is an ancestor of A.
+ return MayAlias;
+
+ RootA = T;
+ T = T.getParent();
+ if (!T.getNode())
+ break;
+ }
+
+ // Climb the DAG from B to see if we reach A.
+ for (TBAANode T(BM); ; ) {
+ if (T.getNode() == AM)
+ // A is an ancestor of B.
+ return MayAlias;
+
+ RootB = T;
+ T = T.getParent();
+ if (!T.getNode())
+ break;
+ }
+
+ // Neither node is an ancestor of the other.
+
+ // If they have the same root, then we've proved there's no alias.
+ if (RootA.getNode() == RootB.getNode())
+ return NoAlias;
+
+ // If they have different roots, they're part of different potentially
+ // unrelated type systems, so we must be conservative.
+ return MayAlias;
+}
+
+bool TypeBasedAliasAnalysis::pointsToConstantMemory(const Value *P) {
+ // Currently, metadata can only be attached to Instructions.
+ const Instruction *I = dyn_cast<Instruction>(P);
+ if (!I) return false;
+
+ MDNode *M =
+ I->getMetadata(I->getParent()->getParent()->getParent()
+ ->getMDKindID("tbaa"));
+ if (!M) return false;
+
+ // If this is an "immutable" type, we can assume the pointer is pointing
+ // to constant memory.
+ return TBAANode(M).TypeIsImmutable();
+}