From a9cf19670f50095eac7191a5360ed03839e87465 Mon Sep 17 00:00:00 2001
From: Chris Lattner
Date: Mon, 1 Mar 2010 19:24:17 +0000
Subject: [PATCH] remove anders-aa from mainline, it isn't maintained and is
tantalyzing enough that people keep trying to use it.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@97483 91177308-0d34-0410-b5e6-96231b3b80d8
---
docs/AliasAnalysis.html | 23 +-
docs/Passes.html | 75 -
docs/ReleaseNotes.html | 2 -
include/llvm/Analysis/Passes.h | 7 -
include/llvm/LinkAllPasses.h | 1 -
lib/Analysis/IPA/Andersens.cpp | 2868 --------------------------------
6 files changed, 2 insertions(+), 2974 deletions(-)
delete mode 100644 lib/Analysis/IPA/Andersens.cpp
diff --git a/docs/AliasAnalysis.html b/docs/AliasAnalysis.html
index ebf63868982..5b4eb937a52 100644
--- a/docs/AliasAnalysis.html
+++ b/docs/AliasAnalysis.html
@@ -403,7 +403,7 @@ implementing, you just override the interfaces you can improve.
href="#basic-aa">basicaa and
-
-
The -anders-aa pass implements the well-known "Andersen's algorithm"
-for interprocedural alias analysis. This algorithm is a subset-based,
-flow-insensitive, context-insensitive, and field-insensitive alias analysis that
-is widely believed to be fairly precise. Unfortunately, this algorithm is also
-O(N3). The LLVM implementation currently does not implement any of
-the refinements (such as "online cycle elimination" or "offline variable
-substitution") to improve its efficiency, so it can be quite slow in common
-cases.
-
-
-
-
The -steens-aa pass
@@ -855,7 +836,7 @@ pointer.
These passes are useful for evaluating the various alias analysis
-implementations. You can use them with commands like 'opt -anders-aa -ds-aa
+implementations. You can use them with commands like 'opt -ds-aa
-aa-eval foo.bc -disable-output -stats'.
diff --git a/docs/Passes.html b/docs/Passes.html
index bbf6b3dc943..a2bacf95e77 100644
--- a/docs/Passes.html
+++ b/docs/Passes.html
@@ -75,7 +75,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "
\n" if !
ANALYSIS PASSES |
Option | Name |
-aa-eval | Exhaustive Alias Analysis Precision Evaluator |
-
-anders-aa | Andersen's Interprocedural Alias Analysis |
-basicaa | Basic Alias Analysis (default AA impl) |
-basiccg | Basic CallGraph Construction |
-codegenprepare | Optimize for code generation |
@@ -202,80 +201,6 @@ perl -e '$/ = undef; for (split(/\n/, <>)) { s:^ *///? ?::; print "
\n" if !
Spadini, and Wojciech Stryjewski.
-
-
-
- This is an implementation of Andersen's interprocedural alias
- analysis
-
-
-
- In pointer analysis terms, this is a subset-based, flow-insensitive,
- field-sensitive, and context-insensitive algorithm pointer algorithm.
-
-
-
- This algorithm is implemented as three stages:
-
-
-
- - Object identification.
- - Inclusion constraint identification.
- - Offline constraint graph optimization.
- - Inclusion constraint solving.
-
-
-
- The object identification stage identifies all of the memory objects in the
- program, which includes globals, heap allocated objects, and stack allocated
- objects.
-
-
-
- The inclusion constraint identification stage finds all inclusion constraints
- in the program by scanning the program, looking for pointer assignments and
- other statements that effect the points-to graph. For a statement like
- A = B
, this statement is processed to
- indicate that A can point to anything that B can point
- to. Constraints can handle copies, loads, and stores, and address taking.
-
-
-
- The offline constraint graph optimization portion includes offline variable
- substitution algorithms intended to computer pointer and location
- equivalences. Pointer equivalences are those pointers that will have the
- same points-to sets, and location equivalences are those variables that
- always appear together in points-to sets.
-
-
-
- The inclusion constraint solving phase iteratively propagates the inclusion
- constraints until a fixed point is reached. This is an O(n³)
- algorithm.
-
-
-
- Function constraints are handled as if they were structs with X
- fields. Thus, an access to argument X of function Y is
- an access to node index getNode(Y) + X
.
- This representation allows handling of indirect calls without any issues. To
- wit, an indirect call Y(a,b)
is
- equivalent to *(Y + 1) = a, *(Y + 2) =
- b
. The return node for a function F is always
- located at getNode(F) + CallReturnPos
. The arguments
- start at getNode(F) + CallArgPos
.
-
-
-
- Please keep in mind that the current andersen's pass has many known
- problems and bugs. It should be considered "research quality".
-
-
-
-
Basic Alias Analysis (default AA impl)
diff --git a/docs/ReleaseNotes.html b/docs/ReleaseNotes.html
index 84200c3b727..3b96432ea83 100644
--- a/docs/ReleaseNotes.html
+++ b/docs/ReleaseNotes.html
@@ -66,7 +66,6 @@ Almost dead code.
llvm/Analysis/PointerTracking.h => Edwin wants this, consider for 2.8.
ABCD, SCCVN, GEPSplitterPass
MSIL backend?
- AndersAA -> Unsupported, zap after branch.
-->
@@ -734,7 +733,6 @@ href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">LLVMdev list.
experimental.
The llc "-filetype=asm" (the default) is the only
supported value for this option. The ELF writer is experimental.
-
The implementation of Andersen's Alias Analysis has many known bugs.
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index 2f39c6ad126..1a5cbb2298b 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -79,13 +79,6 @@ namespace llvm {
//
FunctionPass *createScalarEvolutionAliasAnalysisPass();
- //===--------------------------------------------------------------------===//
- //
- // createAndersensPass - This pass implements Andersen's interprocedural alias
- // analysis.
- //
- ModulePass *createAndersensPass();
-
//===--------------------------------------------------------------------===//
//
// createProfileLoaderPass - This pass loads information from a profile dump
diff --git a/include/llvm/LinkAllPasses.h b/include/llvm/LinkAllPasses.h
index a7e2e05b931..ae538518ceb 100644
--- a/include/llvm/LinkAllPasses.h
+++ b/include/llvm/LinkAllPasses.h
@@ -46,7 +46,6 @@ namespace {
(void) llvm::createAggressiveDCEPass();
(void) llvm::createAliasAnalysisCounterPass();
(void) llvm::createAliasDebugger();
- (void) llvm::createAndersensPass();
(void) llvm::createArgumentPromotionPass();
(void) llvm::createStructRetPromotionPass();
(void) llvm::createBasicAliasAnalysisPass();
diff --git a/lib/Analysis/IPA/Andersens.cpp b/lib/Analysis/IPA/Andersens.cpp
deleted file mode 100644
index 2e35a56e7d4..00000000000
--- a/lib/Analysis/IPA/Andersens.cpp
+++ /dev/null
@@ -1,2868 +0,0 @@
-//===- Andersens.cpp - Andersen's Interprocedural 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 an implementation of Andersen's interprocedural alias
-// analysis
-//
-// In pointer analysis terms, this is a subset-based, flow-insensitive,
-// field-sensitive, and context-insensitive algorithm pointer algorithm.
-//
-// This algorithm is implemented as three stages:
-// 1. Object identification.
-// 2. Inclusion constraint identification.
-// 3. Offline constraint graph optimization
-// 4. Inclusion constraint solving.
-//
-// The object identification stage identifies all of the memory objects in the
-// program, which includes globals, heap allocated objects, and stack allocated
-// objects.
-//
-// The inclusion constraint identification stage finds all inclusion constraints
-// in the program by scanning the program, looking for pointer assignments and
-// other statements that effect the points-to graph. For a statement like "A =
-// B", this statement is processed to indicate that A can point to anything that
-// B can point to. Constraints can handle copies, loads, and stores, and
-// address taking.
-//
-// The offline constraint graph optimization portion includes offline variable
-// substitution algorithms intended to compute pointer and location
-// equivalences. Pointer equivalences are those pointers that will have the
-// same points-to sets, and location equivalences are those variables that
-// always appear together in points-to sets. It also includes an offline
-// cycle detection algorithm that allows cycles to be collapsed sooner
-// during solving.
-//
-// The inclusion constraint solving phase iteratively propagates the inclusion
-// constraints until a fixed point is reached. This is an O(N^3) algorithm.
-//
-// Function constraints are handled as if they were structs with X fields.
-// Thus, an access to argument X of function Y is an access to node index
-// getNode(Y) + X. This representation allows handling of indirect calls
-// without any issues. To wit, an indirect call Y(a,b) is equivalent to
-// *(Y + 1) = a, *(Y + 2) = b.
-// The return node for a function is always located at getNode(F) +
-// CallReturnPos. The arguments start at getNode(F) + CallArgPos.
-//
-// Future Improvements:
-// Use of BDD's.
-//===----------------------------------------------------------------------===//
-
-#define DEBUG_TYPE "anders-aa"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Instructions.h"
-#include "llvm/Module.h"
-#include "llvm/Pass.h"
-#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/InstIterator.h"
-#include "llvm/Support/InstVisitor.h"
-#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/MemoryBuiltins.h"
-#include "llvm/Analysis/Passes.h"
-#include "llvm/Support/Debug.h"
-#include "llvm/System/Atomic.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/SparseBitVector.h"
-#include "llvm/ADT/DenseSet.h"
-#include