[analyzer] Model iterator random incrementation symmetrically

[gamesh411]

Summary

In case a pointer iterator is incremented in a binary plus expression
(operator+), where the iterator is on the RHS, IteratorModeling should
now detect, and track the resulting value.

[gamesh411]

remove unrelated comment formatting

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

288

What do you think about this detection strategy? This assumes that the Iterator being detected is a pointer (and not a used-defined type like STL iterators etc.). Would you say that this assumption holds every time because the pointer-iterators are only handled in this checkPostStmt callback and the traditional iterators in another callback?

291

During the development of this patch, I saw something related. At the beginning of handlePtrIncrOrDecr, there is a branch on whether the Expr (2nd argument) is a pointer. I think that branch could just be an assertion. What do you think? (or maybe I should create a patch to show what I mean?)

[steakhal]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

265–270

You should probably use const where applicable.
Especially where the refs value depends on a condition operator (eg. few lines below)

[baloghadamsoftware]

Nice work, but please implement this feature also for non-pointer iterators for the matter of consistence.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

288

Instead of It please use Iter, beacause It can be understood as the English it pronoun: "Is it on the left-hand side?"

291

I wonder whether this should be implemented here in checkPostStmt() ot in handlePtrIncrOrDecr(). Your current implementation is in checkPostStmt(), in this case we can assert in handlePtrIncrOrDecl().

[gamesh411]

rename misleading variables
apply local consts

[gamesh411]

In order to test the non-pointer iterators, an extension has to be made to the system header simulator. Please check the related patch (parent of this one in the stack) https://reviews.llvm.org/D83226.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

265–270

Definitely should have done that, thanks!

[gamesh411]

implement traditional iterator support as well

[gamesh411]

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

291

I checked and decided it not really worth it to move the logic inside the handlePtrIncrOrDecr() function, as that would require us to pass both the left and right-hand side as Expr-s. This would be fine when we handle a binary operator, but if we handle a unary operator, we manually pass the SVal of RHS (namely a manually created ConcreteInt with value 1). All this could be abstracted with a function wrapping the original handlePtrIncrOrDecr(), but for now, I don't think it is worth it.

clang/test/Analysis/iterator-modeling.cpp

169

Note that this line requires the parent patch.

[gamesh411]

fix tidy diagnostic

[gamesh411]

rebase upon hotfix patch

[gamesh411]

It would be nice to see the measurements on llvm as this patch introduced some (IMO reasonable) asserts. Also in the unlikely case, there is an expression like 1 + iter, there could be more results.

[baloghadamsoftware]

Looks good, aside from the few naming issues I mentioned. Please try it on LLVM/Clang before committing it to avoid unexpected crashes.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

112

In my subsequent patches I began to use the name Amount instead of Offset to not confuse with IteratorPosition::Offset.

281

AmountExpr.

385

Expr1, Expr2, Type1, Type2 or something similar. Fst is to be confused with Fast and Snd with Sound. Or spell out First and Second.

400

This is generally true in C++ that overloaded operators must either be class member or must have at least one class argument. Do we have to assert it in this particular checker?

clang/test/Analysis/iterator-modeling.cpp

152

plus_lhs, plus_rhs to begin with the name of the operation.

[gamesh411]

Thanks for reviewing this patch this quickly!
I have updated the diff according to your suggestions, but I will not land it till I run a llvm+clang analysis with it.
Do you think non-ctu mode is enough to test the stability?

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

400

I think you are right, at second glance this assert seems confusing for someone reading the code for the first time and does not specifically belong to the logic of 'checking an overloaded increment or decrement operation'. Moreover, the special instance that is modelled as an iterator is not strictly tied to the type system (I mean there could be other things that we could model as iterators, not just structs or classes even beside pointer which are handled in another method of this modelling class).
All in all, I removed the assert.

[gamesh411]

apply review suggestions

• rename variables
• remove 1 assert
• rename tests

[gamesh411]

rename Offset -> Amount inside handleRandomIncrOrDecl
minor local variable renaming

[gamesh411]

I experienced 2 crashes with and without this patch using commit 1af9fc82132da7c876e8f70c4e986cc9c59010ee on master:
I have used the clang built on that revision to analyse itself, and also used the patched version (with this current revision applied) to do the same.

