Use the expression map correctly.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@1140 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 188 insertions, 49 deletions

diff --git a/lib/Transforms/ExprTypeConvert.cpp b/lib/Transforms/ExprTypeConvert.cpp
index d7b1b77..5c94f8c 100644
--- a/lib/Transforms/ExprTypeConvert.cpp
+++ b/lib/Transforms/ExprTypeConvert.cpp
@@ -19,6 +19,22 @@
 
 #include "llvm/Assembly/Writer.h"
 
+//#define DEBUG_EXPR_CONVERT 1
+
+static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
+  ValueTypeCache::iterator I = CT.find(V);
+  if (I == CT.end()) return V->getType();
+  return I->second;
+}
+
+
+static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
+                                     ValueTypeCache &ConvertedTypes);
+
+static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
+                                 ValueMapCache &VMC);
+
+
 // ExpressionConvertableToType - Return true if it is possible
 static bool ExpressionConvertableToType(Value *V, const Type *Ty,
                                         ValueTypeCache &CTMap) {
@@ -26,6 +42,14 @@ static bool ExpressionConvertableToType(Value *V, const Type *Ty,
   if (CTMI != CTMap.end()) return CTMI->second == Ty;
   CTMap[V] = Ty;
 
+  // Expressions are only convertable if all of the users of the expression can
+  // have this value converted.  This makes use of the map to avoid infinite
+  // recursion.
+  //
+  for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I)
+    if (!OperandConvertableToType(*I, V, Ty, CTMap))
+      return false;
+
   Instruction *I = dyn_cast<Instruction>(V);
   if (I == 0) {
     // It's not an instruction, check to see if it's a constant... all constants
@@ -101,6 +125,10 @@ static bool ExpressionConvertableToType(Value *V, const Type *Ty,
 
 static Value *ConvertExpressionToType(Value *V, const Type *Ty,
                                       ValueMapCache &VMC) {
+  ValueMapCache::ExprMapTy::iterator VMCI = VMC.ExprMap.find(V);
+  if (VMCI != VMC.ExprMap.end())
+    return VMCI->second;
+
   Instruction *I = dyn_cast<Instruction>(V);
   if (I == 0)
     if (ConstPoolVal *CPV = cast<ConstPoolVal>(V)) {
@@ -109,6 +137,9 @@ static Value *ConvertExpressionToType(Value *V, const Type *Ty,
       Value *Result = opt::ConstantFoldCastInstruction(CPV, Ty);
       if (!Result) cerr << "Couldn't fold " << CPV << " to " << Ty << endl;
       assert(Result && "ConstantFoldCastInstruction Failed!!!");
+
+      // Add the instruction to the expression map
+      VMC.ExprMap[V] = Result;
       return Result;
     }
 
@@ -194,26 +225,29 @@ static Value *ConvertExpressionToType(Value *V, const Type *Ty,
   assert(It != BIL.end() && "Instruction not in own basic block??");
   BIL.insert(It, Res);
 
-  //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
-
-  return Res;
-}
-
-
-
-
+  // Add the instruction to the expression map
+  VMC.ExprMap[I] = Res;
 
+  // Expressions are only convertable if all of the users of the expression can
+  // have this value converted.  This makes use of the map to avoid infinite
+  // recursion.
+  //
+  unsigned NumUses = I->use_size();
+  for (unsigned It = 0; It < NumUses; ) {
+    unsigned OldSize = NumUses;
+    ConvertOperandToType(*(I->use_begin()+It), I, Res, VMC);
+    NumUses = I->use_size();
+    if (NumUses == OldSize) ++It;
+  }
 
+#ifdef DEBUG_EXPR_CONVERT
+  cerr << "ExpIn: " << I << "ExpOut: " << Res;
+#endif
 
-static inline const Type *getTy(const Value *V, ValueTypeCache &CT) {
-  ValueTypeCache::iterator I = CT.find(V);
-  if (I == CT.end()) return V->getType();
-  return I->second;
+  return Res;
 }
 
 
-static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
-                                     ValueTypeCache &ConvertedTypes);
 
 // RetValConvertableToType - Return true if it is possible
 bool RetValConvertableToType(Value *V, const Type *Ty,
@@ -233,6 +267,11 @@ bool RetValConvertableToType(Value *V, const Type *Ty,
 }
 
 
+
+
+
+
+
 // OperandConvertableToType - Return true if it is possible to convert operand
 // V of User (instruction) U to the specified type.  This is true iff it is
 // possible to change the specified instruction to accept this.  CTMap is a map
@@ -347,29 +386,42 @@ static bool OperandConvertableToType(User *U, Value *V, const Type *Ty,
 }
 
 
-
-
-
-
-static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
-                                 ValueMapCache &VMC);
-
 void ConvertUsersType(Value *V, Value *NewVal, ValueMapCache &VMC) {
-  
-  // It is safe to convert the specified value to the specified type IFF all of
-  // the uses of the value can be converted to accept the new typed value.
-  //
-  while (!V->use_empty()) {
-    unsigned OldSize = V->use_size();
-    ConvertOperandToType(V->use_back(), V, NewVal, VMC);
-    assert(V->use_size() != OldSize && "Use didn't detatch from value!");
+  unsigned NumUses = V->use_size();
+  for (unsigned It = 0; It < NumUses; ) {
+    unsigned OldSize = NumUses;
+    ConvertOperandToType(*(V->use_begin()+It), V, NewVal, VMC);
+    NumUses = V->use_size();
+    if (NumUses == OldSize) ++It;
   }
+
+  if (NumUses == 0)
+    if (Instruction *I = dyn_cast<Instruction>(V)) {
+      BasicBlock *BB = I->getParent();
+
+      // Now we just need to remove the old instruction so we don't get infinite
+      // loops.  Note that we cannot use DCE because DCE won't remove a store
+      // instruction, for example.
+      //
+      BasicBlock::iterator It = find(BB->begin(), BB->end(), I);
+      assert(It != BB->end() && "Instruction no longer in basic block??");
+#ifdef DEBUG_EXPR_CONVERT
+      cerr << "DELETING: " << (void*)I << " " << I;
+#endif
+      delete BB->getInstList().remove(It);
+    }
 }
 
 
 
 static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
                                  ValueMapCache &VMC) {
+  if (isa<ValueHandle>(U)) return;  // Valuehandles don't let go of operands...
+
+  if (VMC.OperandsMapped.count(make_pair(U, OldVal))) return;
+
+  VMC.OperandsMapped.insert(make_pair(U, OldVal));
+
   Instruction *I = cast<Instruction>(U);  // Only Instructions convertable
 
   BasicBlock *BB = I->getParent();
@@ -379,6 +431,12 @@ static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
 
   //cerr << endl << endl << "Type:\t" << Ty << "\nInst: " << I << "BB Before: " << BB << endl;
 
+  // Prevent I from being removed...
+  ValueHandle IHandle(I);
+#ifdef DEBUG_EXPR_CONVERT
+  cerr << "VH AQUIRING: " << I;
+#endif
+
   switch (I->getOpcode()) {
   case Instruction::Cast:
     assert(I->getOperand(0) == OldVal);
@@ -472,23 +530,63 @@ static void ConvertOperandToType(User *U, Value *OldVal, Value *NewVal,
   assert(It != BIL.end() && "Instruction not in own basic block??");
   BIL.insert(It, Res);   // Keep It pointing to old instruction
 
-#if DEBUG_PEEPHOLE_INSTS
+#ifdef DEBUG_EXPR_CONVERT
   cerr << "In: " << I << "Out: " << Res;
 #endif
 
-  //cerr << "RInst: " << Res << "BB After: " << BB << endl << endl;
-
   if (I->getType() != Res->getType())
     ConvertUsersType(I, Res, VMC);
-  else
-    I->replaceAllUsesWith(Res);
+  else {
+    for (unsigned It = 0; It < I->use_size(); ) {
+      User *Use = *(I->use_begin()+It);
+      if (isa<ValueHandle>(Use))            // Don't remove ValueHandles!
+        ++It;
+      else
+        Use->replaceUsesOfWith(I, Res);
+    }
+
+    if (I->use_size() == 0) {
+      // Now we just need to remove the old instruction so we don't get infinite
+      // loops.  Note that we cannot use DCE because DCE won't remove a store
+      // instruction, for example.
+      //
+      BasicBlock::iterator It = find(BIL.begin(), BIL.end(), I);
+      assert(It != BIL.end() && "Instruction no longer in basic block??");
+#ifdef DEBUG_EXPR_CONVERT
+      cerr << "DELETING: " << (void*)I << " " << I;
+#endif
+      delete BIL.remove(It);
+    } else {
+      for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
+           UI != UE; ++UI)
+        assert(isa<ValueHandle>((Value*)*UI) && "Uses of Instruction remain!!!");
+    }
+  }
+}
+
 
-  // Now we just need to remove the old instruction so we don't get infinite
-  // loops.  Note that we cannot use DCE because DCE won't remove a store
-  // instruction, for example.
-  assert(I->use_size() == 0 && "Uses of Instruction remain!!!");
+ValueHandle::~ValueHandle() {
+  if (Operands[0]->use_size() == 1) {
+    Value *V = Operands[0];
+    Operands.clear();   // Drop use!
 
-  It = find(BIL.begin(), BIL.end(), I);
-  assert(It != BIL.end() && "Instruction no longer in basic block??");
-  delete BIL.remove(It);
+    // Now we just need to remove the old instruction so we don't get infinite
+    // loops.  Note that we cannot use DCE because DCE won't remove a store
+    // instruction, for example.
+    //
+    Instruction *I = cast<Instruction>(V);
+    BasicBlock *BB = I->getParent();
+    assert(BB && "Inst not in basic block!");
+
+    BasicBlock::iterator It = find(BB->begin(), BB->end(), I);
+    assert(It != BB->end() && "Instruction no longer in basic block??");
+#ifdef DEBUG_EXPR_CONVERT
+    cerr << "VH DELETING: " << (void*)I << " " << I;
+#endif
+    delete BB->getInstList().remove(It);
+  } else {
+#ifdef DEBUG_EXPR_CONVERT
+    cerr << "VH RELEASING: " << Operands[0];
+#endif
+  }
 }
diff --git a/lib/Transforms/LevelRaise.cpp b/lib/Transforms/LevelRaise.cpp
index 6883008..ccba32b 100644
--- a/lib/Transforms/LevelRaise.cpp
+++ b/lib/Transforms/LevelRaise.cpp
@@ -42,7 +42,7 @@
 
 #include "llvm/Assembly/Writer.h"
 
-#define DEBUG_PEEPHOLE_INSTS 1
+//#define DEBUG_PEEPHOLE_INSTS 1
 
 #ifdef DEBUG_PEEPHOLE_INSTS
 #define PRINT_PEEPHOLE(ID, NUM, I)            \
@@ -356,11 +356,8 @@ static bool PeepholeOptimize(BasicBlock *BB, BasicBlock::iterator &BI) {
         PRINT_PEEPHOLE2("CAST-DEST-EXPR-CONV:in ", CI, Src);
 
         ValueMapCache ValueMap;
-        ConvertUsersType(CI, Src, ValueMap);
-        if (!Src->hasName() && CI->hasName()) {
-          string Name = CI->getName(); CI->setName("");
-          Src->setName(Name, BB->getParent()->getSymbolTable());
-        }
+        ConvertUsersType(CI, Src, ValueMap);  // This will delete CI!
+
         BI = BB->begin();  // Rescan basic block.  BI might be invalidated.
         PRINT_PEEPHOLE1("CAST-DEST-EXPR-CONV:out", I);
         return true;
diff --git a/lib/Transforms/TransformInternals.h b/lib/Transforms/TransformInternals.h
index e6e65ef..5c753c5 100644
--- a/lib/Transforms/TransformInternals.h
+++ b/lib/Transforms/TransformInternals.h
@@ -9,8 +9,10 @@
 #define TRANSFORM_INTERNALS_H
 
 #include "llvm/BasicBlock.h"
+#include "llvm/Instruction.h"
 #include "llvm/Target/TargetData.h"
 #include <map>
+#include <set>
 
 // TargetData Hack: Eventually we will have annotations given to us by the
 // backend so that we know stuff about type size and alignments.  For now
@@ -43,8 +45,20 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 
 // ------------- Expression Conversion ---------------------
 
-typedef map<const Value*, const Type*> ValueTypeCache;
-typedef map<const Value*, Value*>      ValueMapCache;
+typedef map<const Value*, const Type*>         ValueTypeCache;
+
+struct ValueMapCache {
+  // Operands mapped - Contains an entry if the first value (the user) has had
+  // the second value (the operand) mapped already.
+  //
+  set<pair<const User*, const Value*> > OperandsMapped;
+
+  // Expression Map - Contains an entry from the old value to the new value of
+  // an expression that has been converted over.
+  //
+  map<const Value *, Value *> ExprMap;
+  typedef map<const Value *, Value *> ExprMapTy;
+};
 
 // RetValConvertableToType - Return true if it is possible
 bool RetValConvertableToType(Value *V, const Type *Ty,
@@ -53,4 +67,34 @@ bool RetValConvertableToType(Value *V, const Type *Ty,
 void ConvertUsersType(Value *V, Value *NewVal, ValueMapCache &VMC);
 
 
+//===----------------------------------------------------------------------===//
+//  ValueHandle Class - Smart pointer that occupies a slot on the users USE list
+//  that prevents it from being destroyed.  This "looks" like an Instruction
+//  with Opcode UserOp1.
+// 
+class ValueHandle : public Instruction {
+  ValueHandle(const ValueHandle &); // DO NOT IMPLEMENT
+public:
+  ValueHandle(Value *V) : Instruction(Type::VoidTy, UserOp1, "") {
+    Operands.push_back(Use(V, this));
+  }
+
+  ~ValueHandle();
+
+  virtual Instruction *clone() const { abort(); return 0; }
+
+  virtual const char *getOpcodeName() const {
+    return "ValueHandle";
+  }
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const ValueHandle *) { return true; }
+  static inline bool classof(const Instruction *I) {
+    return (I->getOpcode() == Instruction::UserOp1);
+  }
+  static inline bool classof(const Value *V) {
+    return isa<Instruction>(V) && classof(cast<Instruction>(V));
+  }
+};
+
 #endif