PNaCl: Fix ReplacePtrsWithInts to handle some corner cases correctly

Running the LLVM test suite with the ReplacePtrsWithInts pass enabled
produced a single failure (in MultiSource/Applications/SPASS),
revealing a corner case in which a mixture of forward and backward
references plus a bitcast causes the pass to fail (see
@forwards_reference() in the test).

The problem was that we were doing replaceAllUsesWith() on a
placeholder value too early.  RewriteMap was mapping a bitcast to a
placeholder P, but RewriteMap's reference to P didn't get updated by
P->replaceAllUsesWith() and P became a dangling pointer.

The fix is:

 * Change convert() to strip off casts first, so that RewriteMap isn't
   used for mapping casts to converted values.

 * Defer the replaceAllUsesWith() calls until after creating all the
   replacement instructions.  This makes the pass more robust against
   instruction ordering in the input.

   This requires debug instrinsics to be updated in a separate pass,
   because replaceAllUsesWith() doesn't work for references by
   metadata nodes.

This also fixes some pathological corner cases of cyclic references in
unreachable blocks.

Fix indentation in one place.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3343
TEST=replace-ptrs-with-ints.ll + LLVM test suite

Review URL: https://codereview.chromium.org/15761003

2 files changed, 182 insertions, 48 deletions

diff --git a/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp b/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
index 4ca5b59e00..619ae04826 100644
--- a/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
+++ b/lib/Transforms/NaCl/ReplacePtrsWithInts.cpp
@@ -43,6 +43,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Function.h"
@@ -77,21 +78,16 @@ namespace {
     Type *IntPtrType;
 
     struct RewrittenVal {
-      RewrittenVal(): IsPlaceholder(true), NewIntVal(NULL) {}
-      bool IsPlaceholder;
+      RewrittenVal(): Placeholder(NULL), NewIntVal(NULL) {}
+      Value *Placeholder;
       Value *NewIntVal;
     };
     // Maps from old values (of pointer type) to converted values (of
     // IntPtrType type).
     DenseMap<Value *, RewrittenVal> RewriteMap;
-    // Number of placeholders; used for detecting unhandled cases.
-    int PlaceholderCount;
-    // List of instructions whose deletion has been deferred.
-    SmallVector<Instruction *, 20> ToErase;
 
   public:
-    FunctionConverter(Type *IntPtrType)
-      : IntPtrType(IntPtrType), PlaceholderCount(0) {}
+    FunctionConverter(Type *IntPtrType) : IntPtrType(IntPtrType) {}
 
     // Returns the normalized version of the given type, converting
     // pointer types to IntPtrType.
@@ -106,8 +102,19 @@ namespace {
     void recordConverted(Value *From, Value *To);
     void recordConvertedAndErase(Instruction *From, Value *To);
 
+    // Returns Val with no-op casts (those that convert between
+    // IntPtrType and pointer types) stripped off.
+    Value *stripNoopCasts(Value *Val);
+
     // Returns the normalized version of the given value.
-    Value *convert(Value *Val);
+    //
+    // If the conversion of Val has been deferred, this returns a
+    // placeholder object, which will later be replaceAllUsesWith'd to
+    // the final value.  Since replaceAllUsesWith does not work on
+    // references by metadata nodes, this can be bypassed using
+    // BypassPlaceholder to get the real converted value, assuming it
+    // is available.
+    Value *convert(Value *Val, bool BypassPlaceholder = false);
     // Returns the NormalizedPtr form of the given pointer value.
     // Inserts conversion instructions at InsertPt.
     Value *convertBackToPtr(Value *Val, Instruction *InsertPt);
@@ -119,6 +126,9 @@ namespace {
     void convertInPlace(Instruction *Inst);
 
     void eraseReplacedInstructions();
+
+    // List of instructions whose deletion has been deferred.
+    SmallVector<Instruction *, 20> ToErase;
   };
 }
 
@@ -144,14 +154,7 @@ void FunctionConverter::recordConverted(Value *From, Value *To) {
     return;
   }
   RewrittenVal *RV = &RewriteMap[From];
-  if (RV->NewIntVal) {
-    assert(RV->IsPlaceholder);
-    // Resolve placeholder.
-    RV->NewIntVal->replaceAllUsesWith(To);
-    delete RV->NewIntVal;
-    RV->IsPlaceholder = false;
-    --PlaceholderCount;
-  }
+  assert(!RV->NewIntVal);
   RV->NewIntVal = To;
 }
 