clang-12: /mnt/ssd/zfulend/llvm-project/clang/lib/Analysis/PathDiagnostic.cpp:399: bool compare(const clang::ento::PathDiagnostic&, const clang::ento::PathDiagnostic&): Assertion `b.hasValue()' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /mnt/ssd/zfulend/clang-rwa/bin/clang-12 --analyze -Qunused-arguments -Xclang -analyzer-opt-analyze-headers -Xclang -analyzer-output=plist-multi-file -o /mnt/ssd/zfulend/symm_with_patch/Verifier.cpp_clangsa_5e3a41accb2e401b7b63c8ab1892a17d.plist -Xclang -analyzer-config -Xclang expand-macros=true -Xclang -analyzer-checker=alpha.cplusplus.InvalidatedIterator -Xclang -analyzer-checker=alpha.cplusplus.IteratorModeling -Xclang -analyzer-checker=alpha.cplusplus.IteratorRange -Xclang -analyzer-checker=alpha.cplusplus.MismatchedIterator -Xclang -analyzer-checker=apiModeling.StdCLibraryFunctions -Xclang -analyzer-checker=apiModeling.TrustNonnull -Xclang -analyzer-checker=apiModeling.google.GTest -Xclang -analyzer-checker=apiModeling.llvm.CastValue -Xclang -analyzer-checker=apiModeling.llvm.ReturnValue -Xclang -analyzer-checker=core.CallAndMessage -Xclang -analyzer-checker=core.CallAndMessageModeling -Xclang -analyzer-checker=core.DivideZero -Xclang -analyzer-checker=core.DynamicTypePropagation -Xclang -analyzer-checker=core.NonNullParamChecker -Xclang -analyzer-checker=core.NonnilStringConstants -Xclang -analyzer-checker=core.NullDereference -Xclang -analyzer-checker=core.StackAddrEscapeBase -Xclang -analyzer-checker=core.StackAddressEscape -Xclang -analyzer-checker=core.UndefinedBinaryOperatorResult -Xclang -analyzer-checker=core.VLASize -Xclang -analyzer-checker=core.builtin.BuiltinFunctions -Xclang -analyzer-checker=core.builtin.NoReturnFunctions -Xclang -analyzer-checker=core.uninitialized.ArraySubscript -Xclang -analyzer-checker=core.uninitialized.Assign -Xclang -analyzer-checker=core.uninitialized.Branch -Xclang -analyzer-checker=core.uninitialized.CapturedBlockVariable -Xclang -analyzer-checker=core.uninitialized.UndefReturn -Xclang -analyzer-checker=cplusplus.InnerPointer -Xclang -analyzer-checker=cplusplus.Move -Xclang -analyzer-checker=cplusplus.NewDelete -Xclang -analyzer-checker=cplusplus.NewDeleteLeaks -Xclang -analyzer-checker=cplusplus.PlacementNew -Xclang -analyzer-checker=cplusplus.PureVirtualCall -Xclang -analyzer-checker=cplusplus.SelfAssignment -Xclang -analyzer-checker=cplusplus.SmartPtrModeling -Xclang -analyzer-checker=cplusplus.VirtualCallModeling -Xclang -analyzer-checker=deadcode.DeadStores -Xclang -analyzer-checker=nullability.NullPassedToNonnull -Xclang -analyzer-checker=nullability.NullReturnedFromNonnull -Xclang -analyzer-checker=optin.cplusplus.UninitializedObject -Xclang -analyzer-checker=optin.cplusplus.VirtualCall -Xclang -analyzer-checker=optin.portability.UnixAPI -Xclang -analyzer-checker=security.FloatLoopCounter -Xclang -analyzer-checker=security.insecureAPI.UncheckedReturn -Xclang -analyzer-checker=security.insecureAPI.getpw -Xclang -analyzer-checker=security.insecureAPI.gets -Xclang -analyzer-checker=security.insecureAPI.mkstemp -Xclang -analyzer-checker=security.insecureAPI.mktemp -Xclang -analyzer-checker=security.insecureAPI.rand -Xclang -analyzer-checker=security.insecureAPI.vfork -Xclang -analyzer-checker=unix.API -Xclang -analyzer-checker=unix.DynamicMemoryModeling -Xclang -analyzer-checker=unix.Malloc -Xclang -analyzer-checker=unix.MallocSizeof -Xclang -analyzer-checker=unix.MismatchedDeallocator -Xclang -analyzer-checker=unix.Vfork -Xclang -analyzer-checker=unix.cstring.BadSizeArg -Xclang -analyzer-checker=unix.cstring.CStringModeling -Xclang -analyzer-checker=unix.cstring.NullArg -Xclang -analyzer-checker=valist.CopyToSelf -Xclang -analyzer-checker=valist.Uninitialized -Xclang -analyzer-checker=valist.Unterminated -Xclang -analyzer-checker=valist.ValistBase -Xclang -analyzer-config -Xclang aggressive-binary-operation-simplification=true -x c++ --target=x86_64-linux-gnu -std=gnu++14 -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/mnt/ssd/zfulend/clang-rwa/lib/IR -I/mnt/ssd/zfulend/llvm-project/llvm/lib/IR -I/usr/include/libxml2 -I/mnt/ssd/zfulend/clang-rwa/include -I/mnt/ssd/zfulend/llvm-project/llvm/include -fPIC -fvisibility-inlines-hidden -Wno-unused-parameter -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wno-noexcept-type -Wno-comment -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -isystem /usr/include/c++/7 -isystem /usr/include/x86_64-linux-gnu/c++/7 -isystem /usr/include/c++/7/backward -isystem /usr/local/include -isystem /usr/include/x86_64-linux-gnu -isystem /usr/include /mnt/ssd/zfulend/llvm-project/llvm/lib/IR/Verifier.cpp
1.      <eof> parser at end of file
 #0 0x00005612e45a104a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf304a)
 #1 0x00005612e459ed04 llvm::sys::RunSignalHandlers() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf0d04)
 #2 0x00005612e459ef75 llvm::sys::CleanupOnSignal(unsigned long) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf0f75)
 #3 0x00005612e450faf8 CrashRecoverySignalHandler(int) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1c61af8)
 #4 0x00007f8a95dde8a0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x128a0)
 #5 0x00007f8a94a8ff47 raise /build/glibc-2ORdQG/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007f8a94a918b1 abort /build/glibc-2ORdQG/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007f8a94a8142a __assert_fail_base /build/glibc-2ORdQG/glibc-2.27/assert/assert.c:89:0
 #8 0x00007f8a94a814a2 (/lib/x86_64-linux-gnu/libc.so.6+0x304a2)
 #9 0x00005612e68ec082 compare(clang::ento::PathDiagnostic const&, clang::ento::PathDiagnostic const&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x403e082)
#10 0x00005612e68ec19c clang::ento::PathDiagnosticConsumer::FlushDiagnostics(clang::ento::PathDiagnosticConsumer::FilesMade*)::'lambda'(clang::ento::PathDiagnostic const* const*, clang::ento::PathDiagnostic const* const*)::_FUN(clang::ento::PathDiagnostic const* const*, clang::ento::PathDiagnostic const* const*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x403e19c)
#11 0x00007f8a94a932a2 msort_with_tmp /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:83:0
#12 0x00007f8a94a93220 msort_with_tmp /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:117:0
#13 0x00007f8a94a93220 msort_with_tmp /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:53:0
#14 0x00007f8a94a9320e msort_with_tmp /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:117:0
#15 0x00007f8a94a9320e msort_with_tmp /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:54:0
#16 0x00007f8a94a93646 qsort_r /build/glibc-2ORdQG/glibc-2.27/stdlib/msort.c:299:0
#17 0x00005612e68f3085 clang::ento::PathDiagnosticConsumer::FlushDiagnostics(clang::ento::PathDiagnosticConsumer::FilesMade*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x4045085)
#18 0x00005612e5e9324f clang::ento::AnalysisManager::FlushDiagnostics() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x35e524f)
#19 0x00005612e5e932a0 clang::ento::AnalysisManager::~AnalysisManager() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x35e52a0)
#20 0x00005612e5e933b9 clang::ento::AnalysisManager::~AnalysisManager() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x35e53b9)
#21 0x00005612e5acd0c0 (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x321f0c0)
#22 0x00005612e5ffe2b9 clang::ParseAST(clang::Sema&, bool, bool) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x37502b9)
#23 0x00005612e4db1e69 clang::FrontendAction::Execute() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2503e69)
#24 0x00005612e4d6caba clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x24beaba)
#25 0x00005612e4e7b9f6 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x25cd9f6)
#26 0x00005612e34a4fbc cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf6fbc)
#27 0x00005612e34a0309 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf2309)
#28 0x00005612e4c46965 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::'lambda'()>(long) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2398965)
#29 0x00005612e450fbd3 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1c61bd3)
#30 0x00005612e4c472a8 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const (.part.146) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x23992a8)
#31 0x00005612e4c223c5 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x23743c5)
#32 0x00005612e4c22e6f clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2374e6f)
#33 0x00005612e4c2b5b9 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x237d5b9)
#34 0x00005612e342461a main (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xb7661a)
#35 0x00007f8a94a72b97 __libc_start_main /build/glibc-2ORdQG/glibc-2.27/csu/../csu/libc-start.c:344:0
#36 0x00005612e349fada _start (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf1ada)

the other:

clang-12: /mnt/ssd/zfulend/llvm-project/clang/include/clang/AST/TemplateBase.h:259: clang::QualType clang::TemplateArgument::getAsType() const: Assertion `getKind() == Type && "Unexpected kind"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /mnt/ssd/zfulend/clang-rwa/bin/clang-12 --analyze -Qunused-arguments -Xclang -analyzer-opt-analyze-headers -Xclang -analyzer-output=plist-multi-file -o /mnt/ssd/zfulend/symm_with_patch/CodeGenPrepare.cpp_clangsa_68b9820696aadf0c8f57a3505a013b14.plist -Xclang -analyzer-config -Xclang expand-macros=true -Xclang -analyzer-checker=alpha.cplusplus.InvalidatedIterator -Xclang -analyzer-checker=alpha.cplusplus.IteratorModeling -Xclang -analyzer-checker=alpha.cplusplus.IteratorRange -Xclang -analyzer-checker=alpha.cplusplus.MismatchedIterator -Xclang -analyzer-checker=apiModeling.StdCLibraryFunctions -Xclang -analyzer-checker=apiModeling.TrustNonnull -Xclang -analyzer-checker=apiModeling.google.GTest -Xclang -analyzer-checker=apiModeling.llvm.CastValue -Xclang -analyzer-checker=apiModeling.llvm.ReturnValue -Xclang -analyzer-checker=core.CallAndMessage -Xclang -analyzer-checker=core.CallAndMessageModeling -Xclang -analyzer-checker=core.DivideZero -Xclang -analyzer-checker=core.DynamicTypePropagation -Xclang -analyzer-checker=core.NonNullParamChecker -Xclang -analyzer-checker=core.NonnilStringConstants -Xclang -analyzer-checker=core.NullDereference -Xclang -analyzer-checker=core.StackAddrEscapeBase -Xclang -analyzer-checker=core.StackAddressEscape -Xclang -analyzer-checker=core.UndefinedBinaryOperatorResult -Xclang -analyzer-checker=core.VLASize -Xclang -analyzer-checker=core.builtin.BuiltinFunctions -Xclang -analyzer-checker=core.builtin.NoReturnFunctions -Xclang -analyzer-checker=core.uninitialized.ArraySubscript -Xclang -analyzer-checker=core.uninitialized.Assign -Xclang -analyzer-checker=core.uninitialized.Branch -Xclang -analyzer-checker=core.uninitialized.CapturedBlockVariable -Xclang -analyzer-checker=core.uninitialized.UndefReturn -Xclang -analyzer-checker=cplusplus.InnerPointer -Xclang -analyzer-checker=cplusplus.Move -Xclang -analyzer-checker=cplusplus.NewDelete -Xclang -analyzer-checker=cplusplus.NewDeleteLeaks -Xclang -analyzer-checker=cplusplus.PlacementNew -Xclang -analyzer-checker=cplusplus.PureVirtualCall -Xclang -analyzer-checker=cplusplus.SelfAssignment -Xclang -analyzer-checker=cplusplus.SmartPtrModeling -Xclang -analyzer-checker=cplusplus.VirtualCallModeling -Xclang -analyzer-checker=deadcode.DeadStores -Xclang -analyzer-checker=nullability.NullPassedToNonnull -Xclang -analyzer-checker=nullability.NullReturnedFromNonnull -Xclang -analyzer-checker=optin.cplusplus.UninitializedObject -Xclang -analyzer-checker=optin.cplusplus.VirtualCall -Xclang -analyzer-checker=optin.portability.UnixAPI -Xclang -analyzer-checker=security.FloatLoopCounter -Xclang -analyzer-checker=security.insecureAPI.UncheckedReturn -Xclang -analyzer-checker=security.insecureAPI.getpw -Xclang -analyzer-checker=security.insecureAPI.gets -Xclang -analyzer-checker=security.insecureAPI.mkstemp -Xclang -analyzer-checker=security.insecureAPI.mktemp -Xclang -analyzer-checker=security.insecureAPI.rand -Xclang -analyzer-checker=security.insecureAPI.vfork -Xclang -analyzer-checker=unix.API -Xclang -analyzer-checker=unix.DynamicMemoryModeling -Xclang -analyzer-checker=unix.Malloc -Xclang -analyzer-checker=unix.MallocSizeof -Xclang -analyzer-checker=unix.MismatchedDeallocator -Xclang -analyzer-checker=unix.Vfork -Xclang -analyzer-checker=unix.cstring.BadSizeArg -Xclang -analyzer-checker=unix.cstring.CStringModeling -Xclang -analyzer-checker=unix.cstring.NullArg -Xclang -analyzer-checker=valist.CopyToSelf -Xclang -analyzer-checker=valist.Uninitialized -Xclang -analyzer-checker=valist.Unterminated -Xclang -analyzer-checker=valist.ValistBase -Xclang -analyzer-config -Xclang aggressive-binary-operation-simplification=true -x c++ --target=x86_64-linux-gnu -std=gnu++14 -DGTEST_HAS_RTTI=0 -D_DEBUG -D_GNU_SOURCE -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/mnt/ssd/zfulend/clang-rwa/lib/CodeGen -I/mnt/ssd/zfulend/llvm-project/llvm/lib/CodeGen -I/usr/include/libxml2 -I/mnt/ssd/zfulend/clang-rwa/include -I/mnt/ssd/zfulend/llvm-project/llvm/include -fPIC -fvisibility-inlines-hidden -Wno-unused-parameter -Wno-missing-field-initializers -pedantic -Wno-long-long -Wno-maybe-uninitialized -Wno-noexcept-type -Wno-comment -fdiagnostics-color -ffunction-sections -fdata-sections -O3 -fno-exceptions -fno-rtti -UNDEBUG -std=c++14 -isystem /usr/include/c++/7 -isystem /usr/include/x86_64-linux-gnu/c++/7 -isystem /usr/include/c++/7/backward -isystem /usr/local/include -isystem /usr/include/x86_64-linux-gnu -isystem /usr/include /mnt/ssd/zfulend/llvm-project/llvm/lib/CodeGen/CodeGenPrepare.cpp
1.      <eof> parser at end of file
2.      While analyzing stack:
        #0 Calling (anonymous namespace)::TypePromotionHelper::canGetThrough at line 4078
        #1 Calling (anonymous namespace)::TypePromotionHelper::getAction at line 4503
        #2 Calling (anonymous namespace)::AddressingModeMatcher::matchOperationAddr
