*FINALLY* Fix a really nasty nondeterministic bug that has been haunting us

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

diff --git a/lib/Analysis/ValueNumbering.cpp b/lib/Analysis/ValueNumbering.cpp
index 32e4439eaaba591352d68eed59b1847e6053aad2..49b75bd6acc05b40f6ea6871ba1cb0883de01054 100644 (file)
--- a/lib/Analysis/ValueNumbering.cpp
+++ b/lib/Analysis/ValueNumbering.cpp
@@ -1,4 +1,11 @@
 //===- ValueNumbering.cpp - Value #'ing Implementation ----------*- C++ -*-===//
+// 
+//                     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 file implements the non-abstract Value Numbering methods as well as a
 // default implementation for the analysis group.
@@ -8,9 +15,10 @@
 #include "llvm/Analysis/ValueNumbering.h"
 #include "llvm/Support/InstVisitor.h"
 #include "llvm/BasicBlock.h"
+#include "llvm/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Type.h"
-#include "llvm/iMemory.h"
+using namespace llvm;
 
 // Register the ValueNumbering interface, providing a nice name to refer to.
 static RegisterAnalysisGroup<ValueNumbering> X("Value Numbering");
@@ -32,24 +40,14 @@ ValueNumbering::~ValueNumbering() {}
 // into the tool that uses it.  As such, we register and implement the class
 // here.
 //
+
 namespace {
   /// BasicVN - This class is the default implementation of the ValueNumbering
   /// interface.  It walks the SSA def-use chains to trivially identify
   /// lexically identical expressions.  This does not require any ahead of time
   /// analysis, so it is a very fast default implementation.
   ///
-  struct BasicVN : public FunctionPass, public ValueNumbering {
-  
-    /// Pass Implementation stuff.  This isn't much of a pass.
-    ///
-    bool runOnFunction(Function &) { return false; }
-    
-    /// getAnalysisUsage - Does not modify anything.
-    ///
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.setPreservesAll();
-    }
-  
+  struct 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.
@@ -66,9 +64,7 @@ namespace {
 
   // Declare that we implement the ValueNumbering interface
   RegisterAnalysisGroup<ValueNumbering, BasicVN, true> Y;
-}  // End of anonymous namespace
 
-namespace {
   /// BVNImpl - Implement BasicVN in terms of a visitor class that
   /// handles the different types of instructions as appropriate.
   ///
@@ -107,17 +103,14 @@ void BVNImpl::visitCastInst(CastInst &CI) {
   
   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 cast is not I, but has the 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
+    if (CastInst *Other = dyn_cast<CastInst>(*UI))
+      // Check that the types are the same, since this code handles casts...
+      if (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 &&
-
-          // Check that the types are the same, since this code handles casts...
-          Other->getType() == I.getType()) {
-        
+          // Check to see if this new cast is not I.
+          Other != &I) {
         // These instructions are identical.  Add to list...
         RetVals.push_back(Other);
       }
@@ -129,7 +122,7 @@ void BVNImpl::visitCastInst(CastInst &CI) {
 //
 static inline bool isIdenticalBinaryInst(const Instruction &I1,
                                          const Instruction *I2) {
-  // Is it embeded in the same function?  (This could be false if LHS
+  // Is it embedded 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())
@@ -140,16 +133,12 @@ static inline bool isIdenticalBinaryInst(const Instruction &I1,
       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 the instruction is commutative, 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))
+      I1.isCommutative())
     return true;
 
   return false;
@@ -187,7 +176,14 @@ static bool IdenticalComplexInst(const Instruction *I1, const Instruction *I2) {
 
 void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) {
   Value *Op = I.getOperand(0);
-  Function *F = I.getParent()->getParent();
+
+  // Try to pick a local operand if possible instead of a constant or a global
+  // that might have a lot of uses.
+  for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i)
+    if (isa<Instruction>(I.getOperand(i)) || isa<Argument>(I.getOperand(i))) {
+      Op = I.getOperand(i);
+      break;
+    }
   
   for (Value::use_iterator UI = Op->use_begin(), UE = Op->use_end();
        UI != UE; ++UI)
@@ -198,3 +194,5 @@ void BVNImpl::visitGetElementPtrInst(GetElementPtrInst &I) {
         RetVals.push_back(Other);
       }
 }
+
+void llvm::BasicValueNumberingStub() { }