- BasicBlock::iterator BI = find(BB2->begin(), BB2->end(), Other);
- assert(BI != BB2->end() && "I not in parent basic block!");
- ReplaceInstWithInst(I, BI);
- }
-}
-
-//===----------------------------------------------------------------------===//
-//
-// 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();
-
- // FIXME: This is incredibly painful with broken rep
- BasicBlock::iterator L1I = std::find(BB1->begin(), BB1->end(), L1);
- assert(L1I != BB1->end() && "Inst not in own parent?");
-
- // 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;