3.      /mnt/ssd/zfulend/llvm-project/llvm/lib/CodeGen/CodeGenPrepare.cpp:3986:7: Error evaluating statement
4.      /mnt/ssd/zfulend/llvm-project/llvm/lib/CodeGen/CodeGenPrepare.cpp:3986:7: Error evaluating statement
 #0 0x00005583e0be004a llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf304a)
 #1 0x00005583e0bddd04 llvm::sys::RunSignalHandlers() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf0d04)
 #2 0x00005583e0bddf75 llvm::sys::CleanupOnSignal(unsigned long) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1cf0f75)
 #3 0x00005583e0b4eaf8 CrashRecoverySignalHandler(int) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1c61af8)
 #4 0x00007f90a50c08a0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x128a0)
 #5 0x00007f90a3d71f47 raise /build/glibc-2ORdQG/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007f90a3d738b1 abort /build/glibc-2ORdQG/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007f90a3d6342a __assert_fail_base /build/glibc-2ORdQG/glibc-2.27/assert/assert.c:89:0
 #8 0x00007f90a3d634a2 (/lib/x86_64-linux-gnu/libc.so.6+0x304a2)
 #9 0x00005583e2180856 addInstanceOfTransition(clang::ento::CallEvent const&, clang::ento::DefinedOrUnknownSVal, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>, clang::ento::CheckerContext&, bool) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3293856)
