//===-- GCSE.cpp - SSA based Global Common Subexpr Elimination ------------===//
+//
+// 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 pass is designed to be a very quick global transformation that
// eliminates global common subexpressions from a function. It does this by
class GCSE : public FunctionPass {
std::set<Instruction*> WorkList;
DominatorSet *DomSetInfo;
-#if 0
- ImmediateDominators *ImmDominator;
-#endif
ValueNumbering *VN;
public:
virtual bool runOnFunction(Function &F);
// This transformation requires dominator and immediate dominator info
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.preservesCFG();
+ AU.setPreservesCFG();
AU.addRequired<DominatorSet>();
AU.addRequired<ImmediateDominators>();
AU.addRequired<ValueNumbering>();
// Get pointers to the analysis results that we will be using...
DomSetInfo = &getAnalysis<DominatorSet>();
-#if 0
- ImmDominator = &getAnalysis<ImmediateDominators>();
-#endif
VN = &getAnalysis<ValueNumbering>();
// Step #1: Add all instructions in the function to the worklist for
// Erase the instruction from the program.
I->getParent()->getInstList().erase(I);
+ WorkList.erase(I);
}
return true;
Instruction *Ret = 0;
if (BB1 == BB2) {
- // Eliminate the second occuring instruction. Add all uses of the second
+ // Eliminate the second occurring instruction. Add all uses of the second
// instruction to the worklist.
//
// Scan the basic block looking for the "first" instruction
//
// Here there are no shared dominators. Additionally, this had the habit of
// moving computations where they were not always computed. For example, in
- // a cast like this:
+ // a case like this:
// if (c) {
// if (d) ...
// else ... X+Y ...
// ... X+Y ...
// }
//
- // In thiscase, the expression would be hoisted to outside the 'if' stmt,
+ // In this case, the expression would be hoisted to outside the 'if' stmt,
// causing the expression to be evaluated, even for the if (d) path, which
// could cause problems, if, for example, it caused a divide by zero. In
// general the problem this case is trying to solve is better addressed with
// PRE than GCSE.
//
return 0;
-
-#if 0
- // Handle the most general case now. In this case, neither I dom Other nor
- // Other dom I. Because we are in SSA form, we are guaranteed that the
- // operands of the two instructions both dominate the uses, so we _know_
- // that there must exist a block that dominates both instructions (if the
- // operands of the instructions are globals or constants, worst case we
- // would get the entry node of the function). Search for this block now.
- //
-
- // Search up the immediate dominator chain of BB1 for the shared dominator
- BasicBlock *SharedDom = (*ImmDominator)[BB1];
- while (!DomSetInfo->dominates(SharedDom, BB2))
- SharedDom = (*ImmDominator)[SharedDom];
-
- // At this point, shared dom must dominate BOTH BB1 and BB2...
- assert(SharedDom && DomSetInfo->dominates(SharedDom, BB1) &&
- DomSetInfo->dominates(SharedDom, BB2) && "Dominators broken!");
-
- // Rip 'I' out of BB1, and move it to the end of SharedDom.
- BB1->getInstList().remove(I);
- SharedDom->getInstList().insert(--SharedDom->end(), I);
-
- // Eliminate 'Other' now.
- ReplaceInstWithInst(I, Other);
-#endif
}
if (isa<LoadInst>(Ret))