/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/divbin2_unwindbound20.i -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 16:31:13,965 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 16:31:13,966 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 16:31:14,002 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 16:31:14,003 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 16:31:14,004 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 16:31:14,005 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 16:31:14,007 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 16:31:14,009 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 16:31:14,012 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 16:31:14,012 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 16:31:14,013 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 16:31:14,013 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 16:31:14,015 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 16:31:14,015 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 16:31:14,017 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 16:31:14,018 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 16:31:14,018 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 16:31:14,020 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 16:31:14,023 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 16:31:14,024 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 16:31:14,025 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 16:31:14,026 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 16:31:14,026 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 16:31:14,027 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 16:31:14,032 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 16:31:14,032 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 16:31:14,032 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 16:31:14,033 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 16:31:14,033 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 16:31:14,034 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 16:31:14,034 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 16:31:14,035 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 16:31:14,036 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 16:31:14,036 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 16:31:14,037 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 16:31:14,037 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 16:31:14,037 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 16:31:14,037 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 16:31:14,038 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 16:31:14,038 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 16:31:14,039 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 16:31:14,040 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-17 16:31:14,049 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 16:31:14,049 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 16:31:14,051 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 16:31:14,051 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-17 16:31:14,051 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 16:31:14,051 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-17 16:31:14,051 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 16:31:14,051 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 16:31:14,052 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 16:31:14,053 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 16:31:14,053 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 16:31:14,053 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-17 16:31:14,053 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 16:31:14,053 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 16:31:14,053 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 16:31:14,053 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 16:31:14,053 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 16:31:14,054 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-17 16:31:14,237 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 16:31:14,250 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 16:31:14,252 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 16:31:14,252 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 16:31:14,253 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 16:31:14,253 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound20.i [2022-03-17 16:31:14,311 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7790a4bdd/23f57b76a5d04aa3b5e8db62dd2627f2/FLAG77834e4b4 [2022-03-17 16:31:14,657 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 16:31:14,657 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound20.i [2022-03-17 16:31:14,661 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7790a4bdd/23f57b76a5d04aa3b5e8db62dd2627f2/FLAG77834e4b4 [2022-03-17 16:31:14,670 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/7790a4bdd/23f57b76a5d04aa3b5e8db62dd2627f2 [2022-03-17 16:31:14,672 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 16:31:14,673 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 16:31:14,674 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 16:31:14,674 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 16:31:14,683 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 16:31:14,684 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,684 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@717313bc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14, skipping insertion in model container [2022-03-17 16:31:14,685 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,690 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 16:31:14,700 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 16:31:14,813 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound20.i[951,964] [2022-03-17 16:31:14,822 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 16:31:14,827 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 16:31:14,836 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/divbin2_unwindbound20.i[951,964] [2022-03-17 16:31:14,839 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 16:31:14,846 INFO L208 MainTranslator]: Completed translation [2022-03-17 16:31:14,846 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14 WrapperNode [2022-03-17 16:31:14,846 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 16:31:14,847 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 16:31:14,847 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 16:31:14,847 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 16:31:14,853 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,853 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,856 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,857 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,859 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,861 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,862 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,863 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 16:31:14,863 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 16:31:14,863 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 16:31:14,864 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 16:31:14,864 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (1/1) ... [2022-03-17 16:31:14,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 16:31:14,874 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:14,882 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-17 16:31:14,886 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 16:31:14,907 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_perror_fail [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure __assert [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 16:31:14,908 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 16:31:14,909 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 16:31:14,909 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 16:31:14,909 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 16:31:14,909 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 16:31:14,952 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 16:31:14,953 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 16:31:15,051 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 16:31:15,056 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 16:31:15,056 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 16:31:15,057 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 04:31:15 BoogieIcfgContainer [2022-03-17 16:31:15,057 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 16:31:15,058 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 16:31:15,058 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 16:31:15,058 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 16:31:15,060 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 04:31:15" (1/1) ... [2022-03-17 16:31:15,070 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 04:31:15 BasicIcfg [2022-03-17 16:31:15,071 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 16:31:15,088 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 16:31:15,088 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 16:31:15,090 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 16:31:15,090 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 04:31:14" (1/4) ... [2022-03-17 16:31:15,091 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3a23eb56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 04:31:15, skipping insertion in model container [2022-03-17 16:31:15,091 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 04:31:14" (2/4) ... [2022-03-17 16:31:15,091 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3a23eb56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 04:31:15, skipping insertion in model container [2022-03-17 16:31:15,091 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 04:31:15" (3/4) ... [2022-03-17 16:31:15,091 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3a23eb56 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 04:31:15, skipping insertion in model container [2022-03-17 16:31:15,092 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 04:31:15" (4/4) ... [2022-03-17 16:31:15,092 INFO L111 eAbstractionObserver]: Analyzing ICFG divbin2_unwindbound20.iJordan [2022-03-17 16:31:15,095 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-17 16:31:15,095 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 16:31:15,138 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 16:31:15,142 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-17 16:31:15,142 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 16:31:15,155 INFO L276 IsEmpty]: Start isEmpty. Operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-03-17 16:31:15,160 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2022-03-17 16:31:15,160 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:15,161 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:15,161 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:15,164 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:15,164 INFO L85 PathProgramCache]: Analyzing trace with hash 2097950667, now seen corresponding path program 1 times [2022-03-17 16:31:15,170 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:15,170 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1844484231] [2022-03-17 16:31:15,170 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:15,171 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:15,235 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:15,308 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 16:31:15,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:15,324 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:15,325 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:15,325 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1844484231] [2022-03-17 16:31:15,325 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1844484231] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 16:31:15,326 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 16:31:15,326 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 16:31:15,327 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1586249934] [2022-03-17 16:31:15,327 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:15,330 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 16:31:15,330 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:15,353 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 16:31:15,354 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 16:31:15,356 INFO L87 Difference]: Start difference. First operand has 26 states, 17 states have (on average 1.5294117647058822) internal successors, (26), 18 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Second operand has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,406 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:15,407 INFO L93 Difference]: Finished difference Result 27 states and 32 transitions. [2022-03-17 16:31:15,408 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 16:31:15,409 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2022-03-17 16:31:15,409 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:15,422 INFO L225 Difference]: With dead ends: 27 [2022-03-17 16:31:15,422 INFO L226 Difference]: Without dead ends: 22 [2022-03-17 16:31:15,424 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 16:31:15,427 INFO L912 BasicCegarLoop]: 30 mSDtfsCounter, 6 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 18 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 18 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:15,428 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 34 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 18 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:15,438 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 22 states. [2022-03-17 16:31:15,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 22 to 21. [2022-03-17 16:31:15,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 14 states have (on average 1.4285714285714286) internal successors, (20), 15 states have internal predecessors, (20), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 16:31:15,458 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 26 transitions. [2022-03-17 16:31:15,458 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 26 transitions. Word has length 12 [2022-03-17 16:31:15,458 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:15,459 INFO L478 AbstractCegarLoop]: Abstraction has 21 states and 26 transitions. [2022-03-17 16:31:15,459 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 2.6666666666666665) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,459 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 26 transitions. [2022-03-17 16:31:15,459 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2022-03-17 16:31:15,459 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:15,459 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:15,459 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 16:31:15,460 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:15,463 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:15,463 INFO L85 PathProgramCache]: Analyzing trace with hash 923003056, now seen corresponding path program 1 times [2022-03-17 16:31:15,463 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:15,463 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [317708926] [2022-03-17 16:31:15,464 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:15,464 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:15,476 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:15,513 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 16:31:15,517 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:15,524 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:15,524 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:15,524 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [317708926] [2022-03-17 16:31:15,524 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [317708926] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 16:31:15,524 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 16:31:15,524 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-17 16:31:15,525 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2115338612] [2022-03-17 16:31:15,525 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:15,525 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 16:31:15,526 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:15,526 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 16:31:15,526 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 16:31:15,526 INFO L87 Difference]: Start difference. First operand 21 states and 26 transitions. Second operand has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,566 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:15,566 INFO L93 Difference]: Finished difference Result 23 states and 28 transitions. [2022-03-17 16:31:15,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 16:31:15,567 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 14 [2022-03-17 16:31:15,567 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:15,567 INFO L225 Difference]: With dead ends: 23 [2022-03-17 16:31:15,567 INFO L226 Difference]: Without dead ends: 23 [2022-03-17 16:31:15,568 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-17 16:31:15,569 INFO L912 BasicCegarLoop]: 24 mSDtfsCounter, 6 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 53 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:15,569 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 53 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:15,570 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 23 states. [2022-03-17 16:31:15,584 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 23 to 23. [2022-03-17 16:31:15,584 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 23 states, 16 states have (on average 1.375) internal successors, (22), 17 states have internal predecessors, (22), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 16:31:15,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 23 states to 23 states and 28 transitions. [2022-03-17 16:31:15,585 INFO L78 Accepts]: Start accepts. Automaton has 23 states and 28 transitions. Word has length 14 [2022-03-17 16:31:15,585 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:15,585 INFO L478 AbstractCegarLoop]: Abstraction has 23 states and 28 transitions. [2022-03-17 16:31:15,586 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,586 INFO L276 IsEmpty]: Start isEmpty. Operand 23 states and 28 transitions. [2022-03-17 16:31:15,586 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-03-17 16:31:15,586 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:15,586 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:15,586 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-17 16:31:15,587 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:15,587 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:15,587 INFO L85 PathProgramCache]: Analyzing trace with hash 1207414063, now seen corresponding path program 1 times [2022-03-17 16:31:15,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:15,588 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1591075937] [2022-03-17 16:31:15,588 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:15,588 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:15,600 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:15,600 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1855105198] [2022-03-17 16:31:15,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:15,601 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:15,601 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:15,606 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:15,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-17 16:31:15,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:15,661 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 16:31:15,665 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:15,763 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:15,764 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 16:31:15,764 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:15,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1591075937] [2022-03-17 16:31:15,764 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:15,764 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1855105198] [2022-03-17 16:31:15,764 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1855105198] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 16:31:15,764 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 16:31:15,765 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 16:31:15,765 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [14591083] [2022-03-17 16:31:15,765 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:15,765 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 16:31:15,765 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:15,766 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 16:31:15,766 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 16:31:15,766 INFO L87 Difference]: Start difference. First operand 23 states and 28 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,787 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:15,788 INFO L93 Difference]: Finished difference Result 27 states and 33 transitions. [2022-03-17 16:31:15,788 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 16:31:15,788 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-03-17 16:31:15,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:15,789 INFO L225 Difference]: With dead ends: 27 [2022-03-17 16:31:15,789 INFO L226 Difference]: Without dead ends: 27 [2022-03-17 16:31:15,789 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 14 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 16:31:15,790 INFO L912 BasicCegarLoop]: 23 mSDtfsCounter, 3 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 81 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:15,790 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 81 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:15,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-03-17 16:31:15,792 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 26. [2022-03-17 16:31:15,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 26 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 4 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 16:31:15,793 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 26 states to 26 states and 32 transitions. [2022-03-17 16:31:15,793 INFO L78 Accepts]: Start accepts. Automaton has 26 states and 32 transitions. Word has length 15 [2022-03-17 16:31:15,793 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:15,793 INFO L478 AbstractCegarLoop]: Abstraction has 26 states and 32 transitions. [2022-03-17 16:31:15,793 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 3 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:15,793 INFO L276 IsEmpty]: Start isEmpty. Operand 26 states and 32 transitions. [2022-03-17 16:31:15,794 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 16 [2022-03-17 16:31:15,794 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:15,794 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:15,820 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:16,018 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:16,019 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:16,019 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:16,019 INFO L85 PathProgramCache]: Analyzing trace with hash 1208546121, now seen corresponding path program 1 times [2022-03-17 16:31:16,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:16,020 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1900972256] [2022-03-17 16:31:16,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:16,028 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:16,028 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1695332037] [2022-03-17 16:31:16,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:16,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:16,036 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:16,038 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-17 16:31:16,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:16,082 INFO L263 TraceCheckSpWp]: Trace formula consists of 73 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 16:31:16,083 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:16,275 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:16,275 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 16:31:16,277 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:16,277 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1900972256] [2022-03-17 16:31:16,278 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:16,278 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1695332037] [2022-03-17 16:31:16,278 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1695332037] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 16:31:16,278 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 16:31:16,278 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 16:31:16,278 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [411904128] [2022-03-17 16:31:16,278 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:16,278 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 16:31:16,279 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:16,279 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 16:31:16,279 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2022-03-17 16:31:16,279 INFO L87 Difference]: Start difference. First operand 26 states and 32 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:16,326 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:16,326 INFO L93 Difference]: Finished difference Result 33 states and 40 transitions. [2022-03-17 16:31:16,327 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 16:31:16,327 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 15 [2022-03-17 16:31:16,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:16,327 INFO L225 Difference]: With dead ends: 33 [2022-03-17 16:31:16,328 INFO L226 Difference]: Without dead ends: 32 [2022-03-17 16:31:16,328 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2022-03-17 16:31:16,329 INFO L912 BasicCegarLoop]: 21 mSDtfsCounter, 9 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:16,329 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 96 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:16,329 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-03-17 16:31:16,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-03-17 16:31:16,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.3043478260869565) internal successors, (30), 24 states have internal predecessors, (30), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-17 16:31:16,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2022-03-17 16:31:16,333 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 15 [2022-03-17 16:31:16,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:16,333 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2022-03-17 16:31:16,333 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 5 states have internal predecessors, (11), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:16,333 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2022-03-17 16:31:16,333 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-03-17 16:31:16,334 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:16,334 INFO L500 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:16,365 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:16,534 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-03-17 16:31:16,535 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:16,535 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:16,535 INFO L85 PathProgramCache]: Analyzing trace with hash 1227316531, now seen corresponding path program 1 times [2022-03-17 16:31:16,535 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:16,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1146264453] [2022-03-17 16:31:16,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:16,547 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:16,548 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1840156497] [2022-03-17 16:31:16,548 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,548 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:16,548 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:16,555 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:16,558 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-17 16:31:16,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:16,598 INFO L263 TraceCheckSpWp]: Trace formula consists of 80 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 16:31:16,599 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:16,649 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:16,649 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 16:31:16,700 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:16,700 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:16,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1146264453] [2022-03-17 16:31:16,701 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:16,701 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1840156497] [2022-03-17 16:31:16,701 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1840156497] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 16:31:16,701 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 16:31:16,701 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-17 16:31:16,701 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1335039302] [2022-03-17 16:31:16,701 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 16:31:16,702 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-17 16:31:16,702 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:16,703 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-17 16:31:16,703 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-17 16:31:16,703 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:16,758 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:16,758 INFO L93 Difference]: Finished difference Result 54 states and 66 transitions. [2022-03-17 16:31:16,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 16:31:16,759 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-03-17 16:31:16,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:16,761 INFO L225 Difference]: With dead ends: 54 [2022-03-17 16:31:16,761 INFO L226 Difference]: Without dead ends: 54 [2022-03-17 16:31:16,761 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-03-17 16:31:16,762 INFO L912 BasicCegarLoop]: 25 mSDtfsCounter, 31 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:16,762 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 94 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:16,763 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2022-03-17 16:31:16,770 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 40. [2022-03-17 16:31:16,770 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 40 states, 31 states have (on average 1.2903225806451613) internal successors, (40), 32 states have internal predecessors, (40), 5 states have call successors, (5), 4 states have call predecessors, (5), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-17 16:31:16,771 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 40 states to 40 states and 48 transitions. [2022-03-17 16:31:16,771 INFO L78 Accepts]: Start accepts. Automaton has 40 states and 48 transitions. Word has length 17 [2022-03-17 16:31:16,771 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:16,771 INFO L478 AbstractCegarLoop]: Abstraction has 40 states and 48 transitions. [2022-03-17 16:31:16,771 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:16,771 INFO L276 IsEmpty]: Start isEmpty. Operand 40 states and 48 transitions. [2022-03-17 16:31:16,771 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 16:31:16,772 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:16,772 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:16,789 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:16,975 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:16,976 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:16,976 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:16,976 INFO L85 PathProgramCache]: Analyzing trace with hash 2051197196, now seen corresponding path program 1 times [2022-03-17 16:31:16,976 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:16,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2039938533] [2022-03-17 16:31:16,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,977 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:16,985 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:16,985 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [499018441] [2022-03-17 16:31:16,985 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:16,986 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:16,986 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:16,988 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:16,989 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-17 16:31:17,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:17,017 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 16:31:17,018 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:17,070 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:17,070 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 16:31:17,120 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:17,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:17,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2039938533] [2022-03-17 16:31:17,120 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:17,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [499018441] [2022-03-17 16:31:17,120 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [499018441] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 16:31:17,120 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 16:31:17,121 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-03-17 16:31:17,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005941901] [2022-03-17 16:31:17,121 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 16:31:17,121 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 16:31:17,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:17,122 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 16:31:17,122 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-03-17 16:31:17,122 INFO L87 Difference]: Start difference. First operand 40 states and 48 transitions. Second operand has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:17,196 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:17,197 INFO L93 Difference]: Finished difference Result 84 states and 102 transitions. [2022-03-17 16:31:17,197 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-17 16:31:17,198 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-03-17 16:31:17,198 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:17,198 INFO L225 Difference]: With dead ends: 84 [2022-03-17 16:31:17,198 INFO L226 Difference]: Without dead ends: 84 [2022-03-17 16:31:17,199 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=63, Invalid=119, Unknown=0, NotChecked=0, Total=182 [2022-03-17 16:31:17,199 INFO L912 BasicCegarLoop]: 27 mSDtfsCounter, 79 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 79 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 70 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:17,199 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [79 Valid, 136 Invalid, 70 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:17,200 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-03-17 16:31:17,204 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 77. [2022-03-17 16:31:17,204 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 77 states, 59 states have (on average 1.3728813559322033) internal successors, (81), 63 states have internal predecessors, (81), 11 states have call successors, (11), 7 states have call predecessors, (11), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-17 16:31:17,206 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 77 states to 77 states and 98 transitions. [2022-03-17 16:31:17,206 INFO L78 Accepts]: Start accepts. Automaton has 77 states and 98 transitions. Word has length 18 [2022-03-17 16:31:17,207 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:17,207 INFO L478 AbstractCegarLoop]: Abstraction has 77 states and 98 transitions. [2022-03-17 16:31:17,207 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.5) internal successors, (25), 9 states have internal predecessors, (25), 4 states have call successors, (4), 4 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:17,207 INFO L276 IsEmpty]: Start isEmpty. Operand 77 states and 98 transitions. [2022-03-17 16:31:17,207 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 16:31:17,207 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:17,207 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:17,225 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:17,414 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:17,414 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:17,415 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:17,415 INFO L85 PathProgramCache]: Analyzing trace with hash 2052329254, now seen corresponding path program 1 times [2022-03-17 16:31:17,415 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:17,415 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1603734380] [2022-03-17 16:31:17,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:17,415 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:17,427 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:17,427 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1020023447] [2022-03-17 16:31:17,427 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:17,427 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:17,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:17,429 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:17,430 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-17 16:31:17,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:17,471 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 16:31:17,472 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:17,576 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:17,576 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 16:31:17,745 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:17,745 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:17,746 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1603734380] [2022-03-17 16:31:17,746 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:17,746 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1020023447] [2022-03-17 16:31:17,746 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1020023447] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 16:31:17,746 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 16:31:17,746 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2022-03-17 16:31:17,746 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1362637729] [2022-03-17 16:31:17,746 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:17,746 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 16:31:17,747 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:17,747 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 16:31:17,747 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2022-03-17 16:31:17,747 INFO L87 Difference]: Start difference. First operand 77 states and 98 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:17,760 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:17,760 INFO L93 Difference]: Finished difference Result 108 states and 130 transitions. [2022-03-17 16:31:17,761 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 16:31:17,761 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 18 [2022-03-17 16:31:17,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:17,763 INFO L225 Difference]: With dead ends: 108 [2022-03-17 16:31:17,763 INFO L226 Difference]: Without dead ends: 108 [2022-03-17 16:31:17,763 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-03-17 16:31:17,764 INFO L912 BasicCegarLoop]: 31 mSDtfsCounter, 11 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 104 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 11 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:17,764 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 104 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 11 Unchecked, 0.0s Time] [2022-03-17 16:31:17,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-03-17 16:31:17,778 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 107. [2022-03-17 16:31:17,778 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 81 states have (on average 1.2839506172839505) internal successors, (104), 89 states have internal predecessors, (104), 15 states have call successors, (15), 11 states have call predecessors, (15), 10 states have return successors, (10), 6 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-17 16:31:17,779 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 129 transitions. [2022-03-17 16:31:17,779 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 129 transitions. Word has length 18 [2022-03-17 16:31:17,779 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:17,779 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 129 transitions. [2022-03-17 16:31:17,779 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-17 16:31:17,779 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 129 transitions. [2022-03-17 16:31:17,780 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-17 16:31:17,780 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:17,780 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:17,798 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:17,980 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:17,981 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:17,981 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:17,981 INFO L85 PathProgramCache]: Analyzing trace with hash 462666167, now seen corresponding path program 1 times [2022-03-17 16:31:17,981 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:17,981 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [713895100] [2022-03-17 16:31:17,982 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:17,982 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:17,989 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:17,989 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1706630300] [2022-03-17 16:31:17,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:17,989 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:17,989 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:17,992 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:17,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-17 16:31:18,026 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:18,026 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 16:31:18,029 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:18,068 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:18,069 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 16:31:18,069 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:18,069 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [713895100] [2022-03-17 16:31:18,069 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:18,069 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1706630300] [2022-03-17 16:31:18,069 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1706630300] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 16:31:18,069 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 16:31:18,069 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 16:31:18,069 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1375391208] [2022-03-17 16:31:18,069 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 16:31:18,069 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 16:31:18,070 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:18,070 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 16:31:18,070 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 16:31:18,070 INFO L87 Difference]: Start difference. First operand 107 states and 129 transitions. Second operand has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 16:31:18,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:18,088 INFO L93 Difference]: Finished difference Result 103 states and 122 transitions. [2022-03-17 16:31:18,088 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 16:31:18,088 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 24 [2022-03-17 16:31:18,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:18,090 INFO L225 Difference]: With dead ends: 103 [2022-03-17 16:31:18,090 INFO L226 Difference]: Without dead ends: 93 [2022-03-17 16:31:18,090 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 22 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 16:31:18,091 INFO L912 BasicCegarLoop]: 25 mSDtfsCounter, 0 mSDsluCounter, 19 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 44 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:18,091 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 44 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 16:31:18,092 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 93 states. [2022-03-17 16:31:18,106 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 93 to 93. [2022-03-17 16:31:18,106 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 93 states, 71 states have (on average 1.2816901408450705) internal successors, (91), 77 states have internal predecessors, (91), 13 states have call successors, (13), 10 states have call predecessors, (13), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-17 16:31:18,107 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 93 states to 93 states and 112 transitions. [2022-03-17 16:31:18,107 INFO L78 Accepts]: Start accepts. Automaton has 93 states and 112 transitions. Word has length 24 [2022-03-17 16:31:18,107 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:18,107 INFO L478 AbstractCegarLoop]: Abstraction has 93 states and 112 transitions. [2022-03-17 16:31:18,107 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 6.0) internal successors, (18), 3 states have internal predecessors, (18), 3 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 16:31:18,107 INFO L276 IsEmpty]: Start isEmpty. Operand 93 states and 112 transitions. [2022-03-17 16:31:18,108 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2022-03-17 16:31:18,108 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:18,108 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:18,125 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:18,308 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:18,309 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:18,309 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:18,309 INFO L85 PathProgramCache]: Analyzing trace with hash 1651364104, now seen corresponding path program 1 times [2022-03-17 16:31:18,309 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:18,309 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [560022187] [2022-03-17 16:31:18,309 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:18,309 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:18,316 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:18,316 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [110392282] [2022-03-17 16:31:18,316 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:18,316 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:18,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:18,317 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:18,318 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-17 16:31:18,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:18,346 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-17 16:31:18,347 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:18,395 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-17 16:31:18,396 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 16:31:18,469 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2022-03-17 16:31:18,470 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:31:18,470 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [560022187] [2022-03-17 16:31:18,470 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:31:18,470 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [110392282] [2022-03-17 16:31:18,470 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [110392282] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 16:31:18,470 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 16:31:18,470 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 9 [2022-03-17 16:31:18,470 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [37437814] [2022-03-17 16:31:18,470 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 16:31:18,471 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 16:31:18,471 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:31:18,471 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 16:31:18,471 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-03-17 16:31:18,471 INFO L87 Difference]: Start difference. First operand 93 states and 112 transitions. Second operand has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:18,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:31:18,547 INFO L93 Difference]: Finished difference Result 106 states and 121 transitions. [2022-03-17 16:31:18,547 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 16:31:18,547 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 24 [2022-03-17 16:31:18,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:31:18,548 INFO L225 Difference]: With dead ends: 106 [2022-03-17 16:31:18,548 INFO L226 Difference]: Without dead ends: 88 [2022-03-17 16:31:18,548 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 40 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2022-03-17 16:31:18,550 INFO L912 BasicCegarLoop]: 21 mSDtfsCounter, 17 mSDsluCounter, 71 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 92 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 16:31:18,550 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 92 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 16:31:18,551 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2022-03-17 16:31:18,556 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2022-03-17 16:31:18,556 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 69 states have (on average 1.2318840579710144) internal successors, (85), 73 states have internal predecessors, (85), 10 states have call successors, (10), 9 states have call predecessors, (10), 8 states have return successors, (8), 5 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-17 16:31:18,557 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 103 transitions. [2022-03-17 16:31:18,557 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 103 transitions. Word has length 24 [2022-03-17 16:31:18,557 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:31:18,557 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 103 transitions. [2022-03-17 16:31:18,557 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.2222222222222223) internal successors, (20), 8 states have internal predecessors, (20), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 16:31:18,557 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 103 transitions. [2022-03-17 16:31:18,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-03-17 16:31:18,558 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:31:18,558 INFO L500 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:31:18,577 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-17 16:31:18,758 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:18,759 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:31:18,759 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:31:18,759 INFO L85 PathProgramCache]: Analyzing trace with hash -268589446, now seen corresponding path program 1 times [2022-03-17 16:31:18,759 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:31:18,759 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [111691781] [2022-03-17 16:31:18,759 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:18,759 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:31:18,767 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:31:18,767 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1882383579] [2022-03-17 16:31:18,767 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:31:18,767 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:31:18,767 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:31:18,768 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:31:18,800 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-17 16:31:18,822 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 16:31:18,822 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-17 16:31:18,824 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 16:31:19,035 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:31:19,036 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 16:31:36,119 WARN L232 SmtUtils]: Spent 6.38s on a formula simplification that was a NOOP. DAG size: 17 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 16:32:10,278 WARN L232 SmtUtils]: Spent 6.40s on a formula simplification that was a NOOP. DAG size: 21 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 16:32:31,589 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 16:32:31,589 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 16:32:31,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [111691781] [2022-03-17 16:32:31,589 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 16:32:31,589 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1882383579] [2022-03-17 16:32:31,589 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1882383579] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 16:32:31,589 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 16:32:31,590 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 13 [2022-03-17 16:32:31,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1895066583] [2022-03-17 16:32:31,590 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 16:32:31,590 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-17 16:32:31,590 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 16:32:31,590 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-17 16:32:31,590 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=104, Unknown=8, NotChecked=0, Total=156 [2022-03-17 16:32:31,591 INFO L87 Difference]: Start difference. First operand 88 states and 103 transitions. Second operand has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-17 16:32:59,365 WARN L232 SmtUtils]: Spent 19.22s on a formula simplification that was a NOOP. DAG size: 31 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 16:33:01,380 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:03,544 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.16s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:05,668 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.12s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:07,833 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:12,126 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:14,266 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:16,398 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:18,534 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:20,687 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:22,636 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.95s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:24,778 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:26,905 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:50,804 WARN L232 SmtUtils]: Spent 17.34s on a formula simplification that was a NOOP. DAG size: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 16:33:52,810 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:54,964 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:57,109 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:33:59,269 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:01,449 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.18s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=false, quantifiers [] [2022-03-17 16:34:03,633 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.18s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:05,675 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:07,857 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.18s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:10,021 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:12,169 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:14,306 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:16,482 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:18,629 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:20,783 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.15s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:22,929 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:25,002 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:27,195 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:29,385 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:31,525 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.14s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:33,709 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:35,861 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:38,001 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 16:34:38,001 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 16:34:38,001 INFO L93 Difference]: Finished difference Result 122 states and 142 transitions. [2022-03-17 16:34:38,141 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-17 16:34:38,142 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 27 [2022-03-17 16:34:38,142 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 16:34:38,143 INFO L225 Difference]: With dead ends: 122 [2022-03-17 16:34:38,143 INFO L226 Difference]: Without dead ends: 122 [2022-03-17 16:34:38,143 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 42 SyntacticMatches, 2 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 83.6s TimeCoverageRelationStatistics Valid=68, Invalid=156, Unknown=16, NotChecked=0, Total=240 [2022-03-17 16:34:38,143 INFO L912 BasicCegarLoop]: 27 mSDtfsCounter, 33 mSDsluCounter, 170 mSDsCounter, 0 mSdLazyCounter, 87 mSolverCounterSat, 17 mSolverCounterUnsat, 33 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 68.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 87 IncrementalHoareTripleChecker+Invalid, 33 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 72.6s IncrementalHoareTripleChecker+Time [2022-03-17 16:34:38,144 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 197 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 87 Invalid, 33 Unknown, 0 Unchecked, 72.6s Time] [2022-03-17 16:34:38,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2022-03-17 16:34:38,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 99. [2022-03-17 16:34:38,148 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 78 states have (on average 1.205128205128205) internal successors, (94), 81 states have internal predecessors, (94), 11 states have call successors, (11), 10 states have call predecessors, (11), 9 states have return successors, (9), 7 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-17 16:34:38,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 114 transitions. [2022-03-17 16:34:38,149 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 114 transitions. Word has length 27 [2022-03-17 16:34:38,149 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 16:34:38,149 INFO L478 AbstractCegarLoop]: Abstraction has 99 states and 114 transitions. [2022-03-17 16:34:38,149 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.6153846153846154) internal successors, (34), 12 states have internal predecessors, (34), 5 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2022-03-17 16:34:38,149 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 114 transitions. [2022-03-17 16:34:38,150 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 31 [2022-03-17 16:34:38,150 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 16:34:38,150 INFO L500 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 16:34:38,168 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-17 16:34:38,353 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-17 16:34:38,353 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 16:34:38,353 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 16:34:38,353 INFO L85 PathProgramCache]: Analyzing trace with hash -142927336, now seen corresponding path program 1 times [2022-03-17 16:34:38,353 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 16:34:38,354 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [418398766] [2022-03-17 16:34:38,354 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:34:38,354 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 16:34:38,361 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 16:34:38,361 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [20079069] [2022-03-17 16:34:38,361 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 16:34:38,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 16:34:38,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 16:34:38,363 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 16:34:38,368 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process