Populate and walk loop queue.

[oota-llvm.git] / lib / Analysis / ValueNumbering.cpp

diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp
index 06482224544c2be37953d02b57e330c894d3c601..963ccb90f3ea7cacb9c3680d9c21b77789556318 100644 (file)
--- a/lib/Analysis/ValueNumbering.cpp
+++ b/lib/Analysis/ValueNumbering.cpp
@@ -19,6 +19,7 @@
 #include "llvm/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Type.h"
+#include "llvm/Support/Compiler.h"
 using namespace llvm;
 
 // Register the ValueNumbering interface, providing a nice name to refer to.
@@ -48,7 +49,8 @@ namespace {
   /// lexically identical expressions.  This does not require any ahead of time
   /// analysis, so it is a very fast default implementation.
   ///
-  struct BasicVN : public ImmutablePass, public ValueNumbering {
+  struct VISIBILITY_HIDDEN BasicVN 
+      : public ImmutablePass, public ValueNumbering {
     /// getEqualNumberNodes - Return nodes with the same value number as the
     /// specified Value.  This fills in the argument vector with any equal
     /// values.
@@ -60,21 +62,22 @@ namespace {
   };
 
   // Register this pass...
-  RegisterOpt<BasicVN>
+  RegisterPass<BasicVN>
   X("basicvn", "Basic Value Numbering (default GVN impl)");
 
   // Declare that we implement the ValueNumbering interface
-  RegisterAnalysisGroup<ValueNumbering, BasicVN, true> Y;
+  RegisterAnalysisGroup<ValueNumbering, true> Y(X);
 
   /// BVNImpl - Implement BasicVN in terms of a visitor class that
   /// handles the different types of instructions as appropriate.
   ///
-  struct BVNImpl : public InstVisitor<BVNImpl> {
+  struct VISIBILITY_HIDDEN BVNImpl : public InstVisitor<BVNImpl> {
     std::vector<Value*> &RetVals;
     BVNImpl(std::vector<Value*> &RV) : RetVals(RV) {}
 
     void visitCastInst(CastInst &I);
     void visitGetElementPtrInst(GetElementPtrInst &I);
+    void visitCmpInst(CmpInst &I);
 
     void handleBinaryInst(Instruction &I);
     void visitBinaryOperator(Instruction &I)     { handleBinaryInst(I); }
@@ -112,8 +115,10 @@ void BVNImpl::visitCastInst(CastInst &CI) {
   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
        UI != UE; ++UI)
     if (CastInst *Other = dyn_cast<CastInst>(*UI))
-      // Check that the types are the same, since this code handles casts...
-      if (Other->getType() == I.getType() &&
+      // Check that the opcode is the same
+      if (Other->getOpcode() == Instruction::CastOps(I.getOpcode()) &&
+          // Check that the destination types are the same
+          Other->getType() == I.getType() &&
           // Is it embedded in the same function?  (This could be false if LHS
           // is a constant or global!)
           Other->getParent()->getParent() == F &&
@@ -124,6 +129,28 @@ void BVNImpl::visitCastInst(CastInst &CI) {
       }
 }
 
+void  BVNImpl::visitCmpInst(CmpInst &CI1) {
+  Value *LHS = CI1.getOperand(0);
+  for (Value::use_iterator UI = LHS->use_begin(), UE = LHS->use_end();
+       UI != UE; ++UI)
+    if (CmpInst *CI2 = dyn_cast<CmpInst>(*UI))
+      // Check to see if this compare instruction is not CI, but same opcode,
+      // same predicate, and in the same function.
+      if (CI2 != &CI1 && CI2->getOpcode() == CI1.getOpcode() &&
+          CI2->getPredicate() == CI1.getPredicate() &&
+          CI2->getParent()->getParent() == CI1.getParent()->getParent())
+        // If the operands are the same
+        if ((CI2->getOperand(0) == CI1.getOperand(0) &&
+            CI2->getOperand(1) == CI1.getOperand(1)) ||
+            // Or the compare is commutative and the operands are reversed 
+            (CI1.isCommutative() && 
+             CI2->getOperand(0) == CI1.getOperand(1) &&
+             CI2->getOperand(1) == CI1.getOperand(0)))
+          // Then the instructiosn are identical, add to list.
+          RetVals.push_back(CI2);
+}
+
+
 
 // isIdenticalBinaryInst - Return true if the two binary instructions are
 // identical.
@@ -136,6 +163,11 @@ static inline bool isIdenticalBinaryInst(const Instruction &I1,
       I1.getParent()->getParent() != I2->getParent()->getParent())
     return false;
 
+  // If they are CmpInst instructions, check their predicates
+  if (CmpInst *CI1 = dyn_cast<CmpInst>(&const_cast<Instruction&>(I1)))
+    if (CI1->getPredicate() != cast<CmpInst>(I2)->getPredicate())
+      return false;
+
   // They are identical if both operands are the same!
   if (I1.getOperand(0) == I2->getOperand(0) &&
       I1.getOperand(1) == I2->getOperand(1))
@@ -239,4 +271,5 @@ void BVNImpl::handleTernaryInst(Instruction &I) {
 }
 
 
-int llvm::BasicValueNumberingStub; // to ensure linkage of this file
+// Ensure that users of ValueNumbering.h will link with this file
+DEFINING_FILE_FOR(BasicValueNumbering)