Use list preservation when using Instruction::clone

I'm trying to create a clone of a function using Function::Create() and CloneFunctionInto. However, I'm running into an issue. I believe that the instructions in the function clone still have Use edges to values in the original function. This is a problem for my purposes.

For example, consider an original function F. I create a new function G belonging to the same module and call CloneFunctionInto(G, F) to copy over the function body. Now, consider a phi node p in F, and an instruction I in F which uses p. The problem is, the cloned phi node p' in G still lists I as a user.

Is this intended behavior? And if so, is there a way I can remove these Use edges in my cloned function?

Thanks,

Tyler

Hi Tyler,

Doesn’t look right. Would you mind attaching the test?

Btw, instead of creating an empty function and CloneFunctionInto, can you just CloneFunction?

Jingyue

Ok, it took me a little while to isolate this into a test case, but I
have one, in the attached tarball. Please run the attached pass on the
attached bitcode (LLVM 3.4).

The bug I'm seeing is summarized as follows:

1. Save a list of all of the function F's instructions.
2. Create a clone of the function F.
3. JIT and execute the cloned function.
4. Assert that the body of F has not changed.

The bug is the assertion in (4) failing. If you run the test case, you
should see a crash with this message:

Assertion failed: (false), function validateFunctionBody, file Test.cpp, line 50.

The reason I started this thread asking about use lists is I think
this has to do with instructions in the cloned function listing
instructions in the original function as Uses, and thus when the JIT
erases some instructions in the cloned function, the originals are
deleted as dead code. That's just a hypothesis, anyway, I'm not sure
it's correct.

I don't think this seems like intended behavior, but perhaps with this
additional information about the behavior I'm seeing, someone can shed
some light on this for me.

Tyler

Quoting Jingyue Wu <jingyue@google.com>:

bug.tar.gz (6.5 KB)

The attachment of the tarball didn't work, so I've pasted the pass code and the human-readable test bitcode. Hopefully the line breaks stay sane.

// File Test.cpp

#include "llvm/Pass.h"
#include "llvm/ExecutionEngine/JIT.h"
#include "llvm/ExecutionEngine/ExecutionEngine.h"
#include "llvm/ExecutionEngine/GenericValue.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include <set>

using namespace llvm;

class TestPass : public ModulePass {
public:
   static char ID;
   TestPass() : ModulePass(ID) {}

   virtual bool runOnModule(Module &M) {
     for (Module::iterator fit = M.begin(), fite = M.end(); fit != fite; ++fit) {
       Function *F = fit;
       Function *CloneF = createFunctionClone(F, M);
       std::set<Instruction *> Is = getInstructions(F);
       evaluateFunction(CloneF, M);
       validateFunctionBody(F, Is);
       CloneF->eraseFromParent();
     }
     return false;
   }

private:
   // Return all instructions in the given Function.
   std::set<Instruction *> getInstructions(Function *F) {
     std::set<Instruction *> Is;
     for (Function::iterator bbit = F->begin(), bbite = F->end(); bbit != bbite; ++bbit) {
       BasicBlock *BB = bbit;
       for (BasicBlock::iterator it = BB->begin(), ite = BB->end(); it != ite; ++it) {
         Instruction *I = it;
         Is.insert(I);
       }
     }
     return Is;
   }

   // Assert that the given Function's instructions is equal to the given set.
   void validateFunctionBody(Function *F, const std::set<Instruction *> &Is) {
     std::set<Instruction *> CurrIs = getInstructions(F);
     std::set<Instruction *>::iterator a = CurrIs.begin(), b = Is.begin();
     // Compare the two sets.
     while (a != CurrIs.end()) {
       if (b == Is.end() || *a != *b) assert(false);
       ++a; ++b;
     }
   }

   // JIT and evaluate the given function.
   void evaluateFunction(Function *F, Module &M) {
     std::string errStr;
     InitializeNativeTarget();
     ExecutionEngine *EE = ExecutionEngine::create(&M, false, &errStr);
     if (EE == NULL) {
       errs() << "Could not create execution engine: " << errStr << "\n";
       assert(false);
     }
     std::vector<GenericValue> args;
     for (unsigned i = 0; i < F->arg_size(); i++) {
       GenericValue gv;
       gv.IntVal = APInt(32, 0);
       args.push_back(gv);
     }
     // Execute the function
     GenericValue v = EE->runFunction(F, args);
   }

