+ // Volatile loads cannot be replaced with the value of other loads.
+ LoadInst *LI = cast<LoadInst>(V);
+ if (LI->isVolatile())
+ return getAnalysis<ValueNumbering>().getEqualNumberNodes(V, RetVals);
+
+ // If we have a load instruction, find all of the load and store instructions
+ // that use the same source operand. We implement this recursively, because
+ // there could be a load of a load of a load that are all identical. We are
+ // guaranteed that this cannot be an infinite recursion because load
+ // instructions would have to pass through a PHI node in order for there to be
+ // a cycle. The PHI node would be handled by the else case here, breaking the
+ // infinite recursion.
+ //
+ std::vector<Value*> PointerSources;
+ getEqualNumberNodes(LI->getOperand(0), PointerSources);
+ PointerSources.push_back(LI->getOperand(0));
+
+ BasicBlock *LoadBB = LI->getParent();
+ Function *F = LoadBB->getParent();
+
+ // Now that we know the set of equivalent source pointers for the load
+ // instruction, look to see if there are any load or store candidates that are
+ // identical.
+ //
+ std::map<BasicBlock*, std::vector<LoadInst*> > CandidateLoads;
+ std::map<BasicBlock*, std::vector<StoreInst*> > CandidateStores;
+
+ while (!PointerSources.empty()) {
+ Value *Source = PointerSources.back();
+ PointerSources.pop_back(); // Get a source pointer...
+
+ for (Value::use_iterator UI = Source->use_begin(), UE = Source->use_end();
+ UI != UE; ++UI)
+ if (LoadInst *Cand = dyn_cast<LoadInst>(*UI)) {// Is a load of source?
+ if (Cand->getParent()->getParent() == F && // In the same function?
+ Cand != LI && !Cand->isVolatile()) // Not LI itself?
+ CandidateLoads[Cand->getParent()].push_back(Cand); // Got one...
+ } else if (StoreInst *Cand = dyn_cast<StoreInst>(*UI)) {
+ if (Cand->getParent()->getParent() == F && !Cand->isVolatile() &&
+ Cand->getOperand(1) == Source) // It's a store THROUGH the ptr...
+ CandidateStores[Cand->getParent()].push_back(Cand);
+ }
+ }
+
+ // Get alias analysis & dominators.
+ AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+ DominatorSet &DomSetInfo = getAnalysis<DominatorSet>();
+ Value *LoadPtr = LI->getOperand(0);
+ // Find out how many bytes of memory are loaded by the load instruction...
+ unsigned LoadSize = getAnalysis<TargetData>().getTypeSize(LI->getType());
+
+ // Find all of the candidate loads and stores that are in the same block as
+ // the defining instruction.
+ std::set<Instruction*> Instrs;
+ Instrs.insert(CandidateLoads[LoadBB].begin(), CandidateLoads[LoadBB].end());
+ CandidateLoads.erase(LoadBB);
+ Instrs.insert(CandidateStores[LoadBB].begin(), CandidateStores[LoadBB].end());
+ CandidateStores.erase(LoadBB);
+
+ // Figure out if the load is invalidated from the entry of the block it is in
+ // until the actual instruction. This scans the block backwards from LI. If
+ // we see any candidate load or store instructions, then we know that the
+ // candidates have the same value # as LI.
+ bool LoadInvalidatedInBBBefore = false;
+ for (BasicBlock::iterator I = LI; I != LoadBB->begin(); ) {
+ --I;
+ // If this instruction is a candidate load before LI, we know there are no
+ // invalidating instructions between it and LI, so they have the same value
+ // number.
+ if (isa<LoadInst>(I) && Instrs.count(I)) {
+ RetVals.push_back(I);
+ Instrs.erase(I);
+ }