/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf -tc ../../../trunk/examples/toolchains/AutomizerC.xml --sifa.abstract.domain EqDomain -i ../sv-benchmarks/c/heap-manipulation/sll_to_dll_rev-2.i -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-f954360 [2023-04-01 10:51:03,933 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-04-01 10:51:03,935 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-04-01 10:51:03,973 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-04-01 10:51:03,974 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-04-01 10:51:03,976 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-04-01 10:51:03,979 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-04-01 10:51:03,981 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-04-01 10:51:03,982 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-04-01 10:51:03,987 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-04-01 10:51:03,988 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-04-01 10:51:03,990 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-04-01 10:51:03,990 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-04-01 10:51:03,992 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-04-01 10:51:03,994 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-04-01 10:51:03,995 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-04-01 10:51:03,996 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-04-01 10:51:03,997 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-04-01 10:51:03,998 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-04-01 10:51:04,003 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-04-01 10:51:04,004 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-04-01 10:51:04,005 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-04-01 10:51:04,006 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-04-01 10:51:04,007 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-04-01 10:51:04,015 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-04-01 10:51:04,015 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-04-01 10:51:04,016 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-04-01 10:51:04,017 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-04-01 10:51:04,018 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-04-01 10:51:04,018 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-04-01 10:51:04,018 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-04-01 10:51:04,019 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-04-01 10:51:04,020 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-04-01 10:51:04,021 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-04-01 10:51:04,022 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-04-01 10:51:04,022 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-04-01 10:51:04,022 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-04-01 10:51:04,023 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-04-01 10:51:04,023 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-04-01 10:51:04,023 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-04-01 10:51:04,024 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-04-01 10:51:04,025 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf [2023-04-01 10:51:04,054 INFO L113 SettingsManager]: Loading preferences was successful [2023-04-01 10:51:04,054 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-04-01 10:51:04,055 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-04-01 10:51:04,055 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-04-01 10:51:04,056 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-04-01 10:51:04,056 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-04-01 10:51:04,056 INFO L138 SettingsManager]: * User list type=DISABLED [2023-04-01 10:51:04,056 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-04-01 10:51:04,056 INFO L138 SettingsManager]: * Explicit value domain=true [2023-04-01 10:51:04,056 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-04-01 10:51:04,057 INFO L138 SettingsManager]: * Octagon Domain=false [2023-04-01 10:51:04,057 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2023-04-01 10:51:04,057 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-04-01 10:51:04,058 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-04-01 10:51:04,058 INFO L138 SettingsManager]: * Interval Domain=false [2023-04-01 10:51:04,058 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-04-01 10:51:04,058 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-04-01 10:51:04,058 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2023-04-01 10:51:04,059 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-04-01 10:51:04,059 INFO L138 SettingsManager]: * sizeof long=4 [2023-04-01 10:51:04,059 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-04-01 10:51:04,059 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-04-01 10:51:04,059 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-04-01 10:51:04,060 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-04-01 10:51:04,060 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-04-01 10:51:04,060 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-04-01 10:51:04,060 INFO L138 SettingsManager]: * sizeof long double=12 [2023-04-01 10:51:04,061 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-04-01 10:51:04,061 INFO L138 SettingsManager]: * Use constant arrays=true [2023-04-01 10:51:04,061 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-04-01 10:51:04,061 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-04-01 10:51:04,061 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-04-01 10:51:04,061 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-01 10:51:04,062 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-04-01 10:51:04,062 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-04-01 10:51:04,063 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-04-01 10:51:04,063 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.sifa: Abstract Domain -> EqDomain [2023-04-01 10:51:04,299 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-04-01 10:51:04,325 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-04-01 10:51:04,327 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-04-01 10:51:04,328 INFO L271 PluginConnector]: Initializing CDTParser... [2023-04-01 10:51:04,329 INFO L275 PluginConnector]: CDTParser initialized [2023-04-01 10:51:04,330 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/sll_to_dll_rev-2.i [2023-04-01 10:51:05,459 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-04-01 10:51:05,708 INFO L351 CDTParser]: Found 1 translation units. [2023-04-01 10:51:05,708 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/sll_to_dll_rev-2.i [2023-04-01 10:51:05,720 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8675761e1/7ebabe07a2674da287e627c9e337771a/FLAG2ffb0de0f [2023-04-01 10:51:05,733 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8675761e1/7ebabe07a2674da287e627c9e337771a [2023-04-01 10:51:05,735 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-04-01 10:51:05,737 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2023-04-01 10:51:05,739 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-04-01 10:51:05,740 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-04-01 10:51:05,743 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-04-01 10:51:05,744 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 01.04 10:51:05" (1/1) ... [2023-04-01 10:51:05,745 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@3829566a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:05, skipping insertion in model container [2023-04-01 10:51:05,745 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 01.04 10:51:05" (1/1) ... [2023-04-01 10:51:05,751 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-04-01 10:51:05,790 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-04-01 10:51:06,075 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/sll_to_dll_rev-2.i[22636,22649] [2023-04-01 10:51:06,120 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-01 10:51:06,132 INFO L203 MainTranslator]: Completed pre-run [2023-04-01 10:51:06,167 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/sll_to_dll_rev-2.i[22636,22649] [2023-04-01 10:51:06,202 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-01 10:51:06,229 INFO L208 MainTranslator]: Completed translation [2023-04-01 10:51:06,230 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06 WrapperNode [2023-04-01 10:51:06,230 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-04-01 10:51:06,231 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-04-01 10:51:06,231 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-04-01 10:51:06,231 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-04-01 10:51:06,242 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,243 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,274 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,274 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,302 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,309 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,312 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,314 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,319 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-04-01 10:51:06,320 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-04-01 10:51:06,330 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-04-01 10:51:06,330 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-04-01 10:51:06,332 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (1/1) ... [2023-04-01 10:51:06,339 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-01 10:51:06,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-01 10:51:06,363 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-04-01 10:51:06,397 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure __bswap_32 [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure __bswap_64 [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure fail [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure alloc_node [2023-04-01 10:51:06,418 INFO L138 BoogieDeclarations]: Found implementation of procedure chain_node [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure create_sll [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure init_back_link [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure reverse_dll [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure remove_fw_link [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure check_seq_next [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure check_seq_prev [2023-04-01 10:51:06,419 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2023-04-01 10:51:06,419 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2023-04-01 10:51:06,419 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_perror_fail [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure __assert [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure __bswap_32 [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure __bswap_64 [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure __ctype_get_mb_cur_max [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure atof [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure atoi [2023-04-01 10:51:06,420 INFO L130 BoogieDeclarations]: Found specification of procedure atol [2023-04-01 10:51:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure atoll [2023-04-01 10:51:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure strtod [2023-04-01 10:51:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure strtof [2023-04-01 10:51:06,421 INFO L130 BoogieDeclarations]: Found specification of procedure strtold [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtol [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtoul [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtoq [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtouq [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtoll [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure strtoull [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure l64a [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure a64l [2023-04-01 10:51:06,422 INFO L130 BoogieDeclarations]: Found specification of procedure select [2023-04-01 10:51:06,423 INFO L130 BoogieDeclarations]: Found specification of procedure pselect [2023-04-01 10:51:06,423 INFO L130 BoogieDeclarations]: Found specification of procedure gnu_dev_major [2023-04-01 10:51:06,423 INFO L130 BoogieDeclarations]: Found specification of procedure gnu_dev_minor [2023-04-01 10:51:06,423 INFO L130 BoogieDeclarations]: Found specification of procedure gnu_dev_makedev [2023-04-01 10:51:06,424 INFO L130 BoogieDeclarations]: Found specification of procedure random [2023-04-01 10:51:06,424 INFO L130 BoogieDeclarations]: Found specification of procedure srandom [2023-04-01 10:51:06,424 INFO L130 BoogieDeclarations]: Found specification of procedure initstate [2023-04-01 10:51:06,424 INFO L130 BoogieDeclarations]: Found specification of procedure setstate [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure random_r [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure srandom_r [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure initstate_r [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure setstate_r [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure rand [2023-04-01 10:51:06,425 INFO L130 BoogieDeclarations]: Found specification of procedure srand [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure rand_r [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure drand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure erand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure lrand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure nrand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure mrand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure jrand48 [2023-04-01 10:51:06,426 INFO L130 BoogieDeclarations]: Found specification of procedure srand48 [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure seed48 [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure lcong48 [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure drand48_r [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure erand48_r [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure lrand48_r [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure nrand48_r [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure mrand48_r [2023-04-01 10:51:06,427 INFO L130 BoogieDeclarations]: Found specification of procedure jrand48_r [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure srand48_r [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure seed48_r [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure lcong48_r [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure malloc [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure calloc [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure realloc [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure free [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure cfree [2023-04-01 10:51:06,428 INFO L130 BoogieDeclarations]: Found specification of procedure alloca [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure valloc [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure posix_memalign [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure atexit [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure on_exit [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure exit [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure _Exit [2023-04-01 10:51:06,429 INFO L130 BoogieDeclarations]: Found specification of procedure getenv [2023-04-01 10:51:06,432 INFO L130 BoogieDeclarations]: Found specification of procedure putenv [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure setenv [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure unsetenv [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure clearenv [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure mktemp [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure mkstemp [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure mkstemps [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure mkdtemp [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure system [2023-04-01 10:51:06,433 INFO L130 BoogieDeclarations]: Found specification of procedure realpath [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure bsearch [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure qsort [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure abs [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure labs [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure llabs [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure div [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure ldiv [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure lldiv [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure ecvt [2023-04-01 10:51:06,434 INFO L130 BoogieDeclarations]: Found specification of procedure fcvt [2023-04-01 10:51:06,435 INFO L130 BoogieDeclarations]: Found specification of procedure gcvt [2023-04-01 10:51:06,435 INFO L130 BoogieDeclarations]: Found specification of procedure qecvt [2023-04-01 10:51:06,435 INFO L130 BoogieDeclarations]: Found specification of procedure qfcvt [2023-04-01 10:51:06,435 INFO L130 BoogieDeclarations]: Found specification of procedure qgcvt [2023-04-01 10:51:06,435 INFO L130 BoogieDeclarations]: Found specification of procedure ecvt_r [2023-04-01 10:51:06,436 INFO L130 BoogieDeclarations]: Found specification of procedure fcvt_r [2023-04-01 10:51:06,436 INFO L130 BoogieDeclarations]: Found specification of procedure qecvt_r [2023-04-01 10:51:06,436 INFO L130 BoogieDeclarations]: Found specification of procedure qfcvt_r [2023-04-01 10:51:06,436 INFO L130 BoogieDeclarations]: Found specification of procedure mblen [2023-04-01 10:51:06,436 INFO L130 BoogieDeclarations]: Found specification of procedure mbtowc [2023-04-01 10:51:06,437 INFO L130 BoogieDeclarations]: Found specification of procedure wctomb [2023-04-01 10:51:06,437 INFO L130 BoogieDeclarations]: Found specification of procedure mbstowcs [2023-04-01 10:51:06,437 INFO L130 BoogieDeclarations]: Found specification of procedure wcstombs [2023-04-01 10:51:06,437 INFO L130 BoogieDeclarations]: Found specification of procedure rpmatch [2023-04-01 10:51:06,437 INFO L130 BoogieDeclarations]: Found specification of procedure getsubopt [2023-04-01 10:51:06,438 INFO L130 BoogieDeclarations]: Found specification of procedure getloadavg [2023-04-01 10:51:06,440 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2023-04-01 10:51:06,441 INFO L130 BoogieDeclarations]: Found specification of procedure fail [2023-04-01 10:51:06,445 INFO L130 BoogieDeclarations]: Found specification of procedure alloc_node [2023-04-01 10:51:06,445 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-04-01 10:51:06,445 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure chain_node [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure create_sll [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure init_back_link [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure reverse_dll [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure remove_fw_link [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure check_seq_next [2023-04-01 10:51:06,446 INFO L130 BoogieDeclarations]: Found specification of procedure check_seq_prev [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure main [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-04-01 10:51:06,447 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-04-01 10:51:06,729 INFO L236 CfgBuilder]: Building ICFG [2023-04-01 10:51:06,731 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-04-01 10:51:07,069 INFO L277 CfgBuilder]: Performing block encoding [2023-04-01 10:51:07,122 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-04-01 10:51:07,122 INFO L302 CfgBuilder]: Removed 33 assume(true) statements. [2023-04-01 10:51:07,127 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 01.04 10:51:07 BoogieIcfgContainer [2023-04-01 10:51:07,127 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-04-01 10:51:07,129 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-04-01 10:51:07,129 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-04-01 10:51:07,131 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-04-01 10:51:07,132 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 01.04 10:51:05" (1/3) ... [2023-04-01 10:51:07,132 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47c2150f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 01.04 10:51:07, skipping insertion in model container [2023-04-01 10:51:07,132 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 01.04 10:51:06" (2/3) ... [2023-04-01 10:51:07,132 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@47c2150f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 01.04 10:51:07, skipping insertion in model container [2023-04-01 10:51:07,132 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 01.04 10:51:07" (3/3) ... [2023-04-01 10:51:07,133 INFO L112 eAbstractionObserver]: Analyzing ICFG sll_to_dll_rev-2.i [2023-04-01 10:51:07,152 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-04-01 10:51:07,152 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-04-01 10:51:07,207 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-04-01 10:51:07,213 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@b9ab66, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-04-01 10:51:07,214 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-04-01 10:51:07,218 INFO L276 IsEmpty]: Start isEmpty. Operand has 100 states, 66 states have (on average 1.5909090909090908) internal successors, (105), 75 states have internal predecessors, (105), 24 states have call successors, (24), 11 states have call predecessors, (24), 11 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2023-04-01 10:51:07,224 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2023-04-01 10:51:07,224 INFO L187 NwaCegarLoop]: Found error trace [2023-04-01 10:51:07,225 INFO L195 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-01 10:51:07,225 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-01 10:51:07,229 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-01 10:51:07,229 INFO L85 PathProgramCache]: Analyzing trace with hash -484721569, now seen corresponding path program 1 times [2023-04-01 10:51:07,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-01 10:51:07,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [125290968] [2023-04-01 10:51:07,237 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:07,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-01 10:51:07,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:07,397 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-01 10:51:07,398 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-01 10:51:07,398 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [125290968] [2023-04-01 10:51:07,398 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [125290968] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-01 10:51:07,399 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-01 10:51:07,399 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-04-01 10:51:07,400 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [391810736] [2023-04-01 10:51:07,401 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-01 10:51:07,404 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-04-01 10:51:07,405 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-01 10:51:07,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-04-01 10:51:07,435 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-01 10:51:07,437 INFO L87 Difference]: Start difference. First operand has 100 states, 66 states have (on average 1.5909090909090908) internal successors, (105), 75 states have internal predecessors, (105), 24 states have call successors, (24), 11 states have call predecessors, (24), 11 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) Second operand has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-04-01 10:51:07,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-01 10:51:07,525 INFO L93 Difference]: Finished difference Result 189 states and 300 transitions. [2023-04-01 10:51:07,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-04-01 10:51:07,528 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 21 [2023-04-01 10:51:07,528 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-01 10:51:07,534 INFO L225 Difference]: With dead ends: 189 [2023-04-01 10:51:07,534 INFO L226 Difference]: Without dead ends: 94 [2023-04-01 10:51:07,538 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-01 10:51:07,541 INFO L413 NwaCegarLoop]: 107 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-01 10:51:07,542 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 107 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-01 10:51:07,554 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states. [2023-04-01 10:51:07,573 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 94. [2023-04-01 10:51:07,574 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 94 states, 60 states have (on average 1.2666666666666666) internal successors, (76), 68 states have internal predecessors, (76), 24 states have call successors, (24), 11 states have call predecessors, (24), 9 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-04-01 10:51:07,576 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 94 states to 94 states and 114 transitions. [2023-04-01 10:51:07,578 INFO L78 Accepts]: Start accepts. Automaton has 94 states and 114 transitions. Word has length 21 [2023-04-01 10:51:07,578 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-01 10:51:07,578 INFO L495 AbstractCegarLoop]: Abstraction has 94 states and 114 transitions. [2023-04-01 10:51:07,578 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 7.0) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2023-04-01 10:51:07,578 INFO L276 IsEmpty]: Start isEmpty. Operand 94 states and 114 transitions. [2023-04-01 10:51:07,580 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2023-04-01 10:51:07,580 INFO L187 NwaCegarLoop]: Found error trace [2023-04-01 10:51:07,580 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-01 10:51:07,581 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-04-01 10:51:07,581 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-01 10:51:07,581 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-01 10:51:07,581 INFO L85 PathProgramCache]: Analyzing trace with hash -1838638245, now seen corresponding path program 1 times [2023-04-01 10:51:07,582 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-01 10:51:07,582 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848078342] [2023-04-01 10:51:07,582 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:07,582 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-01 10:51:07,770 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:09,696 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 15 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-01 10:51:09,697 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-01 10:51:09,697 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1848078342] [2023-04-01 10:51:09,698 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1848078342] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-01 10:51:09,698 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1154547359] [2023-04-01 10:51:09,698 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:09,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-01 10:51:09,699 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-01 10:51:09,701 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-01 10:51:09,728 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-04-01 10:51:09,989 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:09,994 INFO L262 TraceCheckSpWp]: Trace formula consists of 502 conjuncts, 76 conjunts are in the unsatisfiable core [2023-04-01 10:51:10,008 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-01 10:51:10,072 INFO L321 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2023-04-01 10:51:10,073 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 9 treesize of output 11 [2023-04-01 10:51:10,147 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:10,338 INFO L321 Elim1Store]: treesize reduction 26, result has 42.2 percent of original size [2023-04-01 10:51:10,339 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 74 [2023-04-01 10:51:10,349 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2023-04-01 10:51:10,360 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-04-01 10:51:10,404 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 19 [2023-04-01 10:51:10,409 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2023-04-01 10:51:10,558 INFO L321 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-04-01 10:51:10,558 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 19 [2023-04-01 10:51:10,630 WARN L861 $PredicateComparison]: unable to prove that (and (exists ((v_ArrVal_237 (Array Int Int))) (= |c_#memory_$Pointer$.base| (store |c_old(#memory_$Pointer$.base)| |c_alloc_node_#res.base| v_ArrVal_237))) (< |c_alloc_node_#res.base| |c_#StackHeapBarrier|)) is different from true [2023-04-01 10:51:10,683 WARN L861 $PredicateComparison]: unable to prove that (exists ((chain_node_~node~0.offset Int) (v_ArrVal_237 (Array Int Int)) (chain_node_~node~0.base Int) (v_ArrVal_240 (Array Int Int)) (chain_node_~ppnode.offset Int)) (and (= (store (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base (store v_ArrVal_237 chain_node_~node~0.offset (select (select (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base v_ArrVal_237) |c_chain_node_#in~ppnode.base|) chain_node_~ppnode.offset))) |c_chain_node_#in~ppnode.base| v_ArrVal_240) |c_#memory_$Pointer$.base|) (< chain_node_~node~0.base |c_#StackHeapBarrier|))) is different from true [2023-04-01 10:51:10,739 INFO L321 Elim1Store]: treesize reduction 88, result has 35.8 percent of original size [2023-04-01 10:51:10,739 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 60 treesize of output 111 [2023-04-01 10:51:10,763 INFO L321 Elim1Store]: treesize reduction 36, result has 12.2 percent of original size [2023-04-01 10:51:10,764 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 29 treesize of output 44 [2023-04-01 10:51:10,814 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2023-04-01 10:51:10,889 INFO L321 Elim1Store]: treesize reduction 25, result has 30.6 percent of original size [2023-04-01 10:51:10,890 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 20 treesize of output 15 [2023-04-01 10:51:10,981 INFO L321 Elim1Store]: treesize reduction 38, result has 32.1 percent of original size [2023-04-01 10:51:10,982 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 90 treesize of output 74 [2023-04-01 10:51:11,010 INFO L321 Elim1Store]: treesize reduction 25, result has 30.6 percent of original size [2023-04-01 10:51:11,010 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 20 treesize of output 15 [2023-04-01 10:51:11,040 INFO L321 Elim1Store]: treesize reduction 25, result has 30.6 percent of original size [2023-04-01 10:51:11,040 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 20 treesize of output 15 [2023-04-01 10:51:11,089 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:11,089 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 102 treesize of output 110 [2023-04-01 10:51:11,424 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-04-01 10:51:11,428 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2023-04-01 10:51:11,459 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2023-04-01 10:51:11,465 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 12 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 2 not checked. [2023-04-01 10:51:11,465 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-01 10:51:11,757 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:11,758 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 2388 treesize of output 2341 [2023-04-01 10:51:11,816 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 321 treesize of output 317 [2023-04-01 10:51:11,835 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:11,835 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 416 treesize of output 401 [2023-04-01 10:51:11,899 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 370 treesize of output 354 [2023-04-01 10:51:11,968 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2023-04-01 10:51:12,043 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 18 [2023-04-01 10:51:12,124 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1154547359] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-01 10:51:12,125 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1241768141] [2023-04-01 10:51:12,186 INFO L159 IcfgInterpreter]: Started Sifa with 34 locations of interest [2023-04-01 10:51:12,186 INFO L166 IcfgInterpreter]: Building call graph [2023-04-01 10:51:12,189 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-01 10:51:12,193 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-01 10:51:12,193 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-01 10:51:12,289 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 49 for LOIs [2023-04-01 10:51:13,050 INFO L197 IcfgInterpreter]: Interpreting procedure check_seq_next with input of size 75 for LOIs [2023-04-01 10:51:13,138 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-04-01 10:51:13,144 INFO L197 IcfgInterpreter]: Interpreting procedure fail with input of size 58 for LOIs [2023-04-01 10:51:13,161 INFO L197 IcfgInterpreter]: Interpreting procedure create_sll with input of size 76 for LOIs [2023-04-01 10:51:14,275 INFO L197 IcfgInterpreter]: Interpreting procedure chain_node with input of size 50 for LOIs [2023-04-01 10:51:14,484 INFO L197 IcfgInterpreter]: Interpreting procedure alloc_node with input of size 51 for LOIs [2023-04-01 10:51:14,500 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-01 10:51:23,033 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '728#(and (not (= |#StackHeapBarrier| 0)) (exists ((|v_old(#valid)_BEFORE_CALL_6| (Array Int Int)) (|v_old(#length)_BEFORE_CALL_3| (Array Int Int)) (|v_old(#memory_int)_BEFORE_CALL_3| (Array Int (Array Int Int))) (|v_main_~#p1~0.base_BEFORE_CALL_4| Int)) (and (= (select (select |v_old(#memory_int)_BEFORE_CALL_3| 1) 0) 48) (= (select (select |v_old(#memory_int)_BEFORE_CALL_3| 1) 1) 0) (= (select |v_old(#valid)_BEFORE_CALL_6| |v_main_~#p1~0.base_BEFORE_CALL_4|) 0) (not (= |v_main_~#p1~0.base_BEFORE_CALL_4| 0)) (= 2 (select |v_old(#length)_BEFORE_CALL_3| 1)) (not (= |v_old(#length)_BEFORE_CALL_3| (select |v_old(#memory_int)_BEFORE_CALL_3| 1))) (= (select |v_old(#valid)_BEFORE_CALL_6| 2) 1) (not (= |v_main_~#p1~0.base_BEFORE_CALL_4| |#StackHeapBarrier|)) (not (= |v_main_~#p1~0.base_BEFORE_CALL_4| 2)) (not (= |v_old(#valid)_BEFORE_CALL_6| |v_old(#length)_BEFORE_CALL_3|)) (not (= |v_main_~#p1~0.base_BEFORE_CALL_4| 1)) (not (= |v_old(#valid)_BEFORE_CALL_6| (select |v_old(#memory_int)_BEFORE_CALL_3| 1))) (= 19 (select |v_old(#length)_BEFORE_CALL_3| 2)) (= (select |v_old(#valid)_BEFORE_CALL_6| 1) 1) (= (select (select |#memory_$Pointer$.base| |v_main_~#p1~0.base_BEFORE_CALL_4|) 0) 0) (= (select |v_old(#valid)_BEFORE_CALL_6| 0) 0) (= (select (select |#memory_$Pointer$.offset| |v_main_~#p1~0.base_BEFORE_CALL_4|) 0) 0))) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-01 10:51:23,034 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-01 10:51:23,034 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-01 10:51:23,034 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 32 [2023-04-01 10:51:23,035 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2093184151] [2023-04-01 10:51:23,035 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-01 10:51:23,036 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 32 states [2023-04-01 10:51:23,036 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-01 10:51:23,038 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 32 interpolants. [2023-04-01 10:51:23,039 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=213, Invalid=2975, Unknown=12, NotChecked=222, Total=3422 [2023-04-01 10:51:23,040 INFO L87 Difference]: Start difference. First operand 94 states and 114 transitions. Second operand has 32 states, 17 states have (on average 2.4705882352941178) internal successors, (42), 26 states have internal predecessors, (42), 12 states have call successors, (16), 5 states have call predecessors, (16), 9 states have return successors, (13), 12 states have call predecessors, (13), 10 states have call successors, (13) [2023-04-01 10:51:25,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-01 10:51:25,242 INFO L93 Difference]: Finished difference Result 136 states and 172 transitions. [2023-04-01 10:51:25,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2023-04-01 10:51:25,243 INFO L78 Accepts]: Start accepts. Automaton has has 32 states, 17 states have (on average 2.4705882352941178) internal successors, (42), 26 states have internal predecessors, (42), 12 states have call successors, (16), 5 states have call predecessors, (16), 9 states have return successors, (13), 12 states have call predecessors, (13), 10 states have call successors, (13) Word has length 45 [2023-04-01 10:51:25,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-01 10:51:25,246 INFO L225 Difference]: With dead ends: 136 [2023-04-01 10:51:25,246 INFO L226 Difference]: Without dead ends: 133 [2023-04-01 10:51:25,248 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 137 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 73 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 1434 ImplicationChecksByTransitivity, 9.9s TimeCoverageRelationStatistics Valid=341, Invalid=4910, Unknown=13, NotChecked=286, Total=5550 [2023-04-01 10:51:25,249 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 269 mSDsluCounter, 370 mSDsCounter, 0 mSdLazyCounter, 1479 mSolverCounterSat, 142 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 277 SdHoareTripleChecker+Valid, 416 SdHoareTripleChecker+Invalid, 1957 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 1479 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 336 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2023-04-01 10:51:25,249 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [277 Valid, 416 Invalid, 1957 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 1479 Invalid, 0 Unknown, 336 Unchecked, 1.4s Time] [2023-04-01 10:51:25,250 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 133 states. [2023-04-01 10:51:25,273 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 133 to 105. [2023-04-01 10:51:25,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 70 states have (on average 1.2714285714285714) internal successors, (89), 78 states have internal predecessors, (89), 24 states have call successors, (24), 12 states have call predecessors, (24), 10 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-04-01 10:51:25,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 127 transitions. [2023-04-01 10:51:25,279 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 127 transitions. Word has length 45 [2023-04-01 10:51:25,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-01 10:51:25,279 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 127 transitions. [2023-04-01 10:51:25,280 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 32 states, 17 states have (on average 2.4705882352941178) internal successors, (42), 26 states have internal predecessors, (42), 12 states have call successors, (16), 5 states have call predecessors, (16), 9 states have return successors, (13), 12 states have call predecessors, (13), 10 states have call successors, (13) [2023-04-01 10:51:25,280 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 127 transitions. [2023-04-01 10:51:25,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2023-04-01 10:51:25,282 INFO L187 NwaCegarLoop]: Found error trace [2023-04-01 10:51:25,283 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-01 10:51:25,294 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-04-01 10:51:25,490 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-01 10:51:25,491 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-01 10:51:25,491 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-01 10:51:25,492 INFO L85 PathProgramCache]: Analyzing trace with hash -1699501435, now seen corresponding path program 1 times [2023-04-01 10:51:25,492 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-01 10:51:25,492 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [138900302] [2023-04-01 10:51:25,492 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:25,492 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-01 10:51:25,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:27,738 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-04-01 10:51:27,739 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-01 10:51:27,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [138900302] [2023-04-01 10:51:27,739 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [138900302] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-01 10:51:27,739 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [56999857] [2023-04-01 10:51:27,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:27,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-01 10:51:27,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-01 10:51:27,740 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-01 10:51:27,743 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-04-01 10:51:27,965 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:27,968 INFO L262 TraceCheckSpWp]: Trace formula consists of 504 conjuncts, 124 conjunts are in the unsatisfiable core [2023-04-01 10:51:27,976 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-01 10:51:28,001 INFO L321 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2023-04-01 10:51:28,001 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 18 [2023-04-01 10:51:28,062 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-04-01 10:51:28,129 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:28,177 INFO L321 Elim1Store]: treesize reduction 26, result has 42.2 percent of original size [2023-04-01 10:51:28,177 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 74 [2023-04-01 10:51:28,185 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2023-04-01 10:51:28,192 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-04-01 10:51:28,239 INFO L321 Elim1Store]: treesize reduction 25, result has 3.8 percent of original size [2023-04-01 10:51:28,240 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 66 treesize of output 26 [2023-04-01 10:51:28,245 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 21 treesize of output 15 [2023-04-01 10:51:28,258 WARN L861 $PredicateComparison]: unable to prove that (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_chain_node_#in~ppnode.base|) |c_chain_node_#in~ppnode.offset|))) (let ((.cse1 (not (= .cse0 0)))) (or (and (exists ((v_DerPreprocessor_7 (Array Int Int)) (v_DerPreprocessor_8 (Array Int Int))) (and (= (select (store (store (store (store |c_#memory_$Pointer$.base| .cse0 v_DerPreprocessor_7) |c_chain_node_#in~ppnode.base| v_DerPreprocessor_8) .cse0 v_DerPreprocessor_7) |c_chain_node_#in~ppnode.base| v_DerPreprocessor_8) .cse0) (select |c_#memory_$Pointer$.base| .cse0)) (= .cse0 (select v_DerPreprocessor_8 |c_chain_node_#in~ppnode.offset|)))) .cse1) (and (= .cse0 |c_chain_node_#in~ppnode.base|) .cse1)))) is different from true [2023-04-01 10:51:28,309 WARN L861 $PredicateComparison]: unable to prove that (and (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_create_sll_~#list~0.base|) 0))) (let ((.cse1 (not (= .cse0 0)))) (or (and (= |c_create_sll_~#list~0.base| .cse0) .cse1) (and .cse1 (exists ((v_DerPreprocessor_7 (Array Int Int)) (v_DerPreprocessor_8 (Array Int Int))) (and (= .cse0 (select v_DerPreprocessor_8 0)) (= (select (store (store (store (store |c_#memory_$Pointer$.base| .cse0 v_DerPreprocessor_7) |c_create_sll_~#list~0.base| v_DerPreprocessor_8) .cse0 v_DerPreprocessor_7) |c_create_sll_~#list~0.base| v_DerPreprocessor_8) .cse0) (select |c_#memory_$Pointer$.base| .cse0)))))))) (= |c_create_sll_~#list~0.offset| 0) (= 0 (select |c_old(#valid)| |c_create_sll_~#list~0.base|)) (= |c_create_sll_#in~pp2.base| c_create_sll_~pp2.base) (= c_create_sll_~pp2.offset |c_create_sll_#in~pp2.offset|) (< |c_#StackHeapBarrier| |c_create_sll_~#list~0.base|) (= c_create_sll_~pp1.base |c_create_sll_#in~pp1.base|)) is different from true [2023-04-01 10:51:28,465 INFO L321 Elim1Store]: treesize reduction 38, result has 47.9 percent of original size [2023-04-01 10:51:28,466 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 87 treesize of output 97 [2023-04-01 10:51:28,488 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 5 [2023-04-01 10:51:28,508 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2023-04-01 10:51:28,537 INFO L321 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2023-04-01 10:51:28,538 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 17 treesize of output 19 [2023-04-01 10:51:28,642 INFO L321 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2023-04-01 10:51:28,642 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 8 [2023-04-01 10:51:28,645 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:28,812 WARN L861 $PredicateComparison]: unable to prove that (exists ((chain_node_~node~0.base Int) (v_ArrVal_496 (Array Int Int)) (v_ArrVal_498 (Array Int Int))) (and (= |c_#memory_$Pointer$.base| (store (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base v_ArrVal_496) |c_chain_node_#in~ppnode.base| (store (select (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base v_ArrVal_498) |c_chain_node_#in~ppnode.base|) |c_chain_node_#in~ppnode.offset| chain_node_~node~0.base))) (< chain_node_~node~0.base |c_#StackHeapBarrier|) (not (= chain_node_~node~0.base 0)))) is different from true [2023-04-01 10:51:28,827 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:28,830 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:28,858 INFO L321 Elim1Store]: treesize reduction 26, result has 44.7 percent of original size [2023-04-01 10:51:28,859 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 34 treesize of output 47 [2023-04-01 10:51:28,871 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 17 [2023-04-01 10:51:28,905 INFO L321 Elim1Store]: treesize reduction 21, result has 34.4 percent of original size [2023-04-01 10:51:28,905 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 22 treesize of output 26 [2023-04-01 10:51:28,925 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2023-04-01 10:51:28,940 INFO L321 Elim1Store]: treesize reduction 31, result has 3.1 percent of original size [2023-04-01 10:51:28,940 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 22 treesize of output 1 [2023-04-01 10:51:29,206 INFO L321 Elim1Store]: treesize reduction 20, result has 57.4 percent of original size [2023-04-01 10:51:29,207 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 55 treesize of output 68 [2023-04-01 10:51:29,233 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2023-04-01 10:51:29,291 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 11 [2023-04-01 10:51:29,303 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 8 [2023-04-01 10:51:29,326 WARN L207 Elim1Store]: Array PQE input equivalent to false [2023-04-01 10:51:29,331 WARN L207 Elim1Store]: Array PQE input equivalent to false [2023-04-01 10:51:29,344 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:29,344 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 18 treesize of output 20 [2023-04-01 10:51:29,570 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:29,570 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 91 treesize of output 68 [2023-04-01 10:51:29,577 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:29,767 WARN L861 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_501 (Array Int Int)) (chain_node_~node~0.base Int) (v_ArrVal_506 (Array Int Int))) (and (< chain_node_~node~0.base |c_#StackHeapBarrier|) (= (store (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base (store v_ArrVal_501 0 (select (select (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base v_ArrVal_501) |c_chain_node_#in~ppnode.base|) |c_chain_node_#in~ppnode.offset|))) |c_chain_node_#in~ppnode.base| v_ArrVal_506) |c_#memory_$Pointer$.base|))) is different from true [2023-04-01 10:51:29,818 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:29,821 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:29,855 INFO L321 Elim1Store]: treesize reduction 28, result has 42.9 percent of original size [2023-04-01 10:51:29,855 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 108 treesize of output 109 [2023-04-01 10:51:29,866 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2023-04-01 10:51:30,009 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2023-04-01 10:51:30,031 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2023-04-01 10:51:30,119 INFO L321 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2023-04-01 10:51:30,120 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 83 treesize of output 67 [2023-04-01 10:51:30,167 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:30,167 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 83 treesize of output 71 [2023-04-01 10:51:30,257 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 104 treesize of output 84 [2023-04-01 10:51:31,489 INFO L321 Elim1Store]: treesize reduction 8, result has 80.5 percent of original size [2023-04-01 10:51:31,490 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 81 treesize of output 105 [2023-04-01 10:51:31,643 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:31,643 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 17 [2023-04-01 10:51:31,656 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 3 not checked. [2023-04-01 10:51:31,656 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-01 10:51:32,343 INFO L173 IndexEqualityManager]: detected equality via solver [2023-04-01 10:51:32,344 INFO L173 IndexEqualityManager]: detected equality via solver [2023-04-01 10:51:32,434 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:32,436 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 196982 treesize of output 195839 [2023-04-01 10:51:32,794 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1094 treesize of output 1046 [2023-04-01 10:51:32,972 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:32,972 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 914 treesize of output 891 [2023-04-01 10:51:33,024 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 882 treesize of output 878 [2023-04-01 10:51:33,049 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 878 treesize of output 846 [2023-04-01 10:51:33,986 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [56999857] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-01 10:51:33,987 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [139521030] [2023-04-01 10:51:33,989 INFO L159 IcfgInterpreter]: Started Sifa with 36 locations of interest [2023-04-01 10:51:33,989 INFO L166 IcfgInterpreter]: Building call graph [2023-04-01 10:51:33,989 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-01 10:51:33,989 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-01 10:51:33,990 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-01 10:51:34,042 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 49 for LOIs [2023-04-01 10:51:34,349 INFO L197 IcfgInterpreter]: Interpreting procedure check_seq_next with input of size 75 for LOIs [2023-04-01 10:51:34,409 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 7 for LOIs [2023-04-01 10:51:34,412 INFO L197 IcfgInterpreter]: Interpreting procedure fail with input of size 74 for LOIs [2023-04-01 10:51:34,418 INFO L197 IcfgInterpreter]: Interpreting procedure create_sll with input of size 76 for LOIs [2023-04-01 10:51:34,957 INFO L197 IcfgInterpreter]: Interpreting procedure chain_node with input of size 50 for LOIs [2023-04-01 10:51:35,081 INFO L197 IcfgInterpreter]: Interpreting procedure alloc_node with input of size 51 for LOIs [2023-04-01 10:51:35,089 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-01 10:51:43,392 WARN L223 SmtUtils]: Spent 6.62s on a formula simplification that was a NOOP. DAG size: 68 (called from [L 376] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2023-04-01 10:51:45,840 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1375#(and (exists ((|v_old(#length)_BEFORE_CALL_13| (Array Int Int)) (|v_main_~#p1~0.base_BEFORE_CALL_9| Int) (|v_old(#valid)_BEFORE_CALL_25| (Array Int Int)) (|v_old(#memory_int)_BEFORE_CALL_19| (Array Int (Array Int Int)))) (and (= (select (select |v_old(#memory_int)_BEFORE_CALL_19| 1) 0) 48) (not (= (select |v_old(#memory_int)_BEFORE_CALL_19| 1) |v_old(#length)_BEFORE_CALL_13|)) (not (= |v_main_~#p1~0.base_BEFORE_CALL_9| 1)) (= (select |v_old(#valid)_BEFORE_CALL_25| |v_main_~#p1~0.base_BEFORE_CALL_9|) 0) (= 19 (select |v_old(#length)_BEFORE_CALL_13| 2)) (not (= |v_main_~#p1~0.base_BEFORE_CALL_9| 2)) (or (not (= (select (select |#memory_$Pointer$.offset| |v_main_~#p1~0.base_BEFORE_CALL_9|) 0) 0)) (not (= (select (select |#memory_$Pointer$.base| |v_main_~#p1~0.base_BEFORE_CALL_9|) 0) 0))) (not (= (select |v_old(#memory_int)_BEFORE_CALL_19| 1) |v_old(#valid)_BEFORE_CALL_25|)) (= (select |v_old(#valid)_BEFORE_CALL_25| 2) 1) (= (select |v_old(#valid)_BEFORE_CALL_25| 1) 1) (not (= |v_main_~#p1~0.base_BEFORE_CALL_9| 0)) (= 2 (select |v_old(#length)_BEFORE_CALL_13| 1)) (not (= |v_old(#valid)_BEFORE_CALL_25| |v_old(#length)_BEFORE_CALL_13|)) (= (select |v_old(#valid)_BEFORE_CALL_25| 0) 0) (not (= |v_main_~#p1~0.base_BEFORE_CALL_9| |#StackHeapBarrier|)) (= (select (select |v_old(#memory_int)_BEFORE_CALL_19| 1) 1) 0))) (not (= |#StackHeapBarrier| 0)) (= |#NULL.offset| 0) (exists ((|v_main_~#p2~0.base_BEFORE_CALL_8| Int)) (and (= (select (select |#memory_$Pointer$.base| |v_main_~#p2~0.base_BEFORE_CALL_8|) 0) 0) (not (= |v_main_~#p2~0.base_BEFORE_CALL_8| |#StackHeapBarrier|)) (not (= |v_main_~#p2~0.base_BEFORE_CALL_8| 0)) (= (select (select |#memory_$Pointer$.offset| |v_main_~#p2~0.base_BEFORE_CALL_8|) 0) 0))) (= |#NULL.base| 0))' at error location [2023-04-01 10:51:45,840 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-01 10:51:45,840 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-01 10:51:45,841 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 42 [2023-04-01 10:51:45,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [131952920] [2023-04-01 10:51:45,841 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-01 10:51:45,841 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 42 states [2023-04-01 10:51:45,841 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-01 10:51:45,842 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 42 interpolants. [2023-04-01 10:51:45,843 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=266, Invalid=4021, Unknown=19, NotChecked=524, Total=4830 [2023-04-01 10:51:45,843 INFO L87 Difference]: Start difference. First operand 105 states and 127 transitions. Second operand has 42 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 34 states have internal predecessors, (46), 14 states have call successors, (15), 5 states have call predecessors, (15), 13 states have return successors, (14), 14 states have call predecessors, (14), 12 states have call successors, (14) [2023-04-01 10:51:50,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-01 10:51:50,050 INFO L93 Difference]: Finished difference Result 176 states and 231 transitions. [2023-04-01 10:51:50,051 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2023-04-01 10:51:50,051 INFO L78 Accepts]: Start accepts. Automaton has has 42 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 34 states have internal predecessors, (46), 14 states have call successors, (15), 5 states have call predecessors, (15), 13 states have return successors, (14), 14 states have call predecessors, (14), 12 states have call successors, (14) Word has length 47 [2023-04-01 10:51:50,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-01 10:51:50,053 INFO L225 Difference]: With dead ends: 176 [2023-04-01 10:51:50,053 INFO L226 Difference]: Without dead ends: 173 [2023-04-01 10:51:50,055 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 154 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 87 ConstructedPredicates, 4 IntricatePredicates, 0 DeprecatedPredicates, 2001 ImplicationChecksByTransitivity, 13.9s TimeCoverageRelationStatistics Valid=428, Invalid=6702, Unknown=26, NotChecked=676, Total=7832 [2023-04-01 10:51:50,056 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 252 mSDsluCounter, 623 mSDsCounter, 0 mSdLazyCounter, 2431 mSolverCounterSat, 137 mSolverCounterUnsat, 9 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 260 SdHoareTripleChecker+Valid, 672 SdHoareTripleChecker+Invalid, 3482 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 137 IncrementalHoareTripleChecker+Valid, 2431 IncrementalHoareTripleChecker+Invalid, 9 IncrementalHoareTripleChecker+Unknown, 905 IncrementalHoareTripleChecker+Unchecked, 2.8s IncrementalHoareTripleChecker+Time [2023-04-01 10:51:50,056 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [260 Valid, 672 Invalid, 3482 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [137 Valid, 2431 Invalid, 9 Unknown, 905 Unchecked, 2.8s Time] [2023-04-01 10:51:50,057 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2023-04-01 10:51:50,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 105. [2023-04-01 10:51:50,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 70 states have (on average 1.2571428571428571) internal successors, (88), 78 states have internal predecessors, (88), 24 states have call successors, (24), 12 states have call predecessors, (24), 10 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2023-04-01 10:51:50,075 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 126 transitions. [2023-04-01 10:51:50,075 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 126 transitions. Word has length 47 [2023-04-01 10:51:50,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-01 10:51:50,075 INFO L495 AbstractCegarLoop]: Abstraction has 105 states and 126 transitions. [2023-04-01 10:51:50,076 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 42 states, 19 states have (on average 2.4210526315789473) internal successors, (46), 34 states have internal predecessors, (46), 14 states have call successors, (15), 5 states have call predecessors, (15), 13 states have return successors, (14), 14 states have call predecessors, (14), 12 states have call successors, (14) [2023-04-01 10:51:50,076 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 126 transitions. [2023-04-01 10:51:50,076 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2023-04-01 10:51:50,076 INFO L187 NwaCegarLoop]: Found error trace [2023-04-01 10:51:50,077 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-01 10:51:50,087 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-04-01 10:51:50,282 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2023-04-01 10:51:50,283 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting failErr0ASSERT_VIOLATIONERROR_FUNCTION === [failErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-01 10:51:50,283 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-01 10:51:50,283 INFO L85 PathProgramCache]: Analyzing trace with hash -1788717711, now seen corresponding path program 1 times [2023-04-01 10:51:50,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-01 10:51:50,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1896474381] [2023-04-01 10:51:50,284 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:50,284 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-01 10:51:50,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:54,154 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2023-04-01 10:51:54,154 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-01 10:51:54,154 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1896474381] [2023-04-01 10:51:54,154 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1896474381] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-01 10:51:54,155 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [76973894] [2023-04-01 10:51:54,155 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-01 10:51:54,155 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-01 10:51:54,155 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-01 10:51:54,156 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-01 10:51:54,165 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-04-01 10:51:54,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-01 10:51:54,358 INFO L262 TraceCheckSpWp]: Trace formula consists of 511 conjuncts, 157 conjunts are in the unsatisfiable core [2023-04-01 10:51:54,364 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-01 10:51:54,378 INFO L321 Elim1Store]: treesize reduction 15, result has 25.0 percent of original size [2023-04-01 10:51:54,379 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 9 treesize of output 11 [2023-04-01 10:51:54,440 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:54,511 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:54,550 INFO L321 Elim1Store]: treesize reduction 26, result has 42.2 percent of original size [2023-04-01 10:51:54,551 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 74 [2023-04-01 10:51:54,557 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2023-04-01 10:51:54,564 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-04-01 10:51:54,578 INFO L173 IndexEqualityManager]: detected equality via solver [2023-04-01 10:51:54,579 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 9 [2023-04-01 10:51:54,582 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2023-04-01 10:51:54,615 WARN L861 $PredicateComparison]: unable to prove that (let ((.cse0 (select (select |c_#memory_$Pointer$.base| |c_chain_node_#in~ppnode.base|) |c_chain_node_#in~ppnode.offset|))) (or (and (= .cse0 |c_chain_node_#in~ppnode.base|) (not (= .cse0 0))) (exists ((v_DerPreprocessor_10 (Array Int Int)) (v_DerPreprocessor_11 (Array Int Int))) (let ((.cse1 (select v_DerPreprocessor_11 |c_chain_node_#in~ppnode.offset|))) (and (not (= .cse1 0)) (= .cse1 .cse0) (= (select |c_#memory_$Pointer$.base| .cse1) (select (store (store (store (store |c_#memory_$Pointer$.base| .cse1 v_DerPreprocessor_10) |c_chain_node_#in~ppnode.base| v_DerPreprocessor_11) .cse1 v_DerPreprocessor_10) |c_chain_node_#in~ppnode.base| v_DerPreprocessor_11) .cse1))))))) is different from true [2023-04-01 10:51:54,866 INFO L321 Elim1Store]: treesize reduction 44, result has 48.2 percent of original size [2023-04-01 10:51:54,867 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 77 treesize of output 98 [2023-04-01 10:51:54,914 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 10 [2023-04-01 10:51:54,925 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2023-04-01 10:51:54,979 INFO L321 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2023-04-01 10:51:54,980 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 17 treesize of output 19 [2023-04-01 10:51:55,141 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:55,141 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 40 treesize of output 52 [2023-04-01 10:51:55,146 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:55,209 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2023-04-01 10:51:55,417 INFO L321 Elim1Store]: treesize reduction 26, result has 42.2 percent of original size [2023-04-01 10:51:55,417 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 74 [2023-04-01 10:51:55,429 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2023-04-01 10:51:55,441 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2023-04-01 10:51:55,480 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 11 [2023-04-01 10:51:55,488 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:55,683 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:55,687 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:55,759 INFO L321 Elim1Store]: treesize reduction 62, result has 44.1 percent of original size [2023-04-01 10:51:55,759 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 61 treesize of output 94 [2023-04-01 10:51:55,770 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2023-04-01 10:51:55,866 WARN L207 Elim1Store]: Array PQE input equivalent to false [2023-04-01 10:51:55,871 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 19 [2023-04-01 10:51:56,068 INFO L321 Elim1Store]: treesize reduction 48, result has 32.4 percent of original size [2023-04-01 10:51:56,068 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 52 treesize of output 49 [2023-04-01 10:51:56,098 INFO L321 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2023-04-01 10:51:56,099 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 18 [2023-04-01 10:51:56,213 INFO L321 Elim1Store]: treesize reduction 21, result has 36.4 percent of original size [2023-04-01 10:51:56,213 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 35 [2023-04-01 10:51:56,224 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:56,235 INFO L321 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2023-04-01 10:51:56,235 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 7 [2023-04-01 10:51:56,239 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-04-01 10:51:56,505 WARN L861 $PredicateComparison]: unable to prove that (exists ((v_ArrVal_810 (Array Int Int)) (chain_node_~node~0.offset Int) (chain_node_~node~0.base Int) (v_ArrVal_811 (Array Int Int)) (v_ArrVal_813 (Array Int Int)) (v_ArrVal_816 (Array Int Int)) (chain_node_~ppnode.offset Int)) (and (= (store (store |c_old(#memory_$Pointer$.offset)| chain_node_~node~0.base v_ArrVal_813) |c_chain_node_#in~ppnode.base| v_ArrVal_816) |c_#memory_$Pointer$.offset|) (= (select |c_old(#valid)| chain_node_~node~0.base) 0) (< chain_node_~node~0.base |c_#StackHeapBarrier|) (= |c_#memory_$Pointer$.base| (store (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base (store v_ArrVal_810 chain_node_~node~0.offset (select (select (store |c_old(#memory_$Pointer$.base)| chain_node_~node~0.base v_ArrVal_810) |c_chain_node_#in~ppnode.base|) chain_node_~ppnode.offset))) |c_chain_node_#in~ppnode.base| v_ArrVal_811)))) is different from true [2023-04-01 10:51:56,524 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:56,531 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:56,611 INFO L321 Elim1Store]: treesize reduction 79, result has 24.8 percent of original size [2023-04-01 10:51:56,611 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 64 treesize of output 77 [2023-04-01 10:51:56,623 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-04-01 10:51:56,654 INFO L321 Elim1Store]: treesize reduction 23, result has 47.7 percent of original size [2023-04-01 10:51:56,654 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 24 treesize of output 41 [2023-04-01 10:51:56,666 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2023-04-01 10:51:56,690 INFO L321 Elim1Store]: treesize reduction 4, result has 60.0 percent of original size [2023-04-01 10:51:56,691 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 13 treesize of output 13 [2023-04-01 10:51:56,757 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:56,757 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 44 treesize of output 40 [2023-04-01 10:51:56,808 INFO L321 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-04-01 10:51:56,808 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 20 [2023-04-01 10:51:56,836 INFO L321 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-04-01 10:51:56,837 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 7 [2023-04-01 10:51:56,950 INFO L321 Elim1Store]: treesize reduction 8, result has 68.0 percent of original size [2023-04-01 10:51:56,950 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 46 [2023-04-01 10:51:56,991 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 20 [2023-04-01 10:51:57,030 INFO L321 Elim1Store]: treesize reduction 8, result has 68.0 percent of original size [2023-04-01 10:51:57,030 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 46 [2023-04-01 10:52:00,247 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-04-01 10:52:00,343 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2023-04-01 10:52:00,651 INFO L321 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2023-04-01 10:52:00,651 INFO L350 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 41 treesize of output 20 [2023-04-01 10:52:00,656 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2023-04-01 10:52:00,656 INFO L327 TraceCheckSpWp]: Computing backward predicates...