./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/nla-digbench/divbin.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version a0165632 Calling Ultimate with: /usr/lib/jvm/java-1.11.0-openjdk-amd64/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/config/TaipanReach.xml -i ../../sv-benchmarks/c/nla-digbench/divbin.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash c49641164907d0e2939c5443b0376a8e4377b34a58fd804ad01c6cf7d42c55dc --- Real Ultimate output --- This is Ultimate 0.2.5-dev-a016563 [2024-11-09 01:09:31,639 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 01:09:31,699 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-09 01:09:31,704 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 01:09:31,705 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 01:09:31,728 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 01:09:31,729 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 01:09:31,730 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 01:09:31,730 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-09 01:09:31,731 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-09 01:09:31,731 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-09 01:09:31,732 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-09 01:09:31,732 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-09 01:09:31,732 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-09 01:09:31,733 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-09 01:09:31,733 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-09 01:09:31,734 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-09 01:09:31,734 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-09 01:09:31,734 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-09 01:09:31,735 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-09 01:09:31,735 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-09 01:09:31,736 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-09 01:09:31,737 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 01:09:31,737 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-09 01:09:31,737 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-09 01:09:31,738 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 01:09:31,738 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-09 01:09:31,739 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 01:09:31,739 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-09 01:09:31,739 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-09 01:09:31,740 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-09 01:09:31,740 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 01:09:31,740 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-09 01:09:31,741 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 01:09:31,741 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 01:09:31,742 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 01:09:31,742 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-09 01:09:31,742 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-09 01:09:31,743 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:09:31,743 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 01:09:31,744 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-09 01:09:31,744 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-09 01:09:31,744 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-09 01:09:31,745 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-09 01:09:31,745 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-09 01:09:31,745 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-09 01:09:31,746 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-09 01:09:31,746 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/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.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> c49641164907d0e2939c5443b0376a8e4377b34a58fd804ad01c6cf7d42c55dc [2024-11-09 01:09:32,026 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 01:09:32,053 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 01:09:32,057 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 01:09:32,060 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 01:09:32,060 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 01:09:32,061 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/../../sv-benchmarks/c/nla-digbench/divbin.i Unable to find full path for "g++" [2024-11-09 01:09:34,028 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 01:09:34,201 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 01:09:34,202 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/sv-benchmarks/c/nla-digbench/divbin.i [2024-11-09 01:09:34,208 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/data/cec410b1c/cc620afcdfa9467d8d9286017bb50c62/FLAGf5fee587b [2024-11-09 01:09:34,607 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/data/cec410b1c/cc620afcdfa9467d8d9286017bb50c62 [2024-11-09 01:09:34,609 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 01:09:34,611 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 01:09:34,612 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 01:09:34,612 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 01:09:34,620 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 01:09:34,621 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,623 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4cf1c43d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34, skipping insertion in model container [2024-11-09 01:09:34,625 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,654 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 01:09:34,848 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/sv-benchmarks/c/nla-digbench/divbin.i[950,963] [2024-11-09 01:09:34,877 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:09:34,891 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 01:09:34,904 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/sv-benchmarks/c/nla-digbench/divbin.i[950,963] [2024-11-09 01:09:34,910 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 01:09:34,925 INFO L204 MainTranslator]: Completed translation [2024-11-09 01:09:34,925 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34 WrapperNode [2024-11-09 01:09:34,925 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 01:09:34,926 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 01:09:34,926 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 01:09:34,926 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 01:09:34,933 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,939 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,954 INFO L138 Inliner]: procedures = 16, calls = 10, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 44 [2024-11-09 01:09:34,955 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 01:09:34,955 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 01:09:34,955 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 01:09:34,956 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 01:09:34,964 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,965 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,966 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,966 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,969 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,973 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,975 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,976 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,977 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 01:09:34,978 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 01:09:34,979 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 01:09:34,979 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 01:09:34,980 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (1/1) ... [2024-11-09 01:09:34,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-09 01:09:34,997 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:09:35,008 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-09 01:09:35,010 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-09 01:09:35,036 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-09 01:09:35,036 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-09 01:09:35,036 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-09 01:09:35,036 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-09 01:09:35,036 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 01:09:35,036 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 01:09:35,036 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-09 01:09:35,037 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-09 01:09:35,094 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 01:09:35,096 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 01:09:35,254 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 01:09:35,254 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 01:09:35,300 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 01:09:35,300 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-09 01:09:35,304 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:09:35 BoogieIcfgContainer [2024-11-09 01:09:35,305 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 01:09:35,308 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-09 01:09:35,308 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-09 01:09:35,313 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-09 01:09:35,314 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.11 01:09:34" (1/3) ... [2024-11-09 01:09:35,315 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@610254d5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:09:35, skipping insertion in model container [2024-11-09 01:09:35,315 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 01:09:34" (2/3) ... [2024-11-09 01:09:35,317 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@610254d5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.11 01:09:35, skipping insertion in model container [2024-11-09 01:09:35,317 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 01:09:35" (3/3) ... [2024-11-09 01:09:35,320 INFO L112 eAbstractionObserver]: Analyzing ICFG divbin.i [2024-11-09 01:09:35,339 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-09 01:09:35,340 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-09 01:09:35,400 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-09 01:09:35,419 INFO L333 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, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, 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;@1dbaaca8, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-09 01:09:35,421 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-09 01:09:35,427 INFO L276 IsEmpty]: Start isEmpty. Operand has 20 states, 12 states have (on average 1.5) internal successors, (18), 13 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:09:35,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2024-11-09 01:09:35,447 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:09:35,448 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:09:35,448 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:09:35,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:09:35,453 INFO L85 PathProgramCache]: Analyzing trace with hash -1046620569, now seen corresponding path program 1 times [2024-11-09 01:09:35,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:09:35,464 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [582336044] [2024-11-09 01:09:35,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:35,464 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:09:35,572 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:09:35,626 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:09:35,627 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:09:35,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [582336044] [2024-11-09 01:09:35,628 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [582336044] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:09:35,628 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:09:35,628 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-09 01:09:35,630 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1565770812] [2024-11-09 01:09:35,630 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:09:35,635 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-09 01:09:35,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:09:35,667 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-09 01:09:35,668 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-09 01:09:35,670 INFO L87 Difference]: Start difference. First operand has 20 states, 12 states have (on average 1.5) internal successors, (18), 13 states have internal predecessors, (18), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:09:35,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:09:35,723 INFO L93 Difference]: Finished difference Result 32 states and 43 transitions. [2024-11-09 01:09:35,728 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-09 01:09:35,730 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 14 [2024-11-09 01:09:35,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:09:35,735 INFO L225 Difference]: With dead ends: 32 [2024-11-09 01:09:35,735 INFO L226 Difference]: Without dead ends: 18 [2024-11-09 01:09:35,737 INFO L431 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 [2024-11-09 01:09:35,741 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 4 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 19 SdHoareTripleChecker+Invalid, 5 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 4 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 01:09:35,742 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 19 Invalid, 5 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 4 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 01:09:35,756 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2024-11-09 01:09:35,768 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 18. [2024-11-09 01:09:35,769 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 18 states, 11 states have (on average 1.2727272727272727) internal successors, (14), 12 states have internal predecessors, (14), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-09 01:09:35,770 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 18 states to 18 states and 21 transitions. [2024-11-09 01:09:35,772 INFO L78 Accepts]: Start accepts. Automaton has 18 states and 21 transitions. Word has length 14 [2024-11-09 01:09:35,772 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:09:35,773 INFO L471 AbstractCegarLoop]: Abstraction has 18 states and 21 transitions. [2024-11-09 01:09:35,773 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:09:35,773 INFO L276 IsEmpty]: Start isEmpty. Operand 18 states and 21 transitions. [2024-11-09 01:09:35,774 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2024-11-09 01:09:35,774 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:09:35,775 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:09:35,775 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-09 01:09:35,775 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:09:35,776 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:09:35,776 INFO L85 PathProgramCache]: Analyzing trace with hash -237769385, now seen corresponding path program 1 times [2024-11-09 01:09:35,776 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:09:35,776 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1968749455] [2024-11-09 01:09:35,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:35,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:09:35,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:09:35,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1690276664] [2024-11-09 01:09:35,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:35,829 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:09:35,829 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:09:35,831 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:09:35,833 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-09 01:09:35,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:09:35,910 INFO L255 TraceCheckSpWp]: Trace formula consists of 47 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-09 01:09:35,919 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:09:36,066 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:09:36,067 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-09 01:09:36,067 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:09:36,067 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1968749455] [2024-11-09 01:09:36,068 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:09:36,068 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1690276664] [2024-11-09 01:09:36,069 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1690276664] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:09:36,069 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:09:36,069 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-09 01:09:36,070 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1994674319] [2024-11-09 01:09:36,071 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:09:36,071 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-09 01:09:36,072 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:09:36,072 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-09 01:09:36,073 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-09 01:09:36,073 INFO L87 Difference]: Start difference. First operand 18 states and 21 transitions. Second operand has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:09:36,148 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:09:36,148 INFO L93 Difference]: Finished difference Result 28 states and 32 transitions. [2024-11-09 01:09:36,149 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-09 01:09:36,149 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 15 [2024-11-09 01:09:36,150 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:09:36,150 INFO L225 Difference]: With dead ends: 28 [2024-11-09 01:09:36,151 INFO L226 Difference]: Without dead ends: 25 [2024-11-09 01:09:36,151 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2024-11-09 01:09:36,152 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 5 mSDsluCounter, 36 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-09 01:09:36,153 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 49 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-09 01:09:36,154 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 25 states. [2024-11-09 01:09:36,160 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 25 to 25. [2024-11-09 01:09:36,161 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.1875) internal successors, (19), 17 states have internal predecessors, (19), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:09:36,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2024-11-09 01:09:36,162 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 15 [2024-11-09 01:09:36,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:09:36,162 INFO L471 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2024-11-09 01:09:36,163 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 1.8) internal successors, (9), 4 states have internal predecessors, (9), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-09 01:09:36,163 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2024-11-09 01:09:36,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2024-11-09 01:09:36,164 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:09:36,164 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:09:36,185 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-09 01:09:36,368 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:09:36,369 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:09:36,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:09:36,369 INFO L85 PathProgramCache]: Analyzing trace with hash 997228465, now seen corresponding path program 1 times [2024-11-09 01:09:36,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:09:36,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1477511448] [2024-11-09 01:09:36,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:36,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:09:36,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:09:37,045 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:09:37,045 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:09:37,046 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1477511448] [2024-11-09 01:09:37,046 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1477511448] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-09 01:09:37,046 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-09 01:09:37,046 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-09 01:09:37,046 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1973778818] [2024-11-09 01:09:37,046 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-09 01:09:37,048 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-09 01:09:37,049 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:09:37,050 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-09 01:09:37,051 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 01:09:37,052 INFO L87 Difference]: Start difference. First operand 25 states and 28 transitions. Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 01:09:37,088 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:09:37,089 INFO L93 Difference]: Finished difference Result 40 states and 46 transitions. [2024-11-09 01:09:37,089 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-09 01:09:37,090 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2024-11-09 01:09:37,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:09:37,091 INFO L225 Difference]: With dead ends: 40 [2024-11-09 01:09:37,093 INFO L226 Difference]: Without dead ends: 27 [2024-11-09 01:09:37,093 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-09 01:09:37,095 INFO L432 NwaCegarLoop]: 16 mSDtfsCounter, 0 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 30 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-09 01:09:37,096 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 30 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-09 01:09:37,098 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2024-11-09 01:09:37,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2024-11-09 01:09:37,107 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.1666666666666667) internal successors, (21), 19 states have internal predecessors, (21), 5 states have call successors, (5), 3 states have call predecessors, (5), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-09 01:09:37,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2024-11-09 01:09:37,110 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 22 [2024-11-09 01:09:37,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:09:37,111 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2024-11-09 01:09:37,112 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-09 01:09:37,112 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2024-11-09 01:09:37,113 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-09 01:09:37,113 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:09:37,113 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:09:37,114 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2024-11-09 01:09:37,114 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:09:37,114 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:09:37,115 INFO L85 PathProgramCache]: Analyzing trace with hash -2070291626, now seen corresponding path program 1 times [2024-11-09 01:09:37,115 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:09:37,115 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1813282995] [2024-11-09 01:09:37,116 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:37,116 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:09:37,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:09:37,226 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [571634495] [2024-11-09 01:09:37,226 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:09:37,229 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:09:37,229 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:09:37,231 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:09:37,233 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-09 01:09:37,394 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:09:37,395 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-09 01:09:37,402 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:09:38,291 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-09 01:09:38,293 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:09:56,721 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:10:04,741 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:10:06,754 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse0 (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296)) (.cse2 (mod |c_ULTIMATE.start_main_~b~0#1| 2147483648)) (.cse1 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296))) (or (not (= (mod (+ (* 2 |c_ULTIMATE.start_main_~b~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296) .cse0)) (< .cse1 (mod |c_ULTIMATE.start_main_~b~0#1| 4294967296)) (= (mod (+ |c_ULTIMATE.start_main_~r~0#1| (* 2 .cse2 |c_ULTIMATE.start_main_~q~0#1|)) 4294967296) .cse0) (< (* 2 .cse2) (+ .cse1 1)))) is different from true [2024-11-09 01:10:18,929 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:10:26,955 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:10:27,000 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 1 proven. 3 refuted. 0 times theorem prover too weak. 2 trivial. 2 not checked. [2024-11-09 01:10:27,000 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:10:27,000 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1813282995] [2024-11-09 01:10:27,001 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:10:27,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [571634495] [2024-11-09 01:10:27,001 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [571634495] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:10:27,001 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1331879614] [2024-11-09 01:10:27,020 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:10:27,020 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:10:27,024 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:10:27,029 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:10:27,029 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:10:27,846 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:10:27,866 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:10:27,868 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:10:32,178 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '497#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_13| Int) (|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_13| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_13| Int) (|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_13| Int)) (not (= (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_13| 4294967296) (mod (+ (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_13| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_13|) |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_13|) 4294967296)))))' at error location [2024-11-09 01:10:32,178 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:10:32,178 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:10:32,179 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 19 [2024-11-09 01:10:32,179 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [993273628] [2024-11-09 01:10:32,179 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:10:32,179 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-09 01:10:32,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:10:32,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-09 01:10:32,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=817, Unknown=1, NotChecked=58, Total=992 [2024-11-09 01:10:32,182 INFO L87 Difference]: Start difference. First operand 27 states and 30 transitions. Second operand has 19 states, 17 states have (on average 1.588235294117647) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 01:10:35,280 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:10:37,299 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:10:39,619 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:10:41,629 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:10:43,237 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:10:43,237 INFO L93 Difference]: Finished difference Result 53 states and 61 transitions. [2024-11-09 01:10:43,238 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-09 01:10:43,238 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 1.588235294117647) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) Word has length 24 [2024-11-09 01:10:43,239 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:10:43,241 INFO L225 Difference]: With dead ends: 53 [2024-11-09 01:10:43,241 INFO L226 Difference]: Without dead ends: 49 [2024-11-09 01:10:43,242 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 38 SyntacticMatches, 2 SemanticMatches, 37 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 311 ImplicationChecksByTransitivity, 10.5s TimeCoverageRelationStatistics Valid=179, Invalid=1230, Unknown=1, NotChecked=72, Total=1482 [2024-11-09 01:10:43,243 INFO L432 NwaCegarLoop]: 11 mSDtfsCounter, 29 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 171 mSolverCounterSat, 11 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 171 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 47 IncrementalHoareTripleChecker+Unchecked, 10.2s IncrementalHoareTripleChecker+Time [2024-11-09 01:10:43,243 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 111 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 171 Invalid, 4 Unknown, 47 Unchecked, 10.2s Time] [2024-11-09 01:10:43,244 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 49 states. [2024-11-09 01:10:43,265 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 49 to 36. [2024-11-09 01:10:43,266 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 26 states have (on average 1.1538461538461537) internal successors, (30), 27 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2024-11-09 01:10:43,267 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 40 transitions. [2024-11-09 01:10:43,267 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 40 transitions. Word has length 24 [2024-11-09 01:10:43,267 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:10:43,267 INFO L471 AbstractCegarLoop]: Abstraction has 36 states and 40 transitions. [2024-11-09 01:10:43,268 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 1.588235294117647) internal successors, (27), 15 states have internal predecessors, (27), 6 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-09 01:10:43,268 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 40 transitions. [2024-11-09 01:10:43,269 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-09 01:10:43,269 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:10:43,269 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:10:43,276 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-09 01:10:43,473 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:10:43,474 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:10:43,474 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:10:43,474 INFO L85 PathProgramCache]: Analyzing trace with hash -1057758496, now seen corresponding path program 2 times [2024-11-09 01:10:43,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:10:43,474 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1076661570] [2024-11-09 01:10:43,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:10:43,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:12:16,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:12:16,917 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [344471341] [2024-11-09 01:12:16,918 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 01:12:16,918 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:12:16,918 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:12:16,922 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:12:16,924 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-09 01:12:17,009 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2024-11-09 01:12:17,009 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:12:17,010 INFO L255 TraceCheckSpWp]: Trace formula consists of 65 conjuncts, 19 conjuncts are in the unsatisfiable core [2024-11-09 01:12:17,013 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:12:17,474 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 7 proven. 3 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-09 01:12:17,475 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:12:26,598 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 7 proven. 3 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-09 01:12:26,598 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:12:26,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1076661570] [2024-11-09 01:12:26,598 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:12:26,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [344471341] [2024-11-09 01:12:26,599 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [344471341] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:12:26,599 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [844828421] [2024-11-09 01:12:26,601 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:12:26,605 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:12:26,605 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:12:26,606 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:12:26,606 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:12:27,128 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:12:27,149 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:12:27,151 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:12:29,522 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '840#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_25| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_25| Int) (|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_25| Int) (|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_25| Int)) (not (= (mod (+ |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_25| (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_25| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_25|)) 4294967296) (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_25| 4294967296)))))' at error location [2024-11-09 01:12:29,523 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:12:29,523 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:12:29,523 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2024-11-09 01:12:29,523 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1908433549] [2024-11-09 01:12:29,523 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:12:29,524 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-09 01:12:29,524 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:12:29,525 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-09 01:12:29,525 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=107, Invalid=648, Unknown=1, NotChecked=0, Total=756 [2024-11-09 01:12:29,525 INFO L87 Difference]: Start difference. First operand 36 states and 40 transitions. Second operand has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 5 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 01:12:30,091 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:12:30,092 INFO L93 Difference]: Finished difference Result 48 states and 53 transitions. [2024-11-09 01:12:30,092 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-09 01:12:30,093 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 5 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Word has length 28 [2024-11-09 01:12:30,093 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:12:30,093 INFO L225 Difference]: With dead ends: 48 [2024-11-09 01:12:30,093 INFO L226 Difference]: Without dead ends: 46 [2024-11-09 01:12:30,094 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 212 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=114, Invalid=697, Unknown=1, NotChecked=0, Total=812 [2024-11-09 01:12:30,094 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 4 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-09 01:12:30,094 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 98 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-09 01:12:30,095 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2024-11-09 01:12:30,107 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2024-11-09 01:12:30,108 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.125) internal successors, (36), 34 states have internal predecessors, (36), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 01:12:30,108 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 50 transitions. [2024-11-09 01:12:30,109 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 50 transitions. Word has length 28 [2024-11-09 01:12:30,109 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:12:30,109 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 50 transitions. [2024-11-09 01:12:30,109 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 1.8666666666666667) internal successors, (28), 13 states have internal predecessors, (28), 5 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-09 01:12:30,109 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 50 transitions. [2024-11-09 01:12:30,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2024-11-09 01:12:30,110 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:12:30,110 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:12:30,116 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2024-11-09 01:12:30,311 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:12:30,311 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:12:30,311 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:12:30,312 INFO L85 PathProgramCache]: Analyzing trace with hash -522083118, now seen corresponding path program 3 times [2024-11-09 01:12:30,312 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:12:30,312 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2048213811] [2024-11-09 01:12:30,312 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:12:30,312 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:12:30,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:12:30,932 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 01:12:30,932 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:12:30,932 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2048213811] [2024-11-09 01:12:30,932 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2048213811] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:12:30,932 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2115004124] [2024-11-09 01:12:30,933 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 01:12:30,933 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:12:30,933 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:12:30,934 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:12:30,936 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-09 01:12:31,175 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 01:12:31,175 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:12:31,176 INFO L255 TraceCheckSpWp]: Trace formula consists of 79 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-09 01:12:31,178 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:12:31,560 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 01:12:31,560 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:12:31,844 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2024-11-09 01:12:31,844 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2115004124] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:12:31,844 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1648085859] [2024-11-09 01:12:31,846 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:12:31,846 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:12:31,847 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:12:31,847 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:12:31,847 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:12:32,323 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:12:32,341 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:12:32,343 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:12:33,567 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1196#(and (exists ((|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_38| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_34| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_34| Int) (|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_34| Int)) (not (= (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_34| 4294967296) (mod (+ (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_38| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_34|) |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_34|) 4294967296)))) (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:12:33,567 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:12:33,567 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 01:12:33,568 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 9, 6] total 16 [2024-11-09 01:12:33,568 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [153751090] [2024-11-09 01:12:33,568 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 01:12:33,568 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-09 01:12:33,569 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:12:33,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-09 01:12:33,570 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=695, Unknown=0, NotChecked=0, Total=812 [2024-11-09 01:12:33,570 INFO L87 Difference]: Start difference. First operand 45 states and 50 transitions. Second operand has 16 states, 14 states have (on average 2.5) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 8 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-09 01:12:33,748 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:12:33,748 INFO L93 Difference]: Finished difference Result 60 states and 67 transitions. [2024-11-09 01:12:33,749 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-09 01:12:33,749 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.5) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 8 states have call predecessors, (9), 7 states have call successors, (9) Word has length 31 [2024-11-09 01:12:33,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:12:33,751 INFO L225 Difference]: With dead ends: 60 [2024-11-09 01:12:33,751 INFO L226 Difference]: Without dead ends: 45 [2024-11-09 01:12:33,752 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 71 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 238 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=117, Invalid=695, Unknown=0, NotChecked=0, Total=812 [2024-11-09 01:12:33,753 INFO L432 NwaCegarLoop]: 15 mSDtfsCounter, 8 mSDsluCounter, 78 mSDsCounter, 0 mSdLazyCounter, 62 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 93 SdHoareTripleChecker+Invalid, 62 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 62 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-09 01:12:33,753 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [10 Valid, 93 Invalid, 62 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 62 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-09 01:12:33,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-09 01:12:33,766 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-11-09 01:12:33,766 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 32 states have (on average 1.09375) internal successors, (35), 34 states have internal predecessors, (35), 7 states have call successors, (7), 5 states have call predecessors, (7), 5 states have return successors, (7), 5 states have call predecessors, (7), 7 states have call successors, (7) [2024-11-09 01:12:33,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 49 transitions. [2024-11-09 01:12:33,767 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 49 transitions. Word has length 31 [2024-11-09 01:12:33,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:12:33,767 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 49 transitions. [2024-11-09 01:12:33,768 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.5) internal successors, (35), 14 states have internal predecessors, (35), 8 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (9), 8 states have call predecessors, (9), 7 states have call successors, (9) [2024-11-09 01:12:33,768 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 49 transitions. [2024-11-09 01:12:33,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2024-11-09 01:12:33,769 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:12:33,769 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:12:33,792 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2024-11-09 01:12:33,969 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:12:33,970 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:12:33,970 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:12:33,970 INFO L85 PathProgramCache]: Analyzing trace with hash 1684312781, now seen corresponding path program 4 times [2024-11-09 01:12:33,970 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:12:33,971 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1656458631] [2024-11-09 01:12:33,971 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:12:33,971 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:12:34,004 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:12:34,005 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [659230318] [2024-11-09 01:12:34,005 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2024-11-09 01:12:34,006 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:12:34,006 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:12:34,007 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:12:34,011 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-09 01:12:35,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:12:35,172 INFO L255 TraceCheckSpWp]: Trace formula consists of 83 conjuncts, 33 conjuncts are in the unsatisfiable core [2024-11-09 01:12:35,173 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:13:03,190 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 3 proven. 17 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 01:13:03,191 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:13:13,679 WARN L286 SmtUtils]: Spent 5.36s on a formula simplification that was a NOOP. DAG size: 45 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:13:30,909 WARN L286 SmtUtils]: Spent 8.70s on a formula simplification that was a NOOP. DAG size: 46 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:13:43,896 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:13:55,973 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:14:03,992 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:14:06,003 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse1 (mod |c_ULTIMATE.start_main_~b~0#1| 1073741824)) (.cse0 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296))) (or (< .cse0 (mod |c_ULTIMATE.start_main_~b~0#1| 4294967296)) (not (= (mod (+ (* |c_ULTIMATE.start_main_~b~0#1| 4 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296) (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296))) (< (* .cse1 4) (+ .cse0 1)) (< 4294967294 (mod (+ (* 4294967295 |c_ULTIMATE.start_main_~A~0#1|) (* 2 (mod (+ .cse1 (* 2 .cse1 |c_ULTIMATE.start_main_~q~0#1|)) 2147483648)) 4294967295 |c_ULTIMATE.start_main_~r~0#1| (* .cse1 4294967294)) 4294967296)) (< .cse0 (* 2 (mod |c_ULTIMATE.start_main_~b~0#1| 2147483648))))) is different from true [2024-11-09 01:14:14,028 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:14:26,250 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:14:34,275 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:14:34,306 INFO L134 CoverageAnalysis]: Checked inductivity of 23 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 4 not checked. [2024-11-09 01:14:34,306 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:14:34,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1656458631] [2024-11-09 01:14:34,306 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:14:34,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [659230318] [2024-11-09 01:14:34,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [659230318] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:14:34,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [929398683] [2024-11-09 01:14:34,309 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:14:34,309 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:14:34,309 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:14:34,310 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:14:34,310 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:14:34,721 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:14:34,734 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:14:34,736 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:14:44,306 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1590#(and (<= 1 |#StackHeapBarrier|) (exists ((|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_48| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_48| Int) (|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_52| Int) (|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_48| Int)) (not (= (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_48| 4294967296) (mod (+ (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_52| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_48|) |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_48|) 4294967296)))) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:14:44,306 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:14:44,306 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:14:44,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 24 [2024-11-09 01:14:44,307 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1917307905] [2024-11-09 01:14:44,307 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:14:44,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-09 01:14:44,308 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:14:44,309 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-09 01:14:44,309 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=1125, Unknown=3, NotChecked=68, Total=1332 [2024-11-09 01:14:44,310 INFO L87 Difference]: Start difference. First operand 45 states and 49 transitions. Second operand has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 7 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-09 01:14:46,348 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=true, quantifiers [] [2024-11-09 01:14:48,548 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:14:50,746 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:03,960 WARN L286 SmtUtils]: Spent 11.81s on a formula simplification. DAG size of input: 73 DAG size of output: 71 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:15:06,007 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:08,014 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:10,021 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:16,177 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:24,957 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:27,866 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:30,206 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:33,757 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:52,214 WARN L286 SmtUtils]: Spent 11.96s on a formula simplification that was a NOOP. DAG size: 67 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:15:54,227 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:15:56,233 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:00,159 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:02,171 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:05,678 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:14,334 WARN L286 SmtUtils]: Spent 7.73s on a formula simplification that was a NOOP. DAG size: 44 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:16:16,339 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:17,383 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.04s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:19,386 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:16:21,128 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:16:21,128 INFO L93 Difference]: Finished difference Result 83 states and 93 transitions. [2024-11-09 01:16:21,129 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-09 01:16:21,129 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 7 states have call predecessors, (8), 6 states have call successors, (8) Word has length 33 [2024-11-09 01:16:21,129 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:16:21,130 INFO L225 Difference]: With dead ends: 83 [2024-11-09 01:16:21,130 INFO L226 Difference]: Without dead ends: 81 [2024-11-09 01:16:21,131 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 113 GetRequests, 60 SyntacticMatches, 2 SemanticMatches, 51 ConstructedPredicates, 1 IntricatePredicates, 1 DeprecatedPredicates, 614 ImplicationChecksByTransitivity, 86.5s TimeCoverageRelationStatistics Valid=311, Invalid=2338, Unknown=7, NotChecked=100, Total=2756 [2024-11-09 01:16:21,132 INFO L432 NwaCegarLoop]: 13 mSDtfsCounter, 44 mSDsluCounter, 195 mSDsCounter, 0 mSdLazyCounter, 300 mSolverCounterSat, 23 mSolverCounterUnsat, 17 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 40.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 407 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 300 IncrementalHoareTripleChecker+Invalid, 17 IncrementalHoareTripleChecker+Unknown, 67 IncrementalHoareTripleChecker+Unchecked, 40.3s IncrementalHoareTripleChecker+Time [2024-11-09 01:16:21,132 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [45 Valid, 208 Invalid, 407 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 300 Invalid, 17 Unknown, 67 Unchecked, 40.3s Time] [2024-11-09 01:16:21,133 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2024-11-09 01:16:21,163 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 74. [2024-11-09 01:16:21,163 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 53 states have (on average 1.0943396226415094) internal successors, (58), 57 states have internal predecessors, (58), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (12), 8 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-09 01:16:21,164 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 82 transitions. [2024-11-09 01:16:21,165 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 82 transitions. Word has length 33 [2024-11-09 01:16:21,165 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:16:21,165 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 82 transitions. [2024-11-09 01:16:21,166 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 21 states have (on average 1.8095238095238095) internal successors, (38), 20 states have internal predecessors, (38), 8 states have call successors, (9), 2 states have call predecessors, (9), 3 states have return successors, (8), 7 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-09 01:16:21,166 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 82 transitions. [2024-11-09 01:16:21,167 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-09 01:16:21,167 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:16:21,167 INFO L215 NwaCegarLoop]: trace histogram [4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:16:21,173 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2024-11-09 01:16:21,367 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:21,368 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:16:21,368 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:16:21,368 INFO L85 PathProgramCache]: Analyzing trace with hash -896079493, now seen corresponding path program 5 times [2024-11-09 01:16:21,368 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:16:21,368 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1053304025] [2024-11-09 01:16:21,369 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:16:21,369 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:16:21,663 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 01:16:23,933 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 12 proven. 16 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-09 01:16:23,933 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:16:23,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1053304025] [2024-11-09 01:16:23,934 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1053304025] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-09 01:16:23,934 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [467950692] [2024-11-09 01:16:23,934 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-09 01:16:23,935 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:23,935 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:16:23,937 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:16:23,939 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-09 01:16:24,986 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-09 01:16:24,986 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:16:24,987 INFO L255 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 28 conjuncts are in the unsatisfiable core [2024-11-09 01:16:24,989 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:16:26,473 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 14 trivial. 0 not checked. [2024-11-09 01:16:26,474 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:16:30,379 INFO L134 CoverageAnalysis]: Checked inductivity of 41 backedges. 15 proven. 13 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-09 01:16:30,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [467950692] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:16:30,380 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [68060345] [2024-11-09 01:16:30,382 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:16:30,382 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:16:30,382 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:16:30,382 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:16:30,382 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:16:30,695 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:16:30,713 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:16:30,715 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:16:32,810 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2142#(and (exists ((|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_57| Int) (|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_67| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_57| Int) (|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_57| Int)) (not (= (mod (+ (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_67| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_57|) |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_57|) 4294967296) (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_57| 4294967296)))) (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0))' at error location [2024-11-09 01:16:32,810 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:16:32,810 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-09 01:16:32,810 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 11, 10] total 24 [2024-11-09 01:16:32,810 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [336122547] [2024-11-09 01:16:32,810 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-09 01:16:32,811 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2024-11-09 01:16:32,811 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:16:32,812 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2024-11-09 01:16:32,812 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=172, Invalid=1159, Unknown=1, NotChecked=0, Total=1332 [2024-11-09 01:16:32,813 INFO L87 Difference]: Start difference. First operand 74 states and 82 transitions. Second operand has 24 states, 23 states have (on average 2.130434782608696) internal successors, (49), 21 states have internal predecessors, (49), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-09 01:16:35,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-09 01:16:35,653 INFO L93 Difference]: Finished difference Result 87 states and 96 transitions. [2024-11-09 01:16:35,654 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-09 01:16:35,654 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 23 states have (on average 2.130434782608696) internal successors, (49), 21 states have internal predecessors, (49), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) Word has length 40 [2024-11-09 01:16:35,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-09 01:16:35,655 INFO L225 Difference]: With dead ends: 87 [2024-11-09 01:16:35,656 INFO L226 Difference]: Without dead ends: 65 [2024-11-09 01:16:35,657 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 473 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=195, Invalid=1286, Unknown=1, NotChecked=0, Total=1482 [2024-11-09 01:16:35,657 INFO L432 NwaCegarLoop]: 19 mSDtfsCounter, 18 mSDsluCounter, 141 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 160 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2024-11-09 01:16:35,658 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 160 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 2.4s Time] [2024-11-09 01:16:35,659 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 65 states. [2024-11-09 01:16:35,697 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 65 to 65. [2024-11-09 01:16:35,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 65 states, 47 states have (on average 1.0851063829787233) internal successors, (51), 50 states have internal predecessors, (51), 10 states have call successors, (10), 7 states have call predecessors, (10), 7 states have return successors, (10), 7 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-09 01:16:35,698 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 65 states to 65 states and 71 transitions. [2024-11-09 01:16:35,698 INFO L78 Accepts]: Start accepts. Automaton has 65 states and 71 transitions. Word has length 40 [2024-11-09 01:16:35,699 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-09 01:16:35,699 INFO L471 AbstractCegarLoop]: Abstraction has 65 states and 71 transitions. [2024-11-09 01:16:35,699 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 23 states have (on average 2.130434782608696) internal successors, (49), 21 states have internal predecessors, (49), 13 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-09 01:16:35,699 INFO L276 IsEmpty]: Start isEmpty. Operand 65 states and 71 transitions. [2024-11-09 01:16:35,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2024-11-09 01:16:35,701 INFO L207 NwaCegarLoop]: Found error trace [2024-11-09 01:16:35,701 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 01:16:35,709 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-09 01:16:35,902 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:35,903 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-09 01:16:35,903 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 01:16:35,903 INFO L85 PathProgramCache]: Analyzing trace with hash 2073209918, now seen corresponding path program 6 times [2024-11-09 01:16:35,903 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-09 01:16:35,904 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [405920266] [2024-11-09 01:16:35,904 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 01:16:35,904 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 01:16:36,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-09 01:16:36,010 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [342300914] [2024-11-09 01:16:36,011 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-09 01:16:36,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-09 01:16:36,011 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 [2024-11-09 01:16:36,013 INFO L229 MonitoredProcess]: Starting monitored process 8 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-09 01:16:36,017 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_d531c11f-4cc5-4c7c-9ed4-973821dc3aec/bin/utaipan-verify-YMUCfTKeje/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-09 01:16:38,568 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-09 01:16:38,569 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-09 01:16:38,571 INFO L255 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 44 conjuncts are in the unsatisfiable core [2024-11-09 01:16:38,573 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 01:16:41,629 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 41 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-09 01:16:41,629 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-09 01:17:20,771 WARN L286 SmtUtils]: Spent 5.04s on a formula simplification that was a NOOP. DAG size: 41 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:17:54,176 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:04,249 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:12,271 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:24,316 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:26,544 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse1 (mod |c_ULTIMATE.start_main_~b~0#1| 1073741824))) (let ((.cse2 (mod |c_ULTIMATE.start_main_~B~0#1| 4294967296)) (.cse0 (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296)) (.cse3 (* .cse1 4)) (.cse4 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296))) (or (= .cse0 (mod (+ |c_ULTIMATE.start_main_~r~0#1| (* .cse1 4 |c_ULTIMATE.start_main_~q~0#1|)) 4294967296)) (= .cse2 (* 2 .cse1)) (= .cse3 .cse2) (not (= (mod (+ (* |c_ULTIMATE.start_main_~b~0#1| 4 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296) .cse0)) (< .cse3 (+ .cse4 1)) (< .cse4 (* 2 (mod |c_ULTIMATE.start_main_~b~0#1| 2147483648)))))) is different from true [2024-11-09 01:18:34,575 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:44,734 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:18:52,756 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:04,820 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:12,849 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:20,869 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:30,919 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:40,957 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:42,984 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse1 (mod |c_ULTIMATE.start_main_~b~0#1| 536870912))) (let ((.cse2 (* 8 .cse1)) (.cse0 (mod |c_ULTIMATE.start_main_~B~0#1| 4294967296)) (.cse3 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296)) (.cse4 (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296))) (or (= .cse0 (* 4 .cse1)) (< .cse2 (+ .cse3 1)) (not (= .cse4 (mod (+ (* 8 |c_ULTIMATE.start_main_~b~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296))) (= .cse2 .cse0) (< .cse3 (* (mod |c_ULTIMATE.start_main_~b~0#1| 1073741824) 4)) (= .cse4 (mod (+ (* 8 .cse1 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296))))) is different from true [2024-11-09 01:19:51,013 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:19:59,040 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:09,081 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:19,121 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:29,209 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:41,241 WARN L286 SmtUtils]: Spent 8.01s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:49,272 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:57,302 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:20:59,312 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse0 (mod |c_ULTIMATE.start_main_~b~0#1| 268435456))) (let ((.cse4 (mod |c_ULTIMATE.start_main_~B~0#1| 4294967296)) (.cse3 (* .cse0 16)) (.cse2 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296)) (.cse1 (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296))) (or (= (mod (+ |c_ULTIMATE.start_main_~r~0#1| (* .cse0 16 |c_ULTIMATE.start_main_~q~0#1|)) 4294967296) .cse1) (< .cse2 (* 8 (mod |c_ULTIMATE.start_main_~b~0#1| 536870912))) (= .cse3 .cse4) (= .cse4 (* .cse0 8)) (< .cse3 (+ .cse2 1)) (not (= .cse1 (mod (+ |c_ULTIMATE.start_main_~r~0#1| (* 16 |c_ULTIMATE.start_main_~b~0#1| |c_ULTIMATE.start_main_~q~0#1|)) 4294967296)))))) is different from true [2024-11-09 01:21:09,351 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:21:21,426 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:21:29,446 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:21:37,473 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:21:45,503 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:21:55,537 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:03,565 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:11,589 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:21,638 WARN L286 SmtUtils]: Spent 8.04s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:23,646 WARN L873 $PredicateComparison]: unable to prove that (let ((.cse0 (mod |c_ULTIMATE.start_main_~b~0#1| 134217728))) (let ((.cse2 (mod |c_ULTIMATE.start_main_~r~0#1| 4294967296)) (.cse1 (mod |c_ULTIMATE.start_main_~A~0#1| 4294967296)) (.cse3 (* .cse0 32)) (.cse4 (mod |c_ULTIMATE.start_main_~B~0#1| 4294967296))) (or (= (mod (+ (* .cse0 32 |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~r~0#1|) 4294967296) .cse1) (< .cse2 (mod |c_ULTIMATE.start_main_~b~0#1| 4294967296)) (< .cse3 (+ .cse2 1)) (< .cse2 (* (mod |c_ULTIMATE.start_main_~b~0#1| 268435456) 16)) (not (= (mod (+ |c_ULTIMATE.start_main_~r~0#1| (* 32 |c_ULTIMATE.start_main_~b~0#1| |c_ULTIMATE.start_main_~q~0#1|)) 4294967296) .cse1)) (= .cse4 (* .cse0 16)) (= .cse3 .cse4)))) is different from true [2024-11-09 01:22:31,702 WARN L286 SmtUtils]: Spent 8.05s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:42,102 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:50,125 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 11 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:22:58,143 WARN L286 SmtUtils]: Spent 8.02s on a formula simplification that was a NOOP. DAG size: 6 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:23:08,193 WARN L286 SmtUtils]: Spent 8.03s on a formula simplification that was a NOOP. DAG size: 9 (called from [L 728] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.simplify) [2024-11-09 01:23:08,227 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 3 trivial. 28 not checked. [2024-11-09 01:23:08,228 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-09 01:23:08,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [405920266] [2024-11-09 01:23:08,228 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-09 01:23:08,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [342300914] [2024-11-09 01:23:08,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [342300914] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-09 01:23:08,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1995112838] [2024-11-09 01:23:08,230 INFO L159 IcfgInterpreter]: Started Sifa with 17 locations of interest [2024-11-09 01:23:08,231 INFO L166 IcfgInterpreter]: Building call graph [2024-11-09 01:23:08,231 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-09 01:23:08,231 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-09 01:23:08,231 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-09 01:23:08,659 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 24 for LOIs [2024-11-09 01:23:08,674 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 3 for LOIs [2024-11-09 01:23:08,675 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-09 01:23:23,110 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2657#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (exists ((|v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_71| Int) (|v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_71| Int) (|v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_81| Int) (|v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_71| Int)) (not (= (mod |v_ULTIMATE.start_main_~A~0#1_BEFORE_CALL_71| 4294967296) (mod (+ |v_ULTIMATE.start_main_~r~0#1_BEFORE_CALL_71| (* |v_ULTIMATE.start_main_~b~0#1_BEFORE_CALL_81| |v_ULTIMATE.start_main_~q~0#1_BEFORE_CALL_71|)) 4294967296)))))' at error location [2024-11-09 01:23:23,110 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-09 01:23:23,110 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-09 01:23:23,110 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 30 [2024-11-09 01:23:23,110 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1215664049] [2024-11-09 01:23:23,110 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-09 01:23:23,111 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2024-11-09 01:23:23,111 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-09 01:23:23,113 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2024-11-09 01:23:23,114 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=190, Invalid=1296, Unknown=12, NotChecked=308, Total=1806 [2024-11-09 01:23:23,115 INFO L87 Difference]: Start difference. First operand 65 states and 71 transitions. Second operand has 30 states, 28 states have (on average 1.8571428571428572) internal successors, (52), 26 states have internal predecessors, (52), 8 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 7 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-09 01:23:30,864 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:23:32,992 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:23:51,688 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:24:26,726 WARN L286 SmtUtils]: Spent 31.46s on a formula simplification that was a NOOP. DAG size: 68 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-09 01:24:28,847 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2024-11-09 01:24:30,855 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []