/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/egcd2-ll_valuebound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 02:30:21,472 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 02:30:21,486 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 02:30:21,514 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 02:30:21,514 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 02:30:21,515 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 02:30:21,516 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 02:30:21,518 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 02:30:21,520 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 02:30:21,521 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 02:30:21,521 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 02:30:21,522 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 02:30:21,523 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 02:30:21,524 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 02:30:21,524 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 02:30:21,525 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 02:30:21,526 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 02:30:21,527 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 02:30:21,528 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 02:30:21,530 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 02:30:21,531 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 02:30:21,532 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 02:30:21,533 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 02:30:21,533 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 02:30:21,534 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 02:30:21,536 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 02:30:21,537 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 02:30:21,537 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 02:30:21,538 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 02:30:21,538 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 02:30:21,539 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 02:30:21,539 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 02:30:21,540 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 02:30:21,540 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 02:30:21,541 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 02:30:21,542 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 02:30:21,542 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 02:30:21,543 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 02:30:21,543 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 02:30:21,543 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 02:30:21,544 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 02:30:21,545 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 02:30:21,546 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-04-05 02:30:21,554 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 02:30:21,555 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 02:30:21,556 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 02:30:21,557 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-05 02:30:21,557 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 02:30:21,557 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-05 02:30:21,557 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 02:30:21,557 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 02:30:21,558 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 02:30:21,559 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 02:30:21,559 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 02:30:21,559 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-05 02:30:21,559 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 02:30:21,559 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 02:30:21,559 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 02:30:21,560 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 02:30:21,560 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 02:30:21,561 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-04-05 02:30:21,839 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 02:30:21,877 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 02:30:21,880 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 02:30:21,880 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 02:30:21,882 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 02:30:21,883 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c [2022-04-05 02:30:21,939 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2c00ab45a/a37275369e6d4ae6b892f909dc9c3e74/FLAG9e9f1b6be [2022-04-05 02:30:22,381 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 02:30:22,382 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c [2022-04-05 02:30:22,389 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2c00ab45a/a37275369e6d4ae6b892f909dc9c3e74/FLAG9e9f1b6be [2022-04-05 02:30:22,407 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2c00ab45a/a37275369e6d4ae6b892f909dc9c3e74 [2022-04-05 02:30:22,411 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 02:30:22,412 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 02:30:22,414 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 02:30:22,414 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 02:30:22,421 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 02:30:22,422 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,424 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@49dde03f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22, skipping insertion in model container [2022-04-05 02:30:22,424 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,433 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 02:30:22,451 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 02:30:22,594 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/egcd2-ll_valuebound2.c[490,503] [2022-04-05 02:30:22,613 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 02:30:22,619 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 02:30:22,631 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/egcd2-ll_valuebound2.c[490,503] [2022-04-05 02:30:22,639 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 02:30:22,650 INFO L208 MainTranslator]: Completed translation [2022-04-05 02:30:22,650 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22 WrapperNode [2022-04-05 02:30:22,650 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 02:30:22,651 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 02:30:22,652 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 02:30:22,652 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 02:30:22,662 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,662 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,668 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,669 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,674 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,677 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,679 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,680 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 02:30:22,681 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 02:30:22,681 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 02:30:22,682 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 02:30:22,689 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (1/1) ... [2022-04-05 02:30:22,699 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 02:30:22,710 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:22,722 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-05 02:30:22,749 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-05 02:30:22,765 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 02:30:22,766 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 02:30:22,766 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 02:30:22,766 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 02:30:22,766 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 02:30:22,766 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 02:30:22,766 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 02:30:22,766 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 02:30:22,767 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 02:30:22,768 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 02:30:22,768 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 02:30:22,768 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 02:30:22,768 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 02:30:22,824 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 02:30:22,825 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 02:30:23,037 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 02:30:23,055 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 02:30:23,055 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 02:30:23,062 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 02:30:23 BoogieIcfgContainer [2022-04-05 02:30:23,062 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 02:30:23,063 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 02:30:23,063 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 02:30:23,064 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 02:30:23,067 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 02:30:23" (1/1) ... [2022-04-05 02:30:23,069 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-04-05 02:30:23,088 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 02:30:23 BasicIcfg [2022-04-05 02:30:23,088 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 02:30:23,090 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 02:30:23,090 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 02:30:23,103 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 02:30:23,103 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 02:30:22" (1/4) ... [2022-04-05 02:30:23,104 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5de5f30d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 02:30:23, skipping insertion in model container [2022-04-05 02:30:23,104 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 02:30:22" (2/4) ... [2022-04-05 02:30:23,104 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5de5f30d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 02:30:23, skipping insertion in model container [2022-04-05 02:30:23,104 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 02:30:23" (3/4) ... [2022-04-05 02:30:23,104 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5de5f30d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 02:30:23, skipping insertion in model container [2022-04-05 02:30:23,104 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 02:30:23" (4/4) ... [2022-04-05 02:30:23,105 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound2.cJordan [2022-04-05 02:30:23,110 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-04-05 02:30:23,110 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 02:30:23,183 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 02:30:23,191 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-04-05 02:30:23,192 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 02:30:23,219 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-05 02:30:23,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-04-05 02:30:23,230 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:23,231 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:23,232 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:23,238 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:23,239 INFO L85 PathProgramCache]: Analyzing trace with hash -1630657446, now seen corresponding path program 1 times [2022-04-05 02:30:23,248 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:23,248 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [135645448] [2022-04-05 02:30:23,248 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:23,251 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:23,378 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,461 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 02:30:23,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,473 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 02:30:23,480 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,485 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-05 02:30:23,487 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,491 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-05 02:30:23,493 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,504 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-04-05 02:30:23,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,512 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-04-05 02:30:23,514 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,519 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-04-05 02:30:23,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,528 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-05 02:30:23,528 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:23,528 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [135645448] [2022-04-05 02:30:23,529 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [135645448] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 02:30:23,529 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 02:30:23,529 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 02:30:23,531 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1419370253] [2022-04-05 02:30:23,531 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 02:30:23,535 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 02:30:23,535 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:23,560 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 02:30:23,561 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 02:30:23,563 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 02:30:23,673 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:23,673 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-04-05 02:30:23,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 02:30:23,676 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-04-05 02:30:23,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:23,683 INFO L225 Difference]: With dead ends: 40 [2022-04-05 02:30:23,683 INFO L226 Difference]: Without dead ends: 35 [2022-04-05 02:30:23,685 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 02:30:23,688 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:23,689 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:23,704 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-05 02:30:23,724 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-04-05 02:30:23,725 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 02:30:23,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-04-05 02:30:23,729 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-04-05 02:30:23,731 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:23,731 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-04-05 02:30:23,732 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 02:30:23,732 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-04-05 02:30:23,734 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-05 02:30:23,735 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:23,735 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:23,736 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 02:30:23,736 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:23,737 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:23,737 INFO L85 PathProgramCache]: Analyzing trace with hash -1790145708, now seen corresponding path program 1 times [2022-04-05 02:30:23,737 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:23,737 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1101755046] [2022-04-05 02:30:23,737 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:23,738 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:23,775 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:23,776 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [845215548] [2022-04-05 02:30:23,776 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:23,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:23,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:23,778 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:23,779 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-05 02:30:23,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:23,843 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-05 02:30:23,848 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:24,028 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 02:30:24,029 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:24,186 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 02:30:24,187 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:24,188 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1101755046] [2022-04-05 02:30:24,188 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:24,189 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [845215548] [2022-04-05 02:30:24,191 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [845215548] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:24,191 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:24,191 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-04-05 02:30:24,192 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [129500500] [2022-04-05 02:30:24,192 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:24,193 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-05 02:30:24,193 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:24,193 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-05 02:30:24,193 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 02:30:24,194 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 02:30:24,327 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:24,327 INFO L93 Difference]: Finished difference Result 44 states and 60 transitions. [2022-04-05 02:30:24,328 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 02:30:24,328 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-04-05 02:30:24,330 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:24,332 INFO L225 Difference]: With dead ends: 44 [2022-04-05 02:30:24,332 INFO L226 Difference]: Without dead ends: 44 [2022-04-05 02:30:24,333 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-04-05 02:30:24,334 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 67 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 78 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 67 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:24,335 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 104 Invalid, 78 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 67 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:24,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-05 02:30:24,350 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-05 02:30:24,351 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 02:30:24,354 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-04-05 02:30:24,354 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-04-05 02:30:24,354 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:24,355 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-04-05 02:30:24,355 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-05 02:30:24,355 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-04-05 02:30:24,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-05 02:30:24,358 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:24,358 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:24,390 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-04-05 02:30:24,579 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:24,580 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:24,580 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:24,581 INFO L85 PathProgramCache]: Analyzing trace with hash 375385207, now seen corresponding path program 1 times [2022-04-05 02:30:24,581 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:24,581 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1298451203] [2022-04-05 02:30:24,581 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:24,581 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:24,596 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:24,597 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [726603269] [2022-04-05 02:30:24,597 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:24,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:24,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:24,598 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:24,619 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-05 02:30:24,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:24,658 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 02:30:24,660 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:24,831 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 02:30:24,831 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:24,976 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-04-05 02:30:24,977 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:24,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1298451203] [2022-04-05 02:30:24,977 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:24,977 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [726603269] [2022-04-05 02:30:24,977 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [726603269] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:24,979 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:24,979 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-04-05 02:30:24,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2125983328] [2022-04-05 02:30:24,980 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 02:30:24,980 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 02:30:24,980 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:24,981 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 02:30:24,981 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-04-05 02:30:24,981 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-05 02:30:25,028 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:25,028 INFO L93 Difference]: Finished difference Result 41 states and 51 transitions. [2022-04-05 02:30:25,028 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 02:30:25,029 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-04-05 02:30:25,030 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:25,031 INFO L225 Difference]: With dead ends: 41 [2022-04-05 02:30:25,031 INFO L226 Difference]: Without dead ends: 41 [2022-04-05 02:30:25,032 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-05 02:30:25,035 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 97 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 137 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:25,037 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 137 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 02:30:25,039 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-05 02:30:25,050 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-04-05 02:30:25,050 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-05 02:30:25,055 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-04-05 02:30:25,055 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 45 [2022-04-05 02:30:25,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:25,056 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-04-05 02:30:25,056 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-04-05 02:30:25,056 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-04-05 02:30:25,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-04-05 02:30:25,058 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:25,058 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:25,081 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:25,271 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-05 02:30:25,272 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:25,272 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:25,272 INFO L85 PathProgramCache]: Analyzing trace with hash -788787523, now seen corresponding path program 1 times [2022-04-05 02:30:25,273 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:25,273 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1388772949] [2022-04-05 02:30:25,273 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:25,273 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:25,288 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:25,289 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1798538973] [2022-04-05 02:30:25,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:25,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:25,289 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:25,291 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:25,313 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-05 02:30:25,344 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:25,347 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-05 02:30:25,356 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:25,580 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-04-05 02:30:25,580 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:25,692 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:25,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1388772949] [2022-04-05 02:30:25,693 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:25,693 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1798538973] [2022-04-05 02:30:25,693 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1798538973] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:25,693 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:25,693 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-04-05 02:30:25,694 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1982150529] [2022-04-05 02:30:25,694 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:25,695 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 02:30:25,695 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:25,695 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 02:30:25,695 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-04-05 02:30:25,696 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 02:30:25,894 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:25,894 INFO L93 Difference]: Finished difference Result 52 states and 66 transitions. [2022-04-05 02:30:25,895 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 02:30:25,895 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-04-05 02:30:25,897 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:25,899 INFO L225 Difference]: With dead ends: 52 [2022-04-05 02:30:25,900 INFO L226 Difference]: Without dead ends: 52 [2022-04-05 02:30:25,900 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-04-05 02:30:25,905 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 138 mSDsCounter, 0 mSdLazyCounter, 225 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 168 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 225 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:25,907 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 168 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 225 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:25,912 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-05 02:30:25,916 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-04-05 02:30:25,916 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 02:30:25,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2022-04-05 02:30:25,921 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 50 [2022-04-05 02:30:25,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:25,921 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2022-04-05 02:30:25,921 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-04-05 02:30:25,922 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2022-04-05 02:30:25,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-05 02:30:25,922 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:25,922 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:25,981 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:26,143 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:26,144 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:26,144 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:26,144 INFO L85 PathProgramCache]: Analyzing trace with hash -735644649, now seen corresponding path program 1 times [2022-04-05 02:30:26,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:26,144 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1827368650] [2022-04-05 02:30:26,144 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:26,144 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:26,157 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:26,158 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1244166046] [2022-04-05 02:30:26,158 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:26,158 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:26,158 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:26,165 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:26,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-05 02:30:26,210 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:26,212 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-05 02:30:26,214 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:26,606 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 27 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2022-04-05 02:30:26,606 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:26,781 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-04-05 02:30:26,781 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:26,781 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1827368650] [2022-04-05 02:30:26,781 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:26,781 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1244166046] [2022-04-05 02:30:26,782 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1244166046] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:26,782 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:26,782 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [11] total 13 [2022-04-05 02:30:26,782 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [680920519] [2022-04-05 02:30:26,782 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 02:30:26,782 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 02:30:26,783 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:26,783 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 02:30:26,783 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2022-04-05 02:30:26,783 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-05 02:30:26,843 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:26,844 INFO L93 Difference]: Finished difference Result 56 states and 69 transitions. [2022-04-05 02:30:26,844 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 02:30:26,844 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 55 [2022-04-05 02:30:26,845 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:26,845 INFO L225 Difference]: With dead ends: 56 [2022-04-05 02:30:26,845 INFO L226 Difference]: Without dead ends: 56 [2022-04-05 02:30:26,846 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-04-05 02:30:26,846 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 12 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:26,847 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 146 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 02:30:26,847 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-04-05 02:30:26,851 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-04-05 02:30:26,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 02:30:26,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-05 02:30:26,852 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 55 [2022-04-05 02:30:26,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:26,853 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-05 02:30:26,853 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-05 02:30:26,853 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-05 02:30:26,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-04-05 02:30:26,854 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:26,854 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:26,873 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:27,059 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:27,060 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:27,060 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:27,060 INFO L85 PathProgramCache]: Analyzing trace with hash -1700404515, now seen corresponding path program 1 times [2022-04-05 02:30:27,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:27,060 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [150041067] [2022-04-05 02:30:27,060 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:27,061 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:27,073 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:27,073 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [311522787] [2022-04-05 02:30:27,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:27,074 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:27,074 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:27,075 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:27,095 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-05 02:30:27,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:27,129 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-05 02:30:27,131 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:27,328 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-04-05 02:30:27,328 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:27,411 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:27,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [150041067] [2022-04-05 02:30:27,411 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:27,411 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [311522787] [2022-04-05 02:30:27,411 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [311522787] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:27,412 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:27,412 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-04-05 02:30:27,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1811478927] [2022-04-05 02:30:27,412 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:27,412 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-04-05 02:30:27,412 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:27,413 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-04-05 02:30:27,413 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-04-05 02:30:27,413 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-05 02:30:27,527 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:27,527 INFO L93 Difference]: Finished difference Result 60 states and 72 transitions. [2022-04-05 02:30:27,528 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 02:30:27,528 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2022-04-05 02:30:27,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:27,533 INFO L225 Difference]: With dead ends: 60 [2022-04-05 02:30:27,533 INFO L226 Difference]: Without dead ends: 60 [2022-04-05 02:30:27,536 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-04-05 02:30:27,537 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 11 mSDsluCounter, 128 mSDsCounter, 0 mSdLazyCounter, 128 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 164 SdHoareTripleChecker+Invalid, 130 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 128 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:27,538 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 164 Invalid, 130 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 128 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:27,539 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-04-05 02:30:27,544 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-04-05 02:30:27,545 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 02:30:27,545 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-04-05 02:30:27,546 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 60 [2022-04-05 02:30:27,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:27,546 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-04-05 02:30:27,546 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-04-05 02:30:27,546 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-04-05 02:30:27,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-04-05 02:30:27,547 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:27,547 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:27,569 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-04-05 02:30:27,749 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:27,749 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:27,750 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:27,750 INFO L85 PathProgramCache]: Analyzing trace with hash 2004479621, now seen corresponding path program 1 times [2022-04-05 02:30:27,750 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:27,750 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [642357535] [2022-04-05 02:30:27,750 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:27,750 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:27,765 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:27,765 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1788265048] [2022-04-05 02:30:27,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:27,765 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:27,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:27,778 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:27,780 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-05 02:30:27,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:27,833 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 02:30:27,838 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:27,981 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-05 02:30:27,981 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:28,116 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-04-05 02:30:28,116 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:28,116 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [642357535] [2022-04-05 02:30:28,117 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:28,117 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1788265048] [2022-04-05 02:30:28,117 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1788265048] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:28,117 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:28,117 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-04-05 02:30:28,117 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1962933272] [2022-04-05 02:30:28,117 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:28,118 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 02:30:28,118 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:28,118 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 02:30:28,118 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-04-05 02:30:28,118 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-05 02:30:28,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:28,317 INFO L93 Difference]: Finished difference Result 98 states and 137 transitions. [2022-04-05 02:30:28,317 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 02:30:28,317 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-04-05 02:30:28,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:28,319 INFO L225 Difference]: With dead ends: 98 [2022-04-05 02:30:28,319 INFO L226 Difference]: Without dead ends: 98 [2022-04-05 02:30:28,319 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-04-05 02:30:28,319 INFO L913 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 239 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 299 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:28,320 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 299 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:28,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-04-05 02:30:28,327 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-04-05 02:30:28,328 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-05 02:30:28,329 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-04-05 02:30:28,329 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-04-05 02:30:28,329 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:28,329 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-04-05 02:30:28,330 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-04-05 02:30:28,330 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-04-05 02:30:28,330 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-05 02:30:28,330 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:28,331 INFO L499 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:28,358 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:28,543 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:28,544 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:28,544 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:28,544 INFO L85 PathProgramCache]: Analyzing trace with hash -966489810, now seen corresponding path program 1 times [2022-04-05 02:30:28,544 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:28,544 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [442788718] [2022-04-05 02:30:28,544 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:28,544 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:28,556 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:28,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1922741377] [2022-04-05 02:30:28,556 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:28,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:28,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:28,557 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:28,570 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-05 02:30:28,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:28,613 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2022-04-05 02:30:28,615 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:28,826 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-05 02:30:28,826 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:29,019 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-04-05 02:30:29,019 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:29,019 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [442788718] [2022-04-05 02:30:29,019 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:29,019 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1922741377] [2022-04-05 02:30:29,020 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1922741377] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:29,020 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:29,020 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-05 02:30:29,020 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1431993003] [2022-04-05 02:30:29,020 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:29,021 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 02:30:29,021 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:29,021 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 02:30:29,021 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-04-05 02:30:29,023 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-05 02:30:29,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:29,249 INFO L93 Difference]: Finished difference Result 130 states and 185 transitions. [2022-04-05 02:30:29,250 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-05 02:30:29,250 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 75 [2022-04-05 02:30:29,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:29,252 INFO L225 Difference]: With dead ends: 130 [2022-04-05 02:30:29,253 INFO L226 Difference]: Without dead ends: 128 [2022-04-05 02:30:29,253 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-04-05 02:30:29,254 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 39 mSDsluCounter, 130 mSDsCounter, 0 mSdLazyCounter, 234 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 289 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 234 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:29,254 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [45 Valid, 176 Invalid, 289 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 234 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 02:30:29,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2022-04-05 02:30:29,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 96. [2022-04-05 02:30:29,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 53 states have internal predecessors, (60), 36 states have call successors, (36), 9 states have call predecessors, (36), 8 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-04-05 02:30:29,263 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2022-04-05 02:30:29,263 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 75 [2022-04-05 02:30:29,264 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:29,264 INFO L478 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2022-04-05 02:30:29,264 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-04-05 02:30:29,264 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2022-04-05 02:30:29,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-04-05 02:30:29,265 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:29,265 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:29,295 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:29,478 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:29,479 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:29,479 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:29,479 INFO L85 PathProgramCache]: Analyzing trace with hash -271689658, now seen corresponding path program 2 times [2022-04-05 02:30:29,480 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:29,480 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [846945101] [2022-04-05 02:30:29,480 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:29,480 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:29,491 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:29,491 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1676381520] [2022-04-05 02:30:29,491 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 02:30:29,491 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:29,491 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:29,492 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:29,517 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-05 02:30:29,558 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 02:30:29,559 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:29,560 INFO L263 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-05 02:30:29,563 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:30,153 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 18 proven. 24 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2022-04-05 02:30:30,153 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:30,282 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:30,282 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [846945101] [2022-04-05 02:30:30,282 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:30,282 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1676381520] [2022-04-05 02:30:30,282 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1676381520] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:30,282 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:30,282 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-04-05 02:30:30,284 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1344119244] [2022-04-05 02:30:30,284 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:30,285 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 02:30:30,285 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:30,285 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 02:30:30,285 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2022-04-05 02:30:30,286 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-04-05 02:30:30,583 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:30,583 INFO L93 Difference]: Finished difference Result 126 states and 167 transitions. [2022-04-05 02:30:30,584 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 02:30:30,584 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 80 [2022-04-05 02:30:30,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:30,586 INFO L225 Difference]: With dead ends: 126 [2022-04-05 02:30:30,586 INFO L226 Difference]: Without dead ends: 126 [2022-04-05 02:30:30,586 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 85 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2022-04-05 02:30:30,587 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 35 mSDsluCounter, 185 mSDsCounter, 0 mSdLazyCounter, 327 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 229 SdHoareTripleChecker+Invalid, 354 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 327 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:30,587 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 229 Invalid, 354 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 327 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 02:30:30,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-04-05 02:30:30,594 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 123. [2022-04-05 02:30:30,594 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 67 states have (on average 1.164179104477612) internal successors, (78), 69 states have internal predecessors, (78), 44 states have call successors, (44), 12 states have call predecessors, (44), 11 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-05 02:30:30,596 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 164 transitions. [2022-04-05 02:30:30,596 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 164 transitions. Word has length 80 [2022-04-05 02:30:30,596 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:30,596 INFO L478 AbstractCegarLoop]: Abstraction has 123 states and 164 transitions. [2022-04-05 02:30:30,596 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-04-05 02:30:30,596 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 164 transitions. [2022-04-05 02:30:30,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-04-05 02:30:30,597 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:30,598 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:30,625 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:30,811 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-04-05 02:30:30,812 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:30,812 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:30,812 INFO L85 PathProgramCache]: Analyzing trace with hash -1540307954, now seen corresponding path program 3 times [2022-04-05 02:30:30,812 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:30,812 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [151178182] [2022-04-05 02:30:30,812 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:30,813 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:30,823 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:30,824 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1363949971] [2022-04-05 02:30:30,824 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 02:30:30,824 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:30,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:30,825 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:30,842 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-05 02:30:30,885 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-04-05 02:30:30,885 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:30,886 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 36 conjunts are in the unsatisfiable core [2022-04-05 02:30:30,889 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:31,301 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-04-05 02:30:31,302 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:31,391 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:31,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [151178182] [2022-04-05 02:30:31,391 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:31,391 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1363949971] [2022-04-05 02:30:31,391 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1363949971] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:31,391 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:31,391 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-05 02:30:31,391 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1147219282] [2022-04-05 02:30:31,391 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:31,393 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 02:30:31,393 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:31,393 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 02:30:31,393 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-05 02:30:31,393 INFO L87 Difference]: Start difference. First operand 123 states and 164 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-05 02:30:31,685 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:31,686 INFO L93 Difference]: Finished difference Result 130 states and 170 transitions. [2022-04-05 02:30:31,687 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-05 02:30:31,687 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 85 [2022-04-05 02:30:31,687 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:31,688 INFO L225 Difference]: With dead ends: 130 [2022-04-05 02:30:31,688 INFO L226 Difference]: Without dead ends: 130 [2022-04-05 02:30:31,688 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-04-05 02:30:31,689 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 19 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 277 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 287 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 277 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:31,689 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 208 Invalid, 287 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 277 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 02:30:31,690 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-04-05 02:30:31,695 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2022-04-05 02:30:31,696 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 70 states have (on average 1.1571428571428573) internal successors, (81), 72 states have internal predecessors, (81), 44 states have call successors, (44), 13 states have call predecessors, (44), 12 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-04-05 02:30:31,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 167 transitions. [2022-04-05 02:30:31,697 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 167 transitions. Word has length 85 [2022-04-05 02:30:31,697 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:31,697 INFO L478 AbstractCegarLoop]: Abstraction has 127 states and 167 transitions. [2022-04-05 02:30:31,697 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-04-05 02:30:31,698 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 167 transitions. [2022-04-05 02:30:31,698 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-04-05 02:30:31,698 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:31,698 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:31,723 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:31,919 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-04-05 02:30:31,920 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:31,920 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:31,920 INFO L85 PathProgramCache]: Analyzing trace with hash -757951041, now seen corresponding path program 1 times [2022-04-05 02:30:31,920 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:31,920 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1779509472] [2022-04-05 02:30:31,920 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:31,921 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:31,936 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:31,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [336001499] [2022-04-05 02:30:31,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:31,937 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:31,937 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:31,938 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:31,939 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-04-05 02:30:31,994 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:31,996 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-05 02:30:31,999 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:32,419 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-05 02:30:32,419 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:32,806 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-04-05 02:30:32,806 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:32,806 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1779509472] [2022-04-05 02:30:32,807 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:32,807 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [336001499] [2022-04-05 02:30:32,807 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [336001499] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:32,807 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:32,807 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-04-05 02:30:32,807 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [713674591] [2022-04-05 02:30:32,807 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:32,807 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-05 02:30:32,808 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:32,808 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-05 02:30:32,809 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-04-05 02:30:32,809 INFO L87 Difference]: Start difference. First operand 127 states and 167 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-05 02:30:34,736 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:34,736 INFO L93 Difference]: Finished difference Result 210 states and 297 transitions. [2022-04-05 02:30:34,737 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-04-05 02:30:34,737 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 91 [2022-04-05 02:30:34,737 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:34,739 INFO L225 Difference]: With dead ends: 210 [2022-04-05 02:30:34,739 INFO L226 Difference]: Without dead ends: 208 [2022-04-05 02:30:34,739 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=178, Invalid=692, Unknown=0, NotChecked=0, Total=870 [2022-04-05 02:30:34,740 INFO L913 BasicCegarLoop]: 78 mSDtfsCounter, 57 mSDsluCounter, 257 mSDsCounter, 0 mSdLazyCounter, 581 mSolverCounterSat, 142 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 335 SdHoareTripleChecker+Invalid, 723 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 581 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:34,740 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [61 Valid, 335 Invalid, 723 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 581 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2022-04-05 02:30:34,741 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2022-04-05 02:30:34,752 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 204. [2022-04-05 02:30:34,752 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 107 states have (on average 1.1962616822429906) internal successors, (128), 108 states have internal predecessors, (128), 81 states have call successors, (81), 16 states have call predecessors, (81), 15 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-04-05 02:30:34,754 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 288 transitions. [2022-04-05 02:30:34,754 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 288 transitions. Word has length 91 [2022-04-05 02:30:34,754 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:34,754 INFO L478 AbstractCegarLoop]: Abstraction has 204 states and 288 transitions. [2022-04-05 02:30:34,755 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-04-05 02:30:34,755 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 288 transitions. [2022-04-05 02:30:34,756 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-04-05 02:30:34,756 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:34,756 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:34,781 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-04-05 02:30:34,971 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-04-05 02:30:34,971 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:34,972 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:34,972 INFO L85 PathProgramCache]: Analyzing trace with hash -1452951817, now seen corresponding path program 4 times [2022-04-05 02:30:34,972 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:34,972 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1251771488] [2022-04-05 02:30:34,972 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:34,972 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:34,983 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:34,983 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1347726814] [2022-04-05 02:30:34,983 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 02:30:34,983 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:34,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:34,984 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-04-05 02:30:35,012 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-04-05 02:30:35,050 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 02:30:35,050 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:35,052 INFO L263 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 5 conjunts are in the unsatisfiable core [2022-04-05 02:30:35,053 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:35,191 INFO L134 CoverageAnalysis]: Checked inductivity of 281 backedges. 101 proven. 0 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-04-05 02:30:35,192 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 02:30:35,192 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:35,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1251771488] [2022-04-05 02:30:35,192 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:35,192 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1347726814] [2022-04-05 02:30:35,192 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1347726814] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 02:30:35,192 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 02:30:35,192 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 02:30:35,192 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [460108380] [2022-04-05 02:30:35,192 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 02:30:35,195 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 02:30:35,195 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:35,195 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 02:30:35,195 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 02:30:35,196 INFO L87 Difference]: Start difference. First operand 204 states and 288 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-04-05 02:30:35,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:35,269 INFO L93 Difference]: Finished difference Result 185 states and 250 transitions. [2022-04-05 02:30:35,269 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-05 02:30:35,270 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) Word has length 105 [2022-04-05 02:30:35,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:35,271 INFO L225 Difference]: With dead ends: 185 [2022-04-05 02:30:35,271 INFO L226 Difference]: Without dead ends: 185 [2022-04-05 02:30:35,272 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-04-05 02:30:35,272 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 6 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 64 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 69 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 64 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:35,272 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 161 Invalid, 69 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 64 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 02:30:35,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2022-04-05 02:30:35,278 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 171. [2022-04-05 02:30:35,279 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 90 states have (on average 1.1444444444444444) internal successors, (103), 91 states have internal predecessors, (103), 65 states have call successors, (65), 16 states have call predecessors, (65), 15 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-04-05 02:30:35,280 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 231 transitions. [2022-04-05 02:30:35,280 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 231 transitions. Word has length 105 [2022-04-05 02:30:35,281 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:35,281 INFO L478 AbstractCegarLoop]: Abstraction has 171 states and 231 transitions. [2022-04-05 02:30:35,281 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-04-05 02:30:35,281 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 231 transitions. [2022-04-05 02:30:35,282 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-04-05 02:30:35,282 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:35,282 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:35,311 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-04-05 02:30:35,499 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-04-05 02:30:35,499 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:35,500 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:35,500 INFO L85 PathProgramCache]: Analyzing trace with hash 1708635976, now seen corresponding path program 1 times [2022-04-05 02:30:35,500 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:35,500 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1130731947] [2022-04-05 02:30:35,500 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:35,500 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:35,513 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:35,513 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2055111650] [2022-04-05 02:30:35,514 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:35,514 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:35,514 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:35,517 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-04-05 02:30:35,519 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-04-05 02:30:35,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 02:30:35,576 INFO L263 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 02:30:35,578 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:35,807 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 122 proven. 23 refuted. 0 times theorem prover too weak. 175 trivial. 0 not checked. [2022-04-05 02:30:35,807 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:36,109 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 32 proven. 23 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2022-04-05 02:30:36,109 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:36,109 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1130731947] [2022-04-05 02:30:36,109 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:36,109 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2055111650] [2022-04-05 02:30:36,109 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2055111650] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:36,109 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:36,109 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2022-04-05 02:30:36,109 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [548467007] [2022-04-05 02:30:36,110 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:36,110 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-05 02:30:36,110 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:36,110 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-05 02:30:36,111 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-04-05 02:30:36,111 INFO L87 Difference]: Start difference. First operand 171 states and 231 transitions. Second operand has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) [2022-04-05 02:30:36,509 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:36,509 INFO L93 Difference]: Finished difference Result 150 states and 196 transitions. [2022-04-05 02:30:36,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-04-05 02:30:36,510 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) Word has length 107 [2022-04-05 02:30:36,510 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:36,511 INFO L225 Difference]: With dead ends: 150 [2022-04-05 02:30:36,511 INFO L226 Difference]: Without dead ends: 144 [2022-04-05 02:30:36,511 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 200 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=144, Invalid=456, Unknown=0, NotChecked=0, Total=600 [2022-04-05 02:30:36,512 INFO L913 BasicCegarLoop]: 53 mSDtfsCounter, 35 mSDsluCounter, 313 mSDsCounter, 0 mSdLazyCounter, 310 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 368 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 310 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:36,512 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 366 Invalid, 368 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 310 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 02:30:36,513 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2022-04-05 02:30:36,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 142. [2022-04-05 02:30:36,518 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 75 states have (on average 1.12) internal successors, (84), 76 states have internal predecessors, (84), 53 states have call successors, (53), 14 states have call predecessors, (53), 13 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 02:30:36,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 188 transitions. [2022-04-05 02:30:36,519 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 188 transitions. Word has length 107 [2022-04-05 02:30:36,519 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:36,519 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 188 transitions. [2022-04-05 02:30:36,519 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) [2022-04-05 02:30:36,519 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 188 transitions. [2022-04-05 02:30:36,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-04-05 02:30:36,520 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:36,521 INFO L499 BasicCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:36,548 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-04-05 02:30:36,746 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-05 02:30:36,746 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:36,746 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:36,747 INFO L85 PathProgramCache]: Analyzing trace with hash 259955901, now seen corresponding path program 2 times [2022-04-05 02:30:36,747 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:36,747 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [717051896] [2022-04-05 02:30:36,747 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:36,747 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:36,765 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:36,766 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1127763729] [2022-04-05 02:30:36,766 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 02:30:36,766 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:36,766 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:36,770 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:36,773 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-05 02:30:36,842 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 02:30:36,842 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:36,843 INFO L263 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 02:30:36,846 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:37,130 INFO L134 CoverageAnalysis]: Checked inductivity of 489 backedges. 154 proven. 18 refuted. 0 times theorem prover too weak. 317 trivial. 0 not checked. [2022-04-05 02:30:37,130 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:37,392 INFO L134 CoverageAnalysis]: Checked inductivity of 489 backedges. 48 proven. 32 refuted. 0 times theorem prover too weak. 409 trivial. 0 not checked. [2022-04-05 02:30:37,393 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:37,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [717051896] [2022-04-05 02:30:37,393 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:37,393 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1127763729] [2022-04-05 02:30:37,393 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1127763729] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:37,393 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:37,393 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-04-05 02:30:37,394 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [828922136] [2022-04-05 02:30:37,394 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:37,395 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 02:30:37,395 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:37,395 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 02:30:37,395 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2022-04-05 02:30:37,396 INFO L87 Difference]: Start difference. First operand 142 states and 188 transitions. Second operand has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2022-04-05 02:30:37,838 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:37,838 INFO L93 Difference]: Finished difference Result 146 states and 191 transitions. [2022-04-05 02:30:37,838 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-05 02:30:37,838 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) Word has length 127 [2022-04-05 02:30:37,839 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:37,840 INFO L225 Difference]: With dead ends: 146 [2022-04-05 02:30:37,840 INFO L226 Difference]: Without dead ends: 146 [2022-04-05 02:30:37,840 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 264 GetRequests, 238 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=151, Invalid=551, Unknown=0, NotChecked=0, Total=702 [2022-04-05 02:30:37,841 INFO L913 BasicCegarLoop]: 55 mSDtfsCounter, 41 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 380 mSolverCounterSat, 81 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 304 SdHoareTripleChecker+Invalid, 461 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 81 IncrementalHoareTripleChecker+Valid, 380 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:37,841 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 304 Invalid, 461 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [81 Valid, 380 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 02:30:37,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2022-04-05 02:30:37,846 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 142. [2022-04-05 02:30:37,851 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 76 states have internal predecessors, (82), 53 states have call successors, (53), 14 states have call predecessors, (53), 13 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 02:30:37,852 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 186 transitions. [2022-04-05 02:30:37,853 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 186 transitions. Word has length 127 [2022-04-05 02:30:37,853 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:37,853 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 186 transitions. [2022-04-05 02:30:37,854 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2022-04-05 02:30:37,854 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 186 transitions. [2022-04-05 02:30:37,855 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-04-05 02:30:37,855 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:37,855 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:37,876 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:38,056 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-05 02:30:38,056 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:38,056 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:38,056 INFO L85 PathProgramCache]: Analyzing trace with hash -928796440, now seen corresponding path program 2 times [2022-04-05 02:30:38,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:38,057 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1218148521] [2022-04-05 02:30:38,057 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:38,057 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:38,068 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:38,068 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [306700295] [2022-04-05 02:30:38,069 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 02:30:38,069 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:38,069 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:38,070 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:38,071 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-04-05 02:30:38,148 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 02:30:38,148 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:38,151 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 96 conjunts are in the unsatisfiable core [2022-04-05 02:30:38,155 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:39,711 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 119 proven. 151 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2022-04-05 02:30:39,711 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:40,617 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 154 proven. 12 refuted. 0 times theorem prover too weak. 449 trivial. 0 not checked. [2022-04-05 02:30:40,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:40,617 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1218148521] [2022-04-05 02:30:40,618 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:40,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [306700295] [2022-04-05 02:30:40,618 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [306700295] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:40,618 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:40,618 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 12] total 28 [2022-04-05 02:30:40,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1236306321] [2022-04-05 02:30:40,618 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:40,620 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2022-04-05 02:30:40,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:40,620 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2022-04-05 02:30:40,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=620, Unknown=0, NotChecked=0, Total=756 [2022-04-05 02:30:40,621 INFO L87 Difference]: Start difference. First operand 142 states and 186 transitions. Second operand has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) [2022-04-05 02:30:42,708 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:42,708 INFO L93 Difference]: Finished difference Result 168 states and 215 transitions. [2022-04-05 02:30:42,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-04-05 02:30:42,709 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) Word has length 138 [2022-04-05 02:30:42,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:42,710 INFO L225 Difference]: With dead ends: 168 [2022-04-05 02:30:42,711 INFO L226 Difference]: Without dead ends: 159 [2022-04-05 02:30:42,711 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 289 GetRequests, 246 SyntacticMatches, 3 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 422 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=335, Invalid=1387, Unknown=0, NotChecked=0, Total=1722 [2022-04-05 02:30:42,712 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 86 mSDsluCounter, 255 mSDsCounter, 0 mSdLazyCounter, 1067 mSolverCounterSat, 190 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 296 SdHoareTripleChecker+Invalid, 1257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 190 IncrementalHoareTripleChecker+Valid, 1067 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:42,712 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [94 Valid, 296 Invalid, 1257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [190 Valid, 1067 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2022-04-05 02:30:42,712 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2022-04-05 02:30:42,716 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 146. [2022-04-05 02:30:42,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 78 states have (on average 1.064102564102564) internal successors, (83), 78 states have internal predecessors, (83), 52 states have call successors, (52), 16 states have call predecessors, (52), 15 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 02:30:42,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 186 transitions. [2022-04-05 02:30:42,718 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 186 transitions. Word has length 138 [2022-04-05 02:30:42,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:42,718 INFO L478 AbstractCegarLoop]: Abstraction has 146 states and 186 transitions. [2022-04-05 02:30:42,718 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) [2022-04-05 02:30:42,718 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 186 transitions. [2022-04-05 02:30:42,720 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2022-04-05 02:30:42,720 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:42,720 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:42,748 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:42,936 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:42,937 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:42,937 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:42,937 INFO L85 PathProgramCache]: Analyzing trace with hash -1469599656, now seen corresponding path program 3 times [2022-04-05 02:30:42,937 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:42,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1614458121] [2022-04-05 02:30:42,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:42,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:42,954 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:42,954 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1476692154] [2022-04-05 02:30:42,954 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 02:30:42,954 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:42,954 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:42,959 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:42,961 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-04-05 02:30:43,054 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 02:30:43,055 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:43,057 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 52 conjunts are in the unsatisfiable core [2022-04-05 02:30:43,059 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:44,071 INFO L134 CoverageAnalysis]: Checked inductivity of 762 backedges. 118 proven. 59 refuted. 0 times theorem prover too weak. 585 trivial. 0 not checked. [2022-04-05 02:30:44,071 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:44,368 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 02:30:44,577 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:44,578 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1614458121] [2022-04-05 02:30:44,578 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:44,578 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1476692154] [2022-04-05 02:30:44,578 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1476692154] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 02:30:44,578 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 02:30:44,578 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-04-05 02:30:44,578 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1847081997] [2022-04-05 02:30:44,578 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:44,579 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-05 02:30:44,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:44,579 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-05 02:30:44,579 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=252, Unknown=0, NotChecked=0, Total=306 [2022-04-05 02:30:44,579 INFO L87 Difference]: Start difference. First operand 146 states and 186 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-05 02:30:44,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:44,911 INFO L93 Difference]: Finished difference Result 180 states and 230 transitions. [2022-04-05 02:30:44,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 02:30:44,912 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) Word has length 146 [2022-04-05 02:30:44,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:44,913 INFO L225 Difference]: With dead ends: 180 [2022-04-05 02:30:44,913 INFO L226 Difference]: Without dead ends: 180 [2022-04-05 02:30:44,913 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=80, Invalid=382, Unknown=0, NotChecked=0, Total=462 [2022-04-05 02:30:44,914 INFO L913 BasicCegarLoop]: 29 mSDtfsCounter, 33 mSDsluCounter, 147 mSDsCounter, 0 mSdLazyCounter, 398 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 176 SdHoareTripleChecker+Invalid, 419 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 398 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:44,914 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 176 Invalid, 419 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 398 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 02:30:44,915 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2022-04-05 02:30:44,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 179. [2022-04-05 02:30:44,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 179 states, 96 states have (on average 1.0625) internal successors, (102), 96 states have internal predecessors, (102), 64 states have call successors, (64), 19 states have call predecessors, (64), 18 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-04-05 02:30:44,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 179 states to 179 states and 229 transitions. [2022-04-05 02:30:44,921 INFO L78 Accepts]: Start accepts. Automaton has 179 states and 229 transitions. Word has length 146 [2022-04-05 02:30:44,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:44,921 INFO L478 AbstractCegarLoop]: Abstraction has 179 states and 229 transitions. [2022-04-05 02:30:44,921 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-04-05 02:30:44,922 INFO L276 IsEmpty]: Start isEmpty. Operand 179 states and 229 transitions. [2022-04-05 02:30:44,923 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 152 [2022-04-05 02:30:44,923 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:44,923 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:44,948 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:45,143 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-05 02:30:45,144 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:45,144 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:45,144 INFO L85 PathProgramCache]: Analyzing trace with hash -1402624196, now seen corresponding path program 4 times [2022-04-05 02:30:45,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:45,144 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [322237583] [2022-04-05 02:30:45,144 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:45,144 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:45,153 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:45,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [921883142] [2022-04-05 02:30:45,154 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-05 02:30:45,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:45,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:45,160 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:45,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-04-05 02:30:45,228 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-05 02:30:45,229 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:45,231 INFO L263 TraceCheckSpWp]: Trace formula consists of 309 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 02:30:45,234 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:45,526 INFO L134 CoverageAnalysis]: Checked inductivity of 840 backedges. 246 proven. 51 refuted. 0 times theorem prover too weak. 543 trivial. 0 not checked. [2022-04-05 02:30:45,526 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:45,921 INFO L134 CoverageAnalysis]: Checked inductivity of 840 backedges. 60 proven. 51 refuted. 0 times theorem prover too weak. 729 trivial. 0 not checked. [2022-04-05 02:30:45,922 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:45,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [322237583] [2022-04-05 02:30:45,922 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:45,922 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [921883142] [2022-04-05 02:30:45,922 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [921883142] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:45,922 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:45,922 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2022-04-05 02:30:45,922 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1744502564] [2022-04-05 02:30:45,922 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:45,923 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-05 02:30:45,923 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:45,923 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-05 02:30:45,923 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2022-04-05 02:30:45,924 INFO L87 Difference]: Start difference. First operand 179 states and 229 transitions. Second operand has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) [2022-04-05 02:30:46,285 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:46,285 INFO L93 Difference]: Finished difference Result 150 states and 188 transitions. [2022-04-05 02:30:46,286 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 02:30:46,286 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) Word has length 151 [2022-04-05 02:30:46,286 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:46,287 INFO L225 Difference]: With dead ends: 150 [2022-04-05 02:30:46,287 INFO L226 Difference]: Without dead ends: 124 [2022-04-05 02:30:46,287 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 310 GetRequests, 287 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=104, Invalid=448, Unknown=0, NotChecked=0, Total=552 [2022-04-05 02:30:46,288 INFO L913 BasicCegarLoop]: 62 mSDtfsCounter, 28 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 295 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 264 SdHoareTripleChecker+Invalid, 362 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 295 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:46,288 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 264 Invalid, 362 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 295 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 02:30:46,288 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-04-05 02:30:46,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2022-04-05 02:30:46,291 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 69 states have (on average 1.0434782608695652) internal successors, (72), 69 states have internal predecessors, (72), 40 states have call successors, (40), 15 states have call predecessors, (40), 14 states have return successors, (39), 39 states have call predecessors, (39), 39 states have call successors, (39) [2022-04-05 02:30:46,292 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 151 transitions. [2022-04-05 02:30:46,292 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 151 transitions. Word has length 151 [2022-04-05 02:30:46,292 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:46,292 INFO L478 AbstractCegarLoop]: Abstraction has 124 states and 151 transitions. [2022-04-05 02:30:46,293 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) [2022-04-05 02:30:46,293 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 151 transitions. [2022-04-05 02:30:46,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 172 [2022-04-05 02:30:46,295 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 02:30:46,295 INFO L499 BasicCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:46,320 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:46,510 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-04-05 02:30:46,510 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 02:30:46,510 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 02:30:46,510 INFO L85 PathProgramCache]: Analyzing trace with hash 477503177, now seen corresponding path program 5 times [2022-04-05 02:30:46,511 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 02:30:46,511 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [8681235] [2022-04-05 02:30:46,511 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 02:30:46,511 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 02:30:46,529 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 02:30:46,529 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1413633186] [2022-04-05 02:30:46,530 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-04-05 02:30:46,530 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 02:30:46,530 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 02:30:46,531 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 02:30:46,533 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-04-05 02:30:46,614 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2022-04-05 02:30:46,614 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 02:30:46,615 INFO L263 TraceCheckSpWp]: Trace formula consists of 331 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-05 02:30:46,618 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 02:30:46,956 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 234 proven. 68 refuted. 0 times theorem prover too weak. 813 trivial. 0 not checked. [2022-04-05 02:30:46,956 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 02:30:47,490 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 84 proven. 62 refuted. 0 times theorem prover too weak. 969 trivial. 0 not checked. [2022-04-05 02:30:47,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 02:30:47,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [8681235] [2022-04-05 02:30:47,491 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 02:30:47,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1413633186] [2022-04-05 02:30:47,491 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1413633186] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 02:30:47,491 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 02:30:47,491 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 20 [2022-04-05 02:30:47,491 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1366475631] [2022-04-05 02:30:47,491 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 02:30:47,492 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-04-05 02:30:47,492 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 02:30:47,492 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-04-05 02:30:47,492 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=319, Unknown=0, NotChecked=0, Total=380 [2022-04-05 02:30:47,492 INFO L87 Difference]: Start difference. First operand 124 states and 151 transitions. Second operand has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) [2022-04-05 02:30:47,985 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 02:30:47,985 INFO L93 Difference]: Finished difference Result 93 states and 108 transitions. [2022-04-05 02:30:47,986 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-05 02:30:47,986 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) Word has length 171 [2022-04-05 02:30:47,986 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 02:30:47,986 INFO L225 Difference]: With dead ends: 93 [2022-04-05 02:30:47,986 INFO L226 Difference]: Without dead ends: 0 [2022-04-05 02:30:47,987 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 350 GetRequests, 323 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=168, Invalid=644, Unknown=0, NotChecked=0, Total=812 [2022-04-05 02:30:47,987 INFO L913 BasicCegarLoop]: 65 mSDtfsCounter, 27 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 458 mSolverCounterSat, 138 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 329 SdHoareTripleChecker+Invalid, 596 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 138 IncrementalHoareTripleChecker+Valid, 458 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-05 02:30:47,987 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 329 Invalid, 596 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [138 Valid, 458 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-05 02:30:47,988 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-05 02:30:47,988 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-05 02:30:47,988 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-05 02:30:47,988 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-05 02:30:47,988 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 171 [2022-04-05 02:30:47,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 02:30:47,988 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-05 02:30:47,988 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) [2022-04-05 02:30:47,988 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-05 02:30:47,989 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-05 02:30:47,991 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-05 02:30:48,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-04-05 02:30:48,207 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-04-05 02:30:48,211 INFO L719 BasicCegarLoop]: Path program histogram: [5, 4, 2, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 02:30:48,212 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-05 02:30:48,214 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 02:30:48 BasicIcfg [2022-04-05 02:30:48,214 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-05 02:30:48,215 INFO L158 Benchmark]: Toolchain (without parser) took 25802.73ms. Allocated memory was 183.5MB in the beginning and 221.2MB in the end (delta: 37.7MB). Free memory was 137.0MB in the beginning and 188.6MB in the end (delta: -51.5MB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-05 02:30:48,215 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 183.5MB. Free memory is still 153.9MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-05 02:30:48,215 INFO L158 Benchmark]: CACSL2BoogieTranslator took 237.10ms. Allocated memory is still 183.5MB. Free memory was 136.8MB in the beginning and 162.0MB in the end (delta: -25.2MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. [2022-04-05 02:30:48,215 INFO L158 Benchmark]: Boogie Preprocessor took 29.29ms. Allocated memory is still 183.5MB. Free memory was 162.0MB in the beginning and 160.7MB in the end (delta: 1.3MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-05 02:30:48,215 INFO L158 Benchmark]: RCFGBuilder took 380.78ms. Allocated memory is still 183.5MB. Free memory was 160.5MB in the beginning and 149.4MB in the end (delta: 11.0MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-05 02:30:48,216 INFO L158 Benchmark]: IcfgTransformer took 25.70ms. Allocated memory is still 183.5MB. Free memory was 149.4MB in the beginning and 147.9MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-05 02:30:48,216 INFO L158 Benchmark]: TraceAbstraction took 25124.49ms. Allocated memory was 183.5MB in the beginning and 221.2MB in the end (delta: 37.7MB). Free memory was 147.3MB in the beginning and 188.6MB in the end (delta: -41.2MB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-05 02:30:48,217 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 183.5MB. Free memory is still 153.9MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 237.10ms. Allocated memory is still 183.5MB. Free memory was 136.8MB in the beginning and 162.0MB in the end (delta: -25.2MB). Peak memory consumption was 13.6MB. Max. memory is 8.0GB. * Boogie Preprocessor took 29.29ms. Allocated memory is still 183.5MB. Free memory was 162.0MB in the beginning and 160.7MB in the end (delta: 1.3MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 380.78ms. Allocated memory is still 183.5MB. Free memory was 160.5MB in the beginning and 149.4MB in the end (delta: 11.0MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * IcfgTransformer took 25.70ms. Allocated memory is still 183.5MB. Free memory was 149.4MB in the beginning and 147.9MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 25124.49ms. Allocated memory was 183.5MB in the beginning and 221.2MB in the end (delta: 37.7MB). Free memory was 147.3MB in the beginning and 188.6MB in the end (delta: -41.2MB). There was no memory consumed. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 40 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 25.0s, OverallIterations: 18, TraceHistogramMax: 23, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 8.0s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 625 SdHoareTripleChecker+Valid, 5.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 532 mSDsluCounter, 3904 SdHoareTripleChecker+Invalid, 5.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 3047 mSDsCounter, 888 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 5122 IncrementalHoareTripleChecker+Invalid, 6010 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 888 mSolverCounterUnsat, 857 mSDtfsCounter, 5122 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2853 GetRequests, 2538 SyntacticMatches, 19 SemanticMatches, 296 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1023 ImplicationChecksByTransitivity, 4.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=204occurred in iteration=11, InterpolantAutomatonStates: 201, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 18 MinimizatonAttempts, 95 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.2s SsaConstructionTime, 0.7s SatisfiabilityAnalysisTime, 11.5s InterpolantComputationTime, 1642 NumberOfCodeBlocks, 1520 NumberOfCodeBlocksAsserted, 35 NumberOfCheckSat, 2686 ConstructedInterpolants, 0 QuantifiedInterpolants, 9132 SizeOfPredicates, 113 NumberOfNonLiveVariables, 3743 ConjunctsInSsa, 435 ConjunctsInUnsatCore, 29 InterpolantComputations, 4 PerfectInterpolantSequences, 8794/9490 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2022-04-05 02:30:48,251 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...