/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/prod4br-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 13:01:35,060 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 13:01:35,074 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 13:01:35,116 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 13:01:35,116 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 13:01:35,118 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 13:01:35,120 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 13:01:35,121 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 13:01:35,122 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 13:01:35,124 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 13:01:35,124 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 13:01:35,125 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 13:01:35,125 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 13:01:35,126 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 13:01:35,127 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 13:01:35,128 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 13:01:35,128 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 13:01:35,129 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 13:01:35,130 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 13:01:35,131 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 13:01:35,132 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 13:01:35,133 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 13:01:35,134 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 13:01:35,134 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 13:01:35,135 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 13:01:35,137 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 13:01:35,137 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 13:01:35,138 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 13:01:35,138 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 13:01:35,139 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 13:01:35,139 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 13:01:35,139 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 13:01:35,140 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 13:01:35,141 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 13:01:35,141 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 13:01:35,142 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 13:01:35,142 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 13:01:35,143 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 13:01:35,143 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 13:01:35,143 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 13:01:35,144 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 13:01:35,149 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 13:01:35,149 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-06 13:01:35,168 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 13:01:35,168 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 13:01:35,168 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-06 13:01:35,169 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-06 13:01:35,169 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-06 13:01:35,169 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-06 13:01:35,169 INFO L138 SettingsManager]: * Use SBE=true [2022-04-06 13:01:35,170 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 13:01:35,170 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 13:01:35,170 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 13:01:35,170 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 13:01:35,170 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 13:01:35,170 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 13:01:35,171 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 13:01:35,171 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 13:01:35,171 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 13:01:35,171 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 13:01:35,171 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 13:01:35,171 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 13:01:35,172 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-06 13:01:35,172 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 13:01:35,173 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-06 13:01:35,173 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-06 13:01:35,173 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 13:01:35,173 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-06 13:01:35,377 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 13:01:35,397 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 13:01:35,399 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 13:01:35,400 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 13:01:35,401 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 13:01:35,403 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound100.c [2022-04-06 13:01:35,453 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8014d258a/c5287e2151c241be8192b4b2a3db7a07/FLAG123725ab5 [2022-04-06 13:01:35,801 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 13:01:35,802 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prod4br-ll_unwindbound100.c [2022-04-06 13:01:35,806 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8014d258a/c5287e2151c241be8192b4b2a3db7a07/FLAG123725ab5 [2022-04-06 13:01:36,221 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8014d258a/c5287e2151c241be8192b4b2a3db7a07 [2022-04-06 13:01:36,223 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 13:01:36,224 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 13:01:36,228 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 13:01:36,228 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 13:01:36,233 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 13:01:36,234 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,235 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@252ea8e5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36, skipping insertion in model container [2022-04-06 13:01:36,235 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,239 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 13:01:36,250 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 13:01:36,385 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/prod4br-ll_unwindbound100.c[524,537] [2022-04-06 13:01:36,416 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 13:01:36,422 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 13:01:36,429 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/prod4br-ll_unwindbound100.c[524,537] [2022-04-06 13:01:36,442 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 13:01:36,452 INFO L208 MainTranslator]: Completed translation [2022-04-06 13:01:36,452 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36 WrapperNode [2022-04-06 13:01:36,452 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 13:01:36,455 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 13:01:36,455 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 13:01:36,455 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 13:01:36,463 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,463 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,468 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,468 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,472 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,475 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,476 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,477 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 13:01:36,478 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 13:01:36,478 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 13:01:36,478 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 13:01:36,479 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,484 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 13:01:36,494 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:36,507 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-06 13:01:36,508 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-06 13:01:36,535 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 13:01:36,535 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 13:01:36,536 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 13:01:36,536 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 13:01:36,536 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 13:01:36,536 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 13:01:36,536 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 13:01:36,536 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 13:01:36,536 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 13:01:36,536 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 13:01:36,537 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 13:01:36,538 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 13:01:36,579 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 13:01:36,580 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 13:01:36,714 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 13:01:36,719 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 13:01:36,720 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 13:01:36,721 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 01:01:36 BoogieIcfgContainer [2022-04-06 13:01:36,721 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 13:01:36,722 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 13:01:36,722 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 13:01:36,724 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 13:01:36,726 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 01:01:36" (1/1) ... [2022-04-06 13:01:36,727 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-06 13:01:36,745 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 01:01:36 BasicIcfg [2022-04-06 13:01:36,745 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 13:01:36,760 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 13:01:36,760 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 13:01:36,762 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 13:01:36,763 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 01:01:36" (1/4) ... [2022-04-06 13:01:36,763 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@555f7e4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 01:01:36, skipping insertion in model container [2022-04-06 13:01:36,763 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 01:01:36" (2/4) ... [2022-04-06 13:01:36,763 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@555f7e4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 01:01:36, skipping insertion in model container [2022-04-06 13:01:36,764 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 01:01:36" (3/4) ... [2022-04-06 13:01:36,764 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@555f7e4d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 01:01:36, skipping insertion in model container [2022-04-06 13:01:36,764 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 01:01:36" (4/4) ... [2022-04-06 13:01:36,765 INFO L111 eAbstractionObserver]: Analyzing ICFG prod4br-ll_unwindbound100.cqvasr [2022-04-06 13:01:36,777 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-06 13:01:36,777 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 13:01:36,810 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 13:01:36,815 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-06 13:01:36,815 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 13:01:36,828 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 13:01:36,836 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 13:01:36,837 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:36,837 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:36,838 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:36,842 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:36,842 INFO L85 PathProgramCache]: Analyzing trace with hash -1119019339, now seen corresponding path program 1 times [2022-04-06 13:01:36,849 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:36,849 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424224824] [2022-04-06 13:01:36,850 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:36,850 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:36,938 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:37,029 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 13:01:37,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:37,040 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 13:01:37,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:37,046 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-06 13:01:37,047 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:37,047 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424224824] [2022-04-06 13:01:37,047 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1424224824] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 13:01:37,047 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 13:01:37,048 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 13:01:37,049 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1617424512] [2022-04-06 13:01:37,049 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:37,053 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 13:01:37,053 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:37,079 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 13:01:37,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 13:01:37,081 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.45) internal successors, (29), 21 states have internal predecessors, (29), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 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-06 13:01:37,151 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:37,151 INFO L93 Difference]: Finished difference Result 56 states and 77 transitions. [2022-04-06 13:01:37,153 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 13:01:37,154 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 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-06 13:01:37,154 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:37,161 INFO L225 Difference]: With dead ends: 56 [2022-04-06 13:01:37,161 INFO L226 Difference]: Without dead ends: 28 [2022-04-06 13:01:37,163 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 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-06 13:01:37,169 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:37,171 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 40 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 13:01:37,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 28 states. [2022-04-06 13:01:37,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 28 to 27. [2022-04-06 13:01:37,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.3529411764705883) internal successors, (23), 18 states have internal predecessors, (23), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 13:01:37,208 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 33 transitions. [2022-04-06 13:01:37,209 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 33 transitions. Word has length 17 [2022-04-06 13:01:37,210 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:37,210 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 33 transitions. [2022-04-06 13:01:37,210 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 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-06 13:01:37,210 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 33 transitions. [2022-04-06 13:01:37,211 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-06 13:01:37,211 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:37,212 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:37,212 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 13:01:37,212 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:37,213 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:37,213 INFO L85 PathProgramCache]: Analyzing trace with hash -496973861, now seen corresponding path program 1 times [2022-04-06 13:01:37,213 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:37,213 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1661906331] [2022-04-06 13:01:37,214 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:37,214 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:37,229 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:37,230 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1731659233] [2022-04-06 13:01:37,230 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:37,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:37,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:37,232 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-06 13:01:37,233 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-06 13:01:37,289 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:37,291 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 13:01:37,295 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:37,370 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-06 13:01:37,370 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 13:01:37,370 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:37,370 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1661906331] [2022-04-06 13:01:37,371 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:37,371 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1731659233] [2022-04-06 13:01:37,375 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1731659233] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 13:01:37,375 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 13:01:37,375 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-04-06 13:01:37,376 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [438298585] [2022-04-06 13:01:37,377 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:37,378 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-04-06 13:01:37,378 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:37,379 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-04-06 13:01:37,380 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 13:01:37,381 INFO L87 Difference]: Start difference. First operand 27 states and 33 transitions. Second operand has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 13:01:37,403 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:37,403 INFO L93 Difference]: Finished difference Result 37 states and 44 transitions. [2022-04-06 13:01:37,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-04-06 13:01:37,405 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 18 [2022-04-06 13:01:37,405 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:37,406 INFO L225 Difference]: With dead ends: 37 [2022-04-06 13:01:37,406 INFO L226 Difference]: Without dead ends: 29 [2022-04-06 13:01:37,406 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-04-06 13:01:37,407 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 0 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:37,407 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 81 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 13:01:37,408 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 29 states. [2022-04-06 13:01:37,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 29 to 29. [2022-04-06 13:01:37,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 29 states, 19 states have (on average 1.3157894736842106) internal successors, (25), 20 states have internal predecessors, (25), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 13:01:37,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 29 states to 29 states and 35 transitions. [2022-04-06 13:01:37,413 INFO L78 Accepts]: Start accepts. Automaton has 29 states and 35 transitions. Word has length 18 [2022-04-06 13:01:37,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:37,413 INFO L478 AbstractCegarLoop]: Abstraction has 29 states and 35 transitions. [2022-04-06 13:01:37,414 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.0) internal successors, (12), 3 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-04-06 13:01:37,414 INFO L276 IsEmpty]: Start isEmpty. Operand 29 states and 35 transitions. [2022-04-06 13:01:37,414 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-04-06 13:01:37,414 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:37,414 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:37,438 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-06 13:01:37,615 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:37,615 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:37,616 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:37,616 INFO L85 PathProgramCache]: Analyzing trace with hash -495871594, now seen corresponding path program 1 times [2022-04-06 13:01:37,616 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:37,616 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [990370045] [2022-04-06 13:01:37,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:37,616 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:37,629 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:37,629 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1864089838] [2022-04-06 13:01:37,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:37,629 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:37,630 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:37,630 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-06 13:01:37,632 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-06 13:01:37,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:37,679 INFO L263 TraceCheckSpWp]: Trace formula consists of 86 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 13:01:37,680 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:37,814 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-06 13:01:37,814 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 13:01:37,814 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:37,814 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [990370045] [2022-04-06 13:01:37,815 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:37,815 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1864089838] [2022-04-06 13:01:37,815 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1864089838] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 13:01:37,815 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 13:01:37,815 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 13:01:37,815 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [724236833] [2022-04-06 13:01:37,815 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:37,816 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 13:01:37,816 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:37,816 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 13:01:37,816 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 13:01:37,816 INFO L87 Difference]: Start difference. First operand 29 states and 35 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 13:01:37,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:37,908 INFO L93 Difference]: Finished difference Result 42 states and 53 transitions. [2022-04-06 13:01:37,909 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 13:01:37,909 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-04-06 13:01:37,910 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:37,910 INFO L225 Difference]: With dead ends: 42 [2022-04-06 13:01:37,910 INFO L226 Difference]: Without dead ends: 40 [2022-04-06 13:01:37,911 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 14 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-06 13:01:37,912 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 9 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:37,913 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 83 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 13:01:37,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 40 states. [2022-04-06 13:01:37,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 40 to 34. [2022-04-06 13:01:37,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.2727272727272727) internal successors, (28), 24 states have internal predecessors, (28), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 4 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 13:01:37,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 40 transitions. [2022-04-06 13:01:37,920 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 40 transitions. Word has length 18 [2022-04-06 13:01:37,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:37,921 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 40 transitions. [2022-04-06 13:01:37,921 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, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 13:01:37,921 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 40 transitions. [2022-04-06 13:01:37,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-04-06 13:01:37,922 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:37,922 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:37,941 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-06 13:01:38,131 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,SelfDestructingSolverStorable2 [2022-04-06 13:01:38,132 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:38,132 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:38,132 INFO L85 PathProgramCache]: Analyzing trace with hash -1025358414, now seen corresponding path program 1 times [2022-04-06 13:01:38,132 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:38,134 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1019983396] [2022-04-06 13:01:38,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:38,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:38,147 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:38,149 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [307745915] [2022-04-06 13:01:38,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:38,149 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:38,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:38,151 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-06 13:01:38,153 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-06 13:01:38,193 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:38,194 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 13:01:38,197 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:38,521 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:38,521 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 13:01:38,764 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:38,764 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:38,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1019983396] [2022-04-06 13:01:38,764 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:38,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [307745915] [2022-04-06 13:01:38,765 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [307745915] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 13:01:38,765 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 13:01:38,765 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 15 [2022-04-06 13:01:38,765 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [438692579] [2022-04-06 13:01:38,765 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 13:01:38,765 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 13:01:38,766 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:38,766 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 13:01:38,766 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=39, Invalid=171, Unknown=0, NotChecked=0, Total=210 [2022-04-06 13:01:38,767 INFO L87 Difference]: Start difference. First operand 34 states and 40 transitions. Second operand has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 13:01:39,024 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:39,024 INFO L93 Difference]: Finished difference Result 55 states and 72 transitions. [2022-04-06 13:01:39,025 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 13:01:39,025 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) Word has length 24 [2022-04-06 13:01:39,025 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:39,027 INFO L225 Difference]: With dead ends: 55 [2022-04-06 13:01:39,027 INFO L226 Difference]: Without dead ends: 53 [2022-04-06 13:01:39,028 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 53 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=71, Invalid=309, Unknown=0, NotChecked=0, Total=380 [2022-04-06 13:01:39,029 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 38 mSDsluCounter, 132 mSDsCounter, 0 mSdLazyCounter, 250 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 283 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 250 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:39,029 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 152 Invalid, 283 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 250 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 13:01:39,030 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2022-04-06 13:01:39,036 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 39. [2022-04-06 13:01:39,036 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 25 states have (on average 1.24) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 4 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 13:01:39,037 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 45 transitions. [2022-04-06 13:01:39,037 INFO L78 Accepts]: Start accepts. Automaton has 39 states and 45 transitions. Word has length 24 [2022-04-06 13:01:39,038 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:39,038 INFO L478 AbstractCegarLoop]: Abstraction has 39 states and 45 transitions. [2022-04-06 13:01:39,038 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 1.9230769230769231) internal successors, (25), 11 states have internal predecessors, (25), 4 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 4 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 13:01:39,038 INFO L276 IsEmpty]: Start isEmpty. Operand 39 states and 45 transitions. [2022-04-06 13:01:39,039 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-06 13:01:39,039 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:39,039 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:39,065 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-06 13:01:39,258 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:39,258 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:39,259 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:39,259 INFO L85 PathProgramCache]: Analyzing trace with hash -2117889998, now seen corresponding path program 1 times [2022-04-06 13:01:39,259 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:39,259 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1470832154] [2022-04-06 13:01:39,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:39,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:39,272 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:39,272 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1278914523] [2022-04-06 13:01:39,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:39,273 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:39,273 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:39,274 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-06 13:01:39,308 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-06 13:01:39,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:39,322 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 13:01:39,324 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:39,378 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:39,378 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 13:01:39,437 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:39,438 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:39,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1470832154] [2022-04-06 13:01:39,438 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:39,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1278914523] [2022-04-06 13:01:39,438 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1278914523] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 13:01:39,438 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 13:01:39,438 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-04-06 13:01:39,439 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [400081365] [2022-04-06 13:01:39,439 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 13:01:39,439 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-04-06 13:01:39,439 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:39,439 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-04-06 13:01:39,440 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-04-06 13:01:39,440 INFO L87 Difference]: Start difference. First operand 39 states and 45 transitions. Second operand has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-06 13:01:39,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:39,515 INFO L93 Difference]: Finished difference Result 103 states and 123 transitions. [2022-04-06 13:01:39,515 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 13:01:39,516 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) Word has length 27 [2022-04-06 13:01:39,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:39,519 INFO L225 Difference]: With dead ends: 103 [2022-04-06 13:01:39,519 INFO L226 Difference]: Without dead ends: 93 [2022-04-06 13:01:39,520 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 47 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-06 13:01:39,521 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 55 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 31 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 144 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 31 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:39,523 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 144 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 31 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 13:01:39,525 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-04-06 13:01:39,549 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 87. [2022-04-06 13:01:39,551 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 60 states have (on average 1.3333333333333333) internal successors, (80), 64 states have internal predecessors, (80), 16 states have call successors, (16), 12 states have call predecessors, (16), 10 states have return successors, (11), 10 states have call predecessors, (11), 11 states have call successors, (11) [2022-04-06 13:01:39,555 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 107 transitions. [2022-04-06 13:01:39,555 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 107 transitions. Word has length 27 [2022-04-06 13:01:39,555 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:39,556 INFO L478 AbstractCegarLoop]: Abstraction has 87 states and 107 transitions. [2022-04-06 13:01:39,556 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (8), 5 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 5 states have call successors, (6) [2022-04-06 13:01:39,556 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 107 transitions. [2022-04-06 13:01:39,556 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-06 13:01:39,556 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:39,557 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, 1, 1, 1] [2022-04-06 13:01:39,581 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-06 13:01:39,780 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:39,780 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:39,781 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:39,781 INFO L85 PathProgramCache]: Analyzing trace with hash -2116787731, now seen corresponding path program 1 times [2022-04-06 13:01:39,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:39,781 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [626551046] [2022-04-06 13:01:39,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:39,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:39,792 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:39,793 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [96284587] [2022-04-06 13:01:39,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:39,793 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:39,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:39,799 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-06 13:01:39,800 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-06 13:01:39,843 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:39,844 INFO L263 TraceCheckSpWp]: Trace formula consists of 112 conjuncts, 34 conjunts are in the unsatisfiable core [2022-04-06 13:01:39,846 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:40,987 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:40,987 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 13:01:42,106 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:42,106 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:42,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [626551046] [2022-04-06 13:01:42,106 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:42,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [96284587] [2022-04-06 13:01:42,107 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [96284587] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 13:01:42,107 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 13:01:42,107 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 17 [2022-04-06 13:01:42,107 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2024494183] [2022-04-06 13:01:42,107 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 13:01:42,107 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-04-06 13:01:42,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:42,108 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-04-06 13:01:42,108 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=49, Invalid=223, Unknown=0, NotChecked=0, Total=272 [2022-04-06 13:01:42,108 INFO L87 Difference]: Start difference. First operand 87 states and 107 transitions. Second operand has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 13:01:44,444 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:44,444 INFO L93 Difference]: Finished difference Result 127 states and 164 transitions. [2022-04-06 13:01:44,445 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 13:01:44,445 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) Word has length 27 [2022-04-06 13:01:44,445 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:44,446 INFO L225 Difference]: With dead ends: 127 [2022-04-06 13:01:44,446 INFO L226 Difference]: Without dead ends: 121 [2022-04-06 13:01:44,447 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 60 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=84, Invalid=378, Unknown=0, NotChecked=0, Total=462 [2022-04-06 13:01:44,447 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 75 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 384 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 451 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 384 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:44,448 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [78 Valid, 187 Invalid, 451 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 384 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2022-04-06 13:01:44,448 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2022-04-06 13:01:44,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 79. [2022-04-06 13:01:44,470 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 57 states have (on average 1.3157894736842106) internal successors, (75), 59 states have internal predecessors, (75), 12 states have call successors, (12), 11 states have call predecessors, (12), 9 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 13:01:44,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 96 transitions. [2022-04-06 13:01:44,471 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 96 transitions. Word has length 27 [2022-04-06 13:01:44,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:44,471 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 96 transitions. [2022-04-06 13:01:44,472 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 1.7647058823529411) internal successors, (30), 14 states have internal predecessors, (30), 5 states have call successors, (7), 2 states have call predecessors, (7), 3 states have return successors, (5), 5 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 13:01:44,472 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 96 transitions. [2022-04-06 13:01:44,473 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2022-04-06 13:01:44,473 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:44,473 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:44,498 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-06 13:01:44,687 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:44,688 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:44,688 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:44,688 INFO L85 PathProgramCache]: Analyzing trace with hash -410392694, now seen corresponding path program 1 times [2022-04-06 13:01:44,688 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:44,688 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1921528410] [2022-04-06 13:01:44,688 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:44,689 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:44,698 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:44,698 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1981172753] [2022-04-06 13:01:44,698 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:44,698 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:44,698 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:44,704 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-06 13:01:44,705 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-06 13:01:44,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:44,740 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 10 conjunts are in the unsatisfiable core [2022-04-06 13:01:44,743 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:44,816 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 13:01:44,816 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 13:01:44,816 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:44,816 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1921528410] [2022-04-06 13:01:44,816 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:44,816 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1981172753] [2022-04-06 13:01:44,817 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1981172753] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 13:01:44,817 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 13:01:44,817 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 13:01:44,817 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1681600265] [2022-04-06 13:01:44,817 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:44,817 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 13:01:44,817 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:44,818 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 13:01:44,818 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=56, Unknown=0, NotChecked=0, Total=72 [2022-04-06 13:01:44,818 INFO L87 Difference]: Start difference. First operand 79 states and 96 transitions. Second operand has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 13:01:44,922 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:44,922 INFO L93 Difference]: Finished difference Result 116 states and 151 transitions. [2022-04-06 13:01:44,923 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 13:01:44,923 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 29 [2022-04-06 13:01:44,923 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:44,924 INFO L225 Difference]: With dead ends: 116 [2022-04-06 13:01:44,924 INFO L226 Difference]: Without dead ends: 104 [2022-04-06 13:01:44,924 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-06 13:01:44,925 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 33 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 121 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 157 SdHoareTripleChecker+Invalid, 130 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 121 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:44,925 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 157 Invalid, 130 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 121 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 13:01:44,926 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2022-04-06 13:01:44,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 99. [2022-04-06 13:01:44,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 74 states have (on average 1.3243243243243243) internal successors, (98), 76 states have internal predecessors, (98), 15 states have call successors, (15), 11 states have call predecessors, (15), 9 states have return successors, (12), 11 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 13:01:44,939 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 125 transitions. [2022-04-06 13:01:44,939 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 125 transitions. Word has length 29 [2022-04-06 13:01:44,939 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:44,939 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 125 transitions. [2022-04-06 13:01:44,939 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.0) internal successors, (16), 7 states have internal predecessors, (16), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-04-06 13:01:44,939 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 125 transitions. [2022-04-06 13:01:44,940 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-06 13:01:44,940 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:44,940 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:44,963 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-06 13:01:45,156 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:45,156 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:45,157 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:45,157 INFO L85 PathProgramCache]: Analyzing trace with hash 159893073, now seen corresponding path program 1 times [2022-04-06 13:01:45,157 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:45,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [156419578] [2022-04-06 13:01:45,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:45,157 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:45,166 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:45,166 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1347698556] [2022-04-06 13:01:45,166 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:45,166 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:45,166 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:45,167 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-06 13:01:45,191 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-06 13:01:45,221 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:45,222 INFO L263 TraceCheckSpWp]: Trace formula consists of 131 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-06 13:01:45,224 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:45,299 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 13:01:45,299 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 13:01:45,299 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:45,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [156419578] [2022-04-06 13:01:45,299 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:45,299 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1347698556] [2022-04-06 13:01:45,300 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1347698556] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 13:01:45,300 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 13:01:45,300 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 13:01:45,300 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302374575] [2022-04-06 13:01:45,300 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:45,300 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 13:01:45,300 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:45,301 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 13:01:45,301 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-04-06 13:01:45,301 INFO L87 Difference]: Start difference. First operand 99 states and 125 transitions. Second operand has 6 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 13:01:45,369 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:45,369 INFO L93 Difference]: Finished difference Result 141 states and 180 transitions. [2022-04-06 13:01:45,370 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 13:01:45,370 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 40 [2022-04-06 13:01:45,370 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:45,371 INFO L225 Difference]: With dead ends: 141 [2022-04-06 13:01:45,371 INFO L226 Difference]: Without dead ends: 129 [2022-04-06 13:01:45,371 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 35 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-06 13:01:45,372 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 7 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 68 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 68 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:45,372 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 141 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 68 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 13:01:45,373 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2022-04-06 13:01:45,386 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 113. [2022-04-06 13:01:45,386 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 85 states have (on average 1.2941176470588236) internal successors, (110), 87 states have internal predecessors, (110), 18 states have call successors, (18), 11 states have call predecessors, (18), 9 states have return successors, (15), 14 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 13:01:45,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 143 transitions. [2022-04-06 13:01:45,387 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 143 transitions. Word has length 40 [2022-04-06 13:01:45,387 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:45,387 INFO L478 AbstractCegarLoop]: Abstraction has 113 states and 143 transitions. [2022-04-06 13:01:45,387 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 4.4) internal successors, (22), 5 states have internal predecessors, (22), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 13:01:45,388 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 143 transitions. [2022-04-06 13:01:45,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2022-04-06 13:01:45,389 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:45,389 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:45,411 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-04-06 13:01:45,603 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:45,603 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:45,604 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:45,604 INFO L85 PathProgramCache]: Analyzing trace with hash -837179280, now seen corresponding path program 1 times [2022-04-06 13:01:45,604 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:45,604 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1089318011] [2022-04-06 13:01:45,604 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:45,604 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:45,612 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:45,613 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1165347777] [2022-04-06 13:01:45,613 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:45,613 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:45,613 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:45,614 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-06 13:01:45,617 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-06 13:01:45,654 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 13:01:45,654 INFO L263 TraceCheckSpWp]: Trace formula consists of 130 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 13:01:45,656 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:45,774 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 13:01:45,798 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 13:01:45,798 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 13:01:45,900 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 13:01:45,901 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:45,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1089318011] [2022-04-06 13:01:45,901 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:45,901 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1165347777] [2022-04-06 13:01:45,901 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1165347777] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 13:01:45,901 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 13:01:45,901 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 11 [2022-04-06 13:01:45,901 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [529903794] [2022-04-06 13:01:45,901 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 13:01:45,902 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 13:01:45,902 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:45,902 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 13:01:45,902 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-04-06 13:01:45,902 INFO L87 Difference]: Start difference. First operand 113 states and 143 transitions. Second operand has 5 states, 4 states have (on average 5.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 13:01:46,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:46,061 INFO L93 Difference]: Finished difference Result 120 states and 149 transitions. [2022-04-06 13:01:46,061 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 13:01:46,061 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 5.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 40 [2022-04-06 13:01:46,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:46,062 INFO L225 Difference]: With dead ends: 120 [2022-04-06 13:01:46,062 INFO L226 Difference]: Without dead ends: 100 [2022-04-06 13:01:46,063 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=106, Unknown=0, NotChecked=0, Total=132 [2022-04-06 13:01:46,063 INFO L913 BasicCegarLoop]: 37 mSDtfsCounter, 5 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:46,064 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 122 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 13:01:46,064 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2022-04-06 13:01:46,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 66. [2022-04-06 13:01:46,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 49 states have (on average 1.2857142857142858) internal successors, (63), 50 states have internal predecessors, (63), 9 states have call successors, (9), 8 states have call predecessors, (9), 7 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 13:01:46,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 79 transitions. [2022-04-06 13:01:46,071 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 79 transitions. Word has length 40 [2022-04-06 13:01:46,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:46,071 INFO L478 AbstractCegarLoop]: Abstraction has 66 states and 79 transitions. [2022-04-06 13:01:46,071 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 5.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 13:01:46,071 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 79 transitions. [2022-04-06 13:01:46,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-04-06 13:01:46,072 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:46,073 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:46,097 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-06 13:01:46,287 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,SelfDestructingSolverStorable8 [2022-04-06 13:01:46,288 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:46,288 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:46,288 INFO L85 PathProgramCache]: Analyzing trace with hash -1169624165, now seen corresponding path program 2 times [2022-04-06 13:01:46,288 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:46,288 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [588443385] [2022-04-06 13:01:46,288 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:46,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:46,297 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:46,297 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1914810950] [2022-04-06 13:01:46,297 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 13:01:46,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:46,298 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:46,298 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-06 13:01:46,300 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-06 13:01:46,343 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 13:01:46,343 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 13:01:46,343 INFO L263 TraceCheckSpWp]: Trace formula consists of 190 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 13:01:46,345 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 13:01:46,468 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 13:01:46,468 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 13:01:46,627 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 8 proven. 38 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 13:01:46,628 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 13:01:46,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [588443385] [2022-04-06 13:01:46,628 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 13:01:46,628 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1914810950] [2022-04-06 13:01:46,628 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1914810950] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 13:01:46,628 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 13:01:46,628 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-06 13:01:46,628 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [23913530] [2022-04-06 13:01:46,628 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 13:01:46,629 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 13:01:46,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 13:01:46,629 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 13:01:46,629 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-04-06 13:01:46,630 INFO L87 Difference]: Start difference. First operand 66 states and 79 transitions. Second operand has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (14), 8 states have call predecessors, (14), 7 states have return successors, (12), 10 states have call predecessors, (12), 11 states have call successors, (12) [2022-04-06 13:01:46,773 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 13:01:46,773 INFO L93 Difference]: Finished difference Result 140 states and 177 transitions. [2022-04-06 13:01:46,774 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-04-06 13:01:46,774 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (14), 8 states have call predecessors, (14), 7 states have return successors, (12), 10 states have call predecessors, (12), 11 states have call successors, (12) Word has length 54 [2022-04-06 13:01:46,774 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 13:01:46,775 INFO L225 Difference]: With dead ends: 140 [2022-04-06 13:01:46,775 INFO L226 Difference]: Without dead ends: 132 [2022-04-06 13:01:46,776 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 95 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-04-06 13:01:46,776 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 153 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 56 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 153 SdHoareTripleChecker+Valid, 248 SdHoareTripleChecker+Invalid, 90 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 56 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 13:01:46,777 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [153 Valid, 248 Invalid, 90 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 56 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 13:01:46,777 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2022-04-06 13:01:46,786 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 132. [2022-04-06 13:01:46,787 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 103 states have (on average 1.3106796116504855) internal successors, (135), 104 states have internal predecessors, (135), 15 states have call successors, (15), 14 states have call predecessors, (15), 13 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 13:01:46,788 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 163 transitions. [2022-04-06 13:01:46,788 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 163 transitions. Word has length 54 [2022-04-06 13:01:46,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 13:01:46,788 INFO L478 AbstractCegarLoop]: Abstraction has 132 states and 163 transitions. [2022-04-06 13:01:46,788 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.857142857142857) internal successors, (68), 14 states have internal predecessors, (68), 12 states have call successors, (14), 8 states have call predecessors, (14), 7 states have return successors, (12), 10 states have call predecessors, (12), 11 states have call successors, (12) [2022-04-06 13:01:46,788 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 163 transitions. [2022-04-06 13:01:46,789 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 109 [2022-04-06 13:01:46,789 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 13:01:46,789 INFO L499 BasicCegarLoop]: trace histogram [11, 11, 10, 10, 10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 13:01:46,812 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Ended with exit code 0 [2022-04-06 13:01:47,007 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-06 13:01:47,008 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 13:01:47,008 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 13:01:47,008 INFO L85 PathProgramCache]: Analyzing trace with hash 93180219, now seen corresponding path program 3 times [2022-04-06 13:01:47,009 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 13:01:47,009 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1367021471] [2022-04-06 13:01:47,009 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 13:01:47,009 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 13:01:47,019 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 13:01:47,019 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1059618958] [2022-04-06 13:01:47,019 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 13:01:47,019 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 13:01:47,019 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 13:01:47,020 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-06 13:01:47,036 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process