+ AU.addRequiredTransitive<DominatorTree>();
+ AU.addRequiredTransitive<TargetData>();
+}
+
+static bool isPathTransparentTo(BasicBlock *CurBlock, BasicBlock *Dom,
+ Value *Ptr, unsigned Size, AliasAnalysis &AA,
+ std::set<BasicBlock*> &Visited,
+ std::map<BasicBlock*, bool> &TransparentBlocks){
+ // If we have already checked out this path, or if we reached our destination,
+ // stop searching, returning success.
+ if (CurBlock == Dom || !Visited.insert(CurBlock).second)
+ return true;
+
+ // Check whether this block is known transparent or not.
+ std::map<BasicBlock*, bool>::iterator TBI =
+ TransparentBlocks.find(CurBlock);
+
+ if (TBI == TransparentBlocks.end()) {
+ // If this basic block can modify the memory location, then the path is not
+ // transparent!
+ if (AA.canBasicBlockModify(*CurBlock, Ptr, Size)) {
+ TransparentBlocks.insert(TBI, std::make_pair(CurBlock, false));
+ return false;
+ }
+ TransparentBlocks.insert(TBI, std::make_pair(CurBlock, true));
+ } else if (!TBI->second)
+ // This block is known non-transparent, so that path can't be either.
+ return false;
+
+ // The current block is known to be transparent. The entire path is
+ // transparent if all of the predecessors paths to the parent is also
+ // transparent to the memory location.
+ for (pred_iterator PI = pred_begin(CurBlock), E = pred_end(CurBlock);
+ PI != E; ++PI)
+ if (!isPathTransparentTo(*PI, Dom, Ptr, Size, AA, Visited,
+ TransparentBlocks))
+ return false;
+ return true;
+}
+
+/// getCallEqualNumberNodes - Given a call instruction, find other calls that
+/// have the same value number.
+void LoadVN::getCallEqualNumberNodes(CallInst *CI,
+ std::vector<Value*> &RetVals) const {
+ Function *CF = CI->getCalledFunction();
+ if (CF == 0) return; // Indirect call.
+ AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+ AliasAnalysis::ModRefBehavior MRB = AA.getModRefBehavior(CI);
+ if (MRB != AliasAnalysis::DoesNotAccessMemory &&
+ MRB != AliasAnalysis::OnlyReadsMemory)
+ return; // Nothing we can do for now.
+
+ // Scan all of the arguments of the function, looking for one that is not
+ // global. In particular, we would prefer to have an argument or instruction
+ // operand to chase the def-use chains of.
+ Value *Op = CF;
+ for (User::op_iterator i = CI->op_begin() + 1, e = CI->op_end(); i != e; ++i)
+ if (isa<Argument>(*i) ||
+ isa<Instruction>(*i)) {
+ Op = *i;
+ break;
+ }
+
+ // Identify all lexically identical calls in this function.
+ std::vector<CallInst*> IdenticalCalls;
+
+ Function *CIFunc = CI->getParent()->getParent();
+ for (Value::use_iterator UI = Op->use_begin(), E = Op->use_end(); UI != E;
+ ++UI)
+ if (CallInst *C = dyn_cast<CallInst>(*UI))
+ if (C->getNumOperands() == CI->getNumOperands() &&
+ C->getOperand(0) == CI->getOperand(0) &&
+ C->getParent()->getParent() == CIFunc && C != CI) {
+ bool AllOperandsEqual = true;
+ for (User::op_iterator i = CI->op_begin() + 1, j = C->op_begin() + 1,
+ e = CI->op_end(); i != e; ++i, ++j)
+ if (*j != *i) {
+ AllOperandsEqual = false;
+ break;
+ }
+
+ if (AllOperandsEqual)
+ IdenticalCalls.push_back(C);
+ }
+
+ if (IdenticalCalls.empty()) return;
+
+ // Eliminate duplicates, which could occur if we chose a value that is passed
+ // into a call site multiple times.
+ std::sort(IdenticalCalls.begin(), IdenticalCalls.end());
+ IdenticalCalls.erase(std::unique(IdenticalCalls.begin(),IdenticalCalls.end()),
+ IdenticalCalls.end());
+
+ // If the call reads memory, we must make sure that there are no stores
+ // between the calls in question.
+ //
+ // FIXME: This should use mod/ref information. What we really care about it
+ // whether an intervening instruction could modify memory that is read, not
+ // ANY memory.
+ //
+ if (MRB == AliasAnalysis::OnlyReadsMemory) {
+ DominatorTree &DT = getAnalysis<DominatorTree>();
+ BasicBlock *CIBB = CI->getParent();
+ for (unsigned i = 0; i != IdenticalCalls.size(); ++i) {
+ CallInst *C = IdenticalCalls[i];
+ bool CantEqual = false;
+
+ if (DT.dominates(CIBB, C->getParent())) {
+ // FIXME: we currently only handle the case where both calls are in the
+ // same basic block.
+ if (CIBB != C->getParent()) {
+ CantEqual = true;
+ } else {
+ Instruction *First = CI, *Second = C;
+ if (!DT.dominates(CI, C))
+ std::swap(First, Second);
+
+ // Scan the instructions between the calls, checking for stores or
+ // calls to dangerous functions.
+ BasicBlock::iterator I = First;
+ for (++First; I != BasicBlock::iterator(Second); ++I) {
+ if (isa<StoreInst>(I)) {
+ // FIXME: We could use mod/ref information to make this much
+ // better!
+ CantEqual = true;
+ break;
+ } else if (CallInst *CI = dyn_cast<CallInst>(I)) {
+ if (!AA.onlyReadsMemory(CI)) {
+ CantEqual = true;
+ break;
+ }
+ } else if (I->mayWriteToMemory()) {
+ CantEqual = true;
+ break;
+ }
+ }
+ }
+
+ } else if (DT.dominates(C->getParent(), CIBB)) {
+ // FIXME: We could implement this, but we don't for now.
+ CantEqual = true;
+ } else {
+ // FIXME: if one doesn't dominate the other, we can't tell yet.
+ CantEqual = true;
+ }
+
+
+ if (CantEqual) {
+ // This call does not produce the same value as the one in the query.
+ std::swap(IdenticalCalls[i--], IdenticalCalls.back());
+ IdenticalCalls.pop_back();
+ }
+ }
+ }
+
+ // Any calls that are identical and not destroyed will produce equal values!
+ for (unsigned i = 0, e = IdenticalCalls.size(); i != e; ++i)
+ RetVals.push_back(IdenticalCalls[i]);