./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version ff03de63 Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --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 Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 --- Real Ultimate output --- This is Ultimate 0.2.2-dev-ff03de6 [2021-12-21 12:34:29,524 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-21 12:34:29,526 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-21 12:34:29,600 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-21 12:34:29,600 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-21 12:34:29,603 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-21 12:34:29,606 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-21 12:34:29,608 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-21 12:34:29,610 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-21 12:34:29,613 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-21 12:34:29,614 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-21 12:34:29,615 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-21 12:34:29,615 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-21 12:34:29,617 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-21 12:34:29,618 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-21 12:34:29,621 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-21 12:34:29,621 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-21 12:34:29,622 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-21 12:34:29,624 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-21 12:34:29,639 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-21 12:34:29,640 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-21 12:34:29,641 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-21 12:34:29,642 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-21 12:34:29,643 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-21 12:34:29,648 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-21 12:34:29,648 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-21 12:34:29,648 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-21 12:34:29,649 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-21 12:34:29,650 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-21 12:34:29,650 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-21 12:34:29,650 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-21 12:34:29,651 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-21 12:34:29,652 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-21 12:34:29,653 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-21 12:34:29,654 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-21 12:34:29,655 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-21 12:34:29,655 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-21 12:34:29,655 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-21 12:34:29,655 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-21 12:34:29,656 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-21 12:34:29,656 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-21 12:34:29,657 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2021-12-21 12:34:29,680 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-21 12:34:29,681 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-21 12:34:29,681 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-21 12:34:29,681 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-21 12:34:29,682 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-21 12:34:29,682 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-21 12:34:29,682 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-21 12:34:29,682 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-21 12:34:29,683 INFO L138 SettingsManager]: * Use SBE=true [2021-12-21 12:34:29,683 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-21 12:34:29,683 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-21 12:34:29,684 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-21 12:34:29,685 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-21 12:34:29,685 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-21 12:34:29,685 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-21 12:34:29,685 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-21 12:34:29,685 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-21 12:34:29,685 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 12:34:29,686 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-21 12:34:29,686 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-21 12:34:29,687 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-21 12:34:29,687 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-21 12:34:29,687 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux 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 -> Automizer 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 -> aa34b6970b46b2c3f1bda76d086482188f10831dd44cba913e5171769601c6f3 [2021-12-21 12:34:29,873 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-21 12:34:29,892 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-21 12:34:29,900 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-21 12:34:29,901 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-21 12:34:29,901 INFO L275 PluginConnector]: CDTParser initialized [2021-12-21 12:34:29,903 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2021-12-21 12:34:29,950 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bb705d892/7792de1878044f20a52a557cd7caa4c9/FLAG81e76abb4 [2021-12-21 12:34:30,306 INFO L306 CDTParser]: Found 1 translation units. [2021-12-21 12:34:30,306 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c [2021-12-21 12:34:30,313 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bb705d892/7792de1878044f20a52a557cd7caa4c9/FLAG81e76abb4 [2021-12-21 12:34:30,323 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bb705d892/7792de1878044f20a52a557cd7caa4c9 [2021-12-21 12:34:30,325 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-21 12:34:30,326 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-21 12:34:30,327 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-21 12:34:30,327 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-21 12:34:30,345 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-21 12:34:30,346 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,346 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5d28cfe8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30, skipping insertion in model container [2021-12-21 12:34:30,347 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,351 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-21 12:34:30,361 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-21 12:34:30,486 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c[490,503] [2021-12-21 12:34:30,506 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 12:34:30,512 INFO L203 MainTranslator]: Completed pre-run [2021-12-21 12:34:30,521 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd2-ll_unwindbound10.c[490,503] [2021-12-21 12:34:30,536 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-21 12:34:30,545 INFO L208 MainTranslator]: Completed translation [2021-12-21 12:34:30,545 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30 WrapperNode [2021-12-21 12:34:30,545 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-21 12:34:30,546 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-21 12:34:30,546 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-21 12:34:30,546 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-21 12:34:30,551 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,555 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,567 INFO L137 Inliner]: procedures = 14, calls = 17, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 84 [2021-12-21 12:34:30,568 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-21 12:34:30,569 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-21 12:34:30,569 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-21 12:34:30,569 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-21 12:34:30,574 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,574 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,576 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,576 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,578 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,580 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,581 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,582 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-21 12:34:30,583 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-21 12:34:30,583 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-21 12:34:30,583 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-21 12:34:30,596 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (1/1) ... [2021-12-21 12:34:30,604 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-21 12:34:30,619 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:30,644 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-12-21 12:34:30,686 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-12-21 12:34:30,703 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-21 12:34:30,704 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2021-12-21 12:34:30,704 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2021-12-21 12:34:30,704 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-21 12:34:30,704 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-21 12:34:30,704 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-21 12:34:30,704 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-21 12:34:30,704 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-21 12:34:30,750 INFO L234 CfgBuilder]: Building ICFG [2021-12-21 12:34:30,752 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-21 12:34:30,892 INFO L275 CfgBuilder]: Performing block encoding [2021-12-21 12:34:30,897 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-21 12:34:30,898 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2021-12-21 12:34:30,899 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 12:34:30 BoogieIcfgContainer [2021-12-21 12:34:30,899 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-21 12:34:30,900 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-21 12:34:30,900 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-21 12:34:30,902 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-21 12:34:30,903 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 21.12 12:34:30" (1/3) ... [2021-12-21 12:34:30,903 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34416620 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 12:34:30, skipping insertion in model container [2021-12-21 12:34:30,903 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 21.12 12:34:30" (2/3) ... [2021-12-21 12:34:30,903 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34416620 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 21.12 12:34:30, skipping insertion in model container [2021-12-21 12:34:30,904 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 21.12 12:34:30" (3/3) ... [2021-12-21 12:34:30,904 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_unwindbound10.c [2021-12-21 12:34:30,908 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-21 12:34:30,908 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-21 12:34:30,974 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-21 12:34:30,994 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=PETRI_NET, 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-12-21 12:34:30,995 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-21 12:34:31,009 INFO L276 IsEmpty]: Start isEmpty. Operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2021-12-21 12:34:31,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2021-12-21 12:34:31,014 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:31,014 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:31,015 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:31,022 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:31,023 INFO L85 PathProgramCache]: Analyzing trace with hash 1022199732, now seen corresponding path program 1 times [2021-12-21 12:34:31,030 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:31,031 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340976247] [2021-12-21 12:34:31,031 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:31,032 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:31,128 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,177 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2021-12-21 12:34:31,179 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,190 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2021-12-21 12:34:31,192 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,204 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2021-12-21 12:34:31,206 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,214 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2021-12-21 12:34:31,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,222 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-21 12:34:31,223 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:31,224 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [340976247] [2021-12-21 12:34:31,224 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [340976247] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 12:34:31,224 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 12:34:31,225 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-21 12:34:31,226 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [581049937] [2021-12-21 12:34:31,227 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:31,231 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-21 12:34:31,232 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:31,260 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-21 12:34:31,261 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-21 12:34:31,263 INFO L87 Difference]: Start difference. First operand has 34 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 12:34:31,288 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:31,288 INFO L93 Difference]: Finished difference Result 65 states and 104 transitions. [2021-12-21 12:34:31,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-21 12:34:31,296 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2021-12-21 12:34:31,296 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:31,301 INFO L225 Difference]: With dead ends: 65 [2021-12-21 12:34:31,301 INFO L226 Difference]: Without dead ends: 30 [2021-12-21 12:34:31,305 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-21 12:34:31,309 INFO L933 BasicCegarLoop]: 45 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:31,311 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:31,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2021-12-21 12:34:31,347 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2021-12-21 12:34:31,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 17 states have (on average 1.2941176470588236) internal successors, (22), 19 states have internal predecessors, (22), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-21 12:34:31,352 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 41 transitions. [2021-12-21 12:34:31,353 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 41 transitions. Word has length 28 [2021-12-21 12:34:31,353 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:31,354 INFO L470 AbstractCegarLoop]: Abstraction has 30 states and 41 transitions. [2021-12-21 12:34:31,354 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 5.0) internal successors, (10), 2 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 12:34:31,354 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 41 transitions. [2021-12-21 12:34:31,356 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2021-12-21 12:34:31,356 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:31,357 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:31,357 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-21 12:34:31,358 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:31,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:31,359 INFO L85 PathProgramCache]: Analyzing trace with hash -455220980, now seen corresponding path program 1 times [2021-12-21 12:34:31,360 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:31,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1816007171] [2021-12-21 12:34:31,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:31,360 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:31,400 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:31,401 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [517514754] [2021-12-21 12:34:31,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:31,401 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:31,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:31,406 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:31,413 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-21 12:34:31,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,464 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 3 conjunts are in the unsatisfiable core [2021-12-21 12:34:31,468 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:31,549 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-21 12:34:31,550 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 12:34:31,550 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:31,550 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1816007171] [2021-12-21 12:34:31,551 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:31,551 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [517514754] [2021-12-21 12:34:31,551 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [517514754] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 12:34:31,551 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 12:34:31,551 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-12-21 12:34:31,552 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2146600993] [2021-12-21 12:34:31,552 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:31,553 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-21 12:34:31,553 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:31,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-21 12:34:31,553 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 12:34:31,554 INFO L87 Difference]: Start difference. First operand 30 states and 41 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:31,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:31,586 INFO L93 Difference]: Finished difference Result 40 states and 52 transitions. [2021-12-21 12:34:31,587 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-12-21 12:34:31,587 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 29 [2021-12-21 12:34:31,588 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:31,589 INFO L225 Difference]: With dead ends: 40 [2021-12-21 12:34:31,590 INFO L226 Difference]: Without dead ends: 32 [2021-12-21 12:34:31,595 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-21 12:34:31,597 INFO L933 BasicCegarLoop]: 39 mSDtfsCounter, 0 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 9 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 9 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 9 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:31,598 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 100 Invalid, 9 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 9 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:31,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2021-12-21 12:34:31,604 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2021-12-21 12:34:31,606 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.263157894736842) internal successors, (24), 20 states have internal predecessors, (24), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-21 12:34:31,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 43 transitions. [2021-12-21 12:34:31,610 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 43 transitions. Word has length 29 [2021-12-21 12:34:31,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:31,611 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 43 transitions. [2021-12-21 12:34:31,612 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:31,612 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 43 transitions. [2021-12-21 12:34:31,613 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2021-12-21 12:34:31,613 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:31,613 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:31,633 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:31,844 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:31,845 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:31,847 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:31,847 INFO L85 PathProgramCache]: Analyzing trace with hash -1233535180, now seen corresponding path program 1 times [2021-12-21 12:34:31,848 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:31,849 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [257040764] [2021-12-21 12:34:31,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:31,849 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:31,876 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:31,877 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [757060191] [2021-12-21 12:34:31,877 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:31,877 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:31,877 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:31,878 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:31,879 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-21 12:34:31,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:31,914 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 12:34:31,915 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:31,995 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-21 12:34:31,996 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:32,083 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-21 12:34:32,083 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:32,083 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [257040764] [2021-12-21 12:34:32,083 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:32,084 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [757060191] [2021-12-21 12:34:32,084 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [757060191] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:32,084 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:32,084 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2021-12-21 12:34:32,084 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [621904304] [2021-12-21 12:34:32,084 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:32,085 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-21 12:34:32,085 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:32,085 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-21 12:34:32,086 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-12-21 12:34:32,086 INFO L87 Difference]: Start difference. First operand 32 states and 43 transitions. Second operand has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 12:34:32,146 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:32,146 INFO L93 Difference]: Finished difference Result 49 states and 67 transitions. [2021-12-21 12:34:32,146 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 12:34:32,147 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 30 [2021-12-21 12:34:32,147 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:32,148 INFO L225 Difference]: With dead ends: 49 [2021-12-21 12:34:32,148 INFO L226 Difference]: Without dead ends: 41 [2021-12-21 12:34:32,148 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2021-12-21 12:34:32,149 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 30 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 111 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:32,150 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 111 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:32,151 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2021-12-21 12:34:32,156 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 33. [2021-12-21 12:34:32,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 20 states have (on average 1.25) internal successors, (25), 21 states have internal predecessors, (25), 10 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-21 12:34:32,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 44 transitions. [2021-12-21 12:34:32,157 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 44 transitions. Word has length 30 [2021-12-21 12:34:32,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:32,158 INFO L470 AbstractCegarLoop]: Abstraction has 33 states and 44 transitions. [2021-12-21 12:34:32,158 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-21 12:34:32,158 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 44 transitions. [2021-12-21 12:34:32,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-12-21 12:34:32,159 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:32,159 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:32,184 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:32,378 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-12-21 12:34:32,378 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:32,379 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:32,379 INFO L85 PathProgramCache]: Analyzing trace with hash -73118621, now seen corresponding path program 1 times [2021-12-21 12:34:32,379 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:32,379 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1323014462] [2021-12-21 12:34:32,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:32,380 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:32,387 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:32,388 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2009476889] [2021-12-21 12:34:32,388 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:32,388 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:32,388 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:32,389 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:32,434 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-21 12:34:32,441 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:32,443 INFO L263 TraceCheckSpWp]: Trace formula consists of 111 conjuncts, 14 conjunts are in the unsatisfiable core [2021-12-21 12:34:32,445 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:32,539 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-21 12:34:32,539 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:32,628 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-21 12:34:32,629 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:32,629 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1323014462] [2021-12-21 12:34:32,629 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:32,629 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2009476889] [2021-12-21 12:34:32,629 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2009476889] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-21 12:34:32,629 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:34:32,629 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2021-12-21 12:34:32,630 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [300578878] [2021-12-21 12:34:32,630 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:32,630 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 12:34:32,630 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:32,631 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 12:34:32,631 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2021-12-21 12:34:32,631 INFO L87 Difference]: Start difference. First operand 33 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:32,663 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:32,663 INFO L93 Difference]: Finished difference Result 39 states and 49 transitions. [2021-12-21 12:34:32,664 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 12:34:32,664 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 32 [2021-12-21 12:34:32,664 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:32,665 INFO L225 Difference]: With dead ends: 39 [2021-12-21 12:34:32,665 INFO L226 Difference]: Without dead ends: 37 [2021-12-21 12:34:32,665 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 53 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2021-12-21 12:34:32,666 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 7 mSDsluCounter, 89 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:32,666 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 124 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:32,677 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2021-12-21 12:34:32,681 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2021-12-21 12:34:32,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 24 states have internal predecessors, (28), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-21 12:34:32,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2021-12-21 12:34:32,682 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 32 [2021-12-21 12:34:32,682 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:32,683 INFO L470 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2021-12-21 12:34:32,683 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:32,683 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2021-12-21 12:34:32,684 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2021-12-21 12:34:32,684 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:32,684 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:32,702 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:32,901 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:32,901 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:32,902 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:32,902 INFO L85 PathProgramCache]: Analyzing trace with hash 96561445, now seen corresponding path program 1 times [2021-12-21 12:34:32,902 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:32,902 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1935703694] [2021-12-21 12:34:32,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:32,902 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:32,909 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:32,909 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [59942134] [2021-12-21 12:34:32,909 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:32,909 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:32,910 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:32,912 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:32,913 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-21 12:34:32,948 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:32,949 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 12:34:32,951 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:33,022 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-21 12:34:33,023 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 12:34:33,023 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:33,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1935703694] [2021-12-21 12:34:33,023 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:33,023 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [59942134] [2021-12-21 12:34:33,023 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [59942134] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 12:34:33,024 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 12:34:33,024 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-21 12:34:33,024 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [631739397] [2021-12-21 12:34:33,024 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:33,024 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 12:34:33,025 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:33,025 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 12:34:33,025 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-21 12:34:33,025 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:33,048 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:33,048 INFO L93 Difference]: Finished difference Result 62 states and 80 transitions. [2021-12-21 12:34:33,048 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 12:34:33,049 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 35 [2021-12-21 12:34:33,049 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:33,049 INFO L225 Difference]: With dead ends: 62 [2021-12-21 12:34:33,049 INFO L226 Difference]: Without dead ends: 39 [2021-12-21 12:34:33,050 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2021-12-21 12:34:33,050 INFO L933 BasicCegarLoop]: 38 mSDtfsCounter, 5 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:33,051 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 122 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:33,051 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2021-12-21 12:34:33,054 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 39. [2021-12-21 12:34:33,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.2) internal successors, (30), 26 states have internal predecessors, (30), 10 states have call successors, (10), 3 states have call predecessors, (10), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2021-12-21 12:34:33,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 49 transitions. [2021-12-21 12:34:33,055 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 49 transitions. Word has length 35 [2021-12-21 12:34:33,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:33,056 INFO L470 AbstractCegarLoop]: Abstraction has 39 states and 49 transitions. [2021-12-21 12:34:33,056 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-21 12:34:33,056 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 49 transitions. [2021-12-21 12:34:33,057 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2021-12-21 12:34:33,057 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:33,057 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:33,076 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:33,274 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:33,274 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:33,274 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:33,275 INFO L85 PathProgramCache]: Analyzing trace with hash 433790877, now seen corresponding path program 1 times [2021-12-21 12:34:33,275 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:33,275 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180508209] [2021-12-21 12:34:33,275 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:33,275 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:33,282 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:33,282 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [385021665] [2021-12-21 12:34:33,282 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:33,282 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:33,283 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:33,284 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:33,285 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-21 12:34:33,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:33,318 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 15 conjunts are in the unsatisfiable core [2021-12-21 12:34:33,320 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:33,497 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2021-12-21 12:34:33,497 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:33,585 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-21 12:34:33,586 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:33,586 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1180508209] [2021-12-21 12:34:33,586 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:33,586 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [385021665] [2021-12-21 12:34:33,586 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [385021665] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-21 12:34:33,586 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:34:33,586 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2021-12-21 12:34:33,586 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [546391423] [2021-12-21 12:34:33,587 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:33,587 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 12:34:33,587 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:33,587 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 12:34:33,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2021-12-21 12:34:33,588 INFO L87 Difference]: Start difference. First operand 39 states and 49 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-12-21 12:34:33,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:33,619 INFO L93 Difference]: Finished difference Result 53 states and 68 transitions. [2021-12-21 12:34:33,619 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 12:34:33,619 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 37 [2021-12-21 12:34:33,619 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:33,620 INFO L225 Difference]: With dead ends: 53 [2021-12-21 12:34:33,620 INFO L226 Difference]: Without dead ends: 51 [2021-12-21 12:34:33,620 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 63 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2021-12-21 12:34:33,621 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 8 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 153 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:33,621 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 153 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:33,622 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2021-12-21 12:34:33,626 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2021-12-21 12:34:33,626 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 31 states have (on average 1.2258064516129032) internal successors, (38), 32 states have internal predecessors, (38), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 12:34:33,627 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 65 transitions. [2021-12-21 12:34:33,627 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 65 transitions. Word has length 37 [2021-12-21 12:34:33,628 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:33,628 INFO L470 AbstractCegarLoop]: Abstraction has 50 states and 65 transitions. [2021-12-21 12:34:33,628 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2021-12-21 12:34:33,628 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 65 transitions. [2021-12-21 12:34:33,628 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2021-12-21 12:34:33,629 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:33,629 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:33,648 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:33,845 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:33,846 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:33,846 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:33,846 INFO L85 PathProgramCache]: Analyzing trace with hash -553232285, now seen corresponding path program 1 times [2021-12-21 12:34:33,846 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:33,846 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [139207550] [2021-12-21 12:34:33,846 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:33,846 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:33,858 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:33,858 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [17876238] [2021-12-21 12:34:33,860 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:33,860 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:33,860 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:33,861 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:33,900 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-21 12:34:33,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:33,913 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 15 conjunts are in the unsatisfiable core [2021-12-21 12:34:33,928 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:34,143 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 9 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2021-12-21 12:34:34,143 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:34,229 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2021-12-21 12:34:34,229 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:34,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [139207550] [2021-12-21 12:34:34,229 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:34,229 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [17876238] [2021-12-21 12:34:34,229 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [17876238] provided 1 perfect and 1 imperfect interpolant sequences [2021-12-21 12:34:34,229 INFO L186 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:34:34,229 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2021-12-21 12:34:34,230 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [119164387] [2021-12-21 12:34:34,230 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:34:34,231 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 12:34:34,231 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:34,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 12:34:34,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2021-12-21 12:34:34,232 INFO L87 Difference]: Start difference. First operand 50 states and 65 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-12-21 12:34:34,271 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:34,271 INFO L93 Difference]: Finished difference Result 57 states and 71 transitions. [2021-12-21 12:34:34,271 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-21 12:34:34,272 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2021-12-21 12:34:34,272 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:34,274 INFO L225 Difference]: With dead ends: 57 [2021-12-21 12:34:34,274 INFO L226 Difference]: Without dead ends: 55 [2021-12-21 12:34:34,275 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2021-12-21 12:34:34,276 INFO L933 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:34,277 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 144 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-21 12:34:34,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2021-12-21 12:34:34,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 54. [2021-12-21 12:34:34,296 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 34 states have (on average 1.2058823529411764) internal successors, (41), 35 states have internal predecessors, (41), 14 states have call successors, (14), 5 states have call predecessors, (14), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 12:34:34,298 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 68 transitions. [2021-12-21 12:34:34,298 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 68 transitions. Word has length 42 [2021-12-21 12:34:34,300 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:34,300 INFO L470 AbstractCegarLoop]: Abstraction has 54 states and 68 transitions. [2021-12-21 12:34:34,300 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2021-12-21 12:34:34,300 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 68 transitions. [2021-12-21 12:34:34,301 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2021-12-21 12:34:34,301 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:34,301 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:34,320 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:34,501 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:34,502 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:34,502 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:34,502 INFO L85 PathProgramCache]: Analyzing trace with hash 2115683101, now seen corresponding path program 1 times [2021-12-21 12:34:34,502 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:34,503 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1573594513] [2021-12-21 12:34:34,503 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:34,503 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:34,510 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:34,510 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [847906033] [2021-12-21 12:34:34,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:34,510 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:34,511 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:34,512 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:34,513 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-21 12:34:34,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:34,547 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 16 conjunts are in the unsatisfiable core [2021-12-21 12:34:34,549 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:34,711 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 11 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2021-12-21 12:34:34,711 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:34,878 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:34,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1573594513] [2021-12-21 12:34:34,878 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:34,878 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [847906033] [2021-12-21 12:34:34,878 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [847906033] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 12:34:34,878 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:34:34,879 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2021-12-21 12:34:34,879 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338759057] [2021-12-21 12:34:34,879 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:34,879 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-21 12:34:34,879 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:34,880 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-21 12:34:34,880 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-12-21 12:34:34,880 INFO L87 Difference]: Start difference. First operand 54 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-21 12:34:34,966 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:34,966 INFO L93 Difference]: Finished difference Result 61 states and 74 transitions. [2021-12-21 12:34:34,966 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-21 12:34:34,966 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2021-12-21 12:34:34,967 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:34,967 INFO L225 Difference]: With dead ends: 61 [2021-12-21 12:34:34,967 INFO L226 Difference]: Without dead ends: 59 [2021-12-21 12:34:34,968 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 42 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2021-12-21 12:34:34,968 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 12 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 110 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 110 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:34,968 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 152 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 110 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:34:34,969 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2021-12-21 12:34:34,973 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 58. [2021-12-21 12:34:34,973 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 38 states have internal predecessors, (44), 14 states have call successors, (14), 6 states have call predecessors, (14), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2021-12-21 12:34:34,974 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2021-12-21 12:34:34,974 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 47 [2021-12-21 12:34:34,974 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:34,974 INFO L470 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2021-12-21 12:34:34,975 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2021-12-21 12:34:34,975 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2021-12-21 12:34:34,975 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2021-12-21 12:34:34,975 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:34,976 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:34,995 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:35,195 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:35,195 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:35,196 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:35,196 INFO L85 PathProgramCache]: Analyzing trace with hash -879665460, now seen corresponding path program 1 times [2021-12-21 12:34:35,196 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:35,196 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [734017351] [2021-12-21 12:34:35,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:35,196 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:35,215 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:35,216 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [151438029] [2021-12-21 12:34:35,216 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:35,216 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:35,216 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:35,235 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:35,267 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-21 12:34:35,314 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:35,315 INFO L263 TraceCheckSpWp]: Trace formula consists of 167 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 12:34:35,316 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:35,569 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-21 12:34:35,569 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:35,790 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 8 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-21 12:34:35,791 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:35,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [734017351] [2021-12-21 12:34:35,791 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:35,791 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [151438029] [2021-12-21 12:34:35,791 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [151438029] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:35,791 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:35,792 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2021-12-21 12:34:35,792 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [443492478] [2021-12-21 12:34:35,792 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:35,792 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-21 12:34:35,793 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:35,793 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-21 12:34:35,793 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2021-12-21 12:34:35,793 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-21 12:34:36,025 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:36,026 INFO L93 Difference]: Finished difference Result 211 states and 250 transitions. [2021-12-21 12:34:36,026 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-21 12:34:36,026 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 56 [2021-12-21 12:34:36,027 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:36,029 INFO L225 Difference]: With dead ends: 211 [2021-12-21 12:34:36,029 INFO L226 Difference]: Without dead ends: 203 [2021-12-21 12:34:36,029 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=64, Invalid=118, Unknown=0, NotChecked=0, Total=182 [2021-12-21 12:34:36,030 INFO L933 BasicCegarLoop]: 57 mSDtfsCounter, 97 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 163 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:36,030 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [97 Valid, 264 Invalid, 163 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-21 12:34:36,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 203 states. [2021-12-21 12:34:36,047 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 203 to 195. [2021-12-21 12:34:36,048 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 195 states, 125 states have (on average 1.192) internal successors, (149), 129 states have internal predecessors, (149), 44 states have call successors, (44), 25 states have call predecessors, (44), 25 states have return successors, (40), 40 states have call predecessors, (40), 40 states have call successors, (40) [2021-12-21 12:34:36,049 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 195 states to 195 states and 233 transitions. [2021-12-21 12:34:36,050 INFO L78 Accepts]: Start accepts. Automaton has 195 states and 233 transitions. Word has length 56 [2021-12-21 12:34:36,050 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:36,050 INFO L470 AbstractCegarLoop]: Abstraction has 195 states and 233 transitions. [2021-12-21 12:34:36,050 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.9) internal successors, (39), 10 states have internal predecessors, (39), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-21 12:34:36,051 INFO L276 IsEmpty]: Start isEmpty. Operand 195 states and 233 transitions. [2021-12-21 12:34:36,051 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2021-12-21 12:34:36,051 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:36,052 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:36,113 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:36,271 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2021-12-21 12:34:36,272 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:36,272 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:36,272 INFO L85 PathProgramCache]: Analyzing trace with hash -1506412172, now seen corresponding path program 1 times [2021-12-21 12:34:36,272 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:36,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1654553758] [2021-12-21 12:34:36,272 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:36,273 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:36,278 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:36,278 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1137795409] [2021-12-21 12:34:36,278 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:36,279 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:36,279 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:36,299 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:36,301 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2021-12-21 12:34:36,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:36,387 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 9 conjunts are in the unsatisfiable core [2021-12-21 12:34:36,388 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:36,840 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2021-12-21 12:34:36,841 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:36,943 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2021-12-21 12:34:36,943 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:36,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1654553758] [2021-12-21 12:34:36,944 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:36,944 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1137795409] [2021-12-21 12:34:36,944 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1137795409] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:36,944 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:36,944 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2021-12-21 12:34:36,944 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [69273992] [2021-12-21 12:34:36,944 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:36,944 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2021-12-21 12:34:36,944 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:36,945 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-12-21 12:34:36,945 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2021-12-21 12:34:36,945 INFO L87 Difference]: Start difference. First operand 195 states and 233 transitions. Second operand has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-21 12:34:37,059 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:37,059 INFO L93 Difference]: Finished difference Result 279 states and 364 transitions. [2021-12-21 12:34:37,059 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-21 12:34:37,060 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) Word has length 57 [2021-12-21 12:34:37,060 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:37,062 INFO L225 Difference]: With dead ends: 279 [2021-12-21 12:34:37,062 INFO L226 Difference]: Without dead ends: 259 [2021-12-21 12:34:37,064 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 104 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2021-12-21 12:34:37,064 INFO L933 BasicCegarLoop]: 66 mSDtfsCounter, 62 mSDsluCounter, 353 mSDsCounter, 0 mSdLazyCounter, 103 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 67 SdHoareTripleChecker+Valid, 419 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 103 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:37,065 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [67 Valid, 419 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 103 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:34:37,065 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2021-12-21 12:34:37,099 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 235. [2021-12-21 12:34:37,100 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 235 states, 152 states have (on average 1.2236842105263157) internal successors, (186), 155 states have internal predecessors, (186), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2021-12-21 12:34:37,101 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 235 states to 235 states and 299 transitions. [2021-12-21 12:34:37,101 INFO L78 Accepts]: Start accepts. Automaton has 235 states and 299 transitions. Word has length 57 [2021-12-21 12:34:37,101 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:37,101 INFO L470 AbstractCegarLoop]: Abstraction has 235 states and 299 transitions. [2021-12-21 12:34:37,101 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.0) internal successors, (27), 8 states have internal predecessors, (27), 5 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 3 states have call predecessors, (8), 4 states have call successors, (8) [2021-12-21 12:34:37,101 INFO L276 IsEmpty]: Start isEmpty. Operand 235 states and 299 transitions. [2021-12-21 12:34:37,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2021-12-21 12:34:37,102 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:37,102 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:37,120 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2021-12-21 12:34:37,315 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2021-12-21 12:34:37,316 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:37,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:37,316 INFO L85 PathProgramCache]: Analyzing trace with hash -1869160295, now seen corresponding path program 1 times [2021-12-21 12:34:37,316 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:37,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [258473677] [2021-12-21 12:34:37,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:37,317 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:37,323 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:37,323 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [335565012] [2021-12-21 12:34:37,323 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:37,324 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:37,324 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:37,325 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:37,347 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2021-12-21 12:34:37,376 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:37,377 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 7 conjunts are in the unsatisfiable core [2021-12-21 12:34:37,379 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:37,478 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-21 12:34:37,478 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:37,570 INFO L134 CoverageAnalysis]: Checked inductivity of 61 backedges. 11 proven. 2 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2021-12-21 12:34:37,571 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:37,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [258473677] [2021-12-21 12:34:37,571 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:37,571 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [335565012] [2021-12-21 12:34:37,571 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [335565012] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:37,571 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:37,571 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 6] total 10 [2021-12-21 12:34:37,571 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525201458] [2021-12-21 12:34:37,572 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:37,572 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2021-12-21 12:34:37,572 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:37,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2021-12-21 12:34:37,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2021-12-21 12:34:37,573 INFO L87 Difference]: Start difference. First operand 235 states and 299 transitions. Second operand has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-21 12:34:37,697 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:37,697 INFO L93 Difference]: Finished difference Result 344 states and 448 transitions. [2021-12-21 12:34:37,698 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-21 12:34:37,698 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 59 [2021-12-21 12:34:37,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:37,699 INFO L225 Difference]: With dead ends: 344 [2021-12-21 12:34:37,699 INFO L226 Difference]: Without dead ends: 248 [2021-12-21 12:34:37,700 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 108 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2021-12-21 12:34:37,701 INFO L933 BasicCegarLoop]: 56 mSDtfsCounter, 77 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 72 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 188 SdHoareTripleChecker+Invalid, 109 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 72 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:37,701 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [77 Valid, 188 Invalid, 109 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 72 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:34:37,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 248 states. [2021-12-21 12:34:37,723 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 248 to 244. [2021-12-21 12:34:37,724 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 244 states, 161 states have (on average 1.173913043478261) internal successors, (189), 164 states have internal predecessors, (189), 58 states have call successors, (58), 24 states have call predecessors, (58), 24 states have return successors, (55), 55 states have call predecessors, (55), 55 states have call successors, (55) [2021-12-21 12:34:37,725 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 244 states to 244 states and 302 transitions. [2021-12-21 12:34:37,725 INFO L78 Accepts]: Start accepts. Automaton has 244 states and 302 transitions. Word has length 59 [2021-12-21 12:34:37,726 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:37,726 INFO L470 AbstractCegarLoop]: Abstraction has 244 states and 302 transitions. [2021-12-21 12:34:37,726 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.1) internal successors, (41), 10 states have internal predecessors, (41), 5 states have call successors, (17), 4 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2021-12-21 12:34:37,726 INFO L276 IsEmpty]: Start isEmpty. Operand 244 states and 302 transitions. [2021-12-21 12:34:37,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2021-12-21 12:34:37,727 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:37,727 INFO L514 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:37,750 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Ended with exit code 0 [2021-12-21 12:34:37,953 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2021-12-21 12:34:37,953 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:37,953 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:37,954 INFO L85 PathProgramCache]: Analyzing trace with hash 991223133, now seen corresponding path program 1 times [2021-12-21 12:34:37,954 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:37,954 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [724640081] [2021-12-21 12:34:37,954 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:37,954 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:37,960 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:37,961 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [656780614] [2021-12-21 12:34:37,961 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:37,961 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:37,961 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:37,962 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:37,982 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2021-12-21 12:34:38,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:34:38,005 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 24 conjunts are in the unsatisfiable core [2021-12-21 12:34:38,006 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:38,227 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 15 proven. 14 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2021-12-21 12:34:38,228 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:38,353 INFO L134 CoverageAnalysis]: Checked inductivity of 81 backedges. 22 proven. 7 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2021-12-21 12:34:38,353 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:38,353 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [724640081] [2021-12-21 12:34:38,353 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:38,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [656780614] [2021-12-21 12:34:38,354 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [656780614] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:38,354 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:38,354 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2021-12-21 12:34:38,354 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1893532361] [2021-12-21 12:34:38,354 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:38,354 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-21 12:34:38,355 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:38,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-21 12:34:38,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=103, Unknown=0, NotChecked=0, Total=132 [2021-12-21 12:34:38,355 INFO L87 Difference]: Start difference. First operand 244 states and 302 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-12-21 12:34:38,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:38,636 INFO L93 Difference]: Finished difference Result 330 states and 429 transitions. [2021-12-21 12:34:38,636 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-12-21 12:34:38,636 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 64 [2021-12-21 12:34:38,636 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:38,639 INFO L225 Difference]: With dead ends: 330 [2021-12-21 12:34:38,639 INFO L226 Difference]: Without dead ends: 324 [2021-12-21 12:34:38,639 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 117 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2021-12-21 12:34:38,640 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 40 mSDsluCounter, 308 mSDsCounter, 0 mSdLazyCounter, 304 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 358 SdHoareTripleChecker+Invalid, 347 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 304 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:38,640 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 358 Invalid, 347 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 304 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2021-12-21 12:34:38,640 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 324 states. [2021-12-21 12:34:38,665 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 324 to 291. [2021-12-21 12:34:38,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 291 states, 194 states have (on average 1.1958762886597938) internal successors, (232), 203 states have internal predecessors, (232), 69 states have call successors, (69), 27 states have call predecessors, (69), 27 states have return successors, (65), 60 states have call predecessors, (65), 65 states have call successors, (65) [2021-12-21 12:34:38,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 291 states to 291 states and 366 transitions. [2021-12-21 12:34:38,667 INFO L78 Accepts]: Start accepts. Automaton has 291 states and 366 transitions. Word has length 64 [2021-12-21 12:34:38,667 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:38,667 INFO L470 AbstractCegarLoop]: Abstraction has 291 states and 366 transitions. [2021-12-21 12:34:38,668 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 11 states have internal predecessors, (42), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2021-12-21 12:34:38,668 INFO L276 IsEmpty]: Start isEmpty. Operand 291 states and 366 transitions. [2021-12-21 12:34:38,668 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2021-12-21 12:34:38,668 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:38,668 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:38,685 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2021-12-21 12:34:38,879 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2021-12-21 12:34:38,879 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:38,880 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:38,885 INFO L85 PathProgramCache]: Analyzing trace with hash 1694315171, now seen corresponding path program 2 times [2021-12-21 12:34:38,886 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:38,886 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2143277478] [2021-12-21 12:34:38,886 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:38,886 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:38,901 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:38,902 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1913721694] [2021-12-21 12:34:38,902 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 12:34:38,902 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:38,902 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:38,904 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:38,905 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2021-12-21 12:34:38,945 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-21 12:34:38,945 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 12:34:38,946 INFO L263 TraceCheckSpWp]: Trace formula consists of 195 conjuncts, 32 conjunts are in the unsatisfiable core [2021-12-21 12:34:38,948 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:39,332 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 12 proven. 17 refuted. 0 times theorem prover too weak. 75 trivial. 0 not checked. [2021-12-21 12:34:39,332 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:39,442 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:39,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2143277478] [2021-12-21 12:34:39,442 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:39,442 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1913721694] [2021-12-21 12:34:39,442 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1913721694] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 12:34:39,442 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:34:39,443 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2021-12-21 12:34:39,443 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [734403519] [2021-12-21 12:34:39,443 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:39,443 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2021-12-21 12:34:39,443 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:39,443 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-12-21 12:34:39,443 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=194, Unknown=0, NotChecked=0, Total=240 [2021-12-21 12:34:39,443 INFO L87 Difference]: Start difference. First operand 291 states and 366 transitions. Second operand has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2021-12-21 12:34:39,612 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:34:39,612 INFO L93 Difference]: Finished difference Result 315 states and 393 transitions. [2021-12-21 12:34:39,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2021-12-21 12:34:39,613 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) Word has length 69 [2021-12-21 12:34:39,613 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:34:39,615 INFO L225 Difference]: With dead ends: 315 [2021-12-21 12:34:39,615 INFO L226 Difference]: Without dead ends: 313 [2021-12-21 12:34:39,616 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 94 GetRequests, 75 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 54 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2021-12-21 12:34:39,616 INFO L933 BasicCegarLoop]: 47 mSDtfsCounter, 49 mSDsluCounter, 265 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 312 SdHoareTripleChecker+Invalid, 250 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:34:39,616 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [61 Valid, 312 Invalid, 250 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 223 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:34:39,617 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 313 states. [2021-12-21 12:34:39,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 313 to 310. [2021-12-21 12:34:39,638 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 310 states, 206 states have (on average 1.1941747572815533) internal successors, (246), 215 states have internal predecessors, (246), 73 states have call successors, (73), 30 states have call predecessors, (73), 30 states have return successors, (69), 64 states have call predecessors, (69), 69 states have call successors, (69) [2021-12-21 12:34:39,640 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 310 states to 310 states and 388 transitions. [2021-12-21 12:34:39,640 INFO L78 Accepts]: Start accepts. Automaton has 310 states and 388 transitions. Word has length 69 [2021-12-21 12:34:39,640 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:34:39,640 INFO L470 AbstractCegarLoop]: Abstraction has 310 states and 388 transitions. [2021-12-21 12:34:39,641 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.4545454545454546) internal successors, (27), 10 states have internal predecessors, (27), 5 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2021-12-21 12:34:39,641 INFO L276 IsEmpty]: Start isEmpty. Operand 310 states and 388 transitions. [2021-12-21 12:34:39,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2021-12-21 12:34:39,641 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:34:39,642 INFO L514 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:34:39,661 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2021-12-21 12:34:39,856 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-21 12:34:39,856 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:34:39,856 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:34:39,856 INFO L85 PathProgramCache]: Analyzing trace with hash -1349365539, now seen corresponding path program 3 times [2021-12-21 12:34:39,856 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:34:39,857 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [239919673] [2021-12-21 12:34:39,857 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:34:39,857 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:34:39,862 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:34:39,862 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [127272035] [2021-12-21 12:34:39,862 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2021-12-21 12:34:39,863 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:34:39,863 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:34:39,869 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:34:39,870 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2021-12-21 12:34:39,919 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-12-21 12:34:39,920 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 12:34:39,921 INFO L263 TraceCheckSpWp]: Trace formula consists of 168 conjuncts, 51 conjunts are in the unsatisfiable core [2021-12-21 12:34:39,923 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:34:40,632 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 36 proven. 26 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2021-12-21 12:34:40,633 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:34:46,379 INFO L134 CoverageAnalysis]: Checked inductivity of 131 backedges. 36 proven. 17 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2021-12-21 12:34:46,380 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:34:46,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [239919673] [2021-12-21 12:34:46,380 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:34:46,380 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [127272035] [2021-12-21 12:34:46,380 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [127272035] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:34:46,380 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:34:46,381 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 12] total 21 [2021-12-21 12:34:46,381 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1488790044] [2021-12-21 12:34:46,381 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:34:46,383 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-21 12:34:46,384 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:34:46,384 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-21 12:34:46,384 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=336, Unknown=0, NotChecked=0, Total=420 [2021-12-21 12:34:46,384 INFO L87 Difference]: Start difference. First operand 310 states and 388 transitions. Second operand has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2021-12-21 12:35:20,201 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:20,201 INFO L93 Difference]: Finished difference Result 427 states and 568 transitions. [2021-12-21 12:35:20,202 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2021-12-21 12:35:20,202 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) Word has length 74 [2021-12-21 12:35:20,202 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:20,204 INFO L225 Difference]: With dead ends: 427 [2021-12-21 12:35:20,205 INFO L226 Difference]: Without dead ends: 423 [2021-12-21 12:35:20,205 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 125 SyntacticMatches, 2 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 25.7s TimeCoverageRelationStatistics Valid=289, Invalid=971, Unknown=0, NotChecked=0, Total=1260 [2021-12-21 12:35:20,205 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 183 mSDsluCounter, 351 mSDsCounter, 0 mSdLazyCounter, 602 mSolverCounterSat, 163 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 195 SdHoareTripleChecker+Valid, 386 SdHoareTripleChecker+Invalid, 765 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 163 IncrementalHoareTripleChecker+Valid, 602 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.3s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:20,206 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [195 Valid, 386 Invalid, 765 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [163 Valid, 602 Invalid, 0 Unknown, 0 Unchecked, 9.3s Time] [2021-12-21 12:35:20,206 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 423 states. [2021-12-21 12:35:20,280 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 423 to 388. [2021-12-21 12:35:20,281 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 388 states, 254 states have (on average 1.2283464566929134) internal successors, (312), 264 states have internal predecessors, (312), 101 states have call successors, (101), 33 states have call predecessors, (101), 32 states have return successors, (97), 90 states have call predecessors, (97), 97 states have call successors, (97) [2021-12-21 12:35:20,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 388 states to 388 states and 510 transitions. [2021-12-21 12:35:20,283 INFO L78 Accepts]: Start accepts. Automaton has 388 states and 510 transitions. Word has length 74 [2021-12-21 12:35:20,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:20,283 INFO L470 AbstractCegarLoop]: Abstraction has 388 states and 510 transitions. [2021-12-21 12:35:20,283 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 20 states have (on average 2.25) internal successors, (45), 17 states have internal predecessors, (45), 9 states have call successors, (23), 2 states have call predecessors, (23), 3 states have return successors, (22), 10 states have call predecessors, (22), 8 states have call successors, (22) [2021-12-21 12:35:20,283 INFO L276 IsEmpty]: Start isEmpty. Operand 388 states and 510 transitions. [2021-12-21 12:35:20,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2021-12-21 12:35:20,284 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:20,284 INFO L514 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:20,303 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:20,499 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2021-12-21 12:35:20,499 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:20,500 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:20,500 INFO L85 PathProgramCache]: Analyzing trace with hash -484140586, now seen corresponding path program 1 times [2021-12-21 12:35:20,500 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:20,500 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1667035625] [2021-12-21 12:35:20,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:20,500 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:20,506 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:20,506 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [750745635] [2021-12-21 12:35:20,506 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:20,506 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:20,506 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:20,510 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:20,511 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2021-12-21 12:35:20,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:35:20,554 INFO L263 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 38 conjunts are in the unsatisfiable core [2021-12-21 12:35:20,556 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:21,088 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2021-12-21 12:35:21,089 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:21,567 INFO L134 CoverageAnalysis]: Checked inductivity of 162 backedges. 30 proven. 17 refuted. 0 times theorem prover too weak. 115 trivial. 0 not checked. [2021-12-21 12:35:21,567 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:21,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1667035625] [2021-12-21 12:35:21,568 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:21,568 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [750745635] [2021-12-21 12:35:21,568 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [750745635] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:35:21,568 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:35:21,568 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2021-12-21 12:35:21,568 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [799217904] [2021-12-21 12:35:21,568 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:21,568 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2021-12-21 12:35:21,568 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:21,569 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2021-12-21 12:35:21,569 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=284, Unknown=0, NotChecked=0, Total=342 [2021-12-21 12:35:21,569 INFO L87 Difference]: Start difference. First operand 388 states and 510 transitions. Second operand has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2021-12-21 12:35:24,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:24,685 INFO L93 Difference]: Finished difference Result 450 states and 597 transitions. [2021-12-21 12:35:24,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2021-12-21 12:35:24,686 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) Word has length 80 [2021-12-21 12:35:24,686 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:24,687 INFO L225 Difference]: With dead ends: 450 [2021-12-21 12:35:24,687 INFO L226 Difference]: Without dead ends: 439 [2021-12-21 12:35:24,689 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 176 GetRequests, 140 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=248, Invalid=1084, Unknown=0, NotChecked=0, Total=1332 [2021-12-21 12:35:24,690 INFO L933 BasicCegarLoop]: 47 mSDtfsCounter, 94 mSDsluCounter, 499 mSDsCounter, 0 mSdLazyCounter, 614 mSolverCounterSat, 152 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 546 SdHoareTripleChecker+Invalid, 766 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 152 IncrementalHoareTripleChecker+Valid, 614 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.5s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:24,690 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [94 Valid, 546 Invalid, 766 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [152 Valid, 614 Invalid, 0 Unknown, 0 Unchecked, 2.5s Time] [2021-12-21 12:35:24,691 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 439 states. [2021-12-21 12:35:24,772 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 439 to 429. [2021-12-21 12:35:24,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 429 states, 284 states have (on average 1.2288732394366197) internal successors, (349), 292 states have internal predecessors, (349), 111 states have call successors, (111), 33 states have call predecessors, (111), 33 states have return successors, (109), 103 states have call predecessors, (109), 109 states have call successors, (109) [2021-12-21 12:35:24,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 429 states to 429 states and 569 transitions. [2021-12-21 12:35:24,774 INFO L78 Accepts]: Start accepts. Automaton has 429 states and 569 transitions. Word has length 80 [2021-12-21 12:35:24,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:24,775 INFO L470 AbstractCegarLoop]: Abstraction has 429 states and 569 transitions. [2021-12-21 12:35:24,775 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 2.588235294117647) internal successors, (44), 18 states have internal predecessors, (44), 11 states have call successors, (24), 2 states have call predecessors, (24), 2 states have return successors, (22), 9 states have call predecessors, (22), 9 states have call successors, (22) [2021-12-21 12:35:24,775 INFO L276 IsEmpty]: Start isEmpty. Operand 429 states and 569 transitions. [2021-12-21 12:35:24,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 97 [2021-12-21 12:35:24,776 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:24,776 INFO L514 BasicCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:24,809 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:24,991 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:24,992 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:24,992 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:24,992 INFO L85 PathProgramCache]: Analyzing trace with hash 164622435, now seen corresponding path program 4 times [2021-12-21 12:35:24,992 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:24,992 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1775615802] [2021-12-21 12:35:24,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:24,992 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:24,998 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:24,999 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [88005940] [2021-12-21 12:35:24,999 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2021-12-21 12:35:24,999 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:24,999 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:25,002 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:25,002 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2021-12-21 12:35:25,047 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-12-21 12:35:25,048 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 12:35:25,048 INFO L263 TraceCheckSpWp]: Trace formula consists of 224 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-21 12:35:25,050 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:25,160 INFO L134 CoverageAnalysis]: Checked inductivity of 251 backedges. 107 proven. 0 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2021-12-21 12:35:25,161 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2021-12-21 12:35:25,161 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:25,161 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1775615802] [2021-12-21 12:35:25,161 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:25,161 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [88005940] [2021-12-21 12:35:25,161 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [88005940] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-21 12:35:25,161 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-21 12:35:25,162 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-21 12:35:25,162 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1832440767] [2021-12-21 12:35:25,162 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-21 12:35:25,162 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-21 12:35:25,162 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:25,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-21 12:35:25,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-21 12:35:25,163 INFO L87 Difference]: Start difference. First operand 429 states and 569 transitions. Second operand has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2021-12-21 12:35:25,308 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:25,308 INFO L93 Difference]: Finished difference Result 656 states and 926 transitions. [2021-12-21 12:35:25,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-21 12:35:25,308 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) Word has length 96 [2021-12-21 12:35:25,309 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:25,310 INFO L225 Difference]: With dead ends: 656 [2021-12-21 12:35:25,310 INFO L226 Difference]: Without dead ends: 491 [2021-12-21 12:35:25,311 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2021-12-21 12:35:25,311 INFO L933 BasicCegarLoop]: 58 mSDtfsCounter, 12 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:25,311 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 186 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:35:25,312 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 491 states. [2021-12-21 12:35:25,370 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 491 to 456. [2021-12-21 12:35:25,371 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 456 states, 301 states have (on average 1.2425249169435215) internal successors, (374), 309 states have internal predecessors, (374), 121 states have call successors, (121), 33 states have call predecessors, (121), 33 states have return successors, (119), 113 states have call predecessors, (119), 119 states have call successors, (119) [2021-12-21 12:35:25,372 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 456 states to 456 states and 614 transitions. [2021-12-21 12:35:25,372 INFO L78 Accepts]: Start accepts. Automaton has 456 states and 614 transitions. Word has length 96 [2021-12-21 12:35:25,373 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:25,373 INFO L470 AbstractCegarLoop]: Abstraction has 456 states and 614 transitions. [2021-12-21 12:35:25,373 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.6) internal successors, (33), 5 states have internal predecessors, (33), 3 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (14), 3 states have call predecessors, (14), 3 states have call successors, (14) [2021-12-21 12:35:25,373 INFO L276 IsEmpty]: Start isEmpty. Operand 456 states and 614 transitions. [2021-12-21 12:35:25,374 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 113 [2021-12-21 12:35:25,374 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:25,374 INFO L514 BasicCegarLoop]: trace histogram [13, 12, 12, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:25,391 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:25,580 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2021-12-21 12:35:25,580 INFO L402 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:25,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:25,580 INFO L85 PathProgramCache]: Analyzing trace with hash -245423741, now seen corresponding path program 1 times [2021-12-21 12:35:25,581 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:25,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1011730509] [2021-12-21 12:35:25,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:25,581 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:25,597 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:25,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1382493933] [2021-12-21 12:35:25,598 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:25,598 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:25,598 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:25,599 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:25,600 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2021-12-21 12:35:25,645 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:35:25,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 308 conjuncts, 15 conjunts are in the unsatisfiable core [2021-12-21 12:35:25,648 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:25,815 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 229 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2021-12-21 12:35:25,815 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:25,973 INFO L134 CoverageAnalysis]: Checked inductivity of 357 backedges. 32 proven. 37 refuted. 0 times theorem prover too weak. 288 trivial. 0 not checked. [2021-12-21 12:35:25,973 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:25,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1011730509] [2021-12-21 12:35:25,973 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:25,973 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1382493933] [2021-12-21 12:35:25,973 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1382493933] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:35:25,973 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:35:25,974 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2021-12-21 12:35:25,974 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [482079022] [2021-12-21 12:35:25,974 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:25,974 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-21 12:35:25,974 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:25,975 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-21 12:35:25,975 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2021-12-21 12:35:25,975 INFO L87 Difference]: Start difference. First operand 456 states and 614 transitions. Second operand has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2021-12-21 12:35:26,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:26,327 INFO L93 Difference]: Finished difference Result 1062 states and 1468 transitions. [2021-12-21 12:35:26,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-21 12:35:26,327 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) Word has length 112 [2021-12-21 12:35:26,328 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:26,331 INFO L225 Difference]: With dead ends: 1062 [2021-12-21 12:35:26,331 INFO L226 Difference]: Without dead ends: 849 [2021-12-21 12:35:26,332 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 209 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=165, Invalid=297, Unknown=0, NotChecked=0, Total=462 [2021-12-21 12:35:26,332 INFO L933 BasicCegarLoop]: 72 mSDtfsCounter, 134 mSDsluCounter, 276 mSDsCounter, 0 mSdLazyCounter, 147 mSolverCounterSat, 77 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 224 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 77 IncrementalHoareTripleChecker+Valid, 147 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:26,333 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [134 Valid, 348 Invalid, 224 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [77 Valid, 147 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:35:26,333 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 849 states. [2021-12-21 12:35:26,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 849 to 833. [2021-12-21 12:35:26,471 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 833 states, 535 states have (on average 1.2018691588785047) internal successors, (643), 548 states have internal predecessors, (643), 228 states have call successors, (228), 69 states have call predecessors, (228), 69 states have return successors, (223), 215 states have call predecessors, (223), 223 states have call successors, (223) [2021-12-21 12:35:26,474 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 833 states to 833 states and 1094 transitions. [2021-12-21 12:35:26,474 INFO L78 Accepts]: Start accepts. Automaton has 833 states and 1094 transitions. Word has length 112 [2021-12-21 12:35:26,475 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:26,475 INFO L470 AbstractCegarLoop]: Abstraction has 833 states and 1094 transitions. [2021-12-21 12:35:26,475 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.785714285714286) internal successors, (67), 14 states have internal predecessors, (67), 8 states have call successors, (33), 6 states have call predecessors, (33), 5 states have return successors, (32), 7 states have call predecessors, (32), 7 states have call successors, (32) [2021-12-21 12:35:26,475 INFO L276 IsEmpty]: Start isEmpty. Operand 833 states and 1094 transitions. [2021-12-21 12:35:26,476 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 116 [2021-12-21 12:35:26,476 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:26,477 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:26,499 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:26,693 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2021-12-21 12:35:26,693 INFO L402 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:26,693 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:26,693 INFO L85 PathProgramCache]: Analyzing trace with hash -1897577373, now seen corresponding path program 1 times [2021-12-21 12:35:26,693 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:26,693 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [500844036] [2021-12-21 12:35:26,693 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:26,693 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:26,702 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:26,706 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [340762140] [2021-12-21 12:35:26,706 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:26,706 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:26,706 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:26,707 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:26,708 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2021-12-21 12:35:26,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:35:26,778 INFO L263 TraceCheckSpWp]: Trace formula consists of 287 conjuncts, 49 conjunts are in the unsatisfiable core [2021-12-21 12:35:26,795 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:27,521 INFO L134 CoverageAnalysis]: Checked inductivity of 455 backedges. 99 proven. 88 refuted. 0 times theorem prover too weak. 268 trivial. 0 not checked. [2021-12-21 12:35:27,521 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:29,739 WARN L860 $PredicateComparison]: unable to prove that (let ((.cse4 (+ |c_ULTIMATE.start_main_~a~0#1| (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~r~0#1|))) (.cse0 (* |c_ULTIMATE.start_main_~y~0#1| (+ |c_ULTIMATE.start_main_~r~0#1| (* (- 1) (* |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|))))) (.cse2 (+ (* (- 1) |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~p~0#1|)) (.cse3 (= |c_ULTIMATE.start_main_~p~0#1| 0))) (and (let ((.cse1 (div .cse4 |c_ULTIMATE.start_main_~p~0#1|))) (or (= |c_ULTIMATE.start_main_~c~0#1| (+ .cse0 (* .cse1 .cse2))) (not (= (+ (* |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|) (* .cse1 |c_ULTIMATE.start_main_~q~0#1|)) |c_ULTIMATE.start_main_~b~0#1|)) .cse3 (not (= (mod .cse4 |c_ULTIMATE.start_main_~p~0#1|) 0)))) (or (not (= .cse4 0)) (let ((.cse6 (= 0 |c_ULTIMATE.start_main_~q~0#1|)) (.cse5 (+ |c_ULTIMATE.start_main_~b~0#1| (* (- 1) |c_ULTIMATE.start_main_~y~0#1| |c_ULTIMATE.start_main_~s~0#1|)))) (and (or (not (= .cse5 0)) (forall ((|ULTIMATE.start_main_~x~0#1| Int)) (= |c_ULTIMATE.start_main_~c~0#1| (+ (* |c_ULTIMATE.start_main_~y~0#1| (+ |c_ULTIMATE.start_main_~r~0#1| (* (- 1) (* |c_ULTIMATE.start_main_~s~0#1| |c_ULTIMATE.start_main_~k~0#1|)))) (* (+ (* (- 1) |c_ULTIMATE.start_main_~k~0#1| |c_ULTIMATE.start_main_~q~0#1|) |c_ULTIMATE.start_main_~p~0#1|) |ULTIMATE.start_main_~x~0#1|)))) (not .cse6)) (or .cse6 (not (= (mod .cse5 |c_ULTIMATE.start_main_~q~0#1|) 0)) (= |c_ULTIMATE.start_main_~c~0#1| (+ .cse0 (* .cse2 (div .cse5 |c_ULTIMATE.start_main_~q~0#1|))))))) (not .cse3)))) is different from true [2021-12-21 12:35:29,740 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:29,740 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [500844036] [2021-12-21 12:35:29,740 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:29,740 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [340762140] [2021-12-21 12:35:29,740 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [340762140] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-21 12:35:29,740 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-21 12:35:29,740 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14] total 14 [2021-12-21 12:35:29,740 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [195289751] [2021-12-21 12:35:29,741 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:29,741 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-21 12:35:29,741 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:29,741 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-21 12:35:29,741 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=251, Unknown=1, NotChecked=32, Total=342 [2021-12-21 12:35:29,741 INFO L87 Difference]: Start difference. First operand 833 states and 1094 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 8 states have call predecessors, (18), 9 states have call successors, (18) [2021-12-21 12:35:30,329 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:30,329 INFO L93 Difference]: Finished difference Result 878 states and 1150 transitions. [2021-12-21 12:35:30,329 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-21 12:35:30,329 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 8 states have call predecessors, (18), 9 states have call successors, (18) Word has length 115 [2021-12-21 12:35:30,330 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:30,333 INFO L225 Difference]: With dead ends: 878 [2021-12-21 12:35:30,333 INFO L226 Difference]: Without dead ends: 876 [2021-12-21 12:35:30,334 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 127 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=81, Invalid=342, Unknown=1, NotChecked=38, Total=462 [2021-12-21 12:35:30,334 INFO L933 BasicCegarLoop]: 53 mSDtfsCounter, 28 mSDsluCounter, 468 mSDsCounter, 0 mSdLazyCounter, 533 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 521 SdHoareTripleChecker+Invalid, 554 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 533 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:30,334 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [36 Valid, 521 Invalid, 554 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 533 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2021-12-21 12:35:30,335 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 876 states. [2021-12-21 12:35:30,476 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 876 to 872. [2021-12-21 12:35:30,478 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 872 states, 558 states have (on average 1.1989247311827957) internal successors, (669), 571 states have internal predecessors, (669), 240 states have call successors, (240), 73 states have call predecessors, (240), 73 states have return successors, (235), 227 states have call predecessors, (235), 235 states have call successors, (235) [2021-12-21 12:35:30,481 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 872 states to 872 states and 1144 transitions. [2021-12-21 12:35:30,481 INFO L78 Accepts]: Start accepts. Automaton has 872 states and 1144 transitions. Word has length 115 [2021-12-21 12:35:30,483 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:30,483 INFO L470 AbstractCegarLoop]: Abstraction has 872 states and 1144 transitions. [2021-12-21 12:35:30,483 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 11 states have internal predecessors, (33), 9 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (18), 8 states have call predecessors, (18), 9 states have call successors, (18) [2021-12-21 12:35:30,483 INFO L276 IsEmpty]: Start isEmpty. Operand 872 states and 1144 transitions. [2021-12-21 12:35:30,484 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 120 [2021-12-21 12:35:30,484 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:30,484 INFO L514 BasicCegarLoop]: trace histogram [15, 14, 14, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:30,501 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:30,701 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2021-12-21 12:35:30,701 INFO L402 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:30,702 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:30,702 INFO L85 PathProgramCache]: Analyzing trace with hash 364386885, now seen corresponding path program 2 times [2021-12-21 12:35:30,702 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:30,702 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [157271313] [2021-12-21 12:35:30,702 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:30,702 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:30,708 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:30,708 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2019245277] [2021-12-21 12:35:30,708 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 12:35:30,708 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:30,708 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:30,728 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:30,750 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2021-12-21 12:35:30,783 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-21 12:35:30,783 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 12:35:30,785 INFO L263 TraceCheckSpWp]: Trace formula consists of 307 conjuncts, 81 conjunts are in the unsatisfiable core [2021-12-21 12:35:30,787 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:31,539 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 106 proven. 112 refuted. 0 times theorem prover too weak. 244 trivial. 0 not checked. [2021-12-21 12:35:31,539 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:31,974 INFO L134 CoverageAnalysis]: Checked inductivity of 462 backedges. 134 proven. 23 refuted. 0 times theorem prover too weak. 305 trivial. 0 not checked. [2021-12-21 12:35:31,975 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:31,975 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [157271313] [2021-12-21 12:35:31,975 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:31,975 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2019245277] [2021-12-21 12:35:31,975 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2019245277] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:35:31,975 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:35:31,975 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 10] total 21 [2021-12-21 12:35:31,975 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [520685231] [2021-12-21 12:35:31,975 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:31,975 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2021-12-21 12:35:31,975 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:31,976 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2021-12-21 12:35:31,976 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=80, Invalid=340, Unknown=0, NotChecked=0, Total=420 [2021-12-21 12:35:31,976 INFO L87 Difference]: Start difference. First operand 872 states and 1144 transitions. Second operand has 21 states, 17 states have (on average 3.235294117647059) internal successors, (55), 16 states have internal predecessors, (55), 14 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 13 states have call predecessors, (30), 12 states have call successors, (30) [2021-12-21 12:35:34,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:34,672 INFO L93 Difference]: Finished difference Result 965 states and 1235 transitions. [2021-12-21 12:35:34,672 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-21 12:35:34,673 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 17 states have (on average 3.235294117647059) internal successors, (55), 16 states have internal predecessors, (55), 14 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 13 states have call predecessors, (30), 12 states have call successors, (30) Word has length 119 [2021-12-21 12:35:34,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:34,682 INFO L225 Difference]: With dead ends: 965 [2021-12-21 12:35:34,682 INFO L226 Difference]: Without dead ends: 961 [2021-12-21 12:35:34,682 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 250 GetRequests, 218 SyntacticMatches, 4 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 196 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=165, Invalid=705, Unknown=0, NotChecked=0, Total=870 [2021-12-21 12:35:34,683 INFO L933 BasicCegarLoop]: 58 mSDtfsCounter, 99 mSDsluCounter, 376 mSDsCounter, 0 mSdLazyCounter, 526 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 104 SdHoareTripleChecker+Valid, 434 SdHoareTripleChecker+Invalid, 683 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 526 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.4s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:34,683 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [104 Valid, 434 Invalid, 683 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 526 Invalid, 0 Unknown, 0 Unchecked, 2.4s Time] [2021-12-21 12:35:34,684 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 961 states. [2021-12-21 12:35:34,836 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 961 to 955. [2021-12-21 12:35:34,837 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 955 states, 616 states have (on average 1.1834415584415585) internal successors, (729), 628 states have internal predecessors, (729), 249 states have call successors, (249), 90 states have call predecessors, (249), 89 states have return successors, (244), 236 states have call predecessors, (244), 244 states have call successors, (244) [2021-12-21 12:35:34,840 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 955 states to 955 states and 1222 transitions. [2021-12-21 12:35:34,840 INFO L78 Accepts]: Start accepts. Automaton has 955 states and 1222 transitions. Word has length 119 [2021-12-21 12:35:34,840 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:34,840 INFO L470 AbstractCegarLoop]: Abstraction has 955 states and 1222 transitions. [2021-12-21 12:35:34,841 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 17 states have (on average 3.235294117647059) internal successors, (55), 16 states have internal predecessors, (55), 14 states have call successors, (31), 2 states have call predecessors, (31), 2 states have return successors, (30), 13 states have call predecessors, (30), 12 states have call successors, (30) [2021-12-21 12:35:34,841 INFO L276 IsEmpty]: Start isEmpty. Operand 955 states and 1222 transitions. [2021-12-21 12:35:34,842 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2021-12-21 12:35:34,842 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:34,842 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:34,875 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Ended with exit code 0 [2021-12-21 12:35:35,076 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:35,077 INFO L402 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:35,077 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:35,077 INFO L85 PathProgramCache]: Analyzing trace with hash -1036292276, now seen corresponding path program 1 times [2021-12-21 12:35:35,077 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:35,077 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1848022941] [2021-12-21 12:35:35,077 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:35,078 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:35,084 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:35,084 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1753705148] [2021-12-21 12:35:35,084 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:35,084 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:35,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:35,090 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:35,117 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2021-12-21 12:35:35,155 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-21 12:35:35,156 INFO L263 TraceCheckSpWp]: Trace formula consists of 325 conjuncts, 15 conjunts are in the unsatisfiable core [2021-12-21 12:35:35,158 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:35,310 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 434 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2021-12-21 12:35:35,311 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:35,507 INFO L134 CoverageAnalysis]: Checked inductivity of 586 backedges. 32 proven. 50 refuted. 0 times theorem prover too weak. 504 trivial. 0 not checked. [2021-12-21 12:35:35,507 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:35,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1848022941] [2021-12-21 12:35:35,507 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:35,507 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1753705148] [2021-12-21 12:35:35,507 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1753705148] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:35:35,508 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:35:35,508 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 10] total 14 [2021-12-21 12:35:35,508 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1171731223] [2021-12-21 12:35:35,508 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:35,509 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-21 12:35:35,509 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:35,510 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-21 12:35:35,510 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2021-12-21 12:35:35,510 INFO L87 Difference]: Start difference. First operand 955 states and 1222 transitions. Second operand has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2021-12-21 12:35:35,811 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-21 12:35:35,811 INFO L93 Difference]: Finished difference Result 993 states and 1260 transitions. [2021-12-21 12:35:35,812 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2021-12-21 12:35:35,812 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) Word has length 129 [2021-12-21 12:35:35,812 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-21 12:35:35,815 INFO L225 Difference]: With dead ends: 993 [2021-12-21 12:35:35,815 INFO L226 Difference]: Without dead ends: 973 [2021-12-21 12:35:35,816 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 264 GetRequests, 243 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=166, Invalid=296, Unknown=0, NotChecked=0, Total=462 [2021-12-21 12:35:35,816 INFO L933 BasicCegarLoop]: 70 mSDtfsCounter, 101 mSDsluCounter, 246 mSDsCounter, 0 mSdLazyCounter, 219 mSolverCounterSat, 62 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 316 SdHoareTripleChecker+Invalid, 281 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 62 IncrementalHoareTripleChecker+Valid, 219 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-21 12:35:35,816 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [101 Valid, 316 Invalid, 281 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [62 Valid, 219 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-21 12:35:35,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 973 states. [2021-12-21 12:35:35,964 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 973 to 967. [2021-12-21 12:35:35,966 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 967 states, 628 states have (on average 1.164012738853503) internal successors, (731), 640 states have internal predecessors, (731), 249 states have call successors, (249), 90 states have call predecessors, (249), 89 states have return successors, (244), 236 states have call predecessors, (244), 244 states have call successors, (244) [2021-12-21 12:35:35,968 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 967 states to 967 states and 1224 transitions. [2021-12-21 12:35:35,969 INFO L78 Accepts]: Start accepts. Automaton has 967 states and 1224 transitions. Word has length 129 [2021-12-21 12:35:35,969 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-21 12:35:35,969 INFO L470 AbstractCegarLoop]: Abstraction has 967 states and 1224 transitions. [2021-12-21 12:35:35,969 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.142857142857143) internal successors, (72), 14 states have internal predecessors, (72), 10 states have call successors, (41), 7 states have call predecessors, (41), 6 states have return successors, (40), 9 states have call predecessors, (40), 9 states have call successors, (40) [2021-12-21 12:35:35,969 INFO L276 IsEmpty]: Start isEmpty. Operand 967 states and 1224 transitions. [2021-12-21 12:35:35,970 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 131 [2021-12-21 12:35:35,970 INFO L506 BasicCegarLoop]: Found error trace [2021-12-21 12:35:35,971 INFO L514 BasicCegarLoop]: trace histogram [17, 16, 16, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-21 12:35:36,005 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Forceful destruction successful, exit code 0 [2021-12-21 12:35:36,183 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:36,183 INFO L402 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-21 12:35:36,184 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-21 12:35:36,184 INFO L85 PathProgramCache]: Analyzing trace with hash -2066876172, now seen corresponding path program 2 times [2021-12-21 12:35:36,184 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-21 12:35:36,184 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1217267583] [2021-12-21 12:35:36,184 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-21 12:35:36,184 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-21 12:35:36,190 ERROR L247 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2021-12-21 12:35:36,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1545711189] [2021-12-21 12:35:36,190 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-21 12:35:36,190 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-21 12:35:36,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-21 12:35:36,194 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-12-21 12:35:36,195 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2021-12-21 12:35:36,260 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-21 12:35:36,260 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-21 12:35:36,262 INFO L263 TraceCheckSpWp]: Trace formula consists of 327 conjuncts, 80 conjunts are in the unsatisfiable core [2021-12-21 12:35:36,264 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-21 12:35:37,726 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 147 proven. 111 refuted. 0 times theorem prover too weak. 330 trivial. 0 not checked. [2021-12-21 12:35:37,726 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-21 12:35:39,439 INFO L134 CoverageAnalysis]: Checked inductivity of 588 backedges. 156 proven. 12 refuted. 0 times theorem prover too weak. 420 trivial. 0 not checked. [2021-12-21 12:35:39,440 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-21 12:35:39,440 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1217267583] [2021-12-21 12:35:39,440 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2021-12-21 12:35:39,440 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1545711189] [2021-12-21 12:35:39,440 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1545711189] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-21 12:35:39,440 INFO L186 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2021-12-21 12:35:39,440 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 12] total 30 [2021-12-21 12:35:39,440 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1405149667] [2021-12-21 12:35:39,440 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2021-12-21 12:35:39,440 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 30 states [2021-12-21 12:35:39,440 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-21 12:35:39,441 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 30 interpolants. [2021-12-21 12:35:39,441 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=730, Unknown=0, NotChecked=0, Total=870 [2021-12-21 12:35:39,441 INFO L87 Difference]: Start difference. First operand 967 states and 1224 transitions. Second operand has 30 states, 24 states have (on average 2.375) internal successors, (57), 21 states have internal predecessors, (57), 15 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (31), 13 states have call predecessors, (31), 13 states have call successors, (31) [2021-12-21 12:35:44,002 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.76s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers []