-}
-
-//===----------------------------------------------------------------------===//
-//
-// Visitation methods, these are invoked depending on the type of instruction
-// being checked. They should return true if a common subexpression was folded.
-//
-//===----------------------------------------------------------------------===//
-
-bool GCSE::visitUnaryOperator(Instruction &I) {
- Value *Op = I.getOperand(0);
- Function *F = I.getParent()->getParent();
-
- for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
- UI != UE; ++UI)
- if (Instruction *Other = dyn_cast<Instruction>(*UI))
- // Check to see if this new binary operator is not I, but same operand...
- if (Other != &I && Other->getOpcode() == I.getOpcode() &&
- Other->getOperand(0) == Op && // Is the operand the same?
- // Is it embeded in the same function? (This could be false if LHS
- // is a constant or global!)
- Other->getParent()->getParent() == F &&
-
- // Check that the types are the same, since this code handles casts...
- Other->getType() == I.getType()) {
-
- // These instructions are identical. Handle the situation.
- CommonSubExpressionFound(&I, Other);
- return true; // One instruction eliminated!
- }
-
- return false;
-}
-
-// isIdenticalBinaryInst - Return true if the two binary instructions are
-// identical.
-//
-static inline bool isIdenticalBinaryInst(const Instruction &I1,
- const Instruction *I2) {
- // Is it embeded in the same function? (This could be false if LHS
- // is a constant or global!)
- if (I1.getOpcode() != I2->getOpcode() ||
- I1.getParent()->getParent() != I2->getParent()->getParent())
- return false;
-
- // They are identical if both operands are the same!
- if (I1.getOperand(0) == I2->getOperand(0) &&
- I1.getOperand(1) == I2->getOperand(1))
- return true;
-
- // If the instruction is commutative and associative, the instruction can
- // match if the operands are swapped!
- //
- if ((I1.getOperand(0) == I2->getOperand(1) &&
- I1.getOperand(1) == I2->getOperand(0)) &&
- (I1.getOpcode() == Instruction::Add ||
- I1.getOpcode() == Instruction::Mul ||
- I1.getOpcode() == Instruction::And ||
- I1.getOpcode() == Instruction::Or ||
- I1.getOpcode() == Instruction::Xor))
- return true;
-
- return false;
-}
-
-bool GCSE::visitBinaryOperator(Instruction &I) {
- Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
- Function *F = I.getParent()->getParent();
-
- for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
- UI != UE; ++UI)
- if (Instruction *Other = dyn_cast<Instruction>(*UI))
- // Check to see if this new binary operator is not I, but same operand...
- if (Other != &I && isIdenticalBinaryInst(I, Other)) {
- // These instructions are identical. Handle the situation.
- CommonSubExpressionFound(&I, Other);
- return true; // One instruction eliminated!
- }
-
- return false;
-}
-
-// IdenticalComplexInst - Return true if the two instructions are the same, by
-// using a brute force comparison.
-//
-static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
- assert(I1->getOpcode() == I2->getOpcode());
- // Equal if they are in the same function...
- return I1->getParent()->getParent() == I2->getParent()->getParent() &&
- // And return the same type...
- I1->getType() == I2->getType() &&
- // And have the same number of operands...
- I1->getNumOperands() == I2->getNumOperands() &&
- // And all of the operands are equal.
- std::equal(I1->op_begin(), I1->op_end(), I2->op_begin());
-}
-
-bool GCSE::visitGetElementPtrInst(GetElementPtrInst &I) {
- Value *Op = I.getOperand(0);
- Function *F = I.getParent()->getParent();
-
- for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
- UI != UE; ++UI)
- if (GetElementPtrInst *Other = dyn_cast<GetElementPtrInst>(*UI))
- // Check to see if this new getelementptr is not I, but same operand...
- if (Other != &I && IdenticalComplexInst(&I, Other)) {
- // These instructions are identical. Handle the situation.
- CommonSubExpressionFound(&I, Other);
- return true; // One instruction eliminated!
- }
-
- return false;
-}
-
-bool GCSE::visitLoadInst(LoadInst &LI) {
- Value *Op = LI.getOperand(0);
- Function *F = LI.getParent()->getParent();
-
- for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
- UI != UE; ++UI)
- if (LoadInst *Other = dyn_cast<LoadInst>(*UI))
- // Check to see if this new load is not LI, but has the same operands...
- if (Other != &LI && IdenticalComplexInst(&LI, Other) &&
- TryToRemoveALoad(&LI, Other))
- return true; // An instruction was eliminated!
-
- return false;
-}
-
-static inline bool isInvalidatingInst(const Instruction &I) {
- return I.getOpcode() == Instruction::Store ||
- I.getOpcode() == Instruction::Call ||
- I.getOpcode() == Instruction::Invoke;
-}
-
-// TryToRemoveALoad - Try to remove one of L1 or L2. The problem with removing
-// loads is that intervening stores might make otherwise identical load's yield
-// different values. To ensure that this is not the case, we check that there
-// are no intervening stores or calls between the instructions.
-//
-bool GCSE::TryToRemoveALoad(LoadInst *L1, LoadInst *L2) {
- // Figure out which load dominates the other one. If neither dominates the
- // other we cannot eliminate one...
- //
- if (DomSetInfo->dominates(L2, L1))
- std::swap(L1, L2); // Make L1 dominate L2
- else if (!DomSetInfo->dominates(L1, L2))
- return false; // Neither instruction dominates the other one...
-
- BasicBlock *BB1 = L1->getParent(), *BB2 = L2->getParent();
-
- BasicBlock::iterator L1I = L1;
-
- // L1 now dominates L2. Check to see if the intervening instructions between
- // the two loads include a store or call...
- //
- if (BB1 == BB2) { // In same basic block?
- // In this degenerate case, no checking of global basic blocks has to occur
- // just check the instructions BETWEEN L1 & L2...
- //
- for (++L1I; &*L1I != L2; ++L1I)
- if (isInvalidatingInst(*L1I))
- return false; // Cannot eliminate load
-
- ++NumLoadRemoved;
- CommonSubExpressionFound(L1, L2);
- return true;
- } else {
- // Make sure that there are no store instructions between L1 and the end of
- // it's basic block...
- //
- for (++L1I; L1I != BB1->end(); ++L1I)
- if (isInvalidatingInst(*L1I)) {
- BBContainsStore[BB1] = true;
- return false; // Cannot eliminate load
- }
-
- // Make sure that there are no store instructions between the start of BB2
- // and the second load instruction...
- //
- for (BasicBlock::iterator II = BB2->begin(); &*II != L2; ++II)
- if (isInvalidatingInst(*II)) {
- BBContainsStore[BB2] = true;
- return false; // Cannot eliminate load
- }
-
- // Do a depth first traversal of the inverse CFG starting at L2's block,
- // looking for L1's block. The inverse CFG is made up of the predecessor
- // nodes of a block... so all of the edges in the graph are "backward".
- //
- set<BasicBlock*> VisitedSet;
- for (pred_iterator PI = pred_begin(BB2), PE = pred_end(BB2); PI != PE; ++PI)
- if (CheckForInvalidatingInst(*PI, BB1, VisitedSet))
- return false;
-
- ++NumLoadRemoved;
- CommonSubExpressionFound(L1, L2);
- return true;
- }
- return false;
-}
-
-// CheckForInvalidatingInst - Return true if BB or any of the predecessors of BB
-// (until DestBB) contain a store (or other invalidating) instruction.
-//
-bool GCSE::CheckForInvalidatingInst(BasicBlock *BB, BasicBlock *DestBB,
- set<BasicBlock*> &VisitedSet) {
- // Found the termination point!
- if (BB == DestBB || VisitedSet.count(BB)) return false;