search

qir-alliance / qat

QIR compiler tools and optimization passes for targeting QIR to different hardware backends
https://qir-alliance.github.io/qat/
MIT License
26 stars 14 forks source link

Refactor of reindex and allocate on reset passes #80

Closed troelsfr closed 2 years ago

swernli commented 2 years ago

Hmm... looks like I get a heap-use-after-free error if both --reindex-qubits and --replace-qubits-on-reset are used at the same time:

==15405==ERROR: AddressSanitizer: heap-use-after-free on address 0x60d000000234 at pc 0x000000a40cba bp 0x7fff346f4490 sp 0x7fff346f4488
READ of size 4 at 0x60d000000234 thread T0
    #0 0xa40cb9 in llvm::User::setOperand(unsigned int, llvm::Value*) /usr/lib/llvm-11/include/llvm/IR/User.h:175:5
    #1 0xa3ee67 in microsoft::quantum::QubitRemapPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/qat/qir/qat/StaticResourceComponent/QubitRemapPass.cpp:109:28
    #2 0x972880 in llvm::detail::PassModel<llvm::Function, microsoft::quantum::QubitRemapPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/lib/llvm-11/include/llvm/IR/PassManagerInternal.h:79:17
    #3 0x7bddd7 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bddd7)
    #4 0x84cc8b in llvm::ModuleToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x84cc8b)
    #5 0x84c9cc in llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x84c9cc)
    #6 0x7bc81d in llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bc81d)
    #7 0x9af906 in microsoft::quantum::Profile::apply(llvm::Module&) /home/qat/qir/qat/Profile/Profile.cpp:149:30
    #8 0x54b6d4 in main /home/qat/qir/qat/Apps/Qat/Qat.cpp:286:21
    #9 0x7f80763050b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16
    #10 0x49992d in _start (/home/qat/Debug/qir/qat/Apps/qat+0x49992d)

0x60d000000234 is located 84 bytes inside of 144-byte region [0x60d0000001e0,0x60d000000270)
freed by thread T0 here:
    #0 0x543e9d in operator delete(void*) (/home/qat/Debug/qir/qat/Apps/qat+0x543e9d)
    #1 0x76f3f8 in llvm::Instruction::eraseFromParent() (/home/qat/Debug/qir/qat/Apps/qat+0x76f3f8)
    #2 0x96faf0 in llvm::detail::PassModel<llvm::Function, microsoft::quantum::ReplaceQubitOnResetPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/lib/llvm-11/include/llvm/IR/PassManagerInternal.h:79:17
    #3 0x7bddd7 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bddd7)

previously allocated by thread T0 here:
    #0 0x54363d in operator new(unsigned long) (/home/qat/Debug/qir/qat/Apps/qat+0x54363d)
    #1 0x7d7cde in llvm::User::operator new(unsigned long, unsigned int, unsigned int) (/home/qat/Debug/qir/qat/Apps/qat+0x7d7cde)

If I had to guess, I think it's because the --replace-qubits-on-reset is removing the reset instruction and then the --reindex-qubits is trying to update the id for that removed instruction. I think this is based on the analysis pass info that is getting preserved when perhaps it shouldn't, because the analysis keeps a record of qubit uses that is now out of date.

troelsfr commented 2 years ago

Hmm... looks like I get a heap-use-after-free error if both --reindex-qubits and --replace-qubits-on-reset are used at the same time:

==15405==ERROR: AddressSanitizer: heap-use-after-free on address 0x60d000000234 at pc 0x000000a40cba bp 0x7fff346f4490 sp 0x7fff346f4488
READ of size 4 at 0x60d000000234 thread T0
    #0 0xa40cb9 in llvm::User::setOperand(unsigned int, llvm::Value*) /usr/lib/llvm-11/include/llvm/IR/User.h:175:5
    #1 0xa3ee67 in microsoft::quantum::QubitRemapPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /home/qat/qir/qat/StaticResourceComponent/QubitRemapPass.cpp:109:28
    #2 0x972880 in llvm::detail::PassModel<llvm::Function, microsoft::quantum::QubitRemapPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/lib/llvm-11/include/llvm/IR/PassManagerInternal.h:79:17
    #3 0x7bddd7 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bddd7)
    #4 0x84cc8b in llvm::ModuleToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x84cc8b)
    #5 0x84c9cc in llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor<llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> > >, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x84c9cc)
    #6 0x7bc81d in llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bc81d)
    #7 0x9af906 in microsoft::quantum::Profile::apply(llvm::Module&) /home/qat/qir/qat/Profile/Profile.cpp:149:30
    #8 0x54b6d4 in main /home/qat/qir/qat/Apps/Qat/Qat.cpp:286:21
    #9 0x7f80763050b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/../csu/libc-start.c:308:16
    #10 0x49992d in _start (/home/qat/Debug/qir/qat/Apps/qat+0x49992d)

0x60d000000234 is located 84 bytes inside of 144-byte region [0x60d0000001e0,0x60d000000270)
freed by thread T0 here:
    #0 0x543e9d in operator delete(void*) (/home/qat/Debug/qir/qat/Apps/qat+0x543e9d)
    #1 0x76f3f8 in llvm::Instruction::eraseFromParent() (/home/qat/Debug/qir/qat/Apps/qat+0x76f3f8)
    #2 0x96faf0 in llvm::detail::PassModel<llvm::Function, microsoft::quantum::ReplaceQubitOnResetPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) /usr/lib/llvm-11/include/llvm/IR/PassManagerInternal.h:79:17
    #3 0x7bddd7 in llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/qat/Debug/qir/qat/Apps/qat+0x7bddd7)

previously allocated by thread T0 here:
    #0 0x54363d in operator new(unsigned long) (/home/qat/Debug/qir/qat/Apps/qat+0x54363d)
    #1 0x7d7cde in llvm::User::operator new(unsigned long, unsigned int, unsigned int) (/home/qat/Debug/qir/qat/Apps/qat+0x7d7cde)

If I had to guess, I think it's because the --replace-qubits-on-reset is removing the reset instruction and then the --reindex-qubits is trying to update the id for that removed instruction. I think this is based on the analysis pass info that is getting preserved when perhaps it shouldn't, because the analysis keeps a record of qubit uses that is now out of date.

This is likely a result of the result preservation being marked incorrectly. If the analysis is not renewed, the analysis results will have references to nodes that were already deleted.

troelsfr commented 2 years ago

Looks like both the ReplaceQubitOnResetPass and QubitRemapPass should return llvm::PreservedAnalysis::none() instead of all() which triggers the pass manager to automatically rerun any registered analysis passes and update the data structures. This avoids the heap-use-after-free and ensures that the usage annotations have the latest info based on the changes made by the passes!

Yes, this is exactly what I thought.