/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/prodbin-ll_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 11:34:05,064 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 11:34:05,066 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 11:34:05,101 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 11:34:05,101 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 11:34:05,102 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 11:34:05,104 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 11:34:05,105 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 11:34:05,108 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 11:34:05,108 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 11:34:05,109 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 11:34:05,109 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 11:34:05,110 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 11:34:05,110 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 11:34:05,111 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 11:34:05,111 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 11:34:05,112 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 11:34:05,112 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 11:34:05,113 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 11:34:05,114 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 11:34:05,115 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 11:34:05,118 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 11:34:05,119 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 11:34:05,120 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 11:34:05,120 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 11:34:05,123 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 11:34:05,123 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 11:34:05,123 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 11:34:05,124 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 11:34:05,124 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 11:34:05,125 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 11:34:05,125 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 11:34:05,126 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 11:34:05,126 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 11:34:05,127 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 11:34:05,128 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 11:34:05,128 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 11:34:05,128 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 11:34:05,129 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 11:34:05,129 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 11:34:05,130 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 11:34:05,134 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 11:34:05,135 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-20 11:34:05,162 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 11:34:05,163 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 11:34:05,164 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-20 11:34:05,164 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-20 11:34:05,165 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-20 11:34:05,165 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-20 11:34:05,167 INFO L138 SettingsManager]: * Use SBE=true [2022-03-20 11:34:05,167 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 11:34:05,167 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 11:34:05,168 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 11:34:05,168 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 11:34:05,169 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-20 11:34:05,169 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-20 11:34:05,170 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 11:34:05,170 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-03-20 11:34:05,332 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 11:34:05,361 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 11:34:05,362 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 11:34:05,363 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 11:34:05,364 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 11:34:05,364 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/prodbin-ll_unwindbound20.c [2022-03-20 11:34:05,406 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d305943df/45886369a8c84051a5c0a6581188ba99/FLAGf03acc508 [2022-03-20 11:34:05,846 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 11:34:05,846 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prodbin-ll_unwindbound20.c [2022-03-20 11:34:05,851 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d305943df/45886369a8c84051a5c0a6581188ba99/FLAGf03acc508 [2022-03-20 11:34:05,864 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/d305943df/45886369a8c84051a5c0a6581188ba99 [2022-03-20 11:34:05,866 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 11:34:05,868 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 11:34:05,869 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 11:34:05,876 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 11:34:05,879 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 11:34:05,880 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:34:05" (1/1) ... [2022-03-20 11:34:05,881 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1a4c8e64 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:05, skipping insertion in model container [2022-03-20 11:34:05,881 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 11:34:05" (1/1) ... [2022-03-20 11:34:05,885 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 11:34:05,897 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 11:34:06,041 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/prodbin-ll_unwindbound20.c[537,550] [2022-03-20 11:34:06,053 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 11:34:06,058 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 11:34:06,067 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/prodbin-ll_unwindbound20.c[537,550] [2022-03-20 11:34:06,078 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 11:34:06,087 INFO L208 MainTranslator]: Completed translation [2022-03-20 11:34:06,088 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06 WrapperNode [2022-03-20 11:34:06,089 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 11:34:06,090 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 11:34:06,090 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 11:34:06,090 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 11:34:06,097 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,098 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,103 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,103 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,106 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,108 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,108 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,109 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 11:34:06,110 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 11:34:06,110 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 11:34:06,110 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 11:34:06,110 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,115 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 11:34:06,124 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:06,144 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-03-20 11:34:06,167 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-03-20 11:34:06,170 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 11:34:06,170 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 11:34:06,170 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 11:34:06,170 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 11:34:06,171 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 11:34:06,171 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 11:34:06,171 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 11:34:06,171 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 11:34:06,172 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 11:34:06,173 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 11:34:06,173 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 11:34:06,173 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 11:34:06,217 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 11:34:06,218 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 11:34:06,299 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 11:34:06,302 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 11:34:06,303 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-20 11:34:06,304 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:34:06 BoogieIcfgContainer [2022-03-20 11:34:06,304 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 11:34:06,304 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 11:34:06,304 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 11:34:06,320 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 11:34:06,322 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:34:06" (1/1) ... [2022-03-20 11:34:06,323 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-03-20 11:34:06,333 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 11:34:06 BasicIcfg [2022-03-20 11:34:06,333 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 11:34:06,334 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 11:34:06,334 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 11:34:06,352 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 11:34:06,352 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 11:34:05" (1/4) ... [2022-03-20 11:34:06,353 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b80bdd6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:34:06, skipping insertion in model container [2022-03-20 11:34:06,353 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 11:34:06" (2/4) ... [2022-03-20 11:34:06,353 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b80bdd6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 11:34:06, skipping insertion in model container [2022-03-20 11:34:06,353 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 11:34:06" (3/4) ... [2022-03-20 11:34:06,353 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b80bdd6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 11:34:06, skipping insertion in model container [2022-03-20 11:34:06,354 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 11:34:06" (4/4) ... [2022-03-20 11:34:06,354 INFO L111 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound20.cqvasr [2022-03-20 11:34:06,357 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-20 11:34:06,357 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 11:34:06,406 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 11:34:06,415 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-03-20 11:34:06,415 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 11:34:06,428 INFO L276 IsEmpty]: Start isEmpty. Operand has 30 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-03-20 11:34:06,432 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-20 11:34:06,432 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:06,432 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:34:06,437 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:06,440 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:06,441 INFO L85 PathProgramCache]: Analyzing trace with hash 1957529129, now seen corresponding path program 1 times [2022-03-20 11:34:06,446 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:06,446 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1971664509] [2022-03-20 11:34:06,446 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:06,447 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:06,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:06,543 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 11:34:06,546 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:06,551 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 11:34:06,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:06,555 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:06,556 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:06,556 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1971664509] [2022-03-20 11:34:06,556 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1971664509] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 11:34:06,557 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 11:34:06,557 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 11:34:06,558 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [155631483] [2022-03-20 11:34:06,558 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 11:34:06,560 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 11:34:06,561 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:06,577 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 11:34:06,578 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 11:34:06,579 INFO L87 Difference]: Start difference. First operand has 30 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 5 states have call successors, (5), 4 states have call predecessors, (5), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) 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), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 11:34:06,647 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:06,648 INFO L93 Difference]: Finished difference Result 52 states and 66 transitions. [2022-03-20 11:34:06,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 11:34:06,650 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), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-20 11:34:06,650 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:06,660 INFO L225 Difference]: With dead ends: 52 [2022-03-20 11:34:06,661 INFO L226 Difference]: Without dead ends: 26 [2022-03-20 11:34:06,664 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 6 GetRequests, 5 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-03-20 11:34:06,670 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:06,670 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 35 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 11:34:06,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-03-20 11:34:06,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 25. [2022-03-20 11:34:06,705 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 25 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-20 11:34:06,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2022-03-20 11:34:06,708 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 17 [2022-03-20 11:34:06,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:06,708 INFO L478 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2022-03-20 11:34:06,708 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), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 11:34:06,709 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2022-03-20 11:34:06,709 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 11:34:06,710 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:06,710 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:34:06,710 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 11:34:06,710 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:06,712 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:06,712 INFO L85 PathProgramCache]: Analyzing trace with hash 583261658, now seen corresponding path program 1 times [2022-03-20 11:34:06,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:06,713 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101849931] [2022-03-20 11:34:06,714 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:06,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:06,738 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:06,738 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [235772685] [2022-03-20 11:34:06,739 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:06,739 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:06,739 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:06,752 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-03-20 11:34:06,753 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-03-20 11:34:06,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:06,801 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-20 11:34:06,805 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:06,885 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:06,886 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 11:34:06,886 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:06,886 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101849931] [2022-03-20 11:34:06,886 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:06,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [235772685] [2022-03-20 11:34:06,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [235772685] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 11:34:06,890 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 11:34:06,890 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 11:34:06,890 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [901130217] [2022-03-20 11:34:06,891 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 11:34:06,892 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-20 11:34:06,892 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:06,893 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-20 11:34:06,893 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-20 11:34:06,896 INFO L87 Difference]: Start difference. First operand 25 states and 28 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-03-20 11:34:06,909 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:06,911 INFO L93 Difference]: Finished difference Result 34 states and 37 transitions. [2022-03-20 11:34:06,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-20 11:34:06,912 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-03-20 11:34:06,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:06,913 INFO L225 Difference]: With dead ends: 34 [2022-03-20 11:34:06,913 INFO L226 Difference]: Without dead ends: 27 [2022-03-20 11:34:06,913 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-03-20 11:34:06,914 INFO L913 BasicCegarLoop]: 26 mSDtfsCounter, 0 mSDsluCounter, 40 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 66 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-03-20 11:34:06,914 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 66 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 11:34:06,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-20 11:34:06,918 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-03-20 11:34:06,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-20 11:34:06,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2022-03-20 11:34:06,919 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 18 [2022-03-20 11:34:06,919 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:06,919 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2022-03-20 11:34:06,919 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-03-20 11:34:06,919 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2022-03-20 11:34:06,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 11:34:06,919 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:06,920 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:34:06,940 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-03-20 11:34:07,137 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-03-20 11:34:07,137 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:07,138 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:07,138 INFO L85 PathProgramCache]: Analyzing trace with hash 584363925, now seen corresponding path program 1 times [2022-03-20 11:34:07,138 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:07,138 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [935045930] [2022-03-20 11:34:07,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,138 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:07,157 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:07,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [105293863] [2022-03-20 11:34:07,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:07,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:07,170 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-03-20 11:34:07,183 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-03-20 11:34:07,208 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:07,209 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 11:34:07,211 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:07,291 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:07,291 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 11:34:07,291 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:07,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [935045930] [2022-03-20 11:34:07,291 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:07,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [105293863] [2022-03-20 11:34:07,292 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [105293863] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 11:34:07,292 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 11:34:07,292 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 11:34:07,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1365194951] [2022-03-20 11:34:07,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 11:34:07,292 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 11:34:07,292 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:07,293 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 11:34:07,293 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 11:34:07,293 INFO L87 Difference]: Start difference. First operand 27 states and 30 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-03-20 11:34:07,322 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:07,322 INFO L93 Difference]: Finished difference Result 38 states and 43 transitions. [2022-03-20 11:34:07,322 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 11:34:07,323 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-03-20 11:34:07,323 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:07,323 INFO L225 Difference]: With dead ends: 38 [2022-03-20 11:34:07,323 INFO L226 Difference]: Without dead ends: 36 [2022-03-20 11:34:07,324 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-03-20 11:34:07,324 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 8 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 83 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:07,325 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 83 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 11:34:07,325 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-20 11:34:07,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 32. [2022-03-20 11:34:07,329 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 21 states have (on average 1.1904761904761905) internal successors, (25), 23 states have internal predecessors, (25), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 11:34:07,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2022-03-20 11:34:07,329 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 18 [2022-03-20 11:34:07,330 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:07,330 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2022-03-20 11:34:07,330 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-03-20 11:34:07,330 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2022-03-20 11:34:07,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-20 11:34:07,330 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:07,331 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-03-20 11:34:07,347 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-03-20 11:34:07,547 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-03-20 11:34:07,547 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:07,548 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:07,548 INFO L85 PathProgramCache]: Analyzing trace with hash 1698322804, now seen corresponding path program 1 times [2022-03-20 11:34:07,548 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:07,548 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [271772371] [2022-03-20 11:34:07,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,548 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:07,567 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:07,567 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [199556496] [2022-03-20 11:34:07,567 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,567 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:07,567 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:07,568 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-03-20 11:34:07,618 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-03-20 11:34:07,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:07,620 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 11:34:07,621 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:07,701 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:07,701 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 11:34:07,701 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:07,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [271772371] [2022-03-20 11:34:07,702 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:07,702 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [199556496] [2022-03-20 11:34:07,702 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [199556496] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 11:34:07,702 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 11:34:07,702 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 11:34:07,702 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843467887] [2022-03-20 11:34:07,702 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 11:34:07,703 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 11:34:07,703 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:07,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 11:34:07,703 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 11:34:07,704 INFO L87 Difference]: Start difference. First operand 32 states and 35 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 11:34:07,745 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:07,746 INFO L93 Difference]: Finished difference Result 42 states and 46 transitions. [2022-03-20 11:34:07,746 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 11:34:07,746 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2022-03-20 11:34:07,746 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:07,747 INFO L225 Difference]: With dead ends: 42 [2022-03-20 11:34:07,747 INFO L226 Difference]: Without dead ends: 35 [2022-03-20 11:34:07,747 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 25 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 11:34:07,748 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 17 mSDsluCounter, 74 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:07,748 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 97 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 11:34:07,749 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-20 11:34:07,751 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 33. [2022-03-20 11:34:07,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 6 states have call successors, (6), 5 states have call predecessors, (6), 4 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-20 11:34:07,752 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 36 transitions. [2022-03-20 11:34:07,752 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 36 transitions. Word has length 24 [2022-03-20 11:34:07,752 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:07,752 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 36 transitions. [2022-03-20 11:34:07,753 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 11:34:07,753 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-03-20 11:34:07,753 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 11:34:07,753 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:07,753 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, 1] [2022-03-20 11:34:07,773 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-03-20 11:34:07,973 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-03-20 11:34:07,974 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:07,974 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:07,974 INFO L85 PathProgramCache]: Analyzing trace with hash 919545147, now seen corresponding path program 1 times [2022-03-20 11:34:07,974 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:07,974 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1181618733] [2022-03-20 11:34:07,974 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,975 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:07,983 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:07,984 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1881220592] [2022-03-20 11:34:07,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:07,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:07,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:07,988 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-03-20 11:34:07,990 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-03-20 11:34:08,033 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:08,034 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 11:34:08,036 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:08,108 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:08,109 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:34:08,174 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:08,175 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:08,175 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1181618733] [2022-03-20 11:34:08,175 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:08,175 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1881220592] [2022-03-20 11:34:08,175 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1881220592] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:34:08,175 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:34:08,175 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-20 11:34:08,175 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1547286381] [2022-03-20 11:34:08,176 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:34:08,176 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-20 11:34:08,176 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:08,176 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-20 11:34:08,176 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-20 11:34:08,177 INFO L87 Difference]: Start difference. First operand 33 states and 36 transitions. Second operand has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 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-03-20 11:34:08,220 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:08,220 INFO L93 Difference]: Finished difference Result 70 states and 80 transitions. [2022-03-20 11:34:08,220 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 11:34:08,220 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 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 28 [2022-03-20 11:34:08,221 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:08,221 INFO L225 Difference]: With dead ends: 70 [2022-03-20 11:34:08,221 INFO L226 Difference]: Without dead ends: 63 [2022-03-20 11:34:08,222 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 49 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-03-20 11:34:08,222 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 42 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 105 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:08,222 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [42 Valid, 105 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 11:34:08,223 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-20 11:34:08,229 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 59. [2022-03-20 11:34:08,229 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 42 states have (on average 1.2619047619047619) internal successors, (53), 45 states have internal predecessors, (53), 10 states have call successors, (10), 7 states have call predecessors, (10), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 11:34:08,230 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 69 transitions. [2022-03-20 11:34:08,230 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 69 transitions. Word has length 28 [2022-03-20 11:34:08,231 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:08,231 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 69 transitions. [2022-03-20 11:34:08,231 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.625) internal successors, (37), 8 states have internal predecessors, (37), 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-03-20 11:34:08,231 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 69 transitions. [2022-03-20 11:34:08,231 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 11:34:08,231 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:08,231 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, 1] [2022-03-20 11:34:08,252 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-03-20 11:34:08,452 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-03-20 11:34:08,452 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:08,453 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:08,453 INFO L85 PathProgramCache]: Analyzing trace with hash 920647414, now seen corresponding path program 1 times [2022-03-20 11:34:08,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:08,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [211621459] [2022-03-20 11:34:08,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:08,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:08,461 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:08,461 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [925162104] [2022-03-20 11:34:08,461 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:08,461 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:08,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:08,462 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-03-20 11:34:08,463 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-03-20 11:34:08,503 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:08,505 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-20 11:34:08,506 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:09,523 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:09,523 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:34:14,831 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:14,831 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:14,831 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [211621459] [2022-03-20 11:34:14,832 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:14,832 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [925162104] [2022-03-20 11:34:14,832 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [925162104] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:34:14,832 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:34:14,832 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 14 [2022-03-20 11:34:14,832 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [833075063] [2022-03-20 11:34:14,832 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:34:14,832 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 11:34:14,832 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:14,833 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 11:34:14,833 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=142, Unknown=0, NotChecked=0, Total=182 [2022-03-20 11:34:14,833 INFO L87 Difference]: Start difference. First operand 59 states and 69 transitions. Second operand has 14 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 11:34:18,043 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:34:19,847 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:19,847 INFO L93 Difference]: Finished difference Result 94 states and 109 transitions. [2022-03-20 11:34:19,847 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 11:34:19,848 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-03-20 11:34:19,848 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:19,849 INFO L225 Difference]: With dead ends: 94 [2022-03-20 11:34:19,849 INFO L226 Difference]: Without dead ends: 92 [2022-03-20 11:34:19,850 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 59 GetRequests, 40 SyntacticMatches, 3 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=66, Invalid=240, Unknown=0, NotChecked=0, Total=306 [2022-03-20 11:34:19,850 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 31 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 141 mSolverCounterSat, 16 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 179 SdHoareTripleChecker+Invalid, 158 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 141 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.4s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:19,850 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 179 Invalid, 158 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 141 Invalid, 1 Unknown, 0 Unchecked, 4.4s Time] [2022-03-20 11:34:19,851 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-03-20 11:34:19,858 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 88. [2022-03-20 11:34:19,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 65 states have (on average 1.2153846153846153) internal successors, (79), 70 states have internal predecessors, (79), 13 states have call successors, (13), 10 states have call predecessors, (13), 9 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 11:34:19,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 101 transitions. [2022-03-20 11:34:19,860 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 101 transitions. Word has length 28 [2022-03-20 11:34:19,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:19,860 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 101 transitions. [2022-03-20 11:34:19,860 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 2.142857142857143) internal successors, (30), 13 states have internal predecessors, (30), 4 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (4), 3 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 11:34:19,860 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 101 transitions. [2022-03-20 11:34:19,861 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 11:34:19,861 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:19,861 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, 1] [2022-03-20 11:34:19,892 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-03-20 11:34:20,061 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-03-20 11:34:20,062 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:20,062 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:20,062 INFO L85 PathProgramCache]: Analyzing trace with hash -1631509547, now seen corresponding path program 1 times [2022-03-20 11:34:20,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:20,062 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [102076819] [2022-03-20 11:34:20,063 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:20,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:20,080 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:20,080 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [529663167] [2022-03-20 11:34:20,080 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:20,080 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:20,080 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:20,082 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-03-20 11:34:20,093 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-03-20 11:34:20,141 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:20,142 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-20 11:34:20,143 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:22,929 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:22,930 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:34:23,669 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:34:23,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:23,669 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [102076819] [2022-03-20 11:34:23,669 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:23,669 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [529663167] [2022-03-20 11:34:23,669 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [529663167] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:34:23,669 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:34:23,669 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2022-03-20 11:34:23,670 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [67526608] [2022-03-20 11:34:23,670 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:34:23,670 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-20 11:34:23,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:23,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-20 11:34:23,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2022-03-20 11:34:23,671 INFO L87 Difference]: Start difference. First operand 88 states and 101 transitions. Second operand has 20 states, 20 states have (on average 1.6) internal successors, (32), 17 states have internal predecessors, (32), 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-03-20 11:34:24,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:24,572 INFO L93 Difference]: Finished difference Result 123 states and 138 transitions. [2022-03-20 11:34:24,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 11:34:24,573 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 1.6) internal successors, (32), 17 states have internal predecessors, (32), 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 28 [2022-03-20 11:34:24,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:24,574 INFO L225 Difference]: With dead ends: 123 [2022-03-20 11:34:24,574 INFO L226 Difference]: Without dead ends: 112 [2022-03-20 11:34:24,575 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 36 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 122 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=127, Invalid=575, Unknown=0, NotChecked=0, Total=702 [2022-03-20 11:34:24,575 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 63 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 205 mSolverCounterSat, 38 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 38 IncrementalHoareTripleChecker+Valid, 205 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:24,575 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [65 Valid, 186 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [38 Valid, 205 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-03-20 11:34:24,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2022-03-20 11:34:24,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 91. [2022-03-20 11:34:24,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 91 states, 69 states have (on average 1.1884057971014492) internal successors, (82), 71 states have internal predecessors, (82), 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-03-20 11:34:24,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 103 transitions. [2022-03-20 11:34:24,583 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 103 transitions. Word has length 28 [2022-03-20 11:34:24,583 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:24,583 INFO L478 AbstractCegarLoop]: Abstraction has 91 states and 103 transitions. [2022-03-20 11:34:24,583 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 1.6) internal successors, (32), 17 states have internal predecessors, (32), 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-03-20 11:34:24,583 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 103 transitions. [2022-03-20 11:34:24,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-20 11:34:24,584 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:24,584 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:34:24,605 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-03-20 11:34:24,803 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-03-20 11:34:24,804 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:24,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:24,804 INFO L85 PathProgramCache]: Analyzing trace with hash -357510123, now seen corresponding path program 1 times [2022-03-20 11:34:24,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:24,804 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1841231999] [2022-03-20 11:34:24,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:24,804 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:24,812 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:24,813 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2012471105] [2022-03-20 11:34:24,813 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:24,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:24,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:24,815 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-03-20 11:34:24,816 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-03-20 11:34:24,845 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:24,846 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 10 conjunts are in the unsatisfiable core [2022-03-20 11:34:24,847 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:24,941 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 11:34:24,941 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:34:25,044 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 7 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 11:34:25,044 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:34:25,044 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1841231999] [2022-03-20 11:34:25,044 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:34:25,044 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2012471105] [2022-03-20 11:34:25,044 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2012471105] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:34:25,044 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:34:25,044 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2022-03-20 11:34:25,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1167464778] [2022-03-20 11:34:25,045 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:34:25,046 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 11:34:25,046 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:34:25,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 11:34:25,046 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 11:34:25,046 INFO L87 Difference]: Start difference. First operand 91 states and 103 transitions. Second operand has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 7 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 11:34:27,050 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:34:27,094 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:34:27,095 INFO L93 Difference]: Finished difference Result 100 states and 111 transitions. [2022-03-20 11:34:27,095 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 11:34:27,095 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 7 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) Word has length 34 [2022-03-20 11:34:27,095 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:34:27,096 INFO L225 Difference]: With dead ends: 100 [2022-03-20 11:34:27,096 INFO L226 Difference]: Without dead ends: 90 [2022-03-20 11:34:27,096 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 58 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=95, Unknown=0, NotChecked=0, Total=132 [2022-03-20 11:34:27,097 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 21 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 48 mSolverCounterSat, 3 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 48 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:34:27,097 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 82 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 48 Invalid, 1 Unknown, 0 Unchecked, 2.0s Time] [2022-03-20 11:34:27,097 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-03-20 11:34:27,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2022-03-20 11:34:27,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 67 states have (on average 1.1343283582089552) internal successors, (76), 69 states have internal predecessors, (76), 11 states have call successors, (11), 10 states have call predecessors, (11), 9 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 11:34:27,111 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 96 transitions. [2022-03-20 11:34:27,111 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 96 transitions. Word has length 34 [2022-03-20 11:34:27,111 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:34:27,111 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 96 transitions. [2022-03-20 11:34:27,112 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 7 states have internal predecessors, (25), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (5), 3 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 11:34:27,112 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 96 transitions. [2022-03-20 11:34:27,114 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-03-20 11:34:27,114 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:34:27,114 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:34:27,132 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 11:34:27,314 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-03-20 11:34:27,315 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:34:27,315 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:34:27,315 INFO L85 PathProgramCache]: Analyzing trace with hash 199111383, now seen corresponding path program 1 times [2022-03-20 11:34:27,316 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:34:27,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [613461082] [2022-03-20 11:34:27,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:27,316 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:34:27,324 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:34:27,324 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1669154472] [2022-03-20 11:34:27,324 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:34:27,325 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:34:27,325 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:34:27,333 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-03-20 11:34:27,336 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-03-20 11:34:27,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 11:34:27,388 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 42 conjunts are in the unsatisfiable core [2022-03-20 11:34:27,389 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:34:30,436 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 11:34:51,802 WARN L232 SmtUtils]: Spent 12.51s on a formula simplification that was a NOOP. DAG size: 63 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 11:35:02,223 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 10 proven. 29 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2022-03-20 11:35:02,223 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:35:07,595 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 11:35:13,636 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 29 proven. 5 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2022-03-20 11:35:13,636 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:35:13,636 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [613461082] [2022-03-20 11:35:13,636 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:35:13,636 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1669154472] [2022-03-20 11:35:13,636 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1669154472] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:35:13,637 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:35:13,637 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 11] total 24 [2022-03-20 11:35:13,637 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040226779] [2022-03-20 11:35:13,637 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:35:13,637 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-20 11:35:13,637 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:35:13,637 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-20 11:35:13,638 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=455, Unknown=3, NotChecked=0, Total=552 [2022-03-20 11:35:13,638 INFO L87 Difference]: Start difference. First operand 88 states and 96 transitions. Second operand has 24 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 22 states have internal predecessors, (50), 7 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 11:35:17,019 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:36:32,059 WARN L232 SmtUtils]: Spent 1.16m on a formula simplification. DAG size of input: 68 DAG size of output: 67 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 11:36:35,066 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:36:40,974 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:36:43,250 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:36:54,364 WARN L232 SmtUtils]: Spent 6.84s on a formula simplification. DAG size of input: 98 DAG size of output: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 11:36:56,390 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 11:36:56,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:36:56,742 INFO L93 Difference]: Finished difference Result 127 states and 143 transitions. [2022-03-20 11:36:56,743 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-20 11:36:56,743 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 22 states have internal predecessors, (50), 7 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 48 [2022-03-20 11:36:56,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:36:56,744 INFO L225 Difference]: With dead ends: 127 [2022-03-20 11:36:56,744 INFO L226 Difference]: Without dead ends: 125 [2022-03-20 11:36:56,745 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 74 SyntacticMatches, 4 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 285 ImplicationChecksByTransitivity, 114.3s TimeCoverageRelationStatistics Valid=193, Invalid=993, Unknown=4, NotChecked=0, Total=1190 [2022-03-20 11:36:56,745 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 53 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 337 mSolverCounterSat, 39 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 16.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 315 SdHoareTripleChecker+Invalid, 411 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 337 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 30 IncrementalHoareTripleChecker+Unchecked, 16.8s IncrementalHoareTripleChecker+Time [2022-03-20 11:36:56,745 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 315 Invalid, 411 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 337 Invalid, 5 Unknown, 30 Unchecked, 16.8s Time] [2022-03-20 11:36:56,746 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-03-20 11:36:56,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-03-20 11:36:56,774 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 94 states have (on average 1.148936170212766) internal successors, (108), 98 states have internal predecessors, (108), 16 states have call successors, (16), 12 states have call predecessors, (16), 11 states have return successors, (14), 11 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 11:36:56,774 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 138 transitions. [2022-03-20 11:36:56,775 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 138 transitions. Word has length 48 [2022-03-20 11:36:56,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:36:56,775 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 138 transitions. [2022-03-20 11:36:56,775 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 24 states have (on average 2.0833333333333335) internal successors, (50), 22 states have internal predecessors, (50), 7 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 11:36:56,775 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 138 transitions. [2022-03-20 11:36:56,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-20 11:36:56,777 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:36:56,777 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:36:56,796 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-03-20 11:36:56,993 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-03-20 11:36:56,994 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:36:56,994 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:36:56,994 INFO L85 PathProgramCache]: Analyzing trace with hash -831185954, now seen corresponding path program 2 times [2022-03-20 11:36:56,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:36:56,994 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1805557641] [2022-03-20 11:36:56,994 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:36:56,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:36:57,020 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:36:57,020 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2141559880] [2022-03-20 11:36:57,020 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 11:36:57,020 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:36:57,020 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:36:57,031 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-03-20 11:36:57,032 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-03-20 11:36:57,072 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 11:36:57,072 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 11:36:57,073 INFO L263 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 11:36:57,076 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:36:57,498 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 68 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 11:36:57,499 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:36:57,876 INFO L134 CoverageAnalysis]: Checked inductivity of 76 backedges. 8 proven. 44 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 11:36:57,876 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:36:57,876 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1805557641] [2022-03-20 11:36:57,876 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:36:57,876 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2141559880] [2022-03-20 11:36:57,876 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2141559880] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:36:57,876 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:36:57,876 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-03-20 11:36:57,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1851644677] [2022-03-20 11:36:57,877 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:36:57,877 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-20 11:36:57,877 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:36:57,877 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-20 11:36:57,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-20 11:36:57,878 INFO L87 Difference]: Start difference. First operand 122 states and 138 transitions. Second operand has 14 states, 14 states have (on average 5.428571428571429) internal successors, (76), 14 states have internal predecessors, (76), 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-03-20 11:36:58,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:36:58,291 INFO L93 Difference]: Finished difference Result 302 states and 347 transitions. [2022-03-20 11:36:58,291 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-20 11:36:58,292 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 5.428571428571429) internal successors, (76), 14 states have internal predecessors, (76), 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 58 [2022-03-20 11:36:58,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:36:58,293 INFO L225 Difference]: With dead ends: 302 [2022-03-20 11:36:58,293 INFO L226 Difference]: Without dead ends: 295 [2022-03-20 11:36:58,294 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-03-20 11:36:58,294 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 112 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 31 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 112 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 88 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 31 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 11:36:58,294 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [112 Valid, 168 Invalid, 88 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [31 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 11:36:58,295 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2022-03-20 11:36:58,311 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 285. [2022-03-20 11:36:58,311 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 285 states, 223 states have (on average 1.1345291479820627) internal successors, (253), 232 states have internal predecessors, (253), 33 states have call successors, (33), 29 states have call predecessors, (33), 28 states have return successors, (31), 23 states have call predecessors, (31), 31 states have call successors, (31) [2022-03-20 11:36:58,312 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 285 states to 285 states and 317 transitions. [2022-03-20 11:36:58,312 INFO L78 Accepts]: Start accepts. Automaton has 285 states and 317 transitions. Word has length 58 [2022-03-20 11:36:58,312 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:36:58,313 INFO L478 AbstractCegarLoop]: Abstraction has 285 states and 317 transitions. [2022-03-20 11:36:58,313 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 5.428571428571429) internal successors, (76), 14 states have internal predecessors, (76), 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-03-20 11:36:58,313 INFO L276 IsEmpty]: Start isEmpty. Operand 285 states and 317 transitions. [2022-03-20 11:36:58,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-20 11:36:58,314 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:36:58,314 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:36:58,332 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-20 11:36:58,534 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-03-20 11:36:58,535 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:36:58,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:36:58,535 INFO L85 PathProgramCache]: Analyzing trace with hash -339082250, now seen corresponding path program 2 times [2022-03-20 11:36:58,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:36:58,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1592732031] [2022-03-20 11:36:58,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:36:58,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:36:58,544 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:36:58,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1716780078] [2022-03-20 11:36:58,544 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 11:36:58,544 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:36:58,545 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:36:58,548 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-03-20 11:36:58,551 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-20 11:36:58,593 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 11:36:58,593 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 11:36:58,595 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 41 conjunts are in the unsatisfiable core [2022-03-20 11:36:58,596 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:37:01,827 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 16 proven. 49 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-20 11:37:01,828 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:37:09,050 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:37:09,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1592732031] [2022-03-20 11:37:09,050 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:37:09,050 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1716780078] [2022-03-20 11:37:09,050 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1716780078] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 11:37:09,050 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 11:37:09,050 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2022-03-20 11:37:09,050 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2041878193] [2022-03-20 11:37:09,050 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 11:37:09,051 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-20 11:37:09,051 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:37:09,051 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-20 11:37:09,051 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=685, Unknown=0, NotChecked=0, Total=812 [2022-03-20 11:37:09,051 INFO L87 Difference]: Start difference. First operand 285 states and 317 transitions. Second operand has 23 states, 23 states have (on average 1.6521739130434783) internal successors, (38), 21 states have internal predecessors, (38), 6 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 11:37:10,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:37:10,401 INFO L93 Difference]: Finished difference Result 307 states and 343 transitions. [2022-03-20 11:37:10,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-20 11:37:10,402 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 1.6521739130434783) internal successors, (38), 21 states have internal predecessors, (38), 6 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) Word has length 58 [2022-03-20 11:37:10,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:37:10,404 INFO L225 Difference]: With dead ends: 307 [2022-03-20 11:37:10,404 INFO L226 Difference]: Without dead ends: 305 [2022-03-20 11:37:10,405 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 48 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 3 DeprecatedPredicates, 374 ImplicationChecksByTransitivity, 7.3s TimeCoverageRelationStatistics Valid=151, Invalid=905, Unknown=0, NotChecked=0, Total=1056 [2022-03-20 11:37:10,405 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 379 mSDsCounter, 0 mSdLazyCounter, 353 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 409 SdHoareTripleChecker+Invalid, 429 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 353 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 72 IncrementalHoareTripleChecker+Unchecked, 1.0s IncrementalHoareTripleChecker+Time [2022-03-20 11:37:10,405 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 409 Invalid, 429 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 353 Invalid, 0 Unknown, 72 Unchecked, 1.0s Time] [2022-03-20 11:37:10,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 305 states. [2022-03-20 11:37:10,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 305 to 305. [2022-03-20 11:37:10,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 305 states, 239 states have (on average 1.1338912133891212) internal successors, (271), 249 states have internal predecessors, (271), 36 states have call successors, (36), 30 states have call predecessors, (36), 29 states have return successors, (34), 25 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-20 11:37:10,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 305 states to 305 states and 341 transitions. [2022-03-20 11:37:10,432 INFO L78 Accepts]: Start accepts. Automaton has 305 states and 341 transitions. Word has length 58 [2022-03-20 11:37:10,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:37:10,433 INFO L478 AbstractCegarLoop]: Abstraction has 305 states and 341 transitions. [2022-03-20 11:37:10,433 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 1.6521739130434783) internal successors, (38), 21 states have internal predecessors, (38), 6 states have call successors, (8), 2 states have call predecessors, (8), 3 states have return successors, (6), 6 states have call predecessors, (6), 5 states have call successors, (6) [2022-03-20 11:37:10,433 INFO L276 IsEmpty]: Start isEmpty. Operand 305 states and 341 transitions. [2022-03-20 11:37:10,436 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-20 11:37:10,436 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:37:10,436 INFO L499 BasicCegarLoop]: trace histogram [5, 5, 5, 5, 4, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:37:10,453 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-20 11:37:10,653 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 11:37:10,653 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:37:10,654 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:37:10,654 INFO L85 PathProgramCache]: Analyzing trace with hash 1548458294, now seen corresponding path program 3 times [2022-03-20 11:37:10,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:37:10,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1244843300] [2022-03-20 11:37:10,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:37:10,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:37:10,671 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:37:10,671 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1738336088] [2022-03-20 11:37:10,671 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 11:37:10,671 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:37:10,671 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:37:10,686 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 11:37:10,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-20 11:37:10,722 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 11:37:10,722 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 11:37:10,723 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 22 conjunts are in the unsatisfiable core [2022-03-20 11:37:10,724 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 11:37:12,386 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 11:37:15,038 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 54 proven. 3 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2022-03-20 11:37:15,038 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 11:37:16,744 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 46 proven. 14 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2022-03-20 11:37:16,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 11:37:16,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1244843300] [2022-03-20 11:37:16,745 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 11:37:16,745 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1738336088] [2022-03-20 11:37:16,745 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1738336088] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 11:37:16,745 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 11:37:16,745 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-03-20 11:37:16,745 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1620304267] [2022-03-20 11:37:16,745 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 11:37:16,745 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-20 11:37:16,745 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 11:37:16,746 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-20 11:37:16,746 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=268, Unknown=0, NotChecked=0, Total=342 [2022-03-20 11:37:16,746 INFO L87 Difference]: Start difference. First operand 305 states and 341 transitions. Second operand has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-03-20 11:37:23,534 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 11:37:23,535 INFO L93 Difference]: Finished difference Result 376 states and 425 transitions. [2022-03-20 11:37:23,535 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 11:37:23,535 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 58 [2022-03-20 11:37:23,535 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 11:37:23,537 INFO L225 Difference]: With dead ends: 376 [2022-03-20 11:37:23,537 INFO L226 Difference]: Without dead ends: 374 [2022-03-20 11:37:23,537 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 98 SyntacticMatches, 3 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 126 ImplicationChecksByTransitivity, 10.2s TimeCoverageRelationStatistics Valid=130, Invalid=470, Unknown=0, NotChecked=0, Total=600 [2022-03-20 11:37:23,538 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 28 mSDsluCounter, 237 mSDsCounter, 0 mSdLazyCounter, 140 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 140 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 6 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-20 11:37:23,538 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 264 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 140 Invalid, 0 Unknown, 6 Unchecked, 0.6s Time] [2022-03-20 11:37:23,538 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 374 states. [2022-03-20 11:37:23,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 374 to 210. [2022-03-20 11:37:23,553 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 210 states, 165 states have (on average 1.1575757575757575) internal successors, (191), 166 states have internal predecessors, (191), 23 states have call successors, (23), 22 states have call predecessors, (23), 21 states have return successors, (21), 21 states have call predecessors, (21), 21 states have call successors, (21) [2022-03-20 11:37:23,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 235 transitions. [2022-03-20 11:37:23,565 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 235 transitions. Word has length 58 [2022-03-20 11:37:23,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 11:37:23,566 INFO L478 AbstractCegarLoop]: Abstraction has 210 states and 235 transitions. [2022-03-20 11:37:23,567 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.5789473684210527) internal successors, (49), 18 states have internal predecessors, (49), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-03-20 11:37:23,567 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 235 transitions. [2022-03-20 11:37:23,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-20 11:37:23,567 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 11:37:23,568 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 11:37:23,584 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-03-20 11:37:23,783 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-20 11:37:23,783 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 11:37:23,784 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 11:37:23,784 INFO L85 PathProgramCache]: Analyzing trace with hash 680514773, now seen corresponding path program 2 times [2022-03-20 11:37:23,784 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 11:37:23,784 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [318951477] [2022-03-20 11:37:23,784 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 11:37:23,784 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 11:37:23,790 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 11:37:23,790 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [312500104] [2022-03-20 11:37:23,790 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 11:37:23,790 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 11:37:23,790 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 11:37:23,796 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 11:37:23,803 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-20 11:37:23,866 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 11:37:23,866 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 11:37:23,867 INFO L263 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 46 conjunts are in the unsatisfiable core [2022-03-20 11:37:23,868 INFO L286 TraceCheckSpWp]: Computing forward predicates...