   // Return a clone of the given function.
   Function *createFunctionClone(Function *F, Module &M) {
     ValueToValueMapTy argVmap;
     SmallVector<ReturnInst *, 8> returns;
     Function *CloneF = Function::Create(F->getFunctionType(), GlobalVariable::ExternalLinkage, "", &M);
     Function::arg_iterator DestI = CloneF->arg_begin();
     for (Function::const_arg_iterator J = F->arg_begin(); J != F->arg_end(); ++J) {
       DestI->setName(J->getName());
       argVmap[J] = DestI++;
     }
     CloneFunctionInto(CloneF, F, argVmap, true, returns);
     return CloneF;
   }
};

char TestPass::ID = 0;
static RegisterPass<TestPass> X("test", "Bug test pass", false, false);

// File bug.ll
define internal i32 @openregion(i32 %i1, i32 %i2, i32 %j1, i32 %j2) #0 {
entry:
   %retval = alloca i32, align 4
   %i1.addr = alloca i32, align 4
   %i2.addr = alloca i32, align 4
   %j1.addr = alloca i32, align 4
   %j2.addr = alloca i32, align 4
   %x = alloca i32, align 4
   %y = alloca i32, align 4
   store i32 %i1, i32* %i1.addr, align 4
   store i32 %i2, i32* %i2.addr, align 4
   store i32 %j1, i32* %j1.addr, align 4
   store i32 %j2, i32* %j2.addr, align 4
   %0 = load i32* %i1.addr, align 4
   %1 = load i32* %i2.addr, align 4
   %cmp = icmp sgt i32 %0, %1
   br i1 %cmp, label %if.then, label %if.end

if.then: ; preds = %entry
   %2 = load i32* %i2.addr, align 4
   %3 = load i32* %i1.addr, align 4
   %4 = load i32* %j1.addr, align 4
   %5 = load i32* %j2.addr, align 4
   %call = call i32 @openregion(i32 %2, i32 %3, i32 %4, i32 %5)
   store i32 %call, i32* %retval
   br label %return

if.end: ; preds = %entry
   %6 = load i32* %j1.addr, align 4
   %7 = load i32* %j2.addr, align 4
   %cmp1 = icmp sgt i32 %6, %7
   br i1 %cmp1, label %if.then2, label %if.end4

if.then2: ; preds = %if.end
   %8 = load i32* %i1.addr, align 4
   %9 = load i32* %i2.addr, align 4
   %10 = load i32* %j2.addr, align 4
   %11 = load i32* %j1.addr, align 4
   %call3 = call i32 @openregion(i32 %8, i32 %9, i32 %10, i32 %11)
   store i32 %call3, i32* %retval
   br label %return

if.end4: ; preds = %if.end
   %12 = load i32* %i1.addr, align 4
   store i32 %12, i32* %x, align 4
   br label %for.cond

for.cond: ; preds = %for.inc14, %if.end4
   %13 = load i32* %x, align 4
   %14 = load i32* %i2.addr, align 4
   %cmp5 = icmp sle i32 %13, %14
   br i1 %cmp5, label %for.body, label %for.end16

for.body: ; preds = %for.cond
   %15 = load i32* %j1.addr, align 4
   store i32 %15, i32* %y, align 4
   br label %for.cond6

for.cond6: ; preds = %for.inc, %for.body
   %16 = load i32* %y, align 4
   %17 = load i32* %j2.addr, align 4
   %cmp7 = icmp sle i32 %16, %17
   br i1 %cmp7, label %for.body8, label %for.end

for.body8: ; preds = %for.cond6
   %18 = load i32* %x, align 4
   %mul = mul nsw i32 %18, 20
   %add = add nsw i32 21, %mul
   %19 = load i32* %y, align 4
   %add9 = add nsw i32 %add, %19
   %idxprom = sext i32 %add9 to i64
   %20 = add nsw i8 0, 0
   %conv = zext i8 %20 to i32
   %cmp10 = icmp ne i32 %conv, 0
   br i1 %cmp10, label %if.then12, label %if.end13

if.then12: ; preds = %for.body8
   store i32 0, i32* %retval
   br label %return

if.end13: ; preds = %for.body8
   br label %for.inc

for.inc: ; preds = %if.end13
   %21 = load i32* %y, align 4
   %inc = add nsw i32 %21, 1
   store i32 %inc, i32* %y, align 4
   br label %for.cond6

for.end: ; preds = %for.cond6
   br label %for.inc14

for.inc14: ; preds = %for.end
   %22 = load i32* %x, align 4
   %inc15 = add nsw i32 %22, 1
   store i32 %inc15, i32* %x, align 4
   br label %for.cond

for.end16: ; preds = %for.cond
   store i32 1, i32* %retval
   br label %return

return: ; preds = %for.end16, %if.then12, %if.then2, %if.then
   %23 = load i32* %retval
   ret i32 %23
}

Quoting Tyler Denniston <tyler@csail.mit.edu>: