/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound10.i -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 06:56:57,481 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 06:56:57,483 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 06:56:57,541 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 06:56:57,542 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 06:56:57,543 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 06:56:57,546 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 06:56:57,549 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 06:56:57,551 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 06:56:57,555 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 06:56:57,556 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 06:56:57,558 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 06:56:57,558 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 06:56:57,561 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 06:56:57,565 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 06:56:57,569 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 06:56:57,569 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 06:56:57,570 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 06:56:57,573 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 06:56:57,580 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 06:56:57,582 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 06:56:57,584 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 06:56:57,585 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 06:56:57,585 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 06:56:57,587 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 06:56:57,594 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 06:56:57,594 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 06:56:57,595 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 06:56:57,595 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 06:56:57,596 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 06:56:57,597 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 06:56:57,598 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 06:56:57,599 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 06:56:57,600 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 06:56:57,601 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 06:56:57,601 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 06:56:57,601 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 06:56:57,602 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 06:56:57,602 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 06:56:57,602 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 06:56:57,603 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 06:56:57,605 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 06:56:57,605 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-05 06:56:57,635 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 06:56:57,636 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 06:56:57,637 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-05 06:56:57,637 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-05 06:56:57,638 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-05 06:56:57,638 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-05 06:56:57,638 INFO L138 SettingsManager]: * Use SBE=true [2022-04-05 06:56:57,639 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 06:56:57,639 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 06:56:57,640 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 06:56:57,641 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 06:56:57,641 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 06:56:57,641 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 06:56:57,641 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 06:56:57,641 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 06:56:57,641 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-05 06:56:57,642 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-05 06:56:57,644 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 06:56:57,644 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-05 06:56:57,861 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 06:56:57,880 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 06:56:57,882 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 06:56:57,883 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 06:56:57,884 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 06:56:57,885 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound10.i [2022-04-05 06:56:57,942 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdfd58f49/a34c801aca26415083c19be6f2eb601f/FLAG64070ba28 [2022-04-05 06:56:58,318 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 06:56:58,318 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound10.i [2022-04-05 06:56:58,328 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdfd58f49/a34c801aca26415083c19be6f2eb601f/FLAG64070ba28 [2022-04-05 06:56:58,342 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bdfd58f49/a34c801aca26415083c19be6f2eb601f [2022-04-05 06:56:58,344 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 06:56:58,345 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 06:56:58,349 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 06:56:58,349 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 06:56:58,353 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 06:56:58,353 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,355 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@47cd2daf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58, skipping insertion in model container [2022-04-05 06:56:58,355 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,365 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 06:56:58,383 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 06:56:58,533 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound10.i[951,964] [2022-04-05 06:56:58,550 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 06:56:58,556 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 06:56:58,567 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound10.i[951,964] [2022-04-05 06:56:58,571 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 06:56:58,582 INFO L208 MainTranslator]: Completed translation [2022-04-05 06:56:58,582 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58 WrapperNode [2022-04-05 06:56:58,582 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 06:56:58,583 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 06:56:58,584 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 06:56:58,584 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 06:56:58,599 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,599 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,607 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,608 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,613 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,617 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,619 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,620 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 06:56:58,621 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 06:56:58,621 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 06:56:58,621 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 06:56:58,623 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,633 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 06:56:58,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:56:58,654 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) [2022-04-05 06:56:58,663 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 [2022-04-05 06:56:58,682 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 06:56:58,683 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 06:56:58,683 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 06:56:58,683 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 06:56:58,683 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 06:56:58,683 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_perror_fail [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure __assert [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 06:56:58,684 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 06:56:58,685 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 06:56:58,686 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 06:56:58,741 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 06:56:58,742 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 06:56:58,853 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 06:56:58,859 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 06:56:58,859 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 06:56:58,861 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:56:58 BoogieIcfgContainer [2022-04-05 06:56:58,862 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 06:56:58,862 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 06:56:58,863 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 06:56:58,864 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 06:56:58,867 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:56:58" (1/1) ... [2022-04-05 06:56:58,869 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-05 06:56:58,884 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 06:56:58 BasicIcfg [2022-04-05 06:56:58,885 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 06:56:58,886 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 06:56:58,887 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 06:56:58,889 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 06:56:58,890 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 06:56:58" (1/4) ... [2022-04-05 06:56:58,890 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b874b4b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 06:56:58, skipping insertion in model container [2022-04-05 06:56:58,891 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 06:56:58" (2/4) ... [2022-04-05 06:56:58,891 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b874b4b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 06:56:58, skipping insertion in model container [2022-04-05 06:56:58,891 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 06:56:58" (3/4) ... [2022-04-05 06:56:58,891 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@b874b4b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 06:56:58, skipping insertion in model container [2022-04-05 06:56:58,891 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 06:56:58" (4/4) ... [2022-04-05 06:56:58,892 INFO L111 eAbstractionObserver]: Analyzing ICFG divbin2_unwindbound10.iqvasr [2022-04-05 06:56:58,897 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-05 06:56:58,898 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 06:56:58,971 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 06:56:58,994 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-05 06:56:58,994 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 06:56:59,030 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-05 06:56:59,035 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-04-05 06:56:59,035 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:56:59,036 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:56:59,036 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:56:59,041 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:56:59,041 INFO L85 PathProgramCache]: Analyzing trace with hash 2097950667, now seen corresponding path program 1 times [2022-04-05 06:56:59,051 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:56:59,053 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [926724007] [2022-04-05 06:56:59,053 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:56:59,054 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:56:59,168 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:56:59,263 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:56:59,267 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:56:59,282 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:56:59,283 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:56:59,283 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [926724007] [2022-04-05 06:56:59,284 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [926724007] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:56:59,284 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:56:59,284 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 06:56:59,289 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1506703775] [2022-04-05 06:56:59,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:56:59,294 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 06:56:59,294 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:56:59,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 06:56:59,329 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:56:59,331 INFO L87 Difference]: Start difference. First operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:56:59,421 INFO L93 Difference]: Finished difference Result 44 states and 60 transitions. [2022-04-05 06:56:59,425 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 06:56:59,427 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-04-05 06:56:59,427 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:56:59,438 INFO L225 Difference]: With dead ends: 44 [2022-04-05 06:56:59,439 INFO L226 Difference]: Without dead ends: 22 [2022-04-05 06:56:59,443 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:56:59,447 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 06:56:59,448 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 34 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 06:56:59,467 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2022-04-05 06:56:59,494 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2022-04-05 06:56:59,495 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:56:59,497 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 26 transitions. [2022-04-05 06:56:59,498 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 26 transitions. Word has length 12 [2022-04-05 06:56:59,499 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:56:59,499 INFO L478 AbstractCegarLoop]: Abstraction has 21 states and 26 transitions. [2022-04-05 06:56:59,500 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,500 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 26 transitions. [2022-04-05 06:56:59,501 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-04-05 06:56:59,501 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:56:59,502 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:56:59,503 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 06:56:59,503 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:56:59,506 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:56:59,506 INFO L85 PathProgramCache]: Analyzing trace with hash 923003056, now seen corresponding path program 1 times [2022-04-05 06:56:59,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:56:59,507 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [268391798] [2022-04-05 06:56:59,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:56:59,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:56:59,532 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:56:59,594 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 06:56:59,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:56:59,619 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:56:59,620 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:56:59,621 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [268391798] [2022-04-05 06:56:59,621 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [268391798] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:56:59,621 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:56:59,621 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-05 06:56:59,621 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1798891090] [2022-04-05 06:56:59,622 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:56:59,623 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 06:56:59,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:56:59,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 06:56:59,626 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:56:59,626 INFO L87 Difference]: Start difference. First operand 21 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:56:59,711 INFO L93 Difference]: Finished difference Result 35 states and 44 transitions. [2022-04-05 06:56:59,712 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 06:56:59,712 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-04-05 06:56:59,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:56:59,713 INFO L225 Difference]: With dead ends: 35 [2022-04-05 06:56:59,713 INFO L226 Difference]: Without dead ends: 23 [2022-04-05 06:56:59,714 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 06:56:59,715 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 06:56:59,715 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 53 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 06:56:59,716 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-04-05 06:56:59,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-04-05 06:56:59,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:56:59,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 28 transitions. [2022-04-05 06:56:59,722 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 28 transitions. Word has length 14 [2022-04-05 06:56:59,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:56:59,722 INFO L478 AbstractCegarLoop]: Abstraction has 23 states and 28 transitions. [2022-04-05 06:56:59,722 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,722 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 28 transitions. [2022-04-05 06:56:59,723 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-04-05 06:56:59,723 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:56:59,723 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:56:59,723 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-05 06:56:59,723 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:56:59,725 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:56:59,725 INFO L85 PathProgramCache]: Analyzing trace with hash 1207414063, now seen corresponding path program 1 times [2022-04-05 06:56:59,725 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:56:59,725 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [494967716] [2022-04-05 06:56:59,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:56:59,726 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:56:59,739 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:56:59,739 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [992239132] [2022-04-05 06:56:59,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:56:59,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:56:59,740 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:56:59,741 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) [2022-04-05 06:56:59,743 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-05 06:56:59,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:56:59,802 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 06:56:59,807 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:56:59,888 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:56:59,889 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:56:59,889 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:56:59,889 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [494967716] [2022-04-05 06:56:59,889 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:56:59,890 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [992239132] [2022-04-05 06:56:59,890 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [992239132] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:56:59,890 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:56:59,890 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 06:56:59,890 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1425603675] [2022-04-05 06:56:59,890 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:56:59,891 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 06:56:59,891 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:56:59,892 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 06:56:59,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:56:59,892 INFO L87 Difference]: Start difference. First operand 23 states and 28 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:56:59,910 INFO L93 Difference]: Finished difference Result 34 states and 40 transitions. [2022-04-05 06:56:59,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 06:56:59,911 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-04-05 06:56:59,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:56:59,912 INFO L225 Difference]: With dead ends: 34 [2022-04-05 06:56:59,912 INFO L226 Difference]: Without dead ends: 27 [2022-04-05 06:56:59,913 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-04-05 06:56:59,914 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 3 mSDsluCounter, 43 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 66 SdHoareTripleChecker+Invalid, 14 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:56:59,915 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 66 Invalid, 14 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 06:56:59,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-05 06:56:59,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-04-05 06:56:59,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:56:59,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2022-04-05 06:56:59,920 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 15 [2022-04-05 06:56:59,920 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:56:59,920 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2022-04-05 06:56:59,920 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:56:59,920 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2022-04-05 06:56:59,921 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-04-05 06:56:59,921 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:56:59,921 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:56:59,950 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:00,143 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:00,144 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:00,144 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:00,144 INFO L85 PathProgramCache]: Analyzing trace with hash 1208546121, now seen corresponding path program 1 times [2022-04-05 06:57:00,145 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:00,145 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2134087140] [2022-04-05 06:57:00,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:00,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:00,157 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:00,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1087995875] [2022-04-05 06:57:00,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:00,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:00,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:00,164 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) [2022-04-05 06:57:00,167 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-05 06:57:00,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:00,234 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 06:57:00,235 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:00,423 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:00,423 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:57:00,423 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:00,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2134087140] [2022-04-05 06:57:00,423 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:00,424 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1087995875] [2022-04-05 06:57:00,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1087995875] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:57:00,429 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:57:00,429 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 06:57:00,430 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1088858882] [2022-04-05 06:57:00,430 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:57:00,430 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 06:57:00,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:00,431 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 06:57:00,431 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-04-05 06:57:00,431 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:57:00,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:00,532 INFO L93 Difference]: Finished difference Result 35 states and 42 transitions. [2022-04-05 06:57:00,534 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 06:57:00,534 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-04-05 06:57:00,534 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:00,535 INFO L225 Difference]: With dead ends: 35 [2022-04-05 06:57:00,535 INFO L226 Difference]: Without dead ends: 32 [2022-04-05 06:57:00,536 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-04-05 06:57:00,536 INFO L913 BasicCegarLoop]: 21 mSDtfsCounter, 10 mSDsluCounter, 54 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 75 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:00,537 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 75 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 06:57:00,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-04-05 06:57:00,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-04-05 06:57:00,542 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 06:57:00,543 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2022-04-05 06:57:00,544 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 15 [2022-04-05 06:57:00,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:00,544 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2022-04-05 06:57:00,544 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:57:00,544 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2022-04-05 06:57:00,545 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-05 06:57:00,545 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:00,545 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:00,572 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:00,763 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-04-05 06:57:00,764 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:00,764 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:00,764 INFO L85 PathProgramCache]: Analyzing trace with hash 1227316531, now seen corresponding path program 1 times [2022-04-05 06:57:00,764 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:00,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1360398822] [2022-04-05 06:57:00,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:00,765 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:00,777 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:00,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [122324895] [2022-04-05 06:57:00,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:00,777 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:00,778 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:00,780 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) [2022-04-05 06:57:00,782 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-05 06:57:00,817 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:00,818 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 06:57:00,820 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:00,888 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:00,889 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:57:01,010 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:01,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:01,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1360398822] [2022-04-05 06:57:01,010 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:01,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [122324895] [2022-04-05 06:57:01,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [122324895] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:57:01,011 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:57:01,011 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-05 06:57:01,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [89333664] [2022-04-05 06:57:01,011 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:57:01,011 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-05 06:57:01,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:01,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-05 06:57:01,012 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-05 06:57:01,012 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:01,089 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:01,089 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-04-05 06:57:01,090 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 06:57:01,090 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-05 06:57:01,090 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:01,094 INFO L225 Difference]: With dead ends: 66 [2022-04-05 06:57:01,094 INFO L226 Difference]: Without dead ends: 54 [2022-04-05 06:57:01,096 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-04-05 06:57:01,099 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 30 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 125 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:01,099 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 125 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 06:57:01,103 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-04-05 06:57:01,110 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 40. [2022-04-05 06:57:01,110 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 06:57:01,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2022-04-05 06:57:01,111 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 17 [2022-04-05 06:57:01,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:01,111 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2022-04-05 06:57:01,112 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:01,112 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2022-04-05 06:57:01,112 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-05 06:57:01,112 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:01,113 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:01,138 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:01,315 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:01,315 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:01,316 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:01,316 INFO L85 PathProgramCache]: Analyzing trace with hash 2051197196, now seen corresponding path program 1 times [2022-04-05 06:57:01,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:01,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1006074298] [2022-04-05 06:57:01,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:01,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:01,328 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:01,329 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2002175790] [2022-04-05 06:57:01,329 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:01,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:01,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:01,330 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) [2022-04-05 06:57:01,331 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-05 06:57:01,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:01,366 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 06:57:01,367 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:01,448 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:01,449 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:57:01,534 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:01,534 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:01,534 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1006074298] [2022-04-05 06:57:01,534 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:01,535 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2002175790] [2022-04-05 06:57:01,535 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2002175790] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:57:01,535 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:57:01,535 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-04-05 06:57:01,535 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1183193321] [2022-04-05 06:57:01,535 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:57:01,536 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 06:57:01,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:01,536 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 06:57:01,536 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-04-05 06:57:01,537 INFO L87 Difference]: Start difference. First operand 40 states and 48 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:01,640 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:01,640 INFO L93 Difference]: Finished difference Result 91 states and 112 transitions. [2022-04-05 06:57:01,641 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 06:57:01,641 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-05 06:57:01,641 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:01,642 INFO L225 Difference]: With dead ends: 91 [2022-04-05 06:57:01,642 INFO L226 Difference]: Without dead ends: 84 [2022-04-05 06:57:01,643 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2022-04-05 06:57:01,643 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 81 mSDsluCounter, 136 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 81 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 76 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:01,644 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [81 Valid, 163 Invalid, 76 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 06:57:01,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-04-05 06:57:01,651 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 77. [2022-04-05 06:57:01,652 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 59 states have (on average 1.3728813559322033) internal successors, (81), 63 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-05 06:57:01,653 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 98 transitions. [2022-04-05 06:57:01,653 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 98 transitions. Word has length 18 [2022-04-05 06:57:01,653 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:01,653 INFO L478 AbstractCegarLoop]: Abstraction has 77 states and 98 transitions. [2022-04-05 06:57:01,654 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:01,654 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 98 transitions. [2022-04-05 06:57:01,654 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-05 06:57:01,654 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:01,654 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:01,679 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:01,875 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:01,876 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:01,876 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:01,876 INFO L85 PathProgramCache]: Analyzing trace with hash 2052329254, now seen corresponding path program 1 times [2022-04-05 06:57:01,876 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:01,876 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [865833691] [2022-04-05 06:57:01,876 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:01,877 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:01,887 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:01,887 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [29453526] [2022-04-05 06:57:01,887 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:01,887 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:01,888 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:01,892 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) [2022-04-05 06:57:01,893 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-05 06:57:01,941 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:01,943 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 06:57:01,944 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:02,063 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:02,064 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:57:02,265 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:02,265 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:02,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [865833691] [2022-04-05 06:57:02,265 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:02,265 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [29453526] [2022-04-05 06:57:02,265 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [29453526] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 06:57:02,265 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 06:57:02,266 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2022-04-05 06:57:02,266 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [807706929] [2022-04-05 06:57:02,266 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:57:02,266 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 06:57:02,266 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:02,267 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 06:57:02,267 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2022-04-05 06:57:02,267 INFO L87 Difference]: Start difference. First operand 77 states and 98 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:57:02,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:02,297 INFO L93 Difference]: Finished difference Result 110 states and 135 transitions. [2022-04-05 06:57:02,301 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 06:57:02,301 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2022-04-05 06:57:02,302 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:02,305 INFO L225 Difference]: With dead ends: 110 [2022-04-05 06:57:02,305 INFO L226 Difference]: Without dead ends: 108 [2022-04-05 06:57:02,305 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-04-05 06:57:02,306 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 11 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 17 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:02,307 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 98 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 17 Unchecked, 0.0s Time] [2022-04-05 06:57:02,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-04-05 06:57:02,324 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 107. [2022-04-05 06:57:02,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 81 states have (on average 1.2839506172839505) internal successors, (104), 89 states have internal predecessors, (104), 15 states have call successors, (15), 11 states have call predecessors, (15), 10 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 06:57:02,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 129 transitions. [2022-04-05 06:57:02,327 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 129 transitions. Word has length 18 [2022-04-05 06:57:02,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:02,327 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 129 transitions. [2022-04-05 06:57:02,327 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 06:57:02,327 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 129 transitions. [2022-04-05 06:57:02,328 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-05 06:57:02,328 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:02,328 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:02,356 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:02,547 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:02,548 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:02,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:02,548 INFO L85 PathProgramCache]: Analyzing trace with hash 462666167, now seen corresponding path program 1 times [2022-04-05 06:57:02,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:02,548 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838233395] [2022-04-05 06:57:02,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:02,549 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:02,558 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:02,558 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [676931469] [2022-04-05 06:57:02,558 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:02,558 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:02,559 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:02,574 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) [2022-04-05 06:57:02,575 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-05 06:57:02,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:02,611 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-05 06:57:02,613 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:02,677 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:02,677 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 06:57:02,678 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:02,678 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [838233395] [2022-04-05 06:57:02,678 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:02,678 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [676931469] [2022-04-05 06:57:02,678 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [676931469] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 06:57:02,678 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 06:57:02,678 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 06:57:02,678 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1838728353] [2022-04-05 06:57:02,678 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 06:57:02,679 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 06:57:02,679 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:02,679 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 06:57:02,679 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:57:02,680 INFO L87 Difference]: Start difference. First operand 107 states and 129 transitions. Second operand has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:57:02,705 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:02,705 INFO L93 Difference]: Finished difference Result 148 states and 181 transitions. [2022-04-05 06:57:02,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 06:57:02,706 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2022-04-05 06:57:02,706 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:02,708 INFO L225 Difference]: With dead ends: 148 [2022-04-05 06:57:02,709 INFO L226 Difference]: Without dead ends: 93 [2022-04-05 06:57:02,709 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 06:57:02,710 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:02,711 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 42 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 06:57:02,712 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-05 06:57:02,736 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-04-05 06:57:02,736 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 71 states have (on average 1.2816901408450705) internal successors, (91), 77 states have internal predecessors, (91), 13 states have call successors, (13), 10 states have call predecessors, (13), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 06:57:02,737 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 112 transitions. [2022-04-05 06:57:02,738 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 112 transitions. Word has length 24 [2022-04-05 06:57:02,738 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:02,738 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 112 transitions. [2022-04-05 06:57:02,738 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-05 06:57:02,738 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 112 transitions. [2022-04-05 06:57:02,739 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-05 06:57:02,739 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:02,739 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:02,767 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:02,964 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:02,965 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:02,965 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:02,965 INFO L85 PathProgramCache]: Analyzing trace with hash 1651364104, now seen corresponding path program 1 times [2022-04-05 06:57:02,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:02,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1498872560] [2022-04-05 06:57:02,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:02,966 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:02,976 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:02,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2132722266] [2022-04-05 06:57:02,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:02,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:02,977 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:02,978 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) [2022-04-05 06:57:02,980 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-05 06:57:03,013 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:03,014 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-04-05 06:57:03,016 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:03,088 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-05 06:57:03,088 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:57:03,187 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-04-05 06:57:03,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:57:03,187 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1498872560] [2022-04-05 06:57:03,187 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:57:03,187 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2132722266] [2022-04-05 06:57:03,188 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2132722266] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:57:03,188 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:57:03,188 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2022-04-05 06:57:03,188 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423630075] [2022-04-05 06:57:03,188 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:57:03,188 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 06:57:03,189 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:57:03,189 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 06:57:03,189 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-04-05 06:57:03,189 INFO L87 Difference]: Start difference. First operand 93 states and 112 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:05,245 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:57:07,333 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.09s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:57:07,503 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 06:57:07,503 INFO L93 Difference]: Finished difference Result 108 states and 126 transitions. [2022-04-05 06:57:07,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 06:57:07,504 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-04-05 06:57:07,504 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 06:57:07,505 INFO L225 Difference]: With dead ends: 108 [2022-04-05 06:57:07,505 INFO L226 Difference]: Without dead ends: 88 [2022-04-05 06:57:07,505 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2022-04-05 06:57:07,506 INFO L913 BasicCegarLoop]: 21 mSDtfsCounter, 12 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 3 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.3s IncrementalHoareTripleChecker+Time [2022-04-05 06:57:07,506 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 117 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 54 Invalid, 2 Unknown, 0 Unchecked, 4.3s Time] [2022-04-05 06:57:07,506 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-04-05 06:57:07,512 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-04-05 06:57:07,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 69 states have (on average 1.2318840579710144) internal successors, (85), 73 states have internal predecessors, (85), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 06:57:07,513 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 103 transitions. [2022-04-05 06:57:07,513 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 103 transitions. Word has length 24 [2022-04-05 06:57:07,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 06:57:07,514 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 103 transitions. [2022-04-05 06:57:07,514 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 06:57:07,514 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 103 transitions. [2022-04-05 06:57:07,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-05 06:57:07,515 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 06:57:07,515 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 06:57:07,561 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-05 06:57:07,735 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:07,736 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 06:57:07,736 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 06:57:07,736 INFO L85 PathProgramCache]: Analyzing trace with hash -268589446, now seen corresponding path program 1 times [2022-04-05 06:57:07,736 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 06:57:07,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [650870903] [2022-04-05 06:57:07,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:07,736 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 06:57:07,747 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 06:57:07,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [120294750] [2022-04-05 06:57:07,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 06:57:07,747 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 06:57:07,747 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 06:57:07,748 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) [2022-04-05 06:57:07,776 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-05 06:57:07,818 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 06:57:07,819 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-05 06:57:07,821 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 06:57:08,210 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:57:08,210 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 06:57:57,008 WARN L232 SmtUtils]: Spent 10.62s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 06:58:16,117 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 3 refuted. 3 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 06:58:16,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 06:58:16,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [650870903] [2022-04-05 06:58:16,118 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 06:58:16,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [120294750] [2022-04-05 06:58:16,118 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [120294750] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 06:58:16,118 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 06:58:16,118 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 13 [2022-04-05 06:58:16,119 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1150556736] [2022-04-05 06:58:16,119 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 06:58:16,119 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-05 06:58:16,119 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 06:58:16,119 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-05 06:58:16,120 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=104, Unknown=8, NotChecked=0, Total=156 [2022-04-05 06:58:16,120 INFO L87 Difference]: Start difference. First operand 88 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 06:58:18,267 WARN L833 $PredicateComparison]: unable to prove that (let ((.cse1 (mod c_main_~b~0 4294967296)) (.cse0 (mod c_main_~A~0 4294967296)) (.cse2 (* c_main_~q~0 2))) (and (= .cse0 (mod (+ c_main_~r~0 (* c_main_~b~0 c_main_~q~0)) 4294967296)) (= .cse0 (mod (+ (* (div .cse1 2) .cse2) c_main_~r~0) 4294967296)) (let ((.cse4 (mod (* c_main_~b~0 2) 4294967296)) (.cse3 (mod c_main_~r~0 4294967296))) (or (not (<= .cse1 .cse3)) (= .cse0 (mod (+ (* (div .cse4 2) .cse2) c_main_~r~0) 4294967296)) (<= .cse4 .cse3))))) is different from false [2022-04-05 06:58:20,383 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse1 (mod c_main_~b~0 4294967296)) (.cse0 (mod c_main_~A~0 4294967296)) (.cse2 (* c_main_~q~0 2))) (and (= .cse0 (mod (+ c_main_~r~0 (* c_main_~b~0 c_main_~q~0)) 4294967296)) (= .cse0 (mod (+ (* (div .cse1 2) .cse2) c_main_~r~0) 4294967296)) (let ((.cse4 (mod (* c_main_~b~0 2) 4294967296)) (.cse3 (mod c_main_~r~0 4294967296))) (or (not (<= .cse1 .cse3)) (= .cse0 (mod (+ (* (div .cse4 2) .cse2) c_main_~r~0) 4294967296)) (<= .cse4 .cse3))))) is different from true [2022-04-05 06:58:22,534 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse1 (mod c_main_~b~0 4294967296)) (.cse5 (mod c_main_~r~0 4294967296))) (let ((.cse3 (<= .cse1 .cse5)) (.cse0 (mod c_main_~A~0 4294967296)) (.cse2 (* c_main_~q~0 2))) (and (or (= .cse0 (mod (+ (* (div .cse1 2) .cse2) c_main_~r~0) 4294967296)) .cse3) (let ((.cse4 (mod (* c_main_~b~0 2) 4294967296))) (or (not .cse3) (= .cse0 (mod (+ (* (div .cse4 2) .cse2) c_main_~r~0) 4294967296)) (<= .cse4 .cse5)))))) is different from true [2022-04-05 06:58:24,554 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.02s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:26,709 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:30,973 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:33,119 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:35,245 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:37,391 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:39,503 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:41,624 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:43,765 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:45,884 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:48,009 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:50,130 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:52,279 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:58:54,391 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:24,367 WARN L232 SmtUtils]: Spent 19.15s on a formula simplification that was a NOOP. DAG size: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 06:59:26,380 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:28,547 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:30,694 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:32,843 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:34,998 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:37,122 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:39,244 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:41,359 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:43,481 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 06:59:45,638 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:05,049 WARN L232 SmtUtils]: Spent 12.87s on a formula simplification that was a NOOP. DAG size: 26 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 07:00:07,057 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:09,181 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:11,314 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:13,430 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:15,550 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:17,697 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:19,810 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:21,958 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:24,106 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:26,252 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:28,391 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:30,526 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:32,640 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:34,754 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-04-05 07:00:36,883 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:38,997 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.11s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:41,123 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-05 07:00:41,247 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:00:41,247 INFO L93 Difference]: Finished difference Result 162 states and 194 transitions. [2022-04-05 07:00:41,248 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-04-05 07:00:41,248 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-04-05 07:00:41,248 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:00:41,249 INFO L225 Difference]: With dead ends: 162 [2022-04-05 07:00:41,249 INFO L226 Difference]: Without dead ends: 130 [2022-04-05 07:00:41,250 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 41 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 2 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 87.6s TimeCoverageRelationStatistics Valid=70, Invalid=158, Unknown=20, NotChecked=58, Total=306 [2022-04-05 07:00:41,250 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 32 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 22 mSolverCounterUnsat, 41 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 82.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 166 SdHoareTripleChecker+Invalid, 161 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 41 IncrementalHoareTripleChecker+Unknown, 7 IncrementalHoareTripleChecker+Unchecked, 87.3s IncrementalHoareTripleChecker+Time [2022-04-05 07:00:41,250 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 166 Invalid, 161 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 91 Invalid, 41 Unknown, 7 Unchecked, 87.3s Time] [2022-04-05 07:00:41,251 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-04-05 07:00:41,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 99. [2022-04-05 07:00:41,261 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 78 states have (on average 1.205128205128205) internal successors, (94), 81 states have internal predecessors, (94), 11 states have call successors, (11), 10 states have call predecessors, (11), 9 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-05 07:00:41,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 114 transitions. [2022-04-05 07:00:41,262 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 114 transitions. Word has length 27 [2022-04-05 07:00:41,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:00:41,263 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 114 transitions. [2022-04-05 07:00:41,263 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-04-05 07:00:41,263 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 114 transitions. [2022-04-05 07:00:41,264 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-05 07:00:41,264 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:00:41,264 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:00:41,293 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-05 07:00:41,482 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-05 07:00:41,483 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:00:41,483 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:00:41,483 INFO L85 PathProgramCache]: Analyzing trace with hash 1969058547, now seen corresponding path program 2 times [2022-04-05 07:00:41,483 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:00:41,483 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1071938552] [2022-04-05 07:00:41,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:00:41,484 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:00:41,513 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:00:41,513 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [810245130] [2022-04-05 07:00:41,513 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 07:00:41,513 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:00:41,514 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:00:41,515 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) [2022-04-05 07:00:41,516 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-05 07:00:41,563 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-04-05 07:00:41,564 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 07:00:41,564 INFO L263 TraceCheckSpWp]: Trace formula consists of 72 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 07:00:41,566 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 07:00:41,724 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-05 07:00:41,725 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 07:00:41,725 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 07:00:41,725 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1071938552] [2022-04-05 07:00:41,725 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 07:00:41,725 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [810245130] [2022-04-05 07:00:41,725 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [810245130] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 07:00:41,725 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 07:00:41,725 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 07:00:41,725 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [905114473] [2022-04-05 07:00:41,726 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 07:00:41,726 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 07:00:41,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 07:00:41,726 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 07:00:41,726 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 07:00:41,726 INFO L87 Difference]: Start difference. First operand 99 states and 114 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 07:00:41,814 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 07:00:41,814 INFO L93 Difference]: Finished difference Result 129 states and 147 transitions. [2022-04-05 07:00:41,814 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 07:00:41,814 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 29 [2022-04-05 07:00:41,815 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 07:00:41,815 INFO L225 Difference]: With dead ends: 129 [2022-04-05 07:00:41,816 INFO L226 Difference]: Without dead ends: 126 [2022-04-05 07:00:41,816 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 29 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 07:00:41,816 INFO L913 BasicCegarLoop]: 18 mSDtfsCounter, 8 mSDsluCounter, 44 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 62 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 07:00:41,817 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 62 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 07:00:41,817 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-04-05 07:00:41,826 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 112. [2022-04-05 07:00:41,826 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 87 states have (on average 1.1724137931034482) internal successors, (102), 90 states have internal predecessors, (102), 13 states have call successors, (13), 12 states have call predecessors, (13), 11 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-05 07:00:41,835 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 126 transitions. [2022-04-05 07:00:41,835 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 126 transitions. Word has length 29 [2022-04-05 07:00:41,837 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 07:00:41,837 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 126 transitions. [2022-04-05 07:00:41,837 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-04-05 07:00:41,837 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 126 transitions. [2022-04-05 07:00:41,841 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-04-05 07:00:41,841 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 07:00:41,841 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 07:00:41,873 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-05 07:00:42,067 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:00:42,068 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 07:00:42,068 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 07:00:42,068 INFO L85 PathProgramCache]: Analyzing trace with hash 1111952806, now seen corresponding path program 2 times [2022-04-05 07:00:42,068 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 07:00:42,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [471664437] [2022-04-05 07:00:42,068 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 07:00:42,069 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 07:00:42,082 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 07:00:42,083 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [785238028] [2022-04-05 07:00:42,083 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 07:00:42,083 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 07:00:42,083 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 07:00:42,085 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) [2022-04-05 07:00:42,095 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process