#10 0x00005583e2180a41 (anonymous namespace)::CastValueChecker::evalIsaAndNonNull(clang::ento::CallEvent const&, clang::ento::DefinedOrUnknownSVal, clang::ento::CheckerContext&) const (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3293a41)
#11 0x00005583e217de00 bool clang::ento::eval::Call::_evalCall<(anonymous namespace)::CastValueChecker>(void*, clang::ento::CallEvent const&, clang::ento::CheckerContext&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3290e00)
#12 0x00005583e2521f4d clang::ento::CheckerManager::runCheckersForEvalCall(clang::ento::ExplodedNodeSet&, clang::ento::ExplodedNodeSet const&, clang::ento::CallEvent const&, clang::ento::ExprEngine&, clang::ento::EvalCallOptions const&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3634f4d)
#13 0x00005583e257a2dc clang::ento::ExprEngine::evalCall(clang::ento::ExplodedNodeSet&, clang::ento::ExplodedNode*, clang::ento::CallEvent const&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x368d2dc)
#14 0x00005583e257ac18 clang::ento::ExprEngine::VisitCallExpr(clang::CallExpr const*, clang::ento::ExplodedNode*, clang::ento::ExplodedNodeSet&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x368dc18)
#15 0x00005583e255e10d clang::ento::ExprEngine::Visit(clang::Stmt const*, clang::ento::ExplodedNode*, clang::ento::ExplodedNodeSet&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x367110d)
#16 0x00005583e255ed84 clang::ento::ExprEngine::ProcessStmt(clang::Stmt const*, clang::ento::ExplodedNode*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3671d84)
#17 0x00005583e255ef72 clang::ento::ExprEngine::processCFGElement(clang::CFGElement, clang::ento::ExplodedNode*, unsigned int, clang::ento::NodeBuilderContext*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x3671f72)
#18 0x00005583e252c899 clang::ento::CoreEngine::HandlePostStmt(clang::CFGBlock const*, unsigned int, clang::ento::ExplodedNode*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x363f899)
#19 0x00005583e252caf7 clang::ento::CoreEngine::dispatchWorkItem(clang::ento::ExplodedNode*, clang::ProgramPoint, clang::ento::WorkListUnit const&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x363faf7)
#20 0x00005583e252cd74 clang::ento::CoreEngine::ExecuteWorkList(clang::LocationContext const*, unsigned int, llvm::IntrusiveRefCntPtr<clang::ento::ProgramState const>) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x363fd74)
#21 0x00005583e20ed89f (anonymous namespace)::AnalysisConsumer::HandleCode(clang::Decl*, unsigned int, clang::ento::ExprEngine::InliningModes, llvm::DenseSet<clang::Decl const*, llvm::DenseMapInfo<clang::Decl const*> >*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x320089f)
#22 0x00005583e210b296 (anonymous namespace)::AnalysisConsumer::HandleDeclsCallGraph(unsigned int) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x321e296)
#23 0x00005583e210c2e2 (anonymous namespace)::AnalysisConsumer::HandleTranslationUnit(clang::ASTContext&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x321f2e2)
#24 0x00005583e263d2b9 clang::ParseAST(clang::Sema&, bool, bool) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x37502b9)
#25 0x00005583e13f0e69 clang::FrontendAction::Execute() (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2503e69)
#26 0x00005583e13ababa clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x24beaba)
#27 0x00005583e14ba9f6 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x25cd9f6)
#28 0x00005583dfae3fbc cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf6fbc)
#29 0x00005583dfadf309 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf2309)
#30 0x00005583e1285965 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::'lambda'()>(long) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2398965)
#31 0x00005583e0b4ebd3 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x1c61bd3)
#32 0x00005583e12862a8 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const (.part.146) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x23992a8)
#33 0x00005583e12613c5 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x23743c5)
#34 0x00005583e1261e6f clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x2374e6f)
#35 0x00005583e126a5b9 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0x237d5b9)
#36 0x00005583dfa6361a main (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xb7661a)
#37 0x00007f90a3d54b97 __libc_start_main /build/glibc-2ORdQG/glibc-2.27/csu/../csu/libc-start.c:344:0
#38 0x00005583dfadeada _start (/mnt/ssd/zfulend/clang-rwa/bin/clang-12+0xbf1ada)