@@ -161,35 +164,56 @@ void FunctionConverter::recordConvertedAndErase(Instruction *From, Value *To) {
   ToErase.push_back(From);
 }
 
-Value *FunctionConverter::convert(Value *Val) {
+Value *FunctionConverter::stripNoopCasts(Value *Val) {
+  SmallPtrSet<Value *, 4> Visited;
+  for (;;) {
+    if (!Visited.insert(Val)) {
+      // It is possible to get a circular reference in unreachable
+      // basic blocks.  Handle this case for completeness.
+      return UndefValue::get(Val->getType());
+    }
+    if (CastInst *Cast = dyn_cast<CastInst>(Val)) {
+      Value *Src = Cast->getOperand(0);
+      if ((isa<BitCastInst>(Cast) && Cast->getType()->isPointerTy()) ||
+          (isa<PtrToIntInst>(Cast) && Cast->getType() == IntPtrType) ||
+          (isa<IntToPtrInst>(Cast) && Src->getType() == IntPtrType)) {
+        Val = Src;
+        continue;
+      }
+    }
+    return Val;
+  }
+}
+
+Value *FunctionConverter::convert(Value *Val, bool BypassPlaceholder) {
+  Val = stripNoopCasts(Val);
   if (!Val->getType()->isPointerTy())
     return Val;
   if (Constant *C = dyn_cast<Constant>(Val))
     return ConstantExpr::getPtrToInt(C, IntPtrType);
   RewrittenVal *RV = &RewriteMap[Val];
-  if (!RV->NewIntVal) {
-    // No converted value available yet, so create a placeholder.
-    Argument *Placeholder = new Argument(convertType(Val->getType()));
-    RV->NewIntVal = Placeholder;
-    ++PlaceholderCount;
+  if (BypassPlaceholder) {
+    assert(RV->NewIntVal);
+    return RV->NewIntVal;
   }
-  return RV->NewIntVal;
+  if (!RV->Placeholder)
+    RV->Placeholder = new Argument(convertType(Val->getType()));
+  return RV->Placeholder;
 }
 
 Value *FunctionConverter::convertBackToPtr(Value *Val, Instruction *InsertPt) {
   Type *NewTy =
     convertType(Val->getType()->getPointerElementType())->getPointerTo();
-  Value *Conv = convert(Val);
-  return new IntToPtrInst(Conv, NewTy, Conv->getName() + ".asptr", InsertPt);
+  return new IntToPtrInst(convert(Val), NewTy, "", InsertPt);
 }
 
 Value *FunctionConverter::convertFunctionPtr(Value *Callee,
                                              Instruction *InsertPt) {
   FunctionType *FuncType = cast<FunctionType>(
       Callee->getType()->getPointerElementType());
-  Value *Conv = convert(Callee);
-  return new IntToPtrInst(Conv, convertFuncType(FuncType)->getPointerTo(),
-                          Conv->getName() + ".asfuncptr", InsertPt);
+  return new IntToPtrInst(convert(Callee),
+                          convertFuncType(FuncType)->getPointerTo(),
+                          "", InsertPt);
 }
 
 static bool ShouldLeaveAlone(Value *V) {
@@ -206,8 +230,7 @@ void FunctionConverter::convertInPlace(Instruction *Inst) {
     Value *Arg = Inst->getOperand(I);
     if (Arg->getType()->isPointerTy() && !ShouldLeaveAlone(Arg)) {
       Value *Conv = convert(Arg);
-      Inst->setOperand(I, new IntToPtrInst(convert(Arg), Arg->getType(),
-                                           Conv->getName() + ".asptr", Inst));
+      Inst->setOperand(I, new IntToPtrInst(Conv, Arg->getType(), "", Inst));
     }
   }
   // Convert result.
@@ -220,14 +243,29 @@ void FunctionConverter::convertInPlace(Instruction *Inst) {
 }
 
 void FunctionConverter::eraseReplacedInstructions() {
-  if (PlaceholderCount) {
-    for (DenseMap<Value *, RewrittenVal>::iterator I = RewriteMap.begin(),
-             E = RewriteMap.end(); I != E; ++I) {
-      if (I->second.IsPlaceholder)
+  bool Error = false;
+  for (DenseMap<Value *, RewrittenVal>::iterator I = RewriteMap.begin(),
+           E = RewriteMap.end(); I != E; ++I) {
+    if (I->second.Placeholder) {
+      if (I->second.NewIntVal) {
+        I->second.Placeholder->replaceAllUsesWith(I->second.NewIntVal);
+      } else {
         errs() << "Not converted: " << *I->first << "\n";
+        Error = true;
+      }
     }
+  }
+  if (Error)
     report_fatal_error("Case not handled in ReplacePtrsWithInts");
+
+  // Delete the placeholders in a separate pass.  This means that if
+  // one placeholder is accidentally rewritten to another, we will get
+  // a useful error message rather than accessing a dangling pointer.
+  for (DenseMap<Value *, RewrittenVal>::iterator I = RewriteMap.begin(),
+           E = RewriteMap.end(); I != E; ++I) {
+    delete I->second.Placeholder;
   }
+
   // We must do dropAllReferences() before doing eraseFromParent(),
   // otherwise we will try to erase instructions that are still
   // referenced.
@@ -250,7 +288,7 @@ static void ConvertMetadataOperand(FunctionConverter *FC,
     return;
   Value *MDArg = MD->getOperand(0);
   if (MDArg && (isa<Argument>(MDArg) || isa<Instruction>(MDArg))) {
-    MDArg = FC->convert(MDArg);
+    MDArg = FC->convert(MDArg, /* BypassPlaceholder= */ true);
     if (PtrToIntInst *Cast = dyn_cast<PtrToIntInst>(MDArg)) {
       // Unwrapping this is necessary for llvm.dbg.declare to work.
       MDArg = Cast->getPointerOperand();
@@ -325,9 +363,9 @@ static void ConvertInstruction(DataLayout *DL, Type *IntPtrType,
     FC->recordConvertedAndErase(Phi, Phi2);
   } else if (SelectInst *Op = dyn_cast<SelectInst>(Inst)) {
     Instruction *Op2 = SelectInst::Create(Op->getCondition(),
-                                         FC->convert(Op->getTrueValue()),
-                                         FC->convert(Op->getFalseValue()),
-                                         "", Op);
+                                          FC->convert(Op->getTrueValue()),
+                                          FC->convert(Op->getFalseValue()),
+                                          "", Op);
     CopyDebug(Op2, Op);
     Op2->takeName(Op);
     FC->recordConvertedAndErase(Op, Op2);
@@ -342,7 +380,7 @@ static void ConvertInstruction(DataLayout *DL, Type *IntPtrType,
     FC->recordConvertedAndErase(Inst, Result);
   } else if (isa<BitCastInst>(Inst)) {
     if (Inst->getType()->isPointerTy()) {
-      FC->recordConvertedAndErase(Inst, FC->convert(Inst->getOperand(0)));
+      FC->ToErase.push_back(Inst);
     }
   } else if (ICmpInst *Cmp = dyn_cast<ICmpInst>(Inst)) {
     Value *Cmp2 = CopyDebug(new ICmpInst(Inst, Cmp->getPredicate(),
@@ -380,9 +418,6 @@ static void ConvertInstruction(DataLayout *DL, Type *IntPtrType,
         // https://code.google.com/p/nativeclient/issues/detail?id=3443
         Inst->eraseFromParent();
       } else {
-        if (ICall->getIntrinsicID() == Intrinsic::dbg_declare) {
-          ConvertMetadataOperand(FC, ICall, 0);
-        }
         FC->convertInPlace(Inst);
       }
     } else if (isa<InlineAsm>(Call->getCalledValue())) {
@@ -482,12 +517,18 @@ static void CleanUpFunction(Function *Func, Type *IntPtrType) {
       SimplifyCasts(Iter++, IntPtrType);
     }
   }
-  // Cleanup: Remove ptrtoints that were introduced for allocas but not used.
+  // Cleanup pass.
   for (Function::iterator BB = Func->begin(), E = Func->end();
        BB != E; ++BB) {
     for (BasicBlock::iterator Iter = BB->begin(), E = BB->end();
          Iter != E; ) {
       Instruction *Inst = Iter++;
+      // Add names to inttoptrs to make the output more readable.  The
+      // placeholder values get in the way of doing this earlier when
+      // the inttoptrs are created.
+      if (isa<IntToPtrInst>(Inst))
+        Inst->setName(Inst->getOperand(0)->getName() + ".asptr");
+      // Remove ptrtoints that were introduced for allocas but not used.
       if (isa<PtrToIntInst>(Inst) && Inst->use_empty())
         Inst->eraseFromParent();
     }
@@ -539,6 +580,19 @@ bool ReplacePtrsWithInts::runOnModule(Module &M) {
         ConvertInstruction(&DL, IntPtrType, &FC, Iter++);
       }
     }
+    // Now that all the replacement instructions have been created, we
+    // can update the debug intrinsic calls.
+    for (Function::iterator BB = NewFunc->begin(), E = NewFunc->end();
+         BB != E; ++BB) {
+      for (BasicBlock::iterator Inst = BB->begin(), E = BB->end();
+           Inst != E; ++Inst) {
+        if (IntrinsicInst *Call = dyn_cast<IntrinsicInst>(Inst)) {
+          if (Call->getIntrinsicID() == Intrinsic::dbg_declare) {
+            ConvertMetadataOperand(&FC, Call, 0);
+          }
+        }
+      }
+    }
     FC.eraseReplacedInstructions();
     OldFunc->replaceAllUsesWith(ConstantExpr::getBitCast(NewFunc,
                                                          OldFunc->getType()));
diff --git a/test/Transforms/NaCl/replace-ptrs-with-ints.ll b/test/Transforms/NaCl/replace-ptrs-with-ints.ll
index c45ca322cd..bab6101848 100644
--- a/test/Transforms/NaCl/replace-ptrs-with-ints.ll
+++ b/test/Transforms/NaCl/replace-ptrs-with-ints.ll
@@ -26,16 +26,79 @@ declare i8* @declared_func(i8*, i64)
 ; CHECK: declare i32 @declared_func(i32, i64)
 
 
-define void @self_reference(i8* %ptr) {
+define void @self_reference_phi(i8* %ptr) {
 entry:
   br label %loop
 loop:
   %x = phi i8* [ %x, %loop ], [ %ptr, %entry ]
   br label %loop
 }
-; CHECK: define void @self_reference(i32 %ptr) {
+; CHECK: define void @self_reference_phi(i32 %ptr) {
 ; CHECK: %x = phi i32 [ %x, %loop ], [ %ptr, %entry ]
 
+; Self-referencing bitcasts are possible in unreachable basic blocks.
+; It is not very likely that we will encounter this, but we handle it
+; for completeness.
+define void @self_reference_bitcast(i8** %dest) {
+  ret void
+unreachable_loop:
+  store i8* %self_ref, i8** %dest
+  %self_ref = bitcast i8* %self_ref to i8*
+  store i8* %self_ref, i8** %dest
+  br label %unreachable_loop
+}
+; CHECK: define void @self_reference_bitcast(i32 %dest) {
+; CHECK: store i32 undef, i32* %dest.asptr
+; CHECK: store i32 undef, i32* %dest.asptr
+
+define void @circular_reference_bitcasts(i8** %dest) {
+  ret void
+unreachable_loop:
+  store i8* %cycle1, i8** %dest
+  %cycle1 = bitcast i8* %cycle2 to i8*
+  %cycle2 = bitcast i8* %cycle1 to i8*
+  br label %unreachable_loop
+}
+; CHECK: define void @circular_reference_bitcasts(i32 %dest) {
+; CHECK: store i32 undef, i32* %dest.asptr
+
+define void @circular_reference_inttoptr(i8** %dest) {
+  ret void
+unreachable_loop:
+  %ptr = inttoptr i32 %int to i8*
+  %int = ptrtoint i8* %ptr to i32
+  store i8* %ptr, i8** %dest
+  br label %unreachable_loop
+}
+; CHECK: define void @circular_reference_inttoptr(i32 %dest) {
+; CHECK: store i32 undef, i32* %dest.asptr
+
+define i8* @forwards_reference(%struct** %ptr) {
+  br label %block1
+block2:
+  ; Forwards reference to %val.
+  %cast = bitcast %struct* %val to i8*
+  br label %block3
+block1:
+  %val = load %struct** %ptr
+  br label %block2
+block3:
+  ; Backwards reference to a forwards reference that has already been
+  ; resolved.
+  ret i8* %cast
+}
+; CHECK: define i32 @forwards_reference(i32 %ptr) {
+; CHECK-NEXT: br label %block1
+; CHECK: block2:
+; CHECK-NEXT: br label %block3
+; CHECK: block1:
+; CHECK-NEXT: %ptr.asptr = inttoptr i32 %ptr to i32*
+; CHECK-NEXT: %val = load i32* %ptr.asptr
+; CHECK-NEXT: br label %block2
+; CHECK: block3:
+; CHECK-NEXT: ret i32 %val
+
+
 define i8* @phi_multiple_entry(i1 %arg, i8* %ptr) {
 entry:
   br i1 %arg, label %done, label %done
@@ -198,8 +261,8 @@ define i8* @indirect_call(i8* (i8*)* %func, i8* %arg) {
   ret i8* %result
 }
 ; CHECK: define i32 @indirect_call(i32 %func, i32 %arg) {
-; CHECK-NEXT: %func.asfuncptr = inttoptr i32 %func to i32 (i32)*
-; CHECK-NEXT: %result = call i32 %func.asfuncptr(i32 %arg)
+; CHECK-NEXT: %func.asptr = inttoptr i32 %func to i32 (i32)*
+; CHECK-NEXT: %result = call i32 %func.asptr(i32 %arg)
 ; CHECK-NEXT: ret i32 %result
 
 
@@ -302,6 +365,23 @@ define void @alloca_lower_alignment() {
 ; CHECK-NEXT: alloca [4 x i8], align 1
 
 
+; This tests for a bug in which, when processing the store's %buf2
+; operand, ReplacePtrsWithInts accidentally strips off the ptrtoint
+; cast that it previously introduced for the 'alloca', causing an
+; internal sanity check to fail.
+define void @alloca_cast_stripping() {
+  %buf = alloca i32
+  %buf1 = ptrtoint i32* %buf to i32
+  %buf2 = inttoptr i32 %buf1 to i32*
+  store i32 0, i32* %buf2
+  ret void
+}
+; CHECK: define void @alloca_cast_stripping() {
+; CHECK-NEXT: %buf = alloca [4 x i8]
+; CHECK-NEXT: %buf.bc = bitcast [4 x i8]* %buf to i32*
+; CHECK-NEXT: store i32 0, i32* %buf.bc
+
+
 define i1 @compare(i8* %ptr1, i8* %ptr2) {
   %cmp = icmp ult i8* %ptr1, %ptr2
   ret i1 %cmp