/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/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/prodbin-ll_unwindbound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 18:12:45,335 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 18:12:45,337 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 18:12:45,401 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 18:12:45,402 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 18:12:45,402 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 18:12:45,403 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 18:12:45,404 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 18:12:45,406 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 18:12:45,406 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 18:12:45,407 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 18:12:45,411 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 18:12:45,427 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 18:12:45,431 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 18:12:45,432 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 18:12:45,435 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 18:12:45,436 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 18:12:45,437 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 18:12:45,441 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 18:12:45,444 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 18:12:45,444 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 18:12:45,445 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 18:12:45,446 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 18:12:45,447 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 18:12:45,447 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 18:12:45,448 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 18:12:45,448 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 18:12:45,449 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 18:12:45,449 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 18:12:45,449 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 18:12:45,450 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 18:12:45,450 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 18:12:45,450 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 18:12:45,451 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 18:12:45,454 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 18:12:45,455 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 18:12:45,455 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 18:12:45,455 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 18:12:45,455 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 18:12:45,456 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 18:12:45,456 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 18:12:45,457 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 18:12:45,458 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-17 18:12:45,477 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 18:12:45,478 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 18:12:45,478 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 18:12:45,479 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 18:12:45,480 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-17 18:12:45,480 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 18:12:45,481 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 18:12:45,481 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 18:12:45,481 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 18:12:45,481 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 18:12:45,481 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN 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-17 18:12:45,665 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 18:12:45,689 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 18:12:45,691 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 18:12:45,692 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 18:12:45,692 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 18:12:45,693 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-17 18:12:45,746 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c21a5e5ad/fe8c418eaa964284bcc66c481968b22d/FLAG452ad7baf [2022-03-17 18:12:46,117 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 18:12:46,117 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/prodbin-ll_unwindbound20.c [2022-03-17 18:12:46,122 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c21a5e5ad/fe8c418eaa964284bcc66c481968b22d/FLAG452ad7baf [2022-03-17 18:12:46,130 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/c21a5e5ad/fe8c418eaa964284bcc66c481968b22d [2022-03-17 18:12:46,134 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 18:12:46,135 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 18:12:46,138 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 18:12:46,139 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 18:12:46,141 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 18:12:46,142 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,143 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@73bd47e6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46, skipping insertion in model container [2022-03-17 18:12:46,143 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,148 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 18:12:46,157 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 18:12:46,285 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-17 18:12:46,311 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 18:12:46,316 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 18:12:46,326 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-17 18:12:46,338 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 18:12:46,348 INFO L208 MainTranslator]: Completed translation [2022-03-17 18:12:46,349 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46 WrapperNode [2022-03-17 18:12:46,349 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 18:12:46,350 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 18:12:46,350 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 18:12:46,350 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 18:12:46,357 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,357 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,361 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,361 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,369 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,372 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,376 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,377 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 18:12:46,378 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 18:12:46,378 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 18:12:46,378 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 18:12:46,379 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 18:12:46,390 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:46,404 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-17 18:12:46,419 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-17 18:12:46,447 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 18:12:46,447 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 18:12:46,448 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 18:12:46,448 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 18:12:46,448 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 18:12:46,448 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 18:12:46,448 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 18:12:46,448 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 18:12:46,448 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 18:12:46,448 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 18:12:46,449 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-17 18:12:46,449 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 18:12:46,449 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 18:12:46,449 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 18:12:46,450 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 18:12:46,495 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 18:12:46,496 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 18:12:46,608 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 18:12:46,612 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 18:12:46,612 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-03-17 18:12:46,613 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 06:12:46 BoogieIcfgContainer [2022-03-17 18:12:46,613 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 18:12:46,613 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 18:12:46,614 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 18:12:46,614 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 18:12:46,616 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 06:12:46" (1/1) ... [2022-03-17 18:12:46,628 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 06:12:46 BasicIcfg [2022-03-17 18:12:46,628 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 18:12:46,630 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 18:12:46,630 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 18:12:46,632 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 18:12:46,632 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 06:12:46" (1/4) ... [2022-03-17 18:12:46,632 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@634d38b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 06:12:46, skipping insertion in model container [2022-03-17 18:12:46,632 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 06:12:46" (2/4) ... [2022-03-17 18:12:46,633 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@634d38b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 06:12:46, skipping insertion in model container [2022-03-17 18:12:46,633 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 06:12:46" (3/4) ... [2022-03-17 18:12:46,633 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@634d38b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 06:12:46, skipping insertion in model container [2022-03-17 18:12:46,633 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 06:12:46" (4/4) ... [2022-03-17 18:12:46,634 INFO L111 eAbstractionObserver]: Analyzing ICFG prodbin-ll_unwindbound20.cJordan [2022-03-17 18:12:46,637 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-17 18:12:46,637 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 18:12:46,666 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 18:12:46,671 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, 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-17 18:12:46,671 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 18:12:46,686 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-17 18:12:46,701 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-17 18:12:46,701 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:46,702 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 18:12:46,702 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:46,709 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:46,709 INFO L85 PathProgramCache]: Analyzing trace with hash 1957529129, now seen corresponding path program 1 times [2022-03-17 18:12:46,715 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:46,716 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [382878193] [2022-03-17 18:12:46,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:46,717 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:46,799 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:46,860 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 18:12:46,870 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:46,877 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 18:12:46,882 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:46,892 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-17 18:12:46,892 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:12:46,893 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [382878193] [2022-03-17 18:12:46,894 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [382878193] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 18:12:46,894 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 18:12:46,894 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 18:12:46,895 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [206467295] [2022-03-17 18:12:46,896 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 18:12:46,899 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 18:12:46,900 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:12:46,921 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 18:12:46,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 18:12:46,924 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-17 18:12:46,973 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:12:46,973 INFO L93 Difference]: Finished difference Result 31 states and 34 transitions. [2022-03-17 18:12:46,974 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 18:12:46,975 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-17 18:12:46,975 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:12:46,983 INFO L225 Difference]: With dead ends: 31 [2022-03-17 18:12:46,984 INFO L226 Difference]: Without dead ends: 26 [2022-03-17 18:12:46,986 INFO L911 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-17 18:12:46,993 INFO L912 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-17 18:12:46,994 INFO L913 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-17 18:12:47,005 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 26 states. [2022-03-17 18:12:47,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 26 to 25. [2022-03-17 18:12:47,017 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-17 18:12:47,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 25 states to 25 states and 28 transitions. [2022-03-17 18:12:47,019 INFO L78 Accepts]: Start accepts. Automaton has 25 states and 28 transitions. Word has length 17 [2022-03-17 18:12:47,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:12:47,019 INFO L478 AbstractCegarLoop]: Abstraction has 25 states and 28 transitions. [2022-03-17 18:12:47,020 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-17 18:12:47,020 INFO L276 IsEmpty]: Start isEmpty. Operand 25 states and 28 transitions. [2022-03-17 18:12:47,021 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 18:12:47,021 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:47,021 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 18:12:47,021 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 18:12:47,021 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:47,023 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:47,023 INFO L85 PathProgramCache]: Analyzing trace with hash 583261658, now seen corresponding path program 1 times [2022-03-17 18:12:47,023 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:47,023 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [545408835] [2022-03-17 18:12:47,023 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,024 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:47,049 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:12:47,049 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [962627323] [2022-03-17 18:12:47,049 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,050 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:12:47,050 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:47,055 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-17 18:12:47,067 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-17 18:12:47,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:47,092 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 18:12:47,095 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:12:47,164 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-17 18:12:47,164 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 18:12:47,165 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:12:47,165 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [545408835] [2022-03-17 18:12:47,165 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:12:47,165 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [962627323] [2022-03-17 18:12:47,165 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [962627323] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 18:12:47,165 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 18:12:47,165 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-17 18:12:47,166 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385930266] [2022-03-17 18:12:47,166 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 18:12:47,167 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-17 18:12:47,167 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:12:47,167 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-17 18:12:47,167 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-17 18:12:47,168 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-17 18:12:47,176 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:12:47,176 INFO L93 Difference]: Finished difference Result 27 states and 30 transitions. [2022-03-17 18:12:47,176 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 18:12:47,176 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-17 18:12:47,177 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:12:47,177 INFO L225 Difference]: With dead ends: 27 [2022-03-17 18:12:47,177 INFO L226 Difference]: Without dead ends: 27 [2022-03-17 18:12:47,177 INFO L911 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-17 18:12:47,178 INFO L912 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-17 18:12:47,179 INFO L913 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-17 18:12:47,180 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-17 18:12:47,182 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-03-17 18:12:47,182 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-17 18:12:47,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2022-03-17 18:12:47,183 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 18 [2022-03-17 18:12:47,183 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:12:47,183 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2022-03-17 18:12:47,183 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-17 18:12:47,184 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2022-03-17 18:12:47,184 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 18:12:47,184 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:47,184 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 18:12:47,201 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-17 18:12:47,388 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-17 18:12:47,388 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:47,389 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:47,389 INFO L85 PathProgramCache]: Analyzing trace with hash 584363925, now seen corresponding path program 1 times [2022-03-17 18:12:47,389 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:47,389 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1634551093] [2022-03-17 18:12:47,389 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,389 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:47,398 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:12:47,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1543191293] [2022-03-17 18:12:47,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,398 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:12:47,398 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:47,400 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-17 18:12:47,402 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-17 18:12:47,447 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:47,448 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-17 18:12:47,450 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:12:47,562 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-17 18:12:47,562 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 18:12:47,562 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:12:47,562 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1634551093] [2022-03-17 18:12:47,562 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:12:47,563 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1543191293] [2022-03-17 18:12:47,563 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1543191293] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 18:12:47,563 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 18:12:47,563 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 18:12:47,563 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [948691087] [2022-03-17 18:12:47,563 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 18:12:47,563 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 18:12:47,564 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:12:47,564 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 18:12:47,564 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 18:12:47,564 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-17 18:12:47,621 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:12:47,621 INFO L93 Difference]: Finished difference Result 36 states and 41 transitions. [2022-03-17 18:12:47,622 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 18:12:47,622 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-17 18:12:47,622 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:12:47,622 INFO L225 Difference]: With dead ends: 36 [2022-03-17 18:12:47,623 INFO L226 Difference]: Without dead ends: 36 [2022-03-17 18:12:47,623 INFO L911 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-17 18:12:47,624 INFO L912 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-17 18:12:47,625 INFO L913 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-17 18:12:47,625 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 36 states. [2022-03-17 18:12:47,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 36 to 32. [2022-03-17 18:12:47,631 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-17 18:12:47,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 35 transitions. [2022-03-17 18:12:47,632 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 35 transitions. Word has length 18 [2022-03-17 18:12:47,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:12:47,632 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 35 transitions. [2022-03-17 18:12:47,632 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-17 18:12:47,632 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 35 transitions. [2022-03-17 18:12:47,633 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-17 18:12:47,633 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:47,633 INFO L500 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-17 18:12:47,651 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-17 18:12:47,833 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-17 18:12:47,834 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:47,834 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:47,834 INFO L85 PathProgramCache]: Analyzing trace with hash 1698322804, now seen corresponding path program 1 times [2022-03-17 18:12:47,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:47,835 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1555485801] [2022-03-17 18:12:47,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:47,844 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:12:47,844 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1876800815] [2022-03-17 18:12:47,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:47,844 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:12:47,844 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:47,856 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-17 18:12:47,899 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-17 18:12:47,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:47,911 INFO L263 TraceCheckSpWp]: Trace formula consists of 95 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 18:12:47,913 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:12:48,009 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-17 18:12:48,009 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 18:12:48,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:12:48,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1555485801] [2022-03-17 18:12:48,010 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:12:48,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1876800815] [2022-03-17 18:12:48,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1876800815] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 18:12:48,010 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 18:12:48,010 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 18:12:48,010 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [542117865] [2022-03-17 18:12:48,011 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 18:12:48,011 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 18:12:48,011 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:12:48,011 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 18:12:48,011 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 18:12:48,012 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-17 18:12:48,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:12:48,063 INFO L93 Difference]: Finished difference Result 35 states and 39 transitions. [2022-03-17 18:12:48,063 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 18:12:48,064 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-17 18:12:48,064 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:12:48,064 INFO L225 Difference]: With dead ends: 35 [2022-03-17 18:12:48,064 INFO L226 Difference]: Without dead ends: 35 [2022-03-17 18:12:48,065 INFO L911 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-17 18:12:48,065 INFO L912 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-17 18:12:48,066 INFO L913 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-17 18:12:48,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-17 18:12:48,068 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 33. [2022-03-17 18:12:48,068 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-17 18:12:48,069 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 36 transitions. [2022-03-17 18:12:48,069 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 36 transitions. Word has length 24 [2022-03-17 18:12:48,069 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:12:48,072 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 36 transitions. [2022-03-17 18:12:48,072 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-17 18:12:48,073 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 36 transitions. [2022-03-17 18:12:48,074 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 18:12:48,074 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:48,076 INFO L500 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-17 18:12:48,103 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-17 18:12:48,291 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-17 18:12:48,292 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:48,292 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:48,292 INFO L85 PathProgramCache]: Analyzing trace with hash 919545147, now seen corresponding path program 1 times [2022-03-17 18:12:48,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:48,293 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [823728531] [2022-03-17 18:12:48,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:48,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:48,301 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:12:48,301 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [488321791] [2022-03-17 18:12:48,301 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:48,302 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:12:48,302 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:48,311 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-17 18:12:48,312 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-17 18:12:48,385 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:48,399 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 18:12:48,401 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:12:48,526 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-17 18:12:48,526 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:12:48,634 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-17 18:12:48,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:12:48,634 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [823728531] [2022-03-17 18:12:48,634 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:12:48,635 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [488321791] [2022-03-17 18:12:48,635 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [488321791] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:12:48,635 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:12:48,635 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-17 18:12:48,635 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1936828873] [2022-03-17 18:12:48,635 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:12:48,636 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-17 18:12:48,636 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:12:48,636 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-17 18:12:48,637 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-17 18:12:48,637 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-17 18:12:48,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:12:48,688 INFO L93 Difference]: Finished difference Result 63 states and 71 transitions. [2022-03-17 18:12:48,688 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 18:12:48,689 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-17 18:12:48,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:12:48,690 INFO L225 Difference]: With dead ends: 63 [2022-03-17 18:12:48,690 INFO L226 Difference]: Without dead ends: 63 [2022-03-17 18:12:48,690 INFO L911 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-17 18:12:48,691 INFO L912 BasicCegarLoop]: 29 mSDtfsCounter, 52 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 23 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 23 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 18:12:48,691 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 99 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 23 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 18:12:48,692 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2022-03-17 18:12:48,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 59. [2022-03-17 18:12:48,695 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-17 18:12:48,696 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 69 transitions. [2022-03-17 18:12:48,696 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 69 transitions. Word has length 28 [2022-03-17 18:12:48,696 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:12:48,697 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 69 transitions. [2022-03-17 18:12:48,697 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-17 18:12:48,697 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 69 transitions. [2022-03-17 18:12:48,697 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 18:12:48,697 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:12:48,697 INFO L500 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-17 18:12:48,729 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-17 18:12:48,914 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-17 18:12:48,915 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:12:48,915 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:12:48,915 INFO L85 PathProgramCache]: Analyzing trace with hash 920647414, now seen corresponding path program 1 times [2022-03-17 18:12:48,915 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:12:48,915 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1946421650] [2022-03-17 18:12:48,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:48,916 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:12:48,926 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:12:48,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [879203129] [2022-03-17 18:12:48,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:12:48,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:12:48,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:12:48,947 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-17 18:12:48,948 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-17 18:12:49,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:12:49,006 INFO L263 TraceCheckSpWp]: Trace formula consists of 109 conjuncts, 28 conjunts are in the unsatisfiable core [2022-03-17 18:12:49,012 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:12:51,775 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-17 18:12:51,776 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:13:04,633 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-17 18:13:04,634 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:13:04,634 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1946421650] [2022-03-17 18:13:04,634 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:13:04,634 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [879203129] [2022-03-17 18:13:04,634 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [879203129] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:13:04,634 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:13:04,634 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 14 [2022-03-17 18:13:04,634 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [299548236] [2022-03-17 18:13:04,634 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:13:04,635 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-17 18:13:04,635 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:13:04,635 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-17 18:13:04,636 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=142, Unknown=3, NotChecked=0, Total=182 [2022-03-17 18:13:04,636 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-17 18:13:06,652 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 18:13:08,657 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-17 18:13:19,535 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:13:19,535 INFO L93 Difference]: Finished difference Result 92 states and 105 transitions. [2022-03-17 18:13:19,536 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-17 18:13:19,536 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-17 18:13:19,536 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:13:19,538 INFO L225 Difference]: With dead ends: 92 [2022-03-17 18:13:19,538 INFO L226 Difference]: Without dead ends: 92 [2022-03-17 18:13:19,539 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 65 GetRequests, 43 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 19.4s TimeCoverageRelationStatistics Valid=84, Invalid=332, Unknown=4, NotChecked=0, Total=420 [2022-03-17 18:13:19,540 INFO L912 BasicCegarLoop]: 22 mSDtfsCounter, 38 mSDsluCounter, 161 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 21 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 175 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.0s IncrementalHoareTripleChecker+Time [2022-03-17 18:13:19,540 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [38 Valid, 183 Invalid, 175 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 152 Invalid, 2 Unknown, 0 Unchecked, 7.0s Time] [2022-03-17 18:13:19,541 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2022-03-17 18:13:19,548 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 88. [2022-03-17 18:13:19,548 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-17 18:13:19,549 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 101 transitions. [2022-03-17 18:13:19,549 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 101 transitions. Word has length 28 [2022-03-17 18:13:19,550 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:13:19,550 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 101 transitions. [2022-03-17 18:13:19,550 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-17 18:13:19,550 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 101 transitions. [2022-03-17 18:13:19,551 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 18:13:19,551 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:13:19,555 INFO L500 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-17 18:13:19,579 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-03-17 18:13:19,779 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-17 18:13:19,779 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:13:19,780 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:13:19,780 INFO L85 PathProgramCache]: Analyzing trace with hash -1631509547, now seen corresponding path program 1 times [2022-03-17 18:13:19,780 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:13:19,780 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [652731379] [2022-03-17 18:13:19,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:19,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:13:19,800 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:13:19,800 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [823958773] [2022-03-17 18:13:19,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:19,801 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:13:19,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:13:19,807 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-17 18:13:19,808 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-17 18:13:19,852 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:13:19,853 INFO L263 TraceCheckSpWp]: Trace formula consists of 104 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-17 18:13:19,855 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:13:21,252 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-17 18:13:21,253 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:13:22,098 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-17 18:13:22,099 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:13:22,099 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [652731379] [2022-03-17 18:13:22,099 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:13:22,099 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [823958773] [2022-03-17 18:13:22,099 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [823958773] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:13:22,099 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:13:22,099 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 20 [2022-03-17 18:13:22,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2069379124] [2022-03-17 18:13:22,099 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:13:22,100 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-17 18:13:22,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:13:22,100 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-17 18:13:22,101 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=313, Unknown=0, NotChecked=0, Total=380 [2022-03-17 18:13:22,101 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-17 18:13:23,074 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:13:23,074 INFO L93 Difference]: Finished difference Result 116 states and 128 transitions. [2022-03-17 18:13:23,075 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-17 18:13:23,075 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-17 18:13:23,075 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:13:23,076 INFO L225 Difference]: With dead ends: 116 [2022-03-17 18:13:23,076 INFO L226 Difference]: Without dead ends: 112 [2022-03-17 18:13:23,077 INFO L911 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-17 18:13:23,077 INFO L912 BasicCegarLoop]: 19 mSDtfsCounter, 49 mSDsluCounter, 186 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 268 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-17 18:13:23,078 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [51 Valid, 205 Invalid, 268 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-17 18:13:23,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2022-03-17 18:13:23,085 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 91. [2022-03-17 18:13:23,085 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-17 18:13:23,086 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 103 transitions. [2022-03-17 18:13:23,086 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 103 transitions. Word has length 28 [2022-03-17 18:13:23,087 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:13:23,087 INFO L478 AbstractCegarLoop]: Abstraction has 91 states and 103 transitions. [2022-03-17 18:13:23,087 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-17 18:13:23,087 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 103 transitions. [2022-03-17 18:13:23,088 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-17 18:13:23,088 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:13:23,088 INFO L500 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-17 18:13:23,115 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-17 18:13:23,304 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-17 18:13:23,304 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:13:23,305 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:13:23,305 INFO L85 PathProgramCache]: Analyzing trace with hash -357510123, now seen corresponding path program 1 times [2022-03-17 18:13:23,305 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:13:23,305 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1948920711] [2022-03-17 18:13:23,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:23,305 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:13:23,313 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:13:23,313 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1723433605] [2022-03-17 18:13:23,314 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:23,314 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:13:23,314 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:13:23,315 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-17 18:13:23,317 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-17 18:13:23,352 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:13:23,353 INFO L263 TraceCheckSpWp]: Trace formula consists of 120 conjuncts, 10 conjunts are in the unsatisfiable core [2022-03-17 18:13:23,355 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:13:23,447 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-17 18:13:23,447 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:13:23,560 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-17 18:13:23,560 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:13:23,560 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1948920711] [2022-03-17 18:13:23,560 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:13:23,560 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1723433605] [2022-03-17 18:13:23,561 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1723433605] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:13:23,561 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:13:23,561 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 10 [2022-03-17 18:13:23,561 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [462137671] [2022-03-17 18:13:23,561 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:13:23,561 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 18:13:23,561 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:13:23,562 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 18:13:23,562 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-17 18:13:23,562 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-17 18:13:25,568 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-17 18:13:27,721 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-17 18:13:27,747 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:13:27,748 INFO L93 Difference]: Finished difference Result 98 states and 108 transitions. [2022-03-17 18:13:27,748 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-17 18:13:27,748 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-17 18:13:27,748 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:13:27,749 INFO L225 Difference]: With dead ends: 98 [2022-03-17 18:13:27,749 INFO L226 Difference]: Without dead ends: 90 [2022-03-17 18:13:27,750 INFO L911 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-17 18:13:27,750 INFO L912 BasicCegarLoop]: 22 mSDtfsCounter, 12 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 81 mSolverCounterSat, 1 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 167 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 81 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.2s IncrementalHoareTripleChecker+Time [2022-03-17 18:13:27,751 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 167 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 81 Invalid, 2 Unknown, 0 Unchecked, 4.2s Time] [2022-03-17 18:13:27,751 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2022-03-17 18:13:27,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 88. [2022-03-17 18:13:27,756 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-17 18:13:27,756 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 96 transitions. [2022-03-17 18:13:27,757 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 96 transitions. Word has length 34 [2022-03-17 18:13:27,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:13:27,757 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 96 transitions. [2022-03-17 18:13:27,757 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-17 18:13:27,757 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 96 transitions. [2022-03-17 18:13:27,758 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-03-17 18:13:27,758 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:13:27,758 INFO L500 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-17 18:13:27,791 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-17 18:13:27,974 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-17 18:13:27,974 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:13:27,974 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:13:27,975 INFO L85 PathProgramCache]: Analyzing trace with hash 199111383, now seen corresponding path program 1 times [2022-03-17 18:13:27,975 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:13:27,975 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1525528891] [2022-03-17 18:13:27,975 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:27,975 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:13:27,991 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:13:27,991 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [677838483] [2022-03-17 18:13:27,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:13:27,991 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:13:27,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:13:28,006 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-17 18:13:28,007 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-17 18:13:28,112 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 18:13:28,128 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 42 conjunts are in the unsatisfiable core [2022-03-17 18:13:28,131 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:13:35,254 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 18:13:57,132 WARN L232 SmtUtils]: Spent 14.57s 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-17 18:14:09,431 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-17 18:14:09,431 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:14:12,568 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 18:14:20,700 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-17 18:14:20,701 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:14:20,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1525528891] [2022-03-17 18:14:20,701 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:14:20,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [677838483] [2022-03-17 18:14:20,701 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [677838483] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:14:20,701 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:14:20,701 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 11] total 24 [2022-03-17 18:14:20,703 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1805412769] [2022-03-17 18:14:20,703 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:14:20,704 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-17 18:14:20,704 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:14:20,704 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-17 18:14:20,705 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=94, Invalid=455, Unknown=3, NotChecked=0, Total=552 [2022-03-17 18:14:20,706 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-17 18:14:25,259 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-17 18:15:13,581 WARN L232 SmtUtils]: Spent 46.52s on a formula simplification that was a NOOP. DAG size: 68 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 18:15:15,274 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.68s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 18:15:17,100 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.09s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 18:15:18,299 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.19s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 18:15:22,153 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-17 18:15:26,350 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-17 18:15:28,506 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-17 18:15:30,573 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-17 18:15:33,882 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.45s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 18:15:43,284 WARN L232 SmtUtils]: Spent 8.42s 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-17 18:15:43,889 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:15:43,889 INFO L93 Difference]: Finished difference Result 125 states and 141 transitions. [2022-03-17 18:15:43,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-17 18:15:43,889 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-17 18:15:43,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:15:43,891 INFO L225 Difference]: With dead ends: 125 [2022-03-17 18:15:43,891 INFO L226 Difference]: Without dead ends: 125 [2022-03-17 18:15:43,893 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 74 SyntacticMatches, 4 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 283 ImplicationChecksByTransitivity, 93.5s TimeCoverageRelationStatistics Valid=187, Invalid=1000, Unknown=3, NotChecked=0, Total=1190 [2022-03-17 18:15:43,894 INFO L912 BasicCegarLoop]: 28 mSDtfsCounter, 53 mSDsluCounter, 262 mSDsCounter, 0 mSdLazyCounter, 284 mSolverCounterSat, 35 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 20.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 290 SdHoareTripleChecker+Invalid, 346 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 35 IncrementalHoareTripleChecker+Valid, 284 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 22 IncrementalHoareTripleChecker+Unchecked, 20.9s IncrementalHoareTripleChecker+Time [2022-03-17 18:15:43,894 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 290 Invalid, 346 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [35 Valid, 284 Invalid, 5 Unknown, 22 Unchecked, 20.9s Time] [2022-03-17 18:15:43,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-03-17 18:15:43,901 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 122. [2022-03-17 18:15:43,902 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-17 18:15:43,903 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 138 transitions. [2022-03-17 18:15:43,903 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 138 transitions. Word has length 48 [2022-03-17 18:15:43,903 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:15:43,903 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 138 transitions. [2022-03-17 18:15:43,903 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-17 18:15:43,904 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 138 transitions. [2022-03-17 18:15:43,905 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-17 18:15:43,905 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:15:43,905 INFO L500 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-17 18:15:43,945 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-17 18:15:44,132 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-17 18:15:44,133 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:15:44,133 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:15:44,133 INFO L85 PathProgramCache]: Analyzing trace with hash -831185954, now seen corresponding path program 2 times [2022-03-17 18:15:44,133 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:15:44,134 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1276420893] [2022-03-17 18:15:44,134 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:15:44,134 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:15:44,150 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:15:44,150 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [994534934] [2022-03-17 18:15:44,150 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 18:15:44,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:15:44,151 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:15:44,159 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-17 18:15:44,196 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-17 18:15:44,239 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 18:15:44,239 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 18:15:44,240 INFO L263 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-17 18:15:44,243 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:15:44,811 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-17 18:15:44,811 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:15:45,422 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-17 18:15:45,422 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:15:45,422 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1276420893] [2022-03-17 18:15:45,423 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:15:45,423 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [994534934] [2022-03-17 18:15:45,423 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [994534934] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:15:45,423 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:15:45,423 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-03-17 18:15:45,423 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [992150378] [2022-03-17 18:15:45,423 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:15:45,424 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-17 18:15:45,424 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:15:45,424 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-17 18:15:45,424 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=111, Unknown=0, NotChecked=0, Total=182 [2022-03-17 18:15:45,424 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-17 18:15:45,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:15:45,919 INFO L93 Difference]: Finished difference Result 295 states and 322 transitions. [2022-03-17 18:15:45,920 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-17 18:15:45,920 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-17 18:15:45,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:15:45,922 INFO L225 Difference]: With dead ends: 295 [2022-03-17 18:15:45,923 INFO L226 Difference]: Without dead ends: 295 [2022-03-17 18:15:45,923 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 103 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 55 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=184, Invalid=322, Unknown=0, NotChecked=0, Total=506 [2022-03-17 18:15:45,924 INFO L912 BasicCegarLoop]: 34 mSDtfsCounter, 149 mSDsluCounter, 124 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 149 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 18:15:45,924 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [149 Valid, 158 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 18:15:45,925 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 295 states. [2022-03-17 18:15:45,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 295 to 285. [2022-03-17 18:15:45,941 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-17 18:15:45,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 285 states to 285 states and 317 transitions. [2022-03-17 18:15:45,943 INFO L78 Accepts]: Start accepts. Automaton has 285 states and 317 transitions. Word has length 58 [2022-03-17 18:15:45,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:15:45,944 INFO L478 AbstractCegarLoop]: Abstraction has 285 states and 317 transitions. [2022-03-17 18:15:45,944 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-17 18:15:45,944 INFO L276 IsEmpty]: Start isEmpty. Operand 285 states and 317 transitions. [2022-03-17 18:15:45,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-17 18:15:45,945 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:15:45,946 INFO L500 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-17 18:15:45,974 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-17 18:15:46,163 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-17 18:15:46,163 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:15:46,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:15:46,164 INFO L85 PathProgramCache]: Analyzing trace with hash -339082250, now seen corresponding path program 2 times [2022-03-17 18:15:46,164 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:15:46,164 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1191658111] [2022-03-17 18:15:46,164 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:15:46,164 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:15:46,189 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:15:46,190 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1827100475] [2022-03-17 18:15:46,190 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 18:15:46,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:15:46,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:15:46,192 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-17 18:15:46,194 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-17 18:15:46,245 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 18:15:46,246 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 18:15:46,248 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 41 conjunts are in the unsatisfiable core [2022-03-17 18:15:46,250 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:15:49,490 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-17 18:15:49,490 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:15:56,657 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:15:56,658 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1191658111] [2022-03-17 18:15:56,658 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:15:56,658 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1827100475] [2022-03-17 18:15:56,658 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1827100475] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 18:15:56,658 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 18:15:56,658 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23] total 23 [2022-03-17 18:15:56,658 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1919062022] [2022-03-17 18:15:56,658 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 18:15:56,659 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2022-03-17 18:15:56,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:15:56,659 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2022-03-17 18:15:56,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=127, Invalid=685, Unknown=0, NotChecked=0, Total=812 [2022-03-17 18:15:56,660 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-17 18:15:57,693 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:15:57,693 INFO L93 Difference]: Finished difference Result 305 states and 341 transitions. [2022-03-17 18:15:57,693 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-17 18:15:57,694 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-17 18:15:57,694 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:15:57,696 INFO L225 Difference]: With dead ends: 305 [2022-03-17 18:15:57,697 INFO L226 Difference]: Without dead ends: 305 [2022-03-17 18:15:57,697 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 48 SyntacticMatches, 5 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 3 DeprecatedPredicates, 374 ImplicationChecksByTransitivity, 7.1s TimeCoverageRelationStatistics Valid=151, Invalid=905, Unknown=0, NotChecked=0, Total=1056 [2022-03-17 18:15:57,698 INFO L912 BasicCegarLoop]: 30 mSDtfsCounter, 30 mSDsluCounter, 347 mSDsCounter, 0 mSdLazyCounter, 307 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 307 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 85 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-17 18:15:57,698 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 377 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 307 Invalid, 0 Unknown, 85 Unchecked, 0.7s Time] [2022-03-17 18:15:57,698 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 305 states. [2022-03-17 18:15:57,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 305 to 305. [2022-03-17 18:15:57,709 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-17 18:15:57,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 305 states to 305 states and 341 transitions. [2022-03-17 18:15:57,710 INFO L78 Accepts]: Start accepts. Automaton has 305 states and 341 transitions. Word has length 58 [2022-03-17 18:15:57,711 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:15:57,711 INFO L478 AbstractCegarLoop]: Abstraction has 305 states and 341 transitions. [2022-03-17 18:15:57,711 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-17 18:15:57,711 INFO L276 IsEmpty]: Start isEmpty. Operand 305 states and 341 transitions. [2022-03-17 18:15:57,712 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-17 18:15:57,712 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:15:57,712 INFO L500 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-17 18:15:57,740 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-17 18:15:57,931 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-17 18:15:57,932 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:15:57,932 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:15:57,932 INFO L85 PathProgramCache]: Analyzing trace with hash 1548458294, now seen corresponding path program 3 times [2022-03-17 18:15:57,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:15:57,932 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [302299899] [2022-03-17 18:15:57,932 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:15:57,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:15:57,942 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:15:57,942 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1943948087] [2022-03-17 18:15:57,942 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 18:15:57,942 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:15:57,943 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:15:57,944 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-17 18:15:57,966 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-17 18:15:58,013 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-17 18:15:58,013 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 18:15:58,014 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 22 conjunts are in the unsatisfiable core [2022-03-17 18:15:58,016 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 18:16:00,117 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 18:16:03,200 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-17 18:16:03,200 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 18:16:04,966 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-17 18:16:04,967 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 18:16:04,967 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [302299899] [2022-03-17 18:16:04,967 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 18:16:04,967 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1943948087] [2022-03-17 18:16:04,967 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1943948087] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 18:16:04,967 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 18:16:04,967 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-03-17 18:16:04,967 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1713231146] [2022-03-17 18:16:04,967 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 18:16:04,968 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-17 18:16:04,968 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 18:16:04,968 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-17 18:16:04,968 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=268, Unknown=1, NotChecked=0, Total=342 [2022-03-17 18:16:04,969 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-17 18:16:06,665 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 18:16:06,665 INFO L93 Difference]: Finished difference Result 381 states and 424 transitions. [2022-03-17 18:16:06,666 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-17 18:16:06,666 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-17 18:16:06,666 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 18:16:06,668 INFO L225 Difference]: With dead ends: 381 [2022-03-17 18:16:06,668 INFO L226 Difference]: Without dead ends: 381 [2022-03-17 18:16:06,668 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 98 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=133, Invalid=466, Unknown=1, NotChecked=0, Total=600 [2022-03-17 18:16:06,669 INFO L912 BasicCegarLoop]: 27 mSDtfsCounter, 31 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 153 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 153 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 1 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-17 18:16:06,669 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 225 Invalid, 170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 153 Invalid, 0 Unknown, 1 Unchecked, 0.8s Time] [2022-03-17 18:16:06,670 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 381 states. [2022-03-17 18:16:06,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 381 to 210. [2022-03-17 18:16:06,677 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-17 18:16:06,678 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 210 states to 210 states and 235 transitions. [2022-03-17 18:16:06,678 INFO L78 Accepts]: Start accepts. Automaton has 210 states and 235 transitions. Word has length 58 [2022-03-17 18:16:06,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 18:16:06,679 INFO L478 AbstractCegarLoop]: Abstraction has 210 states and 235 transitions. [2022-03-17 18:16:06,679 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-17 18:16:06,679 INFO L276 IsEmpty]: Start isEmpty. Operand 210 states and 235 transitions. [2022-03-17 18:16:06,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-17 18:16:06,680 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 18:16:06,680 INFO L500 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-17 18:16:06,706 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-17 18:16:06,901 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-17 18:16:06,901 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 18:16:06,902 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 18:16:06,902 INFO L85 PathProgramCache]: Analyzing trace with hash 680514773, now seen corresponding path program 2 times [2022-03-17 18:16:06,902 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 18:16:06,902 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [47574940] [2022-03-17 18:16:06,902 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 18:16:06,902 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 18:16:06,910 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 18:16:06,910 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [515493426] [2022-03-17 18:16:06,910 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 18:16:06,911 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 18:16:06,911 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 18:16:06,928 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-17 18:16:06,930 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-17 18:16:07,008 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 18:16:07,009 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 18:16:07,025 INFO L263 TraceCheckSpWp]: Trace formula consists of 184 conjuncts, 46 conjunts are in the unsatisfiable core [2022-03-17 18:16:07,027 INFO L286 TraceCheckSpWp]: Computing forward predicates...