[balazske]

Maybe the assert b.hasValue() is related to the problems in D83115 or D83961? The changes in those affect the same functions.

[baloghadamsoftware]

In D83190#2164361, @gamesh411 wrote:

I experienced 2 crashes with and without this patch using commit 1af9fc82132da7c876e8f70c4e986cc9c59010ee on master:
I have used the clang built on that revision to analyse itself, and also used the patched version (with this current revision applied) to do the same.

This crash is unrelated. It also happens if you execute the analyzer without enabling any of the iterator checkers.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp

void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
                          OverloadedOperatorKind Op) const;
   void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
                        bool Postfix) const;
   void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
                               OverloadedOperatorKind Op, const SVal &RetVal,
-                              const SVal &LHS, const SVal &RHS) const;
+                              const SVal &Iterator, const SVal &Amount) const;
   void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
                            OverloadedOperatorKind OK, SVal Offset) const;
   void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
                      SVal Amount) const;
   void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
                   SVal Amount) const;
   void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
                   SVal Amount) const;
void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
   auto &SVB = C.getSValBuilder();
   handlePtrIncrOrDecr(C, UO->getSubExpr(),
                       isIncrementOperator(OK) ? OO_Plus : OO_Minus,
                       SVB.makeArrayIndex(1));
 }
 
 void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
                                      CheckerContext &C) const {
-  ProgramStateRef State = C.getState();
-  BinaryOperatorKind OK = BO->getOpcode();
-  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
+  const ProgramStateRef State = C.getState();
+  const BinaryOperatorKind OK = BO->getOpcode();
+  const Expr *const LHS = BO->getLHS();
+  const Expr *const RHS = BO->getRHS();
+  const SVal LVal = State->getSVal(LHS, C.getLocationContext());
+  const SVal RVal = State->getSVal(RHS, C.getLocationContext());
 
   if (isSimpleComparisonOperator(BO->getOpcode())) {
-    SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
     SVal Result = State->getSVal(BO, C.getLocationContext());
     handleComparison(C, BO, Result, LVal, RVal,
                      BinaryOperator::getOverloadedOperator(OK));
   } else if (isRandomIncrOrDecrOperator(OK)) {
-    if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
-      return;
-    handlePtrIncrOrDecr(C, BO->getLHS(),
-                        BinaryOperator::getOverloadedOperator(OK), RVal);
+    // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),
+    // or on the RHS (eg.: 1 + it). Both cases are modeled.
+    const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();
+    const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;
+    const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;
+
+    // The non-iterator side must have an integral or enumeration type.
+    if (!AmountExpr->getType()->isIntegralOrEnumerationType())
+      return;
+    const SVal &AmountVal = IsIterOnLHS ? RVal : LVal;
+    handlePtrIncrOrDecr(C, IterExpr, BinaryOperator::getOverloadedOperator(OK),
+                        AmountVal);
   }
 }
 
 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
                                      CheckerContext &C) const {
   /* Transfer iterator state to temporary objects */
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
   if (!Pos)
     return;
   State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
if (isSimpleComparisonOperator(Op)) {
 
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         if (Call.getNumArgs() >= 1 &&
               Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
                                  InstCall->getCXXThisVal(), Call.getArgSVal(0));
           return;
         }
-      } else {
-        if (Call.getNumArgs() >= 2 &&
-              Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
+      } else if (Call.getNumArgs() >= 2) {
+        const Expr *FirstArg = Call.getArgExpr(0);
+        const Expr *SecondArg = Call.getArgExpr(1);
+        const QualType FirstType = FirstArg->getType();
+        const QualType SecondType = SecondArg->getType();
+
+        if (FirstType->isIntegralOrEnumerationType() ||
+            SecondType->isIntegralOrEnumerationType()) {
+          // In case of operator+ the iterator can be either on the LHS (eg.:
+          // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.
+          const bool IsIterFirst = FirstType->isStructureOrClassType();
+          const SVal FirstArg = Call.getArgSVal(0);
+          const SVal SecondArg = Call.getArgSVal(1);
+          const SVal &Iterator = IsIterFirst ? FirstArg : SecondArg;
+          const SVal &Amount = IsIterFirst ? SecondArg : FirstArg;
+
           handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
-                                 Call.getArgSVal(0), Call.getArgSVal(1));
+                                 Iterator, Amount);
           return;
         }
       }
     } else if (isIncrementOperator(Op)) {
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
                         Call.getNumArgs());
         return;
       }
 
