llvm dev - Jul 2014 - [LLVMdev] Splitting basic block results in unknown instruction type assertion

Hello,

I would like to see if this issue is a result of a misunderstanding on  
my part before I file a bug. I am using LLVM 3.4, built from the  
source tarballs. My system's uname is "Darwin tyler-air 12.5.0 Darwin  
Kernel Version 12.5.0: Sun Sep 29 13:33:47 PDT 2013;  
root:xnu-2050.48.12~1/RELEASE_X86_64 x86_64".

All I'm trying to do is add a runtime check after all call  
instructions. To do this I would (eventually) like to add a branch to  
an "error" block that aborts the program. However, in trying to insert
a new block after each call site, I encountered this issue. The  
problem I'm seeing is an InstVisitor assertion failure ("UNREACHABLE  
executed" and "Unknown instruction type encountered") after
splitting
a basic block.

Here is a method to reproduce the issue:

     // -------------------- Test.cpp
     #include "llvm/IR/Module.h"
     #include "llvm/Pass.h"
     #include "llvm/InstVisitor.h"

     using namespace llvm;

     namespace {
       class TestInstVisitor : public InstVisitor<TestInstVisitor> {
       public:
         void visitCallInst(CallInst &I) {
           Instruction *splitPoint = I.getNextNode();
           BasicBlock *head = splitPoint->getParent();
           BasicBlock *tail = head->splitBasicBlock(splitPoint);
         }
       };

       class TestPass : public ModulePass {
       public:
         static char ID;
         TestPass() : ModulePass(ID) {}
         virtual bool runOnModule(Module &M) {
           TestInstVisitor visitor;
           visitor.visit(M);
           return true;
         }
       };
     }
     char TestPass::ID = 0;
     static RegisterPass<TestPass> X("bugtest", "Bug test
pass", false, false);

     // -------------------- buginput.cpp
     void foo() {}
     int main() {
       foo();
       return 0;
     }

If you run the "bugtest" pass on the buginput test program, you should
see the following assertion failure:

     Unknown instruction type encountered!
     UNREACHABLE executed at  
/Users/tyler/research/llvm-3.4/include/llvm/InstVisitor.h:125!
     0  opt               0x0000000103bcc77e  
llvm::sys::PrintStackTrace(__sFILE*) + 46
     1  opt               0x0000000103bcca8b  
PrintStackTraceSignalHandler(void*) + 27
     2  opt               0x0000000103bccd99 SignalHandler(int) + 297
     3  libsystem_c.dylib 0x00007fff9455990a _sigtramp + 26
     4  opt               0x000000010367bbc5 llvm::AllocaInst**  
std::__uninitialized_copy_aux<llvm::AllocaInst* const*,  
llvm::AllocaInst**>(llvm::AllocaInst* const*, llvm::AllocaInst*  
const*, llvm::AllocaInst**, std::__true_type) + 37
     5  opt               0x0000000103bccabb raise + 27
     6  opt               0x0000000103bccb72 abort + 18
     7  opt               0x0000000103bb3386  
llvm::llvm_unreachable_internal(char const*, char const*, unsigned  
int) + 198
     8  Test.dylib        0x00000001060d9376  
llvm::InstVisitor<(anonymous namespace)::TestInstVisitor,  
void>::visit(llvm::Instruction&) + 198
     9  Test.dylib        0x00000001060d92a5 void  
llvm::InstVisitor<(anonymous namespace)::TestInstVisitor,  
void>::visit<llvm::ilist_iterator<llvm::Instruction>  
 >(llvm::ilist_iterator<llvm::Instruction>,  
llvm::ilist_iterator<llvm::Instruction>) + 101

(some stack frames omitted for brevity).

Is this due to some mistake on my part, or is this a bug?

Thanks,

Tyler

On 7/7/14, 2:45 PM, Tyler Denniston wrote:
> Hello,
>
> I would like to see if this issue is a result of a misunderstanding on 
> my part before I file a bug. I am using LLVM 3.4, built from the 
> source tarballs. My system's uname is "Darwin tyler-air 12.5.0
Darwin
> Kernel Version 12.5.0: Sun Sep 29 13:33:47 PDT 2013; 
> root:xnu-2050.48.12~1/RELEASE_X86_64 x86_64".
>
> All I'm trying to do is add a runtime check after all call 
> instructions. To do this I would (eventually) like to add a branch to 
> an "error" block that aborts the program. However, in trying to
insert
> a new block after each call site, I encountered this issue. The 
> problem I'm seeing is an InstVisitor assertion failure
("UNREACHABLE
> executed" and "Unknown instruction type encountered") after
splitting
> a basic block.
I don't know for certain, but my guess is that one of the two basic 
blocks after the split has an unreachable instruction (yes, LLVM has an 
instruction called unreachable), and the InstVistor class doesn't like it.

To verify this, call the dump() method on head and tail to print the two 
new basic blocks.

If this is the problem, add code to change the terminator instruction of 
the errant basic block to the value that you want.

Regards,

John Criswell
>
> Here is a method to reproduce the issue:
>
>     // -------------------- Test.cpp
>     #include "llvm/IR/Module.h"
>     #include "llvm/Pass.h"
>     #include "llvm/InstVisitor.h"
>
>     using namespace llvm;
>
>     namespace {
>       class TestInstVisitor : public InstVisitor<TestInstVisitor> {
>       public:
>         void visitCallInst(CallInst &I) {
>           Instruction *splitPoint = I.getNextNode();
>           BasicBlock *head = splitPoint->getParent();
>           BasicBlock *tail = head->splitBasicBlock(splitPoint);
>         }
>       };
>
>       class TestPass : public ModulePass {
>       public:
>         static char ID;
>         TestPass() : ModulePass(ID) {}
>         virtual bool runOnModule(Module &M) {
>           TestInstVisitor visitor;
>           visitor.visit(M);
>           return true;
>         }
>       };
>     }
>     char TestPass::ID = 0;
>     static RegisterPass<TestPass> X("bugtest", "Bug
test pass", false,
> false);
>
>     // -------------------- buginput.cpp
>     void foo() {}
>     int main() {
>       foo();
>       return 0;
>     }
>
> If you run the "bugtest" pass on the buginput test program, you
should
> see the following assertion failure:
>
>     Unknown instruction type encountered!
>     UNREACHABLE executed at 
> /Users/tyler/research/llvm-3.4/include/llvm/InstVisitor.h:125!
>     0  opt               0x0000000103bcc77e 
> llvm::sys::PrintStackTrace(__sFILE*) + 46
>     1  opt               0x0000000103bcca8b 
> PrintStackTraceSignalHandler(void*) + 27
>     2  opt               0x0000000103bccd99 SignalHandler(int) + 297
>     3  libsystem_c.dylib 0x00007fff9455990a _sigtramp + 26
>     4  opt               0x000000010367bbc5 llvm::AllocaInst** 
> std::__uninitialized_copy_aux<llvm::AllocaInst* const*, 
> llvm::AllocaInst**>(llvm::AllocaInst* const*, llvm::AllocaInst* 
> const*, llvm::AllocaInst**, std::__true_type) + 37
>     5  opt               0x0000000103bccabb raise + 27
>     6  opt               0x0000000103bccb72 abort + 18
>     7  opt               0x0000000103bb3386 
> llvm::llvm_unreachable_internal(char const*, char const*, unsigned 
> int) + 198
>     8  Test.dylib        0x00000001060d9376 
> llvm::InstVisitor<(anonymous namespace)::TestInstVisitor, 
> void>::visit(llvm::Instruction&) + 198
>     9  Test.dylib        0x00000001060d92a5 void 
> llvm::InstVisitor<(anonymous namespace)::TestInstVisitor, 
> void>::visit<llvm::ilist_iterator<llvm::Instruction> 
> >(llvm::ilist_iterator<llvm::Instruction>, 
> llvm::ilist_iterator<llvm::Instruction>) + 101
>
> (some stack frames omitted for brevity).
>
> Is this due to some mistake on my part, or is this a bug?
>
> Thanks,
>
> Tyler
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Quoting John Criswell <jtcriswel at gmail.com>:
> I don't know for certain, but my guess is that one of the two basic  
> blocks after the split has an unreachable instruction (yes, LLVM has  
> an instruction called unreachable), and the InstVistor class doesn't  
> like it.
>
> To verify this, call the dump() method on head and tail to print the  
> two new basic blocks.
Hi John,

Thanks for your reply. I'm not sure how unreachable instructions are  
represented, but there don't appear to be any in the dump of the two  
blocks. Here is what I see on the "buginput" program from earlier,  
after the split:

Dump head:

entry:
   call void @_Z3foov()
   br label %0

Dump tail:

; <label>:0                                       ; preds = %entry
   ret i32 0

Tyler
>>
>> Here is a method to reproduce the issue:
>>
>>    // -------------------- Test.cpp
>>    #include "llvm/IR/Module.h"
>>    #include "llvm/Pass.h"
>>    #include "llvm/InstVisitor.h"
>>
>>    using namespace llvm;
>>
>>    namespace {
>>      class TestInstVisitor : public InstVisitor<TestInstVisitor>
{
>>      public:
>>        void visitCallInst(CallInst &I) {
>>          Instruction *splitPoint = I.getNextNode();
>>          BasicBlock *head = splitPoint->getParent();
>>          BasicBlock *tail = head->splitBasicBlock(splitPoint);
>>        }
>>      };
>>
>>      class TestPass : public ModulePass {
>>      public:
>>        static char ID;
>>        TestPass() : ModulePass(ID) {}
>>        virtual bool runOnModule(Module &M) {
>>          TestInstVisitor visitor;
>>          visitor.visit(M);
>>          return true;
>>        }
>>      };
>>    }
>>    char TestPass::ID = 0;
>>    static RegisterPass<TestPass> X("bugtest", "Bug
test pass",
>> false, false);
>>
>>    // -------------------- buginput.cpp
>>    void foo() {}
>>    int main() {
>>      foo();
>>      return 0;
>>    }
>>
>> If you run the "bugtest" pass on the buginput test program,
you
>> should see the following assertion failure:
>>
>>    Unknown instruction type encountered!
>>    UNREACHABLE executed at  
>> /Users/tyler/research/llvm-3.4/include/llvm/InstVisitor.h:125!
>>    0  opt               0x0000000103bcc77e  
>> llvm::sys::PrintStackTrace(__sFILE*) + 46
>>    1  opt               0x0000000103bcca8b  
>> PrintStackTraceSignalHandler(void*) + 27
>>    2  opt               0x0000000103bccd99 SignalHandler(int) + 297
>>    3  libsystem_c.dylib 0x00007fff9455990a _sigtramp + 26
>>    4  opt               0x000000010367bbc5 llvm::AllocaInst**  
>> std::__uninitialized_copy_aux<llvm::AllocaInst* const*,  
>> llvm::AllocaInst**>(llvm::AllocaInst* const*, llvm::AllocaInst*  
>> const*, llvm::AllocaInst**, std::__true_type) + 37
>>    5  opt               0x0000000103bccabb raise + 27
>>    6  opt               0x0000000103bccb72 abort + 18
>>    7  opt               0x0000000103bb3386  
>> llvm::llvm_unreachable_internal(char const*, char const*, unsigned  
>> int) + 198
>>    8  Test.dylib        0x00000001060d9376  
>> llvm::InstVisitor<(anonymous namespace)::TestInstVisitor,  
>> void>::visit(llvm::Instruction&) + 198
>>    9  Test.dylib        0x00000001060d92a5 void  
>> llvm::InstVisitor<(anonymous namespace)::TestInstVisitor,  
>> void>::visit<llvm::ilist_iterator<llvm::Instruction>  
>> >(llvm::ilist_iterator<llvm::Instruction>,  
>> llvm::ilist_iterator<llvm::Instruction>) + 101
>>
>> (some stack frames omitted for brevity).
>>
>> Is this due to some mistake on my part, or is this a bug?
>>
>> Thanks,
>>
>> Tyler
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Hi Tyler,

On 7 July 2014 20:45, Tyler Denniston <tyler at csail.mit.edu>
wrote:
> Is this due to some mistake on my part, or is this a bug?
I suspect the problem is that you're modifying control-flow during
iteration. I don't think the InstVisitor is written to cope with that
(I wouldn't even bet on it working if you added or removed
instructions in a single basic block).

I think passes often build up a list of instructions they want to
change and then deal with them in a second phase.

Cheers.

Tim.

Quoting Tim Northover <t.p.northover at
gmail.com>:
>
> I think passes often build up a list of instructions they want to
> change and then deal with them in a second phase.
Thanks, doing it this way resolves the issue.

Tyler