./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/array-fpi/brs1.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 53f42b1a Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/config/TaipanReach.xml -i ../../sv-benchmarks/c/array-fpi/brs1.c -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P --witnessprinter.witness.filename witness.graphml --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 1719c559f228c1029533750a96ea896ed07efcc9b139440443e471db2c10d1e7 --- Real Ultimate output --- This is Ultimate 0.2.1-dev-53f42b1 [2021-11-21 01:10:56,441 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-11-21 01:10:56,444 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-11-21 01:10:56,510 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-11-21 01:10:56,511 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-11-21 01:10:56,513 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-11-21 01:10:56,516 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-11-21 01:10:56,519 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-11-21 01:10:56,522 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-11-21 01:10:56,524 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-11-21 01:10:56,525 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-11-21 01:10:56,528 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-11-21 01:10:56,528 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-11-21 01:10:56,530 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-11-21 01:10:56,533 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-11-21 01:10:56,535 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-11-21 01:10:56,537 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-11-21 01:10:56,538 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-11-21 01:10:56,542 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-11-21 01:10:56,546 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-11-21 01:10:56,549 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-11-21 01:10:56,551 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-11-21 01:10:56,554 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-11-21 01:10:56,555 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-11-21 01:10:56,560 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-11-21 01:10:56,561 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-11-21 01:10:56,562 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-11-21 01:10:56,563 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-11-21 01:10:56,564 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-11-21 01:10:56,565 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-11-21 01:10:56,566 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-11-21 01:10:56,567 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-11-21 01:10:56,569 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-11-21 01:10:56,570 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-11-21 01:10:56,572 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-11-21 01:10:56,572 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-11-21 01:10:56,573 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-11-21 01:10:56,574 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-11-21 01:10:56,574 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-11-21 01:10:56,576 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-11-21 01:10:56,577 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-11-21 01:10:56,578 INFO L101 SettingsManager]: Beginning loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/config/svcomp-Reach-32bit-Taipan_Default.epf [2021-11-21 01:10:56,611 INFO L113 SettingsManager]: Loading preferences was successful [2021-11-21 01:10:56,612 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-11-21 01:10:56,612 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-11-21 01:10:56,613 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-11-21 01:10:56,614 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-11-21 01:10:56,614 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-11-21 01:10:56,615 INFO L138 SettingsManager]: * User list type=DISABLED [2021-11-21 01:10:56,615 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2021-11-21 01:10:56,616 INFO L138 SettingsManager]: * Explicit value domain=true [2021-11-21 01:10:56,616 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2021-11-21 01:10:56,617 INFO L138 SettingsManager]: * Octagon Domain=false [2021-11-21 01:10:56,617 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2021-11-21 01:10:56,618 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2021-11-21 01:10:56,618 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2021-11-21 01:10:56,619 INFO L138 SettingsManager]: * Interval Domain=false [2021-11-21 01:10:56,619 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2021-11-21 01:10:56,620 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2021-11-21 01:10:56,620 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2021-11-21 01:10:56,621 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-11-21 01:10:56,622 INFO L138 SettingsManager]: * sizeof long=4 [2021-11-21 01:10:56,622 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-11-21 01:10:56,623 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-11-21 01:10:56,623 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-11-21 01:10:56,624 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-11-21 01:10:56,624 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-11-21 01:10:56,625 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-11-21 01:10:56,625 INFO L138 SettingsManager]: * sizeof long double=12 [2021-11-21 01:10:56,626 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-11-21 01:10:56,626 INFO L138 SettingsManager]: * Use constant arrays=true [2021-11-21 01:10:56,626 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-11-21 01:10:56,627 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-11-21 01:10:56,627 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-11-21 01:10:56,627 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-21 01:10:56,628 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-11-21 01:10:56,628 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-11-21 01:10:56,628 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-11-21 01:10:56,629 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2021-11-21 01:10:56,629 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-11-21 01:10:56,629 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-11-21 01:10:56,630 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-11-21 01:10:56,630 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2021-11-21 01:10:56,630 INFO L138 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_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/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_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness.graphml 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 -> 1719c559f228c1029533750a96ea896ed07efcc9b139440443e471db2c10d1e7 [2021-11-21 01:10:57,028 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-11-21 01:10:57,053 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-11-21 01:10:57,057 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-11-21 01:10:57,058 INFO L271 PluginConnector]: Initializing CDTParser... [2021-11-21 01:10:57,060 INFO L275 PluginConnector]: CDTParser initialized [2021-11-21 01:10:57,061 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/../../sv-benchmarks/c/array-fpi/brs1.c [2021-11-21 01:10:57,140 INFO L220 CDTParser]: Created temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/data/77f411c59/f050aec4aadc4244989f78b55593c333/FLAGfaee418ae [2021-11-21 01:10:57,782 INFO L306 CDTParser]: Found 1 translation units. [2021-11-21 01:10:57,782 INFO L160 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/sv-benchmarks/c/array-fpi/brs1.c [2021-11-21 01:10:57,789 INFO L349 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/data/77f411c59/f050aec4aadc4244989f78b55593c333/FLAGfaee418ae [2021-11-21 01:10:58,112 INFO L357 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/data/77f411c59/f050aec4aadc4244989f78b55593c333 [2021-11-21 01:10:58,116 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-11-21 01:10:58,117 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-11-21 01:10:58,137 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-11-21 01:10:58,137 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-11-21 01:10:58,142 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-11-21 01:10:58,143 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,145 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6dd80d07 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58, skipping insertion in model container [2021-11-21 01:10:58,148 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,159 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-11-21 01:10:58,177 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-11-21 01:10:58,381 WARN L230 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_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/sv-benchmarks/c/array-fpi/brs1.c[587,600] [2021-11-21 01:10:58,413 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-21 01:10:58,424 INFO L203 MainTranslator]: Completed pre-run [2021-11-21 01:10:58,436 WARN L230 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_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/sv-benchmarks/c/array-fpi/brs1.c[587,600] [2021-11-21 01:10:58,445 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-11-21 01:10:58,462 INFO L208 MainTranslator]: Completed translation [2021-11-21 01:10:58,463 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58 WrapperNode [2021-11-21 01:10:58,463 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-11-21 01:10:58,465 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-11-21 01:10:58,465 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-11-21 01:10:58,466 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-11-21 01:10:58,475 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,484 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,508 INFO L137 Inliner]: procedures = 17, calls = 27, calls flagged for inlining = 4, calls inlined = 4, statements flattened = 73 [2021-11-21 01:10:58,509 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-11-21 01:10:58,510 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-11-21 01:10:58,510 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-11-21 01:10:58,511 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-11-21 01:10:58,521 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,522 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,525 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,525 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,533 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,545 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,546 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,550 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-11-21 01:10:58,551 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-11-21 01:10:58,551 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-11-21 01:10:58,552 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-11-21 01:10:58,553 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (1/1) ... [2021-11-21 01:10:58,566 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-11-21 01:10:58,583 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:10:58,606 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-11-21 01:10:58,628 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-11-21 01:10:58,672 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-11-21 01:10:58,673 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-11-21 01:10:58,673 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-11-21 01:10:58,673 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2021-11-21 01:10:58,674 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-11-21 01:10:58,674 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-11-21 01:10:58,674 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-11-21 01:10:58,675 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2021-11-21 01:10:58,675 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-11-21 01:10:58,774 INFO L236 CfgBuilder]: Building ICFG [2021-11-21 01:10:58,777 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-11-21 01:10:58,990 INFO L277 CfgBuilder]: Performing block encoding [2021-11-21 01:10:59,053 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-11-21 01:10:59,053 INFO L301 CfgBuilder]: Removed 2 assume(true) statements. [2021-11-21 01:10:59,059 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.11 01:10:59 BoogieIcfgContainer [2021-11-21 01:10:59,059 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-11-21 01:10:59,061 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-11-21 01:10:59,061 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-11-21 01:10:59,069 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-11-21 01:10:59,069 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.11 01:10:58" (1/3) ... [2021-11-21 01:10:59,071 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12cd7126 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.11 01:10:59, skipping insertion in model container [2021-11-21 01:10:59,071 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.11 01:10:58" (2/3) ... [2021-11-21 01:10:59,072 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12cd7126 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.11 01:10:59, skipping insertion in model container [2021-11-21 01:10:59,072 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.11 01:10:59" (3/3) ... [2021-11-21 01:10:59,074 INFO L111 eAbstractionObserver]: Analyzing ICFG brs1.c [2021-11-21 01:10:59,084 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-11-21 01:10:59,084 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-11-21 01:10:59,142 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-11-21 01:10:59,151 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2021-11-21 01:10:59,152 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-11-21 01:10:59,169 INFO L276 IsEmpty]: Start isEmpty. Operand has 10 states, 8 states have (on average 1.625) internal successors, (13), 9 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,176 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 7 [2021-11-21 01:10:59,176 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:10:59,177 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1] [2021-11-21 01:10:59,178 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:10:59,185 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:10:59,185 INFO L85 PathProgramCache]: Analyzing trace with hash -1448994786, now seen corresponding path program 1 times [2021-11-21 01:10:59,197 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:10:59,198 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1119779384] [2021-11-21 01:10:59,198 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:10:59,200 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:10:59,327 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:10:59,453 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:10:59,454 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:10:59,455 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1119779384] [2021-11-21 01:10:59,456 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1119779384] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-21 01:10:59,456 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-21 01:10:59,457 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-11-21 01:10:59,459 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [923068932] [2021-11-21 01:10:59,460 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-21 01:10:59,466 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2021-11-21 01:10:59,467 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:10:59,514 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-11-21 01:10:59,515 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-21 01:10:59,518 INFO L87 Difference]: Start difference. First operand has 10 states, 8 states have (on average 1.625) internal successors, (13), 9 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,569 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:10:59,569 INFO L93 Difference]: Finished difference Result 18 states and 23 transitions. [2021-11-21 01:10:59,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-11-21 01:10:59,573 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 6 [2021-11-21 01:10:59,574 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:10:59,583 INFO L225 Difference]: With dead ends: 18 [2021-11-21 01:10:59,584 INFO L226 Difference]: Without dead ends: 8 [2021-11-21 01:10:59,587 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-11-21 01:10:59,592 INFO L933 BasicCegarLoop]: 5 mSDtfsCounter, 0 mSDsluCounter, 5 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 9 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-21 01:10:59,594 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 9 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-21 01:10:59,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 8 states. [2021-11-21 01:10:59,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 8 to 8. [2021-11-21 01:10:59,667 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 1.2857142857142858) internal successors, (9), 7 states have internal predecessors, (9), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,668 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 9 transitions. [2021-11-21 01:10:59,669 INFO L78 Accepts]: Start accepts. Automaton has 8 states and 9 transitions. Word has length 6 [2021-11-21 01:10:59,670 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:10:59,670 INFO L470 AbstractCegarLoop]: Abstraction has 8 states and 9 transitions. [2021-11-21 01:10:59,670 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.0) internal successors, (6), 3 states have internal predecessors, (6), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,671 INFO L276 IsEmpty]: Start isEmpty. Operand 8 states and 9 transitions. [2021-11-21 01:10:59,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 8 [2021-11-21 01:10:59,671 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:10:59,672 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2021-11-21 01:10:59,672 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-11-21 01:10:59,673 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:10:59,674 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:10:59,674 INFO L85 PathProgramCache]: Analyzing trace with hash -1973441861, now seen corresponding path program 1 times [2021-11-21 01:10:59,674 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:10:59,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1656127942] [2021-11-21 01:10:59,675 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:10:59,676 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:10:59,730 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:10:59,800 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:10:59,801 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:10:59,801 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1656127942] [2021-11-21 01:10:59,801 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1656127942] provided 1 perfect and 0 imperfect interpolant sequences [2021-11-21 01:10:59,802 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-11-21 01:10:59,802 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-11-21 01:10:59,802 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1755812475] [2021-11-21 01:10:59,803 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-11-21 01:10:59,804 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-11-21 01:10:59,805 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:10:59,807 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-11-21 01:10:59,810 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-11-21 01:10:59,811 INFO L87 Difference]: Start difference. First operand 8 states and 9 transitions. Second operand has 4 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,863 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:10:59,866 INFO L93 Difference]: Finished difference Result 12 states and 13 transitions. [2021-11-21 01:10:59,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-11-21 01:10:59,867 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 7 [2021-11-21 01:10:59,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:10:59,868 INFO L225 Difference]: With dead ends: 12 [2021-11-21 01:10:59,868 INFO L226 Difference]: Without dead ends: 9 [2021-11-21 01:10:59,869 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-11-21 01:10:59,872 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 5 mSDsluCounter, 2 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 4 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-21 01:10:59,876 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 4 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-21 01:10:59,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 9 states. [2021-11-21 01:10:59,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 9 to 9. [2021-11-21 01:10:59,886 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.25) internal successors, (10), 8 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,887 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 10 transitions. [2021-11-21 01:10:59,887 INFO L78 Accepts]: Start accepts. Automaton has 9 states and 10 transitions. Word has length 7 [2021-11-21 01:10:59,889 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:10:59,889 INFO L470 AbstractCegarLoop]: Abstraction has 9 states and 10 transitions. [2021-11-21 01:10:59,889 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:10:59,890 INFO L276 IsEmpty]: Start isEmpty. Operand 9 states and 10 transitions. [2021-11-21 01:10:59,892 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2021-11-21 01:10:59,893 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:10:59,893 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2021-11-21 01:10:59,893 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-11-21 01:10:59,894 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:10:59,895 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:10:59,895 INFO L85 PathProgramCache]: Analyzing trace with hash -1046873979, now seen corresponding path program 1 times [2021-11-21 01:10:59,896 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:10:59,896 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1406920012] [2021-11-21 01:10:59,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:10:59,897 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:10:59,954 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:00,055 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:11:00,055 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:00,056 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1406920012] [2021-11-21 01:11:00,056 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1406920012] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:00,056 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1786282552] [2021-11-21 01:11:00,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:00,057 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:00,057 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:00,060 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:00,067 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-11-21 01:11:00,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:00,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 8 conjunts are in the unsatisfiable core [2021-11-21 01:11:00,173 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:00,324 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:00,470 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 28 [2021-11-21 01:11:00,541 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:11:00,541 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-21 01:11:00,803 INFO L354 Elim1Store]: treesize reduction 48, result has 64.2 percent of original size [2021-11-21 01:11:00,804 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 64 treesize of output 119 [2021-11-21 01:11:01,186 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:01,187 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 59 treesize of output 58 [2021-11-21 01:11:01,246 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:01,247 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 70 treesize of output 69 [2021-11-21 01:11:01,374 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:11:01,375 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1786282552] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-21 01:11:01,376 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [967185886] [2021-11-21 01:11:01,416 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2021-11-21 01:11:01,419 INFO L166 IcfgInterpreter]: Building call graph [2021-11-21 01:11:01,426 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-21 01:11:01,433 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-21 01:11:01,434 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-21 01:11:01,687 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,692 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,769 INFO L354 Elim1Store]: treesize reduction 62, result has 35.4 percent of original size [2021-11-21 01:11:01,771 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 55 [2021-11-21 01:11:01,863 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,882 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,883 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,886 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:01,992 INFO L354 Elim1Store]: treesize reduction 94, result has 27.7 percent of original size [2021-11-21 01:11:01,993 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 40 treesize of output 69 [2021-11-21 01:11:02,394 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,402 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 24 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 103 [2021-11-21 01:11:02,778 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,780 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,782 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,784 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,786 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,787 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,792 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,794 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,796 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,799 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,800 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:02,858 INFO L354 Elim1Store]: treesize reduction 153, result has 12.6 percent of original size [2021-11-21 01:11:02,859 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 32 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 12 case distinctions, treesize of input 373 treesize of output 363 [2021-11-21 01:11:03,481 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:03,640 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:03,822 INFO L354 Elim1Store]: treesize reduction 51, result has 58.2 percent of original size [2021-11-21 01:11:03,822 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 73 treesize of output 124 [2021-11-21 01:11:04,157 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:04,163 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:04,163 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 15 [2021-11-21 01:11:04,233 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:04,352 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 11 [2021-11-21 01:11:04,403 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:04,408 INFO L354 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2021-11-21 01:11:04,416 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 61 treesize of output 40 [2021-11-21 01:11:04,523 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 28 treesize of output 20 [2021-11-21 01:11:04,553 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 5 [2021-11-21 01:11:04,730 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:04,734 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:04,739 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2021-11-21 01:11:04,753 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:05,038 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-21 01:11:05,326 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-21 01:11:05,327 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-21 01:11:05,327 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2021-11-21 01:11:05,327 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1793434821] [2021-11-21 01:11:05,327 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-21 01:11:05,328 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-11-21 01:11:05,328 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:11:05,329 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-11-21 01:11:05,330 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2021-11-21 01:11:05,330 INFO L87 Difference]: Start difference. First operand 9 states and 10 transitions. Second operand has 10 states, 10 states have (on average 1.5) internal successors, (15), 10 states have internal predecessors, (15), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:05,399 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:11:05,399 INFO L93 Difference]: Finished difference Result 13 states and 14 transitions. [2021-11-21 01:11:05,400 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-11-21 01:11:05,400 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.5) internal successors, (15), 10 states have internal predecessors, (15), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2021-11-21 01:11:05,401 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:11:05,401 INFO L225 Difference]: With dead ends: 13 [2021-11-21 01:11:05,401 INFO L226 Difference]: Without dead ends: 10 [2021-11-21 01:11:05,402 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=48, Invalid=162, Unknown=0, NotChecked=0, Total=210 [2021-11-21 01:11:05,403 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 6 mSDsluCounter, 14 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 12 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-21 01:11:05,404 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 12 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-11-21 01:11:05,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 10 states. [2021-11-21 01:11:05,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 10 to 10. [2021-11-21 01:11:05,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 10 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 9 states have internal predecessors, (11), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:05,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 10 states to 10 states and 11 transitions. [2021-11-21 01:11:05,409 INFO L78 Accepts]: Start accepts. Automaton has 10 states and 11 transitions. Word has length 8 [2021-11-21 01:11:05,410 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:11:05,410 INFO L470 AbstractCegarLoop]: Abstraction has 10 states and 11 transitions. [2021-11-21 01:11:05,410 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.5) internal successors, (15), 10 states have internal predecessors, (15), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:05,410 INFO L276 IsEmpty]: Start isEmpty. Operand 10 states and 11 transitions. [2021-11-21 01:11:05,411 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 10 [2021-11-21 01:11:05,411 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:11:05,412 INFO L514 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2021-11-21 01:11:05,464 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-11-21 01:11:05,632 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:05,633 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:11:05,634 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:11:05,634 INFO L85 PathProgramCache]: Analyzing trace with hash 1906926587, now seen corresponding path program 2 times [2021-11-21 01:11:05,634 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:11:05,634 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2128426992] [2021-11-21 01:11:05,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:05,635 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:11:05,667 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:05,730 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:05,730 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:05,730 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2128426992] [2021-11-21 01:11:05,730 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2128426992] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:05,731 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2117748745] [2021-11-21 01:11:05,731 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-21 01:11:05,731 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:05,731 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:05,734 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:05,756 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-11-21 01:11:05,801 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2021-11-21 01:11:05,802 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-21 01:11:05,803 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 6 conjunts are in the unsatisfiable core [2021-11-21 01:11:05,804 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:05,872 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:05,872 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-21 01:11:05,915 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:05,916 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2117748745] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-21 01:11:05,916 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [199444667] [2021-11-21 01:11:05,919 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2021-11-21 01:11:05,920 INFO L166 IcfgInterpreter]: Building call graph [2021-11-21 01:11:05,920 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-21 01:11:05,920 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-21 01:11:05,920 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-21 01:11:06,115 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,120 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,187 INFO L354 Elim1Store]: treesize reduction 62, result has 35.4 percent of original size [2021-11-21 01:11:06,188 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 55 [2021-11-21 01:11:06,322 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,330 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,333 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,336 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,420 INFO L354 Elim1Store]: treesize reduction 94, result has 27.7 percent of original size [2021-11-21 01:11:06,421 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 40 treesize of output 69 [2021-11-21 01:11:06,593 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 25 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 0 case distinctions, treesize of input 75 treesize of output 98 [2021-11-21 01:11:06,958 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,961 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,963 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,965 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,967 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:06,969 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:07,038 INFO L354 Elim1Store]: treesize reduction 138, result has 20.2 percent of original size [2021-11-21 01:11:07,039 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 26 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 13 case distinctions, treesize of input 371 treesize of output 367 [2021-11-21 01:11:07,683 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:07,834 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:07,990 INFO L354 Elim1Store]: treesize reduction 51, result has 58.2 percent of original size [2021-11-21 01:11:07,992 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 76 treesize of output 127 [2021-11-21 01:11:08,377 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:08,382 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:08,383 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 29 [2021-11-21 01:11:08,522 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:08,530 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:08,531 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 85 treesize of output 72 [2021-11-21 01:11:08,733 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:08,737 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:08,738 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2021-11-21 01:11:08,749 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:09,039 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-21 01:11:09,300 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-21 01:11:09,300 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-21 01:11:09,300 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6, 6] total 10 [2021-11-21 01:11:09,301 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736848096] [2021-11-21 01:11:09,301 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-21 01:11:09,301 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-11-21 01:11:09,302 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:11:09,302 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-11-21 01:11:09,302 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2021-11-21 01:11:09,303 INFO L87 Difference]: Start difference. First operand 10 states and 11 transitions. Second operand has 10 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:09,374 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:11:09,374 INFO L93 Difference]: Finished difference Result 17 states and 19 transitions. [2021-11-21 01:11:09,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-11-21 01:11:09,376 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 9 [2021-11-21 01:11:09,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:11:09,376 INFO L225 Difference]: With dead ends: 17 [2021-11-21 01:11:09,376 INFO L226 Difference]: Without dead ends: 11 [2021-11-21 01:11:09,377 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2021-11-21 01:11:09,377 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 2 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 2 SdHoareTripleChecker+Valid, 10 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-21 01:11:09,378 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [2 Valid, 10 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-21 01:11:09,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 11 states. [2021-11-21 01:11:09,380 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 11 to 11. [2021-11-21 01:11:09,380 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 11 states, 10 states have (on average 1.2) internal successors, (12), 10 states have internal predecessors, (12), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:09,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 11 states to 11 states and 12 transitions. [2021-11-21 01:11:09,381 INFO L78 Accepts]: Start accepts. Automaton has 11 states and 12 transitions. Word has length 9 [2021-11-21 01:11:09,381 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:11:09,381 INFO L470 AbstractCegarLoop]: Abstraction has 11 states and 12 transitions. [2021-11-21 01:11:09,381 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 1.6) internal successors, (16), 10 states have internal predecessors, (16), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:09,381 INFO L276 IsEmpty]: Start isEmpty. Operand 11 states and 12 transitions. [2021-11-21 01:11:09,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2021-11-21 01:11:09,381 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:11:09,382 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1] [2021-11-21 01:11:09,417 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2021-11-21 01:11:09,582 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:09,583 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:11:09,583 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:11:09,583 INFO L85 PathProgramCache]: Analyzing trace with hash -1099829186, now seen corresponding path program 3 times [2021-11-21 01:11:09,583 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:11:09,584 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1447684760] [2021-11-21 01:11:09,584 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:09,584 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:11:09,710 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:10,039 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:10,040 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:10,040 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1447684760] [2021-11-21 01:11:10,040 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1447684760] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:10,040 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [442536096] [2021-11-21 01:11:10,040 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-21 01:11:10,040 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:10,041 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:10,048 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:10,072 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-11-21 01:11:10,098 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-21 01:11:10,098 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-21 01:11:10,099 INFO L263 TraceCheckSpWp]: Trace formula consists of 35 conjuncts, 17 conjunts are in the unsatisfiable core [2021-11-21 01:11:10,101 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:10,119 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 20 [2021-11-21 01:11:10,272 INFO L354 Elim1Store]: treesize reduction 25, result has 47.9 percent of original size [2021-11-21 01:11:10,272 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 31 treesize of output 42 [2021-11-21 01:11:10,493 INFO L354 Elim1Store]: treesize reduction 80, result has 45.6 percent of original size [2021-11-21 01:11:10,494 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 75 treesize of output 113 [2021-11-21 01:11:13,398 INFO L354 Elim1Store]: treesize reduction 46, result has 6.1 percent of original size [2021-11-21 01:11:13,399 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 103 treesize of output 78 [2021-11-21 01:11:13,569 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:11:13,569 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-21 01:11:14,137 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 3 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-11-21 01:11:14,137 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [442536096] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-21 01:11:14,137 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [2079445148] [2021-11-21 01:11:14,143 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2021-11-21 01:11:14,150 INFO L166 IcfgInterpreter]: Building call graph [2021-11-21 01:11:14,151 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-21 01:11:14,151 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-21 01:11:14,152 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-21 01:11:14,275 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,279 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,345 INFO L354 Elim1Store]: treesize reduction 62, result has 35.4 percent of original size [2021-11-21 01:11:14,346 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 7 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 55 [2021-11-21 01:11:14,465 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,474 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,475 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,478 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,561 INFO L354 Elim1Store]: treesize reduction 94, result has 27.7 percent of original size [2021-11-21 01:11:14,562 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 40 treesize of output 69 [2021-11-21 01:11:14,903 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,905 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:14,910 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 24 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 0 case distinctions, treesize of input 75 treesize of output 98 [2021-11-21 01:11:15,107 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:15,110 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:15,112 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:15,113 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:15,115 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:15,117 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:15,183 INFO L354 Elim1Store]: treesize reduction 138, result has 20.2 percent of original size [2021-11-21 01:11:15,183 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 26 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 13 case distinctions, treesize of input 371 treesize of output 367 [2021-11-21 01:11:16,070 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:16,192 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:16,376 INFO L354 Elim1Store]: treesize reduction 51, result has 58.2 percent of original size [2021-11-21 01:11:16,376 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 73 treesize of output 124 [2021-11-21 01:11:16,860 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:16,928 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:16,933 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:16,934 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 7 [2021-11-21 01:11:17,101 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:17,155 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:17,163 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:17,163 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 54 treesize of output 49 [2021-11-21 01:11:17,333 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:17,565 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:17,569 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:17,570 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2021-11-21 01:11:17,584 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:17,891 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-21 01:11:18,227 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-21 01:11:18,227 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-21 01:11:18,227 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7, 7] total 17 [2021-11-21 01:11:18,227 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [595855406] [2021-11-21 01:11:18,228 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-21 01:11:18,228 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2021-11-21 01:11:18,228 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:11:18,229 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2021-11-21 01:11:18,229 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=351, Unknown=1, NotChecked=0, Total=420 [2021-11-21 01:11:18,229 INFO L87 Difference]: Start difference. First operand 11 states and 12 transitions. Second operand has 17 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 17 states have internal predecessors, (23), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:18,445 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:11:18,445 INFO L93 Difference]: Finished difference Result 18 states and 20 transitions. [2021-11-21 01:11:18,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-11-21 01:11:18,446 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 17 states have internal predecessors, (23), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2021-11-21 01:11:18,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:11:18,446 INFO L225 Difference]: With dead ends: 18 [2021-11-21 01:11:18,446 INFO L226 Difference]: Without dead ends: 15 [2021-11-21 01:11:18,447 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 42 GetRequests, 16 SyntacticMatches, 2 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 112 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=108, Invalid=541, Unknown=1, NotChecked=0, Total=650 [2021-11-21 01:11:18,448 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 0 mSDsluCounter, 18 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 16 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 12 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-21 01:11:18,449 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 16 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 12 Unchecked, 0.0s Time] [2021-11-21 01:11:18,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 15 states. [2021-11-21 01:11:18,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 15 to 12. [2021-11-21 01:11:18,453 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 12 states, 11 states have (on average 1.1818181818181819) internal successors, (13), 11 states have internal predecessors, (13), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:18,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2021-11-21 01:11:18,454 INFO L78 Accepts]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 10 [2021-11-21 01:11:18,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:11:18,455 INFO L470 AbstractCegarLoop]: Abstraction has 12 states and 13 transitions. [2021-11-21 01:11:18,455 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 17 states have internal predecessors, (23), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:18,455 INFO L276 IsEmpty]: Start isEmpty. Operand 12 states and 13 transitions. [2021-11-21 01:11:18,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2021-11-21 01:11:18,456 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:11:18,456 INFO L514 BasicCegarLoop]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1] [2021-11-21 01:11:18,486 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2021-11-21 01:11:18,672 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:18,673 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:11:18,673 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:11:18,673 INFO L85 PathProgramCache]: Analyzing trace with hash 265315170, now seen corresponding path program 4 times [2021-11-21 01:11:18,673 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:11:18,674 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1003555274] [2021-11-21 01:11:18,674 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:18,674 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:11:18,698 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:18,798 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 4 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:18,798 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:18,799 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1003555274] [2021-11-21 01:11:18,799 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1003555274] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:18,799 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1343830228] [2021-11-21 01:11:18,799 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2021-11-21 01:11:18,800 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:18,800 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:18,805 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:18,824 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-11-21 01:11:18,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:18,875 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 8 conjunts are in the unsatisfiable core [2021-11-21 01:11:18,876 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:18,962 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:18,962 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-21 01:11:19,001 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:19,001 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1343830228] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-21 01:11:19,001 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [987834368] [2021-11-21 01:11:19,005 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2021-11-21 01:11:19,005 INFO L166 IcfgInterpreter]: Building call graph [2021-11-21 01:11:19,006 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-21 01:11:19,006 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-21 01:11:19,006 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-21 01:11:19,135 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,140 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,189 INFO L354 Elim1Store]: treesize reduction 62, result has 35.4 percent of original size [2021-11-21 01:11:19,189 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 55 [2021-11-21 01:11:19,325 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,332 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,334 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,336 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,419 INFO L354 Elim1Store]: treesize reduction 94, result has 27.7 percent of original size [2021-11-21 01:11:19,419 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 40 treesize of output 69 [2021-11-21 01:11:19,638 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,640 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 24 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 103 [2021-11-21 01:11:19,874 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,875 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,876 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,878 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,879 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,880 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,886 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,889 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,890 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,891 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,892 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:19,933 INFO L354 Elim1Store]: treesize reduction 153, result has 12.6 percent of original size [2021-11-21 01:11:19,934 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 32 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 12 case distinctions, treesize of input 373 treesize of output 363 [2021-11-21 01:11:20,483 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:20,590 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:20,746 INFO L354 Elim1Store]: treesize reduction 51, result has 58.2 percent of original size [2021-11-21 01:11:20,746 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 76 treesize of output 127 [2021-11-21 01:11:21,035 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:21,044 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:21,045 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 20 treesize of output 7 [2021-11-21 01:11:21,131 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:21,293 INFO L173 IndexEqualityManager]: detected equality via solver [2021-11-21 01:11:21,301 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:21,302 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 54 treesize of output 49 [2021-11-21 01:11:21,463 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:21,467 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:21,493 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2021-11-21 01:11:21,503 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:21,804 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-21 01:11:22,026 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-21 01:11:22,026 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-21 01:11:22,026 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8, 8] total 13 [2021-11-21 01:11:22,026 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1919430718] [2021-11-21 01:11:22,027 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-21 01:11:22,027 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2021-11-21 01:11:22,027 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:11:22,028 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2021-11-21 01:11:22,028 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=64, Invalid=208, Unknown=0, NotChecked=0, Total=272 [2021-11-21 01:11:22,029 INFO L87 Difference]: Start difference. First operand 12 states and 13 transitions. Second operand has 13 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 13 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:22,119 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:11:22,119 INFO L93 Difference]: Finished difference Result 20 states and 22 transitions. [2021-11-21 01:11:22,120 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-11-21 01:11:22,120 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 13 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 11 [2021-11-21 01:11:22,120 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:11:22,120 INFO L225 Difference]: With dead ends: 20 [2021-11-21 01:11:22,121 INFO L226 Difference]: Without dead ends: 13 [2021-11-21 01:11:22,121 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 94 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=81, Invalid=261, Unknown=0, NotChecked=0, Total=342 [2021-11-21 01:11:22,122 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 6 mSDsluCounter, 8 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 10 SdHoareTripleChecker+Invalid, 49 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-11-21 01:11:22,123 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 10 Invalid, 49 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-11-21 01:11:22,124 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 13 states. [2021-11-21 01:11:22,127 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 13 to 13. [2021-11-21 01:11:22,128 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 13 states, 12 states have (on average 1.1666666666666667) internal successors, (14), 12 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:22,128 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2021-11-21 01:11:22,129 INFO L78 Accepts]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 11 [2021-11-21 01:11:22,129 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:11:22,129 INFO L470 AbstractCegarLoop]: Abstraction has 13 states and 14 transitions. [2021-11-21 01:11:22,129 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 1.4615384615384615) internal successors, (19), 13 states have internal predecessors, (19), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:22,130 INFO L276 IsEmpty]: Start isEmpty. Operand 13 states and 14 transitions. [2021-11-21 01:11:22,130 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2021-11-21 01:11:22,130 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:11:22,130 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1] [2021-11-21 01:11:22,172 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-11-21 01:11:22,352 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:22,352 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:11:22,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:11:22,353 INFO L85 PathProgramCache]: Analyzing trace with hash 1286007525, now seen corresponding path program 5 times [2021-11-21 01:11:22,353 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:11:22,353 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [58500292] [2021-11-21 01:11:22,353 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:22,354 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:11:22,410 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:22,734 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:22,734 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:22,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [58500292] [2021-11-21 01:11:22,735 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [58500292] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:22,735 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2132806574] [2021-11-21 01:11:22,735 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-11-21 01:11:22,735 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:22,735 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:22,736 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:22,737 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-11-21 01:11:22,798 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-11-21 01:11:22,798 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-21 01:11:22,800 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 28 conjunts are in the unsatisfiable core [2021-11-21 01:11:22,802 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:22,869 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 9 [2021-11-21 01:11:22,930 INFO L354 Elim1Store]: treesize reduction 31, result has 22.5 percent of original size [2021-11-21 01:11:22,931 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 36 treesize of output 35 [2021-11-21 01:11:23,107 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,112 INFO L354 Elim1Store]: treesize reduction 13, result has 7.1 percent of original size [2021-11-21 01:11:23,112 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 43 treesize of output 45 [2021-11-21 01:11:23,207 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,211 INFO L354 Elim1Store]: treesize reduction 13, result has 7.1 percent of original size [2021-11-21 01:11:23,211 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 62 treesize of output 50 [2021-11-21 01:11:23,415 INFO L354 Elim1Store]: treesize reduction 246, result has 17.2 percent of original size [2021-11-21 01:11:23,416 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 6 new quantified variables, introduced 12 case distinctions, treesize of input 102 treesize of output 122 [2021-11-21 01:11:23,622 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,623 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,624 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,625 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,626 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 4 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 64 treesize of output 34 [2021-11-21 01:11:23,801 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,802 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:23,807 INFO L354 Elim1Store]: treesize reduction 22, result has 4.3 percent of original size [2021-11-21 01:11:23,807 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 58 treesize of output 32 [2021-11-21 01:11:24,372 INFO L354 Elim1Store]: treesize reduction 70, result has 4.1 percent of original size [2021-11-21 01:11:24,372 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 114 treesize of output 79 [2021-11-21 01:11:24,440 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:24,440 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-11-21 01:11:27,137 WARN L838 $PredicateComparison]: unable to prove that (forall ((|v_ULTIMATE.start_main_~i~0#1_118| Int)) (or (let ((.cse0 (= |c_ULTIMATE.start_main_~i~0#1| 0))) (and (or (not .cse0) (forall ((|ULTIMATE.start_main_~#sum~0#1.offset| Int)) (<= (let ((.cse2 (select |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base|))) (let ((.cse1 (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base| (store .cse2 |ULTIMATE.start_main_~#sum~0#1.offset| 0)) |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| (* |c_ULTIMATE.start_main_~i~0#1| 4) 4)))) (+ .cse1 (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base| (store .cse2 |ULTIMATE.start_main_~#sum~0#1.offset| .cse1)) |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| (* |v_ULTIMATE.start_main_~i~0#1_118| 4)))))) c_~N~0))) (or (let ((.cse3 (= (+ |c_ULTIMATE.start_main_~i~0#1| 1) 0))) (and (or (not .cse3) (forall ((|ULTIMATE.start_main_~#sum~0#1.offset| Int)) (<= (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base| (store (select |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base|) |ULTIMATE.start_main_~#sum~0#1.offset| 0)) |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| (* |v_ULTIMATE.start_main_~i~0#1_118| 4))) c_~N~0))) (or (forall ((|ULTIMATE.start_main_~#sum~0#1.offset| Int)) (<= (let ((.cse5 (select |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base|)) (.cse8 (* |c_ULTIMATE.start_main_~i~0#1| 4))) (let ((.cse4 (select (select |c_#memory_int| |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| .cse8))) (.cse6 (select .cse5 |ULTIMATE.start_main_~#sum~0#1.offset|))) (let ((.cse7 (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base| (store .cse5 |ULTIMATE.start_main_~#sum~0#1.offset| (+ .cse4 .cse6))) |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| .cse8 4)))) (+ .cse4 (select (select (store |c_#memory_int| |c_ULTIMATE.start_main_~#sum~0#1.base| (store .cse5 |ULTIMATE.start_main_~#sum~0#1.offset| (+ .cse4 .cse6 .cse7))) |c_ULTIMATE.start_main_~a~0#1.base|) (+ |c_ULTIMATE.start_main_~a~0#1.offset| (* |v_ULTIMATE.start_main_~i~0#1_118| 4))) .cse6 .cse7)))) c_~N~0)) .cse3))) .cse0))) (<= (+ 2 |v_ULTIMATE.start_main_~i~0#1_118|) c_~N~0) (<= c_~N~0 |v_ULTIMATE.start_main_~i~0#1_118|) (= |v_ULTIMATE.start_main_~i~0#1_118| 0))) is different from false [2021-11-21 01:11:27,412 INFO L354 Elim1Store]: treesize reduction 13, result has 7.1 percent of original size [2021-11-21 01:11:27,413 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 2992 treesize of output 2848 [2021-11-21 01:11:28,499 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 3 not checked. [2021-11-21 01:11:28,499 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2132806574] provided 0 perfect and 2 imperfect interpolant sequences [2021-11-21 01:11:28,499 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1329434403] [2021-11-21 01:11:28,502 INFO L159 IcfgInterpreter]: Started Sifa with 7 locations of interest [2021-11-21 01:11:28,502 INFO L166 IcfgInterpreter]: Building call graph [2021-11-21 01:11:28,503 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2021-11-21 01:11:28,503 INFO L176 IcfgInterpreter]: Starting interpretation [2021-11-21 01:11:28,503 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2021-11-21 01:11:28,677 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,681 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,743 INFO L354 Elim1Store]: treesize reduction 62, result has 35.4 percent of original size [2021-11-21 01:11:28,743 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 6 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 27 treesize of output 55 [2021-11-21 01:11:28,843 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,850 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,851 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,854 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:28,944 INFO L354 Elim1Store]: treesize reduction 94, result has 27.7 percent of original size [2021-11-21 01:11:28,945 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 6 select indices, 6 select index equivalence classes, 10 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 8 case distinctions, treesize of input 40 treesize of output 69 [2021-11-21 01:11:29,100 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 9 select indices, 9 select index equivalence classes, 25 disjoint index pairs (out of 36 index pairs), introduced 9 new quantified variables, introduced 0 case distinctions, treesize of input 80 treesize of output 103 [2021-11-21 01:11:29,334 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,336 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,337 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,339 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,341 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,342 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,346 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,347 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,349 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,350 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,352 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:29,407 INFO L354 Elim1Store]: treesize reduction 153, result has 12.6 percent of original size [2021-11-21 01:11:29,408 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 10 select indices, 10 select index equivalence classes, 32 disjoint index pairs (out of 45 index pairs), introduced 10 new quantified variables, introduced 12 case distinctions, treesize of input 373 treesize of output 363 [2021-11-21 01:11:30,064 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:30,186 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:30,311 INFO L354 Elim1Store]: treesize reduction 51, result has 58.2 percent of original size [2021-11-21 01:11:30,311 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 73 treesize of output 124 [2021-11-21 01:11:30,654 WARN L234 Elim1Store]: Array PQE input equivalent to false [2021-11-21 01:11:30,706 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:30,730 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:30,730 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 15 [2021-11-21 01:11:30,840 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 42 treesize of output 25 [2021-11-21 01:11:30,873 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:30,874 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 75 treesize of output 54 [2021-11-21 01:11:31,044 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-11-21 01:11:31,047 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-11-21 01:11:31,048 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 22 [2021-11-21 01:11:31,065 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2021-11-21 01:11:31,333 INFO L180 IcfgInterpreter]: Interpretation finished [2021-11-21 01:11:31,664 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2021-11-21 01:11:31,664 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-11-21 01:11:31,664 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11, 11] total 27 [2021-11-21 01:11:31,664 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2043585973] [2021-11-21 01:11:31,664 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-11-21 01:11:31,665 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2021-11-21 01:11:31,665 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2021-11-21 01:11:31,665 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2021-11-21 01:11:31,666 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=112, Invalid=761, Unknown=1, NotChecked=56, Total=930 [2021-11-21 01:11:31,666 INFO L87 Difference]: Start difference. First operand 13 states and 14 transitions. Second operand has 27 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 27 states have internal predecessors, (31), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:34,108 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-11-21 01:11:34,108 INFO L93 Difference]: Finished difference Result 21 states and 23 transitions. [2021-11-21 01:11:34,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-11-21 01:11:34,109 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 27 states have internal predecessors, (31), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 12 [2021-11-21 01:11:34,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-11-21 01:11:34,109 INFO L225 Difference]: With dead ends: 21 [2021-11-21 01:11:34,109 INFO L226 Difference]: Without dead ends: 18 [2021-11-21 01:11:34,110 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 14 SyntacticMatches, 2 SemanticMatches, 35 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 296 ImplicationChecksByTransitivity, 5.5s TimeCoverageRelationStatistics Valid=171, Invalid=1091, Unknown=2, NotChecked=68, Total=1332 [2021-11-21 01:11:34,111 INFO L933 BasicCegarLoop]: 2 mSDtfsCounter, 0 mSDsluCounter, 34 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 32 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 32 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-11-21 01:11:34,111 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 32 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 32 Unchecked, 0.0s Time] [2021-11-21 01:11:34,112 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 18 states. [2021-11-21 01:11:34,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 18 to 15. [2021-11-21 01:11:34,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 15 states, 14 states have (on average 1.2142857142857142) internal successors, (17), 14 states have internal predecessors, (17), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:34,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 15 states to 15 states and 17 transitions. [2021-11-21 01:11:34,118 INFO L78 Accepts]: Start accepts. Automaton has 15 states and 17 transitions. Word has length 12 [2021-11-21 01:11:34,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-11-21 01:11:34,118 INFO L470 AbstractCegarLoop]: Abstraction has 15 states and 17 transitions. [2021-11-21 01:11:34,118 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 27 states have internal predecessors, (31), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-11-21 01:11:34,119 INFO L276 IsEmpty]: Start isEmpty. Operand 15 states and 17 transitions. [2021-11-21 01:11:34,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2021-11-21 01:11:34,119 INFO L506 BasicCegarLoop]: Found error trace [2021-11-21 01:11:34,119 INFO L514 BasicCegarLoop]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1] [2021-11-21 01:11:34,148 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2021-11-21 01:11:34,324 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:34,325 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-11-21 01:11:34,325 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-11-21 01:11:34,325 INFO L85 PathProgramCache]: Analyzing trace with hash 1211809179, now seen corresponding path program 6 times [2021-11-21 01:11:34,325 INFO L121 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2021-11-21 01:11:34,325 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1451732272] [2021-11-21 01:11:34,325 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-11-21 01:11:34,325 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-11-21 01:11:34,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-11-21 01:11:34,417 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-11-21 01:11:34,417 INFO L139 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2021-11-21 01:11:34,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1451732272] [2021-11-21 01:11:34,418 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1451732272] provided 0 perfect and 1 imperfect interpolant sequences [2021-11-21 01:11:34,418 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1567127437] [2021-11-21 01:11:34,418 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-11-21 01:11:34,419 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-11-21 01:11:34,419 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 [2021-11-21 01:11:34,432 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-11-21 01:11:34,456 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_eb3dd2e8-2c76-4890-a70b-fb2e719b25a1/bin/utaipan-TEXQjIfE4P/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-11-21 01:11:34,489 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-11-21 01:11:34,489 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-11-21 01:11:34,491 WARN L261 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 30 conjunts are in the unsatisfiable core [2021-11-21 01:11:34,493 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-11-21 01:11:34,503 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2021-11-21 01:11:34,531 INFO L354 Elim1Store]: treesize reduction 42, result has 22.2 percent of original size [2021-11-21 01:11:34,531 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 28 [2021-11-21 01:11:34,587 INFO L354 Elim1Store]: treesize reduction 96, result has 20.7 percent of original size [2021-11-21 01:11:34,588 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 48 treesize of output 50 [2021-11-21 01:11:34,769 INFO L354 Elim1Store]: treesize reduction 126, result has 37.6 percent of original size [2021-11-21 01:11:34,769 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 6 case distinctions, treesize of input 55 treesize of output 100 [2021-11-21 01:11:35,247 INFO L354 Elim1Store]: treesize reduction 206, result has 42.3 percent of original size [2021-11-21 01:11:35,248 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 14 case distinctions, treesize of input 114 treesize of output 220 [2021-11-21 01:11:36,494 INFO L354 Elim1Store]: treesize reduction 304, result has 38.6 percent of original size [2021-11-21 01:11:36,494 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 20 case distinctions, treesize of input 141 treesize of output 274 [2021-11-21 01:11:38,470 INFO L354 Elim1Store]: treesize reduction 364, result has 38.4 percent of original size [2021-11-21 01:11:38,471 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 7 new quantified variables, introduced 27 case distinctions, treesize of input 318 treesize of output 392 [2021-11-21 01:12:15,977 INFO L354 Elim1Store]: treesize reduction 4101, result has 12.4 percent of original size [2021-11-21 01:12:15,978 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 24 select indices, 24 select index equivalence classes, 0 disjoint index pairs (out of 276 index pairs), introduced 24 new quantified variables, introduced 276 case distinctions, treesize of input 934 treesize of output 1026