//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===//
-//
+//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file implements the AliasSetTracker and AliasSet classes.
-//
+//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Instructions.h"
#include "llvm/Pass.h"
+#include "llvm/Type.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/InstIterator.h"
#include <iostream>
using namespace llvm;
-/// mergeSetIn - Merge the specified alias set into this alias set...
+/// mergeSetIn - Merge the specified alias set into this alias set.
///
-void AliasSet::mergeSetIn(AliasSet &AS) {
+void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
assert(!AS.Forward && "Alias set is already forwarding!");
assert(!Forward && "This set is a forwarding set!!");
AccessTy |= AS.AccessTy;
AliasTy |= AS.AliasTy;
+ if (AliasTy == MustAlias) {
+ // Check that these two merged sets really are must aliases. Since both
+ // used to be must-alias sets, we can just check any pointer from each set
+ // for aliasing.
+ AliasAnalysis &AA = AST.getAliasAnalysis();
+ HashNodePair *L = getSomePointer();
+ HashNodePair *R = AS.getSomePointer();
+
+ // If the pointers are not a must-alias pair, this set becomes a may alias.
+ if (AA.alias(L->first, L->second.getSize(), R->first, R->second.getSize())
+ != AliasAnalysis::MustAlias)
+ AliasTy = MayAlias;
+ }
+
if (CallSites.empty()) { // Merge call sites...
if (!AS.CallSites.empty())
std::swap(CallSites, AS.CallSites);
CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end());
AS.CallSites.clear();
}
-
+
AS.Forward = this; // Forward across AS now...
addRef(); // AS is now pointing to us...
CallSites.push_back(CS);
if (Function *F = CS.getCalledFunction()) {
- if (AA.doesNotAccessMemory(F))
+ AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(F, CS);
+ if (Behavior == AliasAnalysis::DoesNotAccessMemory)
return;
- else if (AA.onlyReadsMemory(F)) {
+ else if (Behavior == AliasAnalysis::OnlyReadsMemory) {
AliasTy = MayAlias;
AccessTy |= Refs;
return;
AliasSet *FoundSet = 0;
for (iterator I = begin(), E = end(); I != E; ++I)
if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) {
- if (FoundSet == 0) { // If this is the first alias set ptr can go into...
+ if (FoundSet == 0) { // If this is the first alias set ptr can go into.
FoundSet = I; // Remember it.
- } else { // Otherwise, we must merge the sets...
- FoundSet->mergeSetIn(*I); // Merge in contents...
+ } else { // Otherwise, we must merge the sets.
+ FoundSet->mergeSetIn(*I, *this); // Merge in contents.
}
}
return FoundSet;
}
+/// containsPointer - Return true if the specified location is represented by
+/// this alias set, false otherwise. This does not modify the AST object or
+/// alias sets.
+bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const {
+ for (const_iterator I = begin(), E = end(); I != E; ++I)
+ if (!I->Forward && I->aliasesPointer(Ptr, Size, AA))
+ return true;
+ return false;
+}
+
+
+
AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) {
AliasSet *FoundSet = 0;
for (iterator I = begin(), E = end(); I != E; ++I)
if (!I->Forward && I->aliasesCallSite(CS, AA)) {
- if (FoundSet == 0) { // If this is the first alias set ptr can go into...
+ if (FoundSet == 0) { // If this is the first alias set ptr can go into.
FoundSet = I; // Remember it.
- } else if (!I->Forward) { // Otherwise, we must merge the sets...
- FoundSet->mergeSetIn(*I); // Merge in contents...
+ } else if (!I->Forward) { // Otherwise, we must merge the sets.
+ FoundSet->mergeSetIn(*I, *this); // Merge in contents.
}
}
bool NewPtr;
AliasSet &AS = addPointer(FI->getOperand(0), ~0,
AliasSet::Mods, NewPtr);
+
+ // Free operations are volatile ops (cannot be moved).
+ AS.setVolatile();
return NewPtr;
}
bool AliasSetTracker::add(CallSite CS) {
- bool NewPtr;
if (Function *F = CS.getCalledFunction())
if (AA.doesNotAccessMemory(F))
return true; // doesn't alias anything
/// remove - Remove the specified (potentially non-empty) alias set from the
/// tracker.
void AliasSetTracker::remove(AliasSet &AS) {
- bool SetDead;
- do {
- AliasSet::iterator I = AS.begin();
- Value *Ptr = I.getPointer(); ++I;
-
- // deleteValue will delete the set automatically when the last pointer
- // reference is destroyed. "Predict" when this will happen.
- SetDead = I == AS.end();
- deleteValue(Ptr); // Delete all of the pointers from the set
- } while (!SetDead);
+ // Drop all call sites.
+ AS.CallSites.clear();
+
+ // Clear the alias set.
+ unsigned NumRefs = 0;
+ while (!AS.empty()) {
+ AliasSet::HashNodePair *P = AS.PtrList;
+
+ // Unlink from the list of values.
+ P->second.removeFromList();
+
+ // Remember how many references need to be dropped.
+ ++NumRefs;
+
+ // Finally, remove the entry.
+ PointerMap.erase(P->first);
+ }
+
+ // Stop using the alias set, removing it.
+ AS.RefCount -= NumRefs;
+ if (AS.RefCount == 0)
+ AS.removeFromTracker(*this);
}
bool AliasSetTracker::remove(Value *Ptr, unsigned Size) {
// Notify the alias analysis implementation that this value is gone.
AA.deleteValue(PtrVal);
+ // If this is a call instruction, remove the callsite from the appropriate
+ // AliasSet.
+ CallSite CS = CallSite::get(PtrVal);
+ if (CS.getInstruction()) {
+ Function *F = CS.getCalledFunction();
+ if (!F || !AA.doesNotAccessMemory(F)) {
+ if (AliasSet *AS = findAliasSetForCallSite(CS))
+ AS->removeCallSite(CS);
+ }
+ }
+
// First, look up the PointerRec for this pointer.
hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
if (I == PointerMap.end()) return; // Noop
for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
if (i) OS << ", ";
WriteAsOperand(OS, CallSites[i].getCalledValue());
- }
+ }
}
OS << "\n";
}
for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
Tracker->add(&*I);
- return false;
- }
-
- /// print - Convert to human readable form
- virtual void print(std::ostream &OS) const {
- Tracker->print(OS);
- }
-
- virtual void releaseMemory() {
+ Tracker->print(std::cerr);
delete Tracker;
+ return false;
}
};
- RegisterPass<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer",
- PassInfo::Analysis | PassInfo::Optimization);
+ RegisterOpt<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer");
}