/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/hard2_valuebound20.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 07:31:11,738 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 07:31:11,741 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 07:31:11,793 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 07:31:11,793 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 07:31:11,795 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 07:31:11,799 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 07:31:11,802 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 07:31:11,804 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 07:31:11,809 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 07:31:11,810 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 07:31:11,811 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 07:31:11,811 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 07:31:11,812 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 07:31:11,812 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 07:31:11,813 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 07:31:11,815 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 07:31:11,816 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 07:31:11,819 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 07:31:11,826 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 07:31:11,829 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 07:31:11,831 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 07:31:11,832 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 07:31:11,835 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 07:31:11,837 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 07:31:11,840 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 07:31:11,840 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 07:31:11,841 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 07:31:11,841 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 07:31:11,842 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 07:31:11,843 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 07:31:11,843 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 07:31:11,845 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 07:31:11,846 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 07:31:11,846 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 07:31:11,847 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 07:31:11,847 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 07:31:11,848 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 07:31:11,848 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 07:31:11,848 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 07:31:11,849 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 07:31:11,853 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 07:31:11,854 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-04-06 07:31:11,869 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 07:31:11,869 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 07:31:11,871 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 07:31:11,871 INFO L138 SettingsManager]: * sizeof long=4 [2022-04-06 07:31:11,872 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 07:31:11,872 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-04-06 07:31:11,872 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 07:31:11,872 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 07:31:11,872 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 07:31:11,873 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 07:31:11,873 INFO L138 SettingsManager]: * sizeof long double=12 [2022-04-06 07:31:11,873 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 07:31:11,873 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 07:31:11,873 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 07:31:11,874 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 07:31:11,874 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 07:31:11,874 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 07:31:11,874 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 07:31:11,874 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 07:31:11,874 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 07:31:11,875 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 07:31:11,875 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 07:31:11,876 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 07:31:12,101 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 07:31:12,126 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 07:31:12,128 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 07:31:12,128 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 07:31:12,129 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 07:31:12,130 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_valuebound20.c [2022-04-06 07:31:12,184 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ba0c7bdb8/feaabf7e38584d54b6211882e254d460/FLAGb1197e509 [2022-04-06 07:31:12,607 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 07:31:12,607 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_valuebound20.c [2022-04-06 07:31:12,613 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ba0c7bdb8/feaabf7e38584d54b6211882e254d460/FLAGb1197e509 [2022-04-06 07:31:12,624 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/ba0c7bdb8/feaabf7e38584d54b6211882e254d460 [2022-04-06 07:31:12,626 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 07:31:12,628 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 07:31:12,629 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 07:31:12,630 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 07:31:12,635 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 07:31:12,636 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,639 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@178f89e2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12, skipping insertion in model container [2022-04-06 07:31:12,639 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,646 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 07:31:12,662 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 07:31:12,812 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/hard2_valuebound20.c[526,539] [2022-04-06 07:31:12,830 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 07:31:12,838 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 07:31:12,848 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/hard2_valuebound20.c[526,539] [2022-04-06 07:31:12,853 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 07:31:12,864 INFO L208 MainTranslator]: Completed translation [2022-04-06 07:31:12,865 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12 WrapperNode [2022-04-06 07:31:12,865 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 07:31:12,866 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 07:31:12,866 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 07:31:12,866 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 07:31:12,876 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,876 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,887 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,887 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,898 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,902 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,903 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,905 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 07:31:12,906 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 07:31:12,906 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 07:31:12,906 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 07:31:12,914 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (1/1) ... [2022-04-06 07:31:12,920 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 07:31:12,934 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:12,953 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 07:31:12,972 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 07:31:13,006 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 07:31:13,007 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 07:31:13,007 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 07:31:13,007 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 07:31:13,008 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 07:31:13,008 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 07:31:13,008 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 07:31:13,008 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 07:31:13,008 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 07:31:13,008 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 07:31:13,008 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 07:31:13,009 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 07:31:13,061 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 07:31:13,063 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 07:31:13,173 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 07:31:13,179 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 07:31:13,179 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 07:31:13,181 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:31:13 BoogieIcfgContainer [2022-04-06 07:31:13,181 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 07:31:13,182 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 07:31:13,182 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 07:31:13,183 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 07:31:13,186 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:31:13" (1/1) ... [2022-04-06 07:31:13,190 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_JORDAN [2022-04-06 07:31:13,205 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 07:31:13 BasicIcfg [2022-04-06 07:31:13,205 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 07:31:13,206 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 07:31:13,206 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 07:31:13,209 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 07:31:13,209 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 07:31:12" (1/4) ... [2022-04-06 07:31:13,210 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bd18c14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 07:31:13, skipping insertion in model container [2022-04-06 07:31:13,210 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 07:31:12" (2/4) ... [2022-04-06 07:31:13,210 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bd18c14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 07:31:13, skipping insertion in model container [2022-04-06 07:31:13,211 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 07:31:13" (3/4) ... [2022-04-06 07:31:13,211 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bd18c14 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 07:31:13, skipping insertion in model container [2022-04-06 07:31:13,211 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 07:31:13" (4/4) ... [2022-04-06 07:31:13,212 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_valuebound20.cJordan [2022-04-06 07:31:13,233 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-04-06 07:31:13,234 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 07:31:13,289 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 07:31:13,301 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 07:31:13,301 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 07:31:13,332 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 07:31:13,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 07:31:13,339 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:13,340 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:13,340 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:13,352 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:13,352 INFO L85 PathProgramCache]: Analyzing trace with hash -1625753047, now seen corresponding path program 1 times [2022-04-06 07:31:13,360 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:13,362 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1576789062] [2022-04-06 07:31:13,363 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:13,364 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:13,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,549 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:31:13,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,568 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:31:13,573 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,584 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 07:31:13,585 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:13,586 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1576789062] [2022-04-06 07:31:13,587 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1576789062] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:13,587 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:13,587 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 07:31:13,588 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1856216218] [2022-04-06 07:31:13,590 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:13,595 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 07:31:13,596 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:13,627 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 07:31:13,629 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 07:31:13,632 INFO L87 Difference]: Start difference. First operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 07:31:13,724 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:13,725 INFO L93 Difference]: Finished difference Result 35 states and 43 transitions. [2022-04-06 07:31:13,726 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 07:31:13,728 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-06 07:31:13,729 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:13,742 INFO L225 Difference]: With dead ends: 35 [2022-04-06 07:31:13,743 INFO L226 Difference]: Without dead ends: 30 [2022-04-06 07:31:13,745 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 07:31:13,751 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:13,752 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [28 Valid, 38 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:31:13,768 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-04-06 07:31:13,790 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-04-06 07:31:13,792 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 07:31:13,794 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 38 transitions. [2022-04-06 07:31:13,796 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 38 transitions. Word has length 17 [2022-04-06 07:31:13,796 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:13,796 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 38 transitions. [2022-04-06 07:31:13,797 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 07:31:13,798 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 38 transitions. [2022-04-06 07:31:13,799 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-06 07:31:13,799 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:13,799 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:13,800 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 07:31:13,800 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:13,800 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:13,801 INFO L85 PathProgramCache]: Analyzing trace with hash 861759786, now seen corresponding path program 1 times [2022-04-06 07:31:13,801 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:13,801 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1324026143] [2022-04-06 07:31:13,801 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:13,802 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:13,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,931 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:31:13,935 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,945 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:31:13,947 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:13,955 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 07:31:13,956 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:13,956 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1324026143] [2022-04-06 07:31:13,956 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1324026143] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:13,957 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:13,957 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 07:31:13,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [623634738] [2022-04-06 07:31:13,957 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:13,959 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 07:31:13,960 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:13,961 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 07:31:13,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:31:13,962 INFO L87 Difference]: Start difference. First operand 30 states and 38 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 07:31:14,174 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:14,174 INFO L93 Difference]: Finished difference Result 41 states and 53 transitions. [2022-04-06 07:31:14,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:31:14,175 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-06 07:31:14,176 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:14,179 INFO L225 Difference]: With dead ends: 41 [2022-04-06 07:31:14,179 INFO L226 Difference]: Without dead ends: 41 [2022-04-06 07:31:14,182 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:31:14,184 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 37 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:14,184 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 45 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:31:14,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-06 07:31:14,191 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 34. [2022-04-06 07:31:14,191 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 07:31:14,192 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 41 transitions. [2022-04-06 07:31:14,193 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 41 transitions. Word has length 17 [2022-04-06 07:31:14,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:14,193 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 41 transitions. [2022-04-06 07:31:14,193 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-06 07:31:14,193 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 41 transitions. [2022-04-06 07:31:14,194 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-06 07:31:14,194 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:14,194 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:14,194 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 07:31:14,195 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:14,195 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:14,195 INFO L85 PathProgramCache]: Analyzing trace with hash 325569287, now seen corresponding path program 1 times [2022-04-06 07:31:14,195 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:14,195 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1430897327] [2022-04-06 07:31:14,196 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:14,196 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:14,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:14,252 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 07:31:14,256 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:14,266 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 07:31:14,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:14,281 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-04-06 07:31:14,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:14,290 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-06 07:31:14,291 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:14,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1430897327] [2022-04-06 07:31:14,291 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1430897327] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:14,292 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:14,292 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 07:31:14,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [746326271] [2022-04-06 07:31:14,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:14,292 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 07:31:14,293 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:14,293 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 07:31:14,293 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:31:14,294 INFO L87 Difference]: Start difference. First operand 34 states and 41 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 07:31:14,512 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:14,512 INFO L93 Difference]: Finished difference Result 45 states and 56 transitions. [2022-04-06 07:31:14,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:31:14,513 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-06 07:31:14,513 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:14,516 INFO L225 Difference]: With dead ends: 45 [2022-04-06 07:31:14,516 INFO L226 Difference]: Without dead ends: 45 [2022-04-06 07:31:14,518 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:31:14,519 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 32 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:14,520 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [36 Valid, 45 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 07:31:14,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-06 07:31:14,527 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 38. [2022-04-06 07:31:14,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-06 07:31:14,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2022-04-06 07:31:14,529 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 22 [2022-04-06 07:31:14,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:14,529 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2022-04-06 07:31:14,530 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 07:31:14,530 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2022-04-06 07:31:14,530 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-06 07:31:14,531 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:14,531 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:14,531 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 07:31:14,531 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:14,532 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:14,532 INFO L85 PathProgramCache]: Analyzing trace with hash -1461652409, now seen corresponding path program 1 times [2022-04-06 07:31:14,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:14,532 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2058428529] [2022-04-06 07:31:14,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:14,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:14,544 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:14,545 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [958339764] [2022-04-06 07:31:14,545 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:14,545 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:14,545 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:14,547 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:14,566 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 07:31:14,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:14,629 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 07:31:14,635 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:14,785 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 07:31:14,785 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:31:14,785 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:14,785 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2058428529] [2022-04-06 07:31:14,785 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:14,786 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [958339764] [2022-04-06 07:31:14,786 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [958339764] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:14,786 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:14,786 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 07:31:14,786 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2135640254] [2022-04-06 07:31:14,786 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:14,787 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:31:14,788 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:14,788 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:31:14,789 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:31:14,789 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 07:31:14,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:14,861 INFO L93 Difference]: Finished difference Result 53 states and 65 transitions. [2022-04-06 07:31:14,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:31:14,862 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-06 07:31:14,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:14,864 INFO L225 Difference]: With dead ends: 53 [2022-04-06 07:31:14,864 INFO L226 Difference]: Without dead ends: 52 [2022-04-06 07:31:14,865 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:31:14,872 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:14,874 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 128 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:31:14,876 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-06 07:31:14,891 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-06 07:31:14,892 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-06 07:31:14,895 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 63 transitions. [2022-04-06 07:31:14,895 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 63 transitions. Word has length 27 [2022-04-06 07:31:14,896 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:14,896 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 63 transitions. [2022-04-06 07:31:14,896 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 07:31:14,896 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 63 transitions. [2022-04-06 07:31:14,898 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-06 07:31:14,898 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:14,898 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:14,920 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-06 07:31:15,111 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:15,112 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:15,112 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:15,112 INFO L85 PathProgramCache]: Analyzing trace with hash 1008917278, now seen corresponding path program 1 times [2022-04-06 07:31:15,113 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:15,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1352959643] [2022-04-06 07:31:15,113 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:15,113 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:15,124 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:15,125 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [774916879] [2022-04-06 07:31:15,125 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:15,125 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:15,125 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:15,126 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:15,142 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 07:31:15,188 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:15,189 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 07:31:15,191 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:15,290 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 07:31:15,290 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:31:15,291 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:15,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1352959643] [2022-04-06 07:31:15,291 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:15,291 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [774916879] [2022-04-06 07:31:15,291 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [774916879] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:15,291 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:15,291 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 07:31:15,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2073879922] [2022-04-06 07:31:15,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:15,292 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:31:15,292 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:15,293 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:31:15,293 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:31:15,293 INFO L87 Difference]: Start difference. First operand 52 states and 63 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:31:15,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:15,352 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2022-04-06 07:31:15,353 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:31:15,353 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-06 07:31:15,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:15,354 INFO L225 Difference]: With dead ends: 63 [2022-04-06 07:31:15,354 INFO L226 Difference]: Without dead ends: 58 [2022-04-06 07:31:15,355 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 07:31:15,355 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 9 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:15,356 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 103 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:31:15,356 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-04-06 07:31:15,360 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2022-04-06 07:31:15,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 35 states have internal predecessors, (39), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-06 07:31:15,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 69 transitions. [2022-04-06 07:31:15,362 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 69 transitions. Word has length 34 [2022-04-06 07:31:15,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:15,362 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 69 transitions. [2022-04-06 07:31:15,363 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:31:15,363 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 69 transitions. [2022-04-06 07:31:15,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-06 07:31:15,364 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:15,364 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:15,392 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-06 07:31:15,591 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:15,592 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:15,592 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:15,592 INFO L85 PathProgramCache]: Analyzing trace with hash -1762200840, now seen corresponding path program 1 times [2022-04-06 07:31:15,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:15,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1712456643] [2022-04-06 07:31:15,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:15,593 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:15,603 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:15,603 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1080218946] [2022-04-06 07:31:15,603 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:15,603 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:15,604 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:15,604 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:15,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 07:31:15,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:15,652 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 07:31:15,654 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:15,826 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-06 07:31:15,826 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:31:15,982 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-04-06 07:31:15,982 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:15,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1712456643] [2022-04-06 07:31:15,984 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:15,984 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1080218946] [2022-04-06 07:31:15,984 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1080218946] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 07:31:15,984 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 07:31:15,984 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-06 07:31:15,984 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [560489864] [2022-04-06 07:31:15,985 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:15,985 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:31:15,986 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:15,986 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:31:15,987 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-06 07:31:15,987 INFO L87 Difference]: Start difference. First operand 57 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:31:16,043 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:16,043 INFO L93 Difference]: Finished difference Result 67 states and 82 transitions. [2022-04-06 07:31:16,044 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:31:16,044 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 44 [2022-04-06 07:31:16,046 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:16,050 INFO L225 Difference]: With dead ends: 67 [2022-04-06 07:31:16,050 INFO L226 Difference]: Without dead ends: 67 [2022-04-06 07:31:16,050 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 80 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 07:31:16,051 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:16,052 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 112 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:31:16,054 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-04-06 07:31:16,058 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 64. [2022-04-06 07:31:16,059 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 37 states have (on average 1.162162162162162) internal successors, (43), 40 states have internal predecessors, (43), 18 states have call successors, (18), 9 states have call predecessors, (18), 8 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-06 07:31:16,060 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 77 transitions. [2022-04-06 07:31:16,060 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 77 transitions. Word has length 44 [2022-04-06 07:31:16,060 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:16,060 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 77 transitions. [2022-04-06 07:31:16,060 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 07:31:16,060 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-06 07:31:16,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-04-06 07:31:16,061 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:16,061 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:16,079 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-06 07:31:16,263 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:16,264 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:16,264 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:16,264 INFO L85 PathProgramCache]: Analyzing trace with hash -1382136022, now seen corresponding path program 1 times [2022-04-06 07:31:16,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:16,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [811924143] [2022-04-06 07:31:16,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:16,264 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:16,275 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:16,275 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [606767912] [2022-04-06 07:31:16,275 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:16,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:16,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:16,277 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:16,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 07:31:16,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:16,340 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-06 07:31:16,344 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:16,714 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 07:31:16,714 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:31:17,754 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-06 07:31:17,754 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:17,754 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [811924143] [2022-04-06 07:31:17,754 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:17,754 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [606767912] [2022-04-06 07:31:17,755 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [606767912] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:31:17,755 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:31:17,755 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-06 07:31:17,755 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1146172127] [2022-04-06 07:31:17,755 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:31:17,756 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 07:31:17,756 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:17,756 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 07:31:17,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:31:17,756 INFO L87 Difference]: Start difference. First operand 64 states and 77 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-06 07:31:20,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:20,690 INFO L93 Difference]: Finished difference Result 131 states and 176 transitions. [2022-04-06 07:31:20,691 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 07:31:20,691 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 64 [2022-04-06 07:31:20,692 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:20,693 INFO L225 Difference]: With dead ends: 131 [2022-04-06 07:31:20,693 INFO L226 Difference]: Without dead ends: 125 [2022-04-06 07:31:20,693 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 116 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-04-06 07:31:20,694 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 36 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 325 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 396 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 325 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:20,694 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [42 Valid, 198 Invalid, 396 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 325 Invalid, 0 Unknown, 0 Unchecked, 1.1s Time] [2022-04-06 07:31:20,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-04-06 07:31:20,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 113. [2022-04-06 07:31:20,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 67 states have (on average 1.2238805970149254) internal successors, (82), 71 states have internal predecessors, (82), 33 states have call successors, (33), 13 states have call predecessors, (33), 12 states have return successors, (31), 28 states have call predecessors, (31), 31 states have call successors, (31) [2022-04-06 07:31:20,705 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 146 transitions. [2022-04-06 07:31:20,705 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 146 transitions. Word has length 64 [2022-04-06 07:31:20,705 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:20,706 INFO L478 AbstractCegarLoop]: Abstraction has 113 states and 146 transitions. [2022-04-06 07:31:20,706 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-06 07:31:20,706 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 146 transitions. [2022-04-06 07:31:20,707 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 07:31:20,707 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:20,707 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:20,726 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-06 07:31:20,915 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:20,916 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:20,916 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:20,916 INFO L85 PathProgramCache]: Analyzing trace with hash -1085940318, now seen corresponding path program 1 times [2022-04-06 07:31:20,916 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:20,916 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2116783766] [2022-04-06 07:31:20,916 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:20,916 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:20,926 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:20,926 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [77535308] [2022-04-06 07:31:20,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:20,926 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:20,926 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:20,927 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:20,954 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 07:31:20,980 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:20,982 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-06 07:31:20,985 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:21,416 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 66 proven. 11 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-04-06 07:31:21,417 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:31:21,718 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-04-06 07:31:21,718 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:21,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2116783766] [2022-04-06 07:31:21,718 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:21,718 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [77535308] [2022-04-06 07:31:21,718 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [77535308] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:31:21,718 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:31:21,719 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2022-04-06 07:31:21,719 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1448141514] [2022-04-06 07:31:21,719 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:31:21,721 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 07:31:21,721 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:21,721 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 07:31:21,721 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2022-04-06 07:31:21,723 INFO L87 Difference]: Start difference. First operand 113 states and 146 transitions. Second operand has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) [2022-04-06 07:31:22,017 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:22,017 INFO L93 Difference]: Finished difference Result 134 states and 165 transitions. [2022-04-06 07:31:22,017 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 07:31:22,018 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) Word has length 75 [2022-04-06 07:31:22,018 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:22,019 INFO L225 Difference]: With dead ends: 134 [2022-04-06 07:31:22,019 INFO L226 Difference]: Without dead ends: 115 [2022-04-06 07:31:22,020 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 133 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2022-04-06 07:31:22,020 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 39 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 279 mSolverCounterSat, 64 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 52 SdHoareTripleChecker+Valid, 122 SdHoareTripleChecker+Invalid, 343 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 64 IncrementalHoareTripleChecker+Valid, 279 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:22,020 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [52 Valid, 122 Invalid, 343 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [64 Valid, 279 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 07:31:22,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2022-04-06 07:31:22,027 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 101. [2022-04-06 07:31:22,028 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 61 states have (on average 1.1639344262295082) internal successors, (71), 64 states have internal predecessors, (71), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 07:31:22,029 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 121 transitions. [2022-04-06 07:31:22,029 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 121 transitions. Word has length 75 [2022-04-06 07:31:22,029 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:22,030 INFO L478 AbstractCegarLoop]: Abstraction has 101 states and 121 transitions. [2022-04-06 07:31:22,030 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) [2022-04-06 07:31:22,030 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 121 transitions. [2022-04-06 07:31:22,031 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-04-06 07:31:22,031 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:22,031 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:22,062 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 07:31:22,257 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:22,257 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:22,258 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:22,258 INFO L85 PathProgramCache]: Analyzing trace with hash 1480109990, now seen corresponding path program 1 times [2022-04-06 07:31:22,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:22,258 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [470236649] [2022-04-06 07:31:22,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:22,258 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:22,267 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:22,268 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [650815632] [2022-04-06 07:31:22,268 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:22,268 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:22,268 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:22,269 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:22,285 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 07:31:22,319 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:31:22,321 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-06 07:31:22,323 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:22,517 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-04-06 07:31:22,517 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 07:31:22,517 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:22,517 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [470236649] [2022-04-06 07:31:22,517 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:22,518 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [650815632] [2022-04-06 07:31:22,518 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [650815632] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 07:31:22,518 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 07:31:22,518 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 07:31:22,518 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1698787891] [2022-04-06 07:31:22,518 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 07:31:22,519 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 07:31:22,519 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:22,519 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 07:31:22,519 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:31:22,519 INFO L87 Difference]: Start difference. First operand 101 states and 121 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-06 07:31:22,572 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:31:22,572 INFO L93 Difference]: Finished difference Result 103 states and 122 transitions. [2022-04-06 07:31:22,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:31:22,573 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 84 [2022-04-06 07:31:22,573 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:31:22,574 INFO L225 Difference]: With dead ends: 103 [2022-04-06 07:31:22,574 INFO L226 Difference]: Without dead ends: 103 [2022-04-06 07:31:22,574 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-06 07:31:22,575 INFO L913 BasicCegarLoop]: 52 mSDtfsCounter, 14 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 07:31:22,575 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 82 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 07:31:22,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2022-04-06 07:31:22,580 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2022-04-06 07:31:22,581 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 63 states have (on average 1.1428571428571428) internal successors, (72), 64 states have internal predecessors, (72), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-06 07:31:22,582 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 122 transitions. [2022-04-06 07:31:22,582 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 122 transitions. Word has length 84 [2022-04-06 07:31:22,582 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:31:22,582 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 122 transitions. [2022-04-06 07:31:22,582 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-06 07:31:22,582 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 122 transitions. [2022-04-06 07:31:22,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-04-06 07:31:22,584 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:31:22,584 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:31:22,614 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 07:31:22,807 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:22,808 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:31:22,808 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:31:22,808 INFO L85 PathProgramCache]: Analyzing trace with hash -233495842, now seen corresponding path program 2 times [2022-04-06 07:31:22,808 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:31:22,808 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1941587471] [2022-04-06 07:31:22,809 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:31:22,809 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:31:22,818 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:31:22,819 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [930931231] [2022-04-06 07:31:22,819 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 07:31:22,819 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:31:22,819 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:31:22,820 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:31:22,839 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 07:31:22,888 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 07:31:22,888 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:31:22,890 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 39 conjunts are in the unsatisfiable core [2022-04-06 07:31:22,893 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:31:23,479 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 07:31:23,479 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:31:46,369 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-06 07:31:46,370 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:31:46,370 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1941587471] [2022-04-06 07:31:46,370 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:31:46,370 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [930931231] [2022-04-06 07:31:46,370 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [930931231] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:31:46,370 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:31:46,370 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-04-06 07:31:46,371 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [743272892] [2022-04-06 07:31:46,371 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:31:46,371 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-06 07:31:46,371 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:31:46,372 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-06 07:31:46,372 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=179, Unknown=1, NotChecked=0, Total=240 [2022-04-06 07:31:46,372 INFO L87 Difference]: Start difference. First operand 103 states and 122 transitions. Second operand has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2022-04-06 07:31:55,160 WARN L232 SmtUtils]: Spent 8.18s on a formula simplification. DAG size of input: 192 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 07:32:01,705 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:32:01,706 INFO L93 Difference]: Finished difference Result 193 states and 258 transitions. [2022-04-06 07:32:01,706 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-06 07:32:01,706 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) Word has length 94 [2022-04-06 07:32:01,707 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:32:01,708 INFO L225 Difference]: With dead ends: 193 [2022-04-06 07:32:01,708 INFO L226 Difference]: Without dead ends: 177 [2022-04-06 07:32:01,708 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 14.7s TimeCoverageRelationStatistics Valid=114, Invalid=305, Unknown=1, NotChecked=0, Total=420 [2022-04-06 07:32:01,709 INFO L913 BasicCegarLoop]: 61 mSDtfsCounter, 90 mSDsluCounter, 259 mSDsCounter, 0 mSdLazyCounter, 807 mSolverCounterSat, 189 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 101 SdHoareTripleChecker+Valid, 320 SdHoareTripleChecker+Invalid, 996 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 189 IncrementalHoareTripleChecker+Valid, 807 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.2s IncrementalHoareTripleChecker+Time [2022-04-06 07:32:01,709 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [101 Valid, 320 Invalid, 996 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [189 Valid, 807 Invalid, 0 Unknown, 0 Unchecked, 5.2s Time] [2022-04-06 07:32:01,710 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-04-06 07:32:01,719 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 166. [2022-04-06 07:32:01,720 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 100 states have (on average 1.21) internal successors, (121), 104 states have internal predecessors, (121), 49 states have call successors, (49), 17 states have call predecessors, (49), 16 states have return successors, (47), 44 states have call predecessors, (47), 47 states have call successors, (47) [2022-04-06 07:32:01,721 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 217 transitions. [2022-04-06 07:32:01,721 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 217 transitions. Word has length 94 [2022-04-06 07:32:01,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:32:01,722 INFO L478 AbstractCegarLoop]: Abstraction has 166 states and 217 transitions. [2022-04-06 07:32:01,722 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2022-04-06 07:32:01,722 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 217 transitions. [2022-04-06 07:32:01,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-06 07:32:01,724 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:32:01,724 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:32:01,744 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-04-06 07:32:01,935 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:01,936 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:32:01,936 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:32:01,936 INFO L85 PathProgramCache]: Analyzing trace with hash 411415430, now seen corresponding path program 1 times [2022-04-06 07:32:01,936 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:32:01,937 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [825137119] [2022-04-06 07:32:01,937 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:32:01,937 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:32:01,947 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:32:01,947 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [969602295] [2022-04-06 07:32:01,947 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:32:01,947 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:01,948 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:32:01,949 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:32:01,974 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 07:32:02,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 07:32:02,011 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 07:32:02,019 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:32:02,294 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-06 07:32:02,295 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:32:03,045 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-06 07:32:03,046 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:32:03,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [825137119] [2022-04-06 07:32:03,046 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:32:03,046 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [969602295] [2022-04-06 07:32:03,046 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [969602295] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:32:03,046 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:32:03,046 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-06 07:32:03,047 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2057112066] [2022-04-06 07:32:03,048 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:32:03,049 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 07:32:03,049 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:32:03,050 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 07:32:03,050 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-06 07:32:03,050 INFO L87 Difference]: Start difference. First operand 166 states and 217 transitions. Second operand has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) [2022-04-06 07:32:03,321 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:32:03,321 INFO L93 Difference]: Finished difference Result 180 states and 237 transitions. [2022-04-06 07:32:03,321 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:32:03,322 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) Word has length 110 [2022-04-06 07:32:03,322 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:32:03,323 INFO L225 Difference]: With dead ends: 180 [2022-04-06 07:32:03,323 INFO L226 Difference]: Without dead ends: 174 [2022-04-06 07:32:03,325 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-04-06 07:32:03,325 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 7 mSDsluCounter, 261 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 325 SdHoareTripleChecker+Invalid, 231 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 07:32:03,326 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 325 Invalid, 231 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 07:32:03,326 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2022-04-06 07:32:03,334 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 174. [2022-04-06 07:32:03,334 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 104 states have (on average 1.2019230769230769) internal successors, (125), 108 states have internal predecessors, (125), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 48 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-06 07:32:03,336 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 229 transitions. [2022-04-06 07:32:03,336 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 229 transitions. Word has length 110 [2022-04-06 07:32:03,336 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:32:03,336 INFO L478 AbstractCegarLoop]: Abstraction has 174 states and 229 transitions. [2022-04-06 07:32:03,336 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) [2022-04-06 07:32:03,337 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 229 transitions. [2022-04-06 07:32:03,338 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2022-04-06 07:32:03,338 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:32:03,339 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:32:03,363 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 07:32:03,551 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,SelfDestructingSolverStorable10 [2022-04-06 07:32:03,552 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:32:03,552 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:32:03,552 INFO L85 PathProgramCache]: Analyzing trace with hash 564418017, now seen corresponding path program 2 times [2022-04-06 07:32:03,552 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:32:03,552 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [319629873] [2022-04-06 07:32:03,552 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:32:03,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:32:03,562 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:32:03,562 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [759409766] [2022-04-06 07:32:03,563 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 07:32:03,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:03,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:32:03,564 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:32:03,565 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 07:32:03,626 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 07:32:03,626 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:32:03,628 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 07:32:03,632 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:32:03,806 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 102 proven. 42 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-04-06 07:32:03,806 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:32:04,207 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 63 proven. 15 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-04-06 07:32:04,207 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:32:04,207 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [319629873] [2022-04-06 07:32:04,208 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:32:04,208 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [759409766] [2022-04-06 07:32:04,208 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [759409766] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:32:04,208 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:32:04,208 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-06 07:32:04,208 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1787969255] [2022-04-06 07:32:04,208 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:32:04,209 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 07:32:04,209 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:32:04,209 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 07:32:04,209 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-06 07:32:04,210 INFO L87 Difference]: Start difference. First operand 174 states and 229 transitions. Second operand has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) [2022-04-06 07:32:04,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:32:04,291 INFO L93 Difference]: Finished difference Result 159 states and 200 transitions. [2022-04-06 07:32:04,293 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 07:32:04,293 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) Word has length 123 [2022-04-06 07:32:04,293 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:32:04,294 INFO L225 Difference]: With dead ends: 159 [2022-04-06 07:32:04,294 INFO L226 Difference]: Without dead ends: 136 [2022-04-06 07:32:04,295 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 245 GetRequests, 235 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-06 07:32:04,295 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 4 mSDsluCounter, 122 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 186 SdHoareTripleChecker+Invalid, 116 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:32:04,296 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 186 Invalid, 116 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:32:04,296 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2022-04-06 07:32:04,302 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2022-04-06 07:32:04,302 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 82 states have (on average 1.1585365853658536) internal successors, (95), 86 states have internal predecessors, (95), 37 states have call successors, (37), 17 states have call predecessors, (37), 16 states have return successors, (35), 32 states have call predecessors, (35), 35 states have call successors, (35) [2022-04-06 07:32:04,303 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 167 transitions. [2022-04-06 07:32:04,303 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 167 transitions. Word has length 123 [2022-04-06 07:32:04,303 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:32:04,303 INFO L478 AbstractCegarLoop]: Abstraction has 136 states and 167 transitions. [2022-04-06 07:32:04,304 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) [2022-04-06 07:32:04,304 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 167 transitions. [2022-04-06 07:32:04,305 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-04-06 07:32:04,305 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:32:04,305 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:32:04,338 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-06 07:32:04,535 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:04,536 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:32:04,536 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:32:04,536 INFO L85 PathProgramCache]: Analyzing trace with hash -1567600662, now seen corresponding path program 3 times [2022-04-06 07:32:04,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:32:04,536 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [479651855] [2022-04-06 07:32:04,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:32:04,537 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:32:04,545 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:32:04,546 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [80635836] [2022-04-06 07:32:04,546 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 07:32:04,546 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:04,546 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:32:04,547 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:32:04,579 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 07:32:04,646 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-06 07:32:04,646 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:32:04,648 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-06 07:32:04,651 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:32:04,937 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 07:32:04,985 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 07:32:05,023 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 07:32:05,134 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 142 proven. 2 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2022-04-06 07:32:05,135 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:32:15,167 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:32:15,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [479651855] [2022-04-06 07:32:15,168 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:32:15,168 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [80635836] [2022-04-06 07:32:15,168 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [80635836] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 07:32:15,168 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 07:32:15,168 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-06 07:32:15,168 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1949367156] [2022-04-06 07:32:15,168 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-06 07:32:15,169 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 07:32:15,169 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:32:15,169 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 07:32:15,169 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-06 07:32:15,170 INFO L87 Difference]: Start difference. First operand 136 states and 167 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-06 07:32:15,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:32:15,269 INFO L93 Difference]: Finished difference Result 140 states and 170 transitions. [2022-04-06 07:32:15,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 07:32:15,270 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) Word has length 124 [2022-04-06 07:32:15,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:32:15,271 INFO L225 Difference]: With dead ends: 140 [2022-04-06 07:32:15,271 INFO L226 Difference]: Without dead ends: 138 [2022-04-06 07:32:15,271 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 117 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-04-06 07:32:15,272 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 19 mSDsluCounter, 73 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 117 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:32:15,272 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 98 Invalid, 117 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:32:15,273 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2022-04-06 07:32:15,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 118. [2022-04-06 07:32:15,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 73 states have (on average 1.1095890410958904) internal successors, (81), 73 states have internal predecessors, (81), 29 states have call successors, (29), 17 states have call predecessors, (29), 15 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-06 07:32:15,278 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 137 transitions. [2022-04-06 07:32:15,278 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 137 transitions. Word has length 124 [2022-04-06 07:32:15,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:32:15,279 INFO L478 AbstractCegarLoop]: Abstraction has 118 states and 137 transitions. [2022-04-06 07:32:15,279 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-06 07:32:15,279 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 137 transitions. [2022-04-06 07:32:15,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-04-06 07:32:15,280 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 07:32:15,280 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:32:15,305 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 07:32:15,481 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 07:32:15,481 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 07:32:15,482 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 07:32:15,482 INFO L85 PathProgramCache]: Analyzing trace with hash 1333998901, now seen corresponding path program 3 times [2022-04-06 07:32:15,482 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 07:32:15,482 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [563246610] [2022-04-06 07:32:15,482 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 07:32:15,482 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 07:32:15,496 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 07:32:15,496 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [499696248] [2022-04-06 07:32:15,496 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 07:32:15,496 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 07:32:15,496 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 07:32:15,499 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 07:32:15,501 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-06 07:32:15,548 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-06 07:32:15,548 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 07:32:15,550 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-06 07:32:15,561 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 07:32:15,803 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-04-06 07:32:15,804 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 07:32:16,021 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-04-06 07:32:16,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 07:32:16,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [563246610] [2022-04-06 07:32:16,022 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 07:32:16,022 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [499696248] [2022-04-06 07:32:16,022 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [499696248] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 07:32:16,022 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 07:32:16,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-06 07:32:16,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1459638466] [2022-04-06 07:32:16,022 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 07:32:16,022 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 07:32:16,022 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 07:32:16,023 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 07:32:16,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-04-06 07:32:16,023 INFO L87 Difference]: Start difference. First operand 118 states and 137 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) [2022-04-06 07:32:16,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 07:32:16,139 INFO L93 Difference]: Finished difference Result 124 states and 141 transitions. [2022-04-06 07:32:16,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-06 07:32:16,139 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) Word has length 127 [2022-04-06 07:32:16,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 07:32:16,140 INFO L225 Difference]: With dead ends: 124 [2022-04-06 07:32:16,140 INFO L226 Difference]: Without dead ends: 0 [2022-04-06 07:32:16,140 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 243 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-04-06 07:32:16,141 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 16 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 133 SdHoareTripleChecker+Invalid, 168 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 07:32:16,141 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 133 Invalid, 168 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 07:32:16,141 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-06 07:32:16,141 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-06 07:32:16,141 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-06 07:32:16,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-06 07:32:16,142 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 127 [2022-04-06 07:32:16,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 07:32:16,142 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-06 07:32:16,142 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) [2022-04-06 07:32:16,142 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-06 07:32:16,142 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-06 07:32:16,145 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 07:32:16,163 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 07:32:16,347 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 07:32:16,350 INFO L719 BasicCegarLoop]: Path program histogram: [3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 07:32:16,351 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 07:32:16,353 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 07:32:16 BasicIcfg [2022-04-06 07:32:16,354 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 07:32:16,354 INFO L158 Benchmark]: Toolchain (without parser) took 63726.50ms. Allocated memory was 175.1MB in the beginning and 264.2MB in the end (delta: 89.1MB). Free memory was 124.6MB in the beginning and 192.1MB in the end (delta: -67.5MB). Peak memory consumption was 23.0MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,354 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 175.1MB. Free memory was 140.8MB in the beginning and 140.6MB in the end (delta: 136.6kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 07:32:16,355 INFO L158 Benchmark]: CACSL2BoogieTranslator took 235.48ms. Allocated memory is still 175.1MB. Free memory was 124.4MB in the beginning and 150.3MB in the end (delta: -25.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,355 INFO L158 Benchmark]: Boogie Preprocessor took 39.47ms. Allocated memory is still 175.1MB. Free memory was 150.3MB in the beginning and 148.8MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,355 INFO L158 Benchmark]: RCFGBuilder took 275.45ms. Allocated memory is still 175.1MB. Free memory was 148.8MB in the beginning and 138.8MB in the end (delta: 10.0MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,355 INFO L158 Benchmark]: IcfgTransformer took 22.88ms. Allocated memory is still 175.1MB. Free memory was 138.8MB in the beginning and 137.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,356 INFO L158 Benchmark]: TraceAbstraction took 63147.47ms. Allocated memory was 175.1MB in the beginning and 264.2MB in the end (delta: 89.1MB). Free memory was 136.7MB in the beginning and 192.1MB in the end (delta: -55.4MB). Peak memory consumption was 34.7MB. Max. memory is 8.0GB. [2022-04-06 07:32:16,357 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.15ms. Allocated memory is still 175.1MB. Free memory was 140.8MB in the beginning and 140.6MB in the end (delta: 136.6kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 235.48ms. Allocated memory is still 175.1MB. Free memory was 124.4MB in the beginning and 150.3MB in the end (delta: -25.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 39.47ms. Allocated memory is still 175.1MB. Free memory was 150.3MB in the beginning and 148.8MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 275.45ms. Allocated memory is still 175.1MB. Free memory was 148.8MB in the beginning and 138.8MB in the end (delta: 10.0MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 22.88ms. Allocated memory is still 175.1MB. Free memory was 138.8MB in the beginning and 137.3MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 63147.47ms. Allocated memory was 175.1MB in the beginning and 264.2MB in the end (delta: 89.1MB). Free memory was 136.7MB in the beginning and 192.1MB in the end (delta: -55.4MB). Peak memory consumption was 34.7MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 35 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 63.1s, OverallIterations: 14, TraceHistogramMax: 20, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 20.1s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 410 SdHoareTripleChecker+Valid, 7.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 339 mSDsluCounter, 1935 SdHoareTripleChecker+Invalid, 7.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1367 mSDsCounter, 447 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2407 IncrementalHoareTripleChecker+Invalid, 2854 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 447 mSolverCounterUnsat, 568 mSDtfsCounter, 2407 mSolverCounterSat, 0.1s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1596 GetRequests, 1452 SyntacticMatches, 22 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 17.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=174occurred in iteration=11, InterpolantAutomatonStates: 100, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 14 MinimizatonAttempts, 75 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 39.3s InterpolantComputationTime, 962 NumberOfCodeBlocks, 840 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 1578 ConstructedInterpolants, 0 QuantifiedInterpolants, 15993 SizeOfPredicates, 26 NumberOfNonLiveVariables, 1954 ConjunctsInSsa, 196 ConjunctsInUnsatCore, 21 InterpolantComputations, 7 PerfectInterpolantSequences, 6338/6540 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2022-04-06 07:32:16,400 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...