void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal,
   assert(NewPos &&
          "Iterator should have position after successful advancement");
 
   State = setIteratorPosition(State, Iter, *NewPos);
   State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
   C.addTransition(State);
 }
 
-void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C,
-                                              const Expr *CE,
+void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
                                               OverloadedOperatorKind Op,
                                               const SVal &RetVal,
-                                              const SVal &LHS,
-                                              const SVal &RHS) const {
+                                              const SVal &Iterator,
+                                              const SVal &Offset) const {
   // Increment or decrement the symbolic expressions which represents the
   // position of the iterator
   auto State = C.getState();
 
-  const auto *Pos = getIteratorPosition(State, LHS);
+  const auto *Pos = getIteratorPosition(State, Iterator);
   if (!Pos)
     return;
 
-  const auto *value = &RHS;
+  const auto *value = &Offset;
   SVal val;
-  if (auto loc = RHS.getAs<Loc>()) {
+  if (auto loc = Offset.getAs<Loc>()) {
     val = State->getRawSVal(*loc);
     value = &val;
   }
 
-  auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
+  const auto &TgtVal =
+      (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
 
   // `AdvancedState` is a state where the position of `LHS` is advanced. We
   // only need this state to retrieve the new position, but we do not want
   // to change the position of `LHS` (in every case).
-  auto AdvancedState = advancePosition(State, LHS, Op, *value);
+  auto AdvancedState = advancePosition(State, Iterator, Op, *value);
   if (AdvancedState) {
-    const auto *NewPos = getIteratorPosition(AdvancedState, LHS);
+    const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);
     assert(NewPos &&
            "Iterator should have position after successful advancement");
 
     State = setIteratorPosition(State, TgtVal, *NewPos);
     C.addTransition(State);
   } else {
     assignToContainer(C, CE, TgtVal, Pos->getContainer());
   }

clang/test/Analysis/iterator-modeling.cpp

void copy(const std::vector<int> &v) {
 
   auto i2 = i1;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning-re {{$v.end(){{$}}}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning-re {{$v.end(){{$}}}}
 }
 
-void plus(const std::vector<int> &v) {
+void plus_lhs(const std::vector<int> &v) {
   auto i1 = v.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
 
   auto i2 = i1 + 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning-re{{$v.begin(){{$}}}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning-re{{$v.begin() + 2{{$}}}}
 }
 
-void plus_negative(const std::vector<int> &v) {
+void plus_rhs(const std::vector<int> &v) {
+  auto i1 = v.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(v), "$v.begin()");
+
+  auto i2 = 2 + i1;
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning-re{{$v.begin(){{$}}}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning-re{{$v.begin() + 2{{$}}}}
+}
+
+void plus_lhs_negative(const std::vector<int> &v) {
   auto i1 = v.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
 
   auto i2 = i1 + (-2);
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning-re {{$v.end(){{$}}}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning-re {{$v.end() - 2{{$}}}}
 }
 
+void plus_rhs_negative(const std::vector<int> &v) {
+  auto i1 = v.end();
+
+  clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
+
+  auto i2 = (-2) + i1;
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning-re {{$v.end(){{$}}}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning-re {{$v.end() - 2{{$}}}}
+}
+
 void minus(const std::vector<int> &v) {
   auto i1 = v.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(v), "$v.end()");
 
   auto i2 = i1 - 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &v); // expected-warning{{TRUE}}

 
 void minus_equal_ptr_iterator_variable(const cont_with_ptr_iterator<int> &c,
                                        int n) {
   auto i = c.end();
 
   i -= n; // no-crash
 }
 
-void plus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+void plus_lhs_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
   auto i1 = c.begin();
 
   clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
 
   auto i2 = i1 + 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
   clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$c.begin()}}
   clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$c.begin() + 2}}
 }
 
+void plus_rhs_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
+  auto i1 = c.begin();
+
+  clang_analyzer_denote(clang_analyzer_container_begin(c), "$c.begin()");
+
+  auto i2 = 2 + i1;
+
+  clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i1));     // expected-warning{{$c.begin()}}
+  clang_analyzer_express(clang_analyzer_iterator_position(i2));     // expected-warning{{$c.begin() + 2}}
+}
+
 void minus_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
   auto i1 = c.end();
 
   clang_analyzer_denote(clang_analyzer_container_end(c), "$c.end()");
 
   auto i2 = i1 - 2;
 
   clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &c); // expected-warning{{TRUE}}