- /// LoopBodyInfo - We recursively traverse loops from most-deeply-nested to
- /// least-deeply-nested. For all of the loops nested within the current one,
- /// we keep track of information so that we don't have to repeat queries.
- ///
- struct LoopBodyInfo {
- std::vector<CallInst*> Calls; // Call instructions in loop
- std::vector<InvokeInst*> Invokes; // Invoke instructions in loop
-
- // StoredPointers - Targets of store instructions...
- std::set<Value*> StoredPointers;
-
- // LoadedPointers - Source pointers for load instructions...
- std::set<Value*> LoadedPointers;
-
- enum PointerClass {
- PointerUnknown = 0, // Nothing is known about this pointer yet
- PointerMustStore, // Memory is stored to ONLY through this pointer
- PointerMayStore, // Memory is stored to through this or other pointers
- PointerNoStore // Memory is not modified in this loop
- };
-
- // PointerIsModified - Keep track of information as we find out about it in
- // the loop body...
- //
- std::map<Value*, enum PointerClass> PointerIsModified;
-
- /// CantModifyAnyPointers - Return true if no memory modifying instructions
- /// occur in this loop. This is just a conservative approximation, because
- /// a call may not actually store anything.
- bool CantModifyAnyPointers() const {
- return Calls.empty() && Invokes.empty() && StoredPointers.empty();
- }
-
- /// incorporate - Incorporate information about a subloop into the current
- /// loop.
- void incorporate(const LoopBodyInfo &OtherLBI);
- void incorporate(BasicBlock &BB); // do the same for a basic block
-
- PointerClass getPointerInfo(Value *V, AliasAnalysis &AA) {
- PointerClass &VInfo = PointerIsModified[V];
- if (VInfo == PointerUnknown)
- VInfo = calculatePointerInfo(V, AA);
- return VInfo;
- }
- private:
- /// calculatePointerInfo - Calculate information about the specified
- /// pointer.
- PointerClass calculatePointerInfo(Value *V, AliasAnalysis &AA) const;
- };
-}
-
-/// incorporate - Incorporate information about a subloop into the current loop.
-void LoopBodyInfo::incorporate(const LoopBodyInfo &OtherLBI) {
- // Do not incorporate NonModifiedPointers (which is just a cache) because it
- // is too much trouble to make sure it's still valid.
- Calls.insert (Calls.end(), OtherLBI.Calls.begin(), OtherLBI.Calls.end());
- Invokes.insert(Invokes.end(),OtherLBI.Invokes.begin(),OtherLBI.Invokes.end());
- StoredPointers.insert(OtherLBI.StoredPointers.begin(),
- OtherLBI.StoredPointers.end());
- LoadedPointers.insert(OtherLBI.LoadedPointers.begin(),
- OtherLBI.LoadedPointers.end());
-}
-
-void LoopBodyInfo::incorporate(BasicBlock &BB) {
- for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
- if (CallInst *CI = dyn_cast<CallInst>(&*I))
- Calls.push_back(CI);
- else if (StoreInst *SI = dyn_cast<StoreInst>(&*I))
- StoredPointers.insert(SI->getOperand(1));
- else if (LoadInst *LI = dyn_cast<LoadInst>(&*I))
- LoadedPointers.insert(LI->getOperand(0));
-
- if (InvokeInst *II = dyn_cast<InvokeInst>(BB.getTerminator()))
- Invokes.push_back(II);
-}
-
-
-// calculatePointerInfo - Calculate information about the specified pointer.
-LoopBodyInfo::PointerClass LoopBodyInfo::calculatePointerInfo(Value *V,
- AliasAnalysis &AA) const {
- for (unsigned i = 0, e = Calls.size(); i != e; ++i)
- if (AA.getModRefInfo(Calls[i], V, ~0))
- return PointerMayStore;
-
- for (unsigned i = 0, e = Invokes.size(); i != e; ++i)
- if (AA.getModRefInfo(Invokes[i], V, ~0))
- return PointerMayStore;
-
- PointerClass Result = PointerNoStore;
- for (std::set<Value*>::const_iterator I = StoredPointers.begin(),
- E = StoredPointers.end(); I != E; ++I)
- if (AA.alias(V, ~0, *I, ~0))
- if (V == *I)
- Result = PointerMustStore; // If this is the only alias, return must
- else
- return PointerMayStore; // We have to return may
- return Result;
-}
-
-namespace {