/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/hard-ll_unwindbound10.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 17:12:16,765 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 17:12:16,766 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 17:12:16,810 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 17:12:16,811 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 17:12:16,811 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 17:12:16,813 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 17:12:16,814 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 17:12:16,816 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 17:12:16,816 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 17:12:16,817 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 17:12:16,818 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 17:12:16,818 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 17:12:16,821 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 17:12:16,823 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 17:12:16,829 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 17:12:16,829 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 17:12:16,835 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 17:12:16,839 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 17:12:16,840 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 17:12:16,841 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 17:12:16,848 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 17:12:16,849 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 17:12:16,849 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 17:12:16,851 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 17:12:16,859 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 17:12:16,859 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 17:12:16,859 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 17:12:16,860 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 17:12:16,861 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 17:12:16,862 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 17:12:16,862 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 17:12:16,863 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 17:12:16,864 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 17:12:16,864 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 17:12:16,865 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 17:12:16,865 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 17:12:16,866 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 17:12:16,866 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 17:12:16,866 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 17:12:16,867 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 17:12:16,868 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 17:12:16,869 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-17 17:12:16,877 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 17:12:16,877 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 17:12:16,878 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 17:12:16,879 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 17:12:16,880 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 17:12:16,880 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-17 17:12:16,880 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 17:12:16,880 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 17:12:16,881 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 17:12:16,881 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 17:12:16,881 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 17:12:16,882 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 17:12:16,882 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-03-17 17:12:17,103 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 17:12:17,123 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 17:12:17,125 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 17:12:17,126 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 17:12:17,127 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 17:12:17,128 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound10.c [2022-03-17 17:12:17,178 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27c615832/edf4eed952f2440cbd81552f3810dce1/FLAG9221d0dc3 [2022-03-17 17:12:17,572 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 17:12:17,572 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound10.c [2022-03-17 17:12:17,578 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27c615832/edf4eed952f2440cbd81552f3810dce1/FLAG9221d0dc3 [2022-03-17 17:12:17,593 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/27c615832/edf4eed952f2440cbd81552f3810dce1 [2022-03-17 17:12:17,595 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 17:12:17,596 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 17:12:17,597 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 17:12:17,597 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 17:12:17,601 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 17:12:17,601 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,602 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@675b2beb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17, skipping insertion in model container [2022-03-17 17:12:17,603 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,608 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 17:12:17,620 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 17:12:17,792 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/hard-ll_unwindbound10.c[538,551] [2022-03-17 17:12:17,814 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 17:12:17,821 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 17:12:17,831 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/hard-ll_unwindbound10.c[538,551] [2022-03-17 17:12:17,849 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 17:12:17,862 INFO L208 MainTranslator]: Completed translation [2022-03-17 17:12:17,862 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17 WrapperNode [2022-03-17 17:12:17,862 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 17:12:17,863 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 17:12:17,863 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 17:12:17,863 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 17:12:17,873 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,873 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,878 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,878 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,891 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,897 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,902 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,904 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 17:12:17,905 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 17:12:17,905 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 17:12:17,905 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 17:12:17,906 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (1/1) ... [2022-03-17 17:12:17,912 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 17:12:17,920 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:17,932 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-17 17:12:17,965 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-17 17:12:17,980 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 17:12:17,980 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 17:12:17,980 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 17:12:17,980 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 17:12:17,981 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 17:12:17,981 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 17:12:17,981 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 17:12:17,981 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 17:12:17,981 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 17:12:17,981 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 17:12:17,982 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 17:12:17,983 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 17:12:17,983 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 17:12:17,983 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 17:12:17,983 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 17:12:18,034 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 17:12:18,036 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 17:12:18,170 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 17:12:18,174 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 17:12:18,174 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 17:12:18,176 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:12:18 BoogieIcfgContainer [2022-03-17 17:12:18,176 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 17:12:18,177 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 17:12:18,177 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 17:12:18,190 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 17:12:18,205 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:12:18" (1/1) ... [2022-03-17 17:12:18,226 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 05:12:18 BasicIcfg [2022-03-17 17:12:18,226 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 17:12:18,227 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 17:12:18,227 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 17:12:18,242 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 17:12:18,242 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 05:12:17" (1/4) ... [2022-03-17 17:12:18,242 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c35dbc2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 05:12:18, skipping insertion in model container [2022-03-17 17:12:18,242 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:12:17" (2/4) ... [2022-03-17 17:12:18,243 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c35dbc2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 05:12:18, skipping insertion in model container [2022-03-17 17:12:18,243 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:12:18" (3/4) ... [2022-03-17 17:12:18,243 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2c35dbc2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 05:12:18, skipping insertion in model container [2022-03-17 17:12:18,243 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 05:12:18" (4/4) ... [2022-03-17 17:12:18,244 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound10.cJordan [2022-03-17 17:12:18,247 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-17 17:12:18,248 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 17:12:18,310 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 17:12:18,317 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-03-17 17:12:18,317 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 17:12:18,329 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 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-03-17 17:12:18,335 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 17:12:18,335 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:18,336 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:18,336 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:18,340 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:18,341 INFO L85 PathProgramCache]: Analyzing trace with hash 79654685, now seen corresponding path program 1 times [2022-03-17 17:12:18,348 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:18,349 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1959217807] [2022-03-17 17:12:18,349 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:18,350 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:18,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,527 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 17:12:18,529 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,538 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 17:12:18,543 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,552 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 17:12:18,553 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:18,553 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1959217807] [2022-03-17 17:12:18,553 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1959217807] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:18,553 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:18,554 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 17:12:18,555 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [873608545] [2022-03-17 17:12:18,556 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:18,560 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 17:12:18,560 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:18,586 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 17:12:18,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 17:12:18,589 INFO L87 Difference]: Start difference. First operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 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 4.0) internal successors, (12), 2 states have internal predecessors, (12), 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-03-17 17:12:18,681 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:18,682 INFO L93 Difference]: Finished difference Result 38 states and 48 transitions. [2022-03-17 17:12:18,683 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 17:12:18,684 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (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 18 [2022-03-17 17:12:18,685 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:18,692 INFO L225 Difference]: With dead ends: 38 [2022-03-17 17:12:18,692 INFO L226 Difference]: Without dead ends: 33 [2022-03-17 17:12:18,694 INFO L911 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-03-17 17:12:18,697 INFO L912 BasicCegarLoop]: 45 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:18,698 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 49 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:12:18,712 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-17 17:12:18,727 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2022-03-17 17:12:18,728 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 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-03-17 17:12:18,729 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-03-17 17:12:18,730 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 18 [2022-03-17 17:12:18,730 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:18,731 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-03-17 17:12:18,731 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (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-03-17 17:12:18,731 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-03-17 17:12:18,732 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-17 17:12:18,732 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:18,732 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:18,733 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 17:12:18,733 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:18,733 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:18,734 INFO L85 PathProgramCache]: Analyzing trace with hash -85369733, now seen corresponding path program 1 times [2022-03-17 17:12:18,734 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:18,734 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1125674167] [2022-03-17 17:12:18,734 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:18,735 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:18,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,868 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 17:12:18,873 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,879 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 17:12:18,881 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:18,888 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 17:12:18,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:18,888 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1125674167] [2022-03-17 17:12:18,889 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1125674167] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:18,889 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:18,889 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 17:12:18,890 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2029916661] [2022-03-17 17:12:18,890 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:18,891 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 17:12:18,891 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:18,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 17:12:18,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 17:12:18,892 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 17:12:19,067 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:19,067 INFO L93 Difference]: Finished difference Result 45 states and 60 transitions. [2022-03-17 17:12:19,068 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-17 17:12:19,068 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 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 18 [2022-03-17 17:12:19,068 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:19,069 INFO L225 Difference]: With dead ends: 45 [2022-03-17 17:12:19,069 INFO L226 Difference]: Without dead ends: 45 [2022-03-17 17:12:19,070 INFO L911 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-03-17 17:12:19,071 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 28 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:19,071 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 96 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:12:19,072 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-17 17:12:19,078 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 36. [2022-03-17 17:12:19,078 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 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-03-17 17:12:19,079 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 45 transitions. [2022-03-17 17:12:19,079 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 45 transitions. Word has length 18 [2022-03-17 17:12:19,079 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:19,079 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 45 transitions. [2022-03-17 17:12:19,080 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-17 17:12:19,080 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-03-17 17:12:19,080 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-03-17 17:12:19,080 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:19,081 INFO L500 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:19,081 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-17 17:12:19,081 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:19,081 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:19,081 INFO L85 PathProgramCache]: Analyzing trace with hash -1527809342, now seen corresponding path program 1 times [2022-03-17 17:12:19,082 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:19,082 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [947748804] [2022-03-17 17:12:19,082 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:19,082 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:19,098 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:19,098 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1111208597] [2022-03-17 17:12:19,098 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:19,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:19,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:19,103 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:19,115 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-17 17:12:19,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,156 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 17:12:19,160 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:19,276 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 17:12:19,276 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:12:19,276 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:19,276 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [947748804] [2022-03-17 17:12:19,276 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:19,276 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1111208597] [2022-03-17 17:12:19,277 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1111208597] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:19,277 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:19,277 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-17 17:12:19,277 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [997333189] [2022-03-17 17:12:19,277 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:19,277 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-17 17:12:19,278 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:19,278 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-17 17:12:19,278 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-17 17:12:19,278 INFO L87 Difference]: Start difference. First operand 36 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 17:12:19,297 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:19,297 INFO L93 Difference]: Finished difference Result 38 states and 47 transitions. [2022-03-17 17:12:19,306 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 17:12:19,306 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-03-17 17:12:19,306 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:19,307 INFO L225 Difference]: With dead ends: 38 [2022-03-17 17:12:19,307 INFO L226 Difference]: Without dead ends: 38 [2022-03-17 17:12:19,307 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-17 17:12:19,308 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:19,309 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 107 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:12:19,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-03-17 17:12:19,312 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-03-17 17:12:19,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 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-03-17 17:12:19,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2022-03-17 17:12:19,313 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 20 [2022-03-17 17:12:19,314 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:19,314 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2022-03-17 17:12:19,314 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-17 17:12:19,314 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2022-03-17 17:12:19,314 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-03-17 17:12:19,314 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:19,314 INFO L500 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:19,350 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:19,531 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:19,532 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:19,532 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:19,532 INFO L85 PathProgramCache]: Analyzing trace with hash 2128444854, now seen corresponding path program 1 times [2022-03-17 17:12:19,532 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:19,533 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1350045253] [2022-03-17 17:12:19,533 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:19,533 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:19,552 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,625 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 17:12:19,629 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,641 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 17:12:19,643 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,659 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-03-17 17:12:19,662 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,668 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-17 17:12:19,669 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:19,669 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1350045253] [2022-03-17 17:12:19,669 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1350045253] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:19,669 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:19,669 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 17:12:19,669 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [193583374] [2022-03-17 17:12:19,670 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:19,670 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 17:12:19,670 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:19,670 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 17:12:19,670 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 17:12:19,671 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 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-03-17 17:12:19,833 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:19,833 INFO L93 Difference]: Finished difference Result 50 states and 64 transitions. [2022-03-17 17:12:19,833 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-17 17:12:19,834 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 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 23 [2022-03-17 17:12:19,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:19,835 INFO L225 Difference]: With dead ends: 50 [2022-03-17 17:12:19,835 INFO L226 Difference]: Without dead ends: 50 [2022-03-17 17:12:19,835 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-17 17:12:19,836 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 23 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:19,836 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 89 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:12:19,837 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-03-17 17:12:19,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 42. [2022-03-17 17:12:19,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 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-03-17 17:12:19,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2022-03-17 17:12:19,842 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 23 [2022-03-17 17:12:19,843 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:19,843 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2022-03-17 17:12:19,843 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 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-03-17 17:12:19,843 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2022-03-17 17:12:19,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-17 17:12:19,844 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:19,844 INFO L500 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, 1] [2022-03-17 17:12:19,844 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-03-17 17:12:19,844 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:19,844 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:19,845 INFO L85 PathProgramCache]: Analyzing trace with hash 135546551, now seen corresponding path program 1 times [2022-03-17 17:12:19,856 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:19,856 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [46952777] [2022-03-17 17:12:19,856 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:19,857 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:19,867 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:19,867 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [171515150] [2022-03-17 17:12:19,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:19,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:19,868 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:19,869 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:19,877 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-17 17:12:19,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:19,916 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 17:12:19,918 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:20,002 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-17 17:12:20,003 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:12:20,003 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:20,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [46952777] [2022-03-17 17:12:20,003 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:20,003 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [171515150] [2022-03-17 17:12:20,003 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [171515150] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:20,003 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:20,004 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 17:12:20,004 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [606708741] [2022-03-17 17:12:20,004 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:20,004 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:12:20,004 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:20,005 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:12:20,005 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:12:20,005 INFO L87 Difference]: Start difference. First operand 42 states and 50 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, (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-03-17 17:12:20,046 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:20,046 INFO L93 Difference]: Finished difference Result 57 states and 72 transitions. [2022-03-17 17:12:20,047 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 17:12:20,047 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, (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 28 [2022-03-17 17:12:20,047 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:20,048 INFO L225 Difference]: With dead ends: 57 [2022-03-17 17:12:20,048 INFO L226 Difference]: Without dead ends: 56 [2022-03-17 17:12:20,048 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-17 17:12:20,049 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 10 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:20,050 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 154 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:12:20,050 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-03-17 17:12:20,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2022-03-17 17:12:20,055 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 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-03-17 17:12:20,056 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 70 transitions. [2022-03-17 17:12:20,056 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 70 transitions. Word has length 28 [2022-03-17 17:12:20,056 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:20,057 INFO L478 AbstractCegarLoop]: Abstraction has 56 states and 70 transitions. [2022-03-17 17:12:20,057 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, (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-03-17 17:12:20,057 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2022-03-17 17:12:20,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-03-17 17:12:20,058 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:20,058 INFO L500 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, 1, 1] [2022-03-17 17:12:20,084 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:20,280 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-03-17 17:12:20,280 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:20,281 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:20,281 INFO L85 PathProgramCache]: Analyzing trace with hash 1016025214, now seen corresponding path program 1 times [2022-03-17 17:12:20,281 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:20,281 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2117622221] [2022-03-17 17:12:20,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:20,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:20,298 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:20,298 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [705677512] [2022-03-17 17:12:20,298 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:20,298 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:20,299 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:20,301 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:20,303 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-17 17:12:20,339 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:20,340 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 17:12:20,342 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:20,429 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 17:12:20,429 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:12:20,430 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:20,430 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2117622221] [2022-03-17 17:12:20,430 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:20,430 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [705677512] [2022-03-17 17:12:20,430 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [705677512] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:20,430 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:20,430 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 17:12:20,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [777523251] [2022-03-17 17:12:20,431 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:20,431 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:12:20,431 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:20,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:12:20,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:12:20,432 INFO L87 Difference]: Start difference. First operand 56 states and 70 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-03-17 17:12:20,458 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:20,458 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2022-03-17 17:12:20,458 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 17:12:20,459 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 36 [2022-03-17 17:12:20,459 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:20,460 INFO L225 Difference]: With dead ends: 69 [2022-03-17 17:12:20,460 INFO L226 Difference]: Without dead ends: 69 [2022-03-17 17:12:20,460 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:12:20,461 INFO L912 BasicCegarLoop]: 42 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:20,461 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 117 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:12:20,463 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-03-17 17:12:20,468 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 68. [2022-03-17 17:12:20,468 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-17 17:12:20,469 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 78 transitions. [2022-03-17 17:12:20,469 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 78 transitions. Word has length 36 [2022-03-17 17:12:20,470 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:20,470 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 78 transitions. [2022-03-17 17:12:20,470 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-03-17 17:12:20,470 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 78 transitions. [2022-03-17 17:12:20,471 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-03-17 17:12:20,471 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:20,471 INFO L500 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, 1, 1] [2022-03-17 17:12:20,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:20,679 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-03-17 17:12:20,680 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:20,680 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:20,680 INFO L85 PathProgramCache]: Analyzing trace with hash 1017127481, now seen corresponding path program 1 times [2022-03-17 17:12:20,680 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:20,681 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1386168119] [2022-03-17 17:12:20,681 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:20,681 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:20,694 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:20,694 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1109113961] [2022-03-17 17:12:20,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:20,695 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:20,695 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:20,702 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:20,704 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-17 17:12:20,744 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:20,745 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 17:12:20,747 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:20,952 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 17:12:20,953 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:12:20,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:20,953 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1386168119] [2022-03-17 17:12:20,953 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:20,953 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1109113961] [2022-03-17 17:12:20,953 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1109113961] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:12:20,954 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:12:20,954 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-17 17:12:20,954 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1372742536] [2022-03-17 17:12:20,955 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:20,956 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 17:12:20,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:20,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 17:12:20,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-17 17:12:20,959 INFO L87 Difference]: Start difference. First operand 68 states and 78 transitions. Second operand has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 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-03-17 17:12:21,030 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:21,031 INFO L93 Difference]: Finished difference Result 72 states and 81 transitions. [2022-03-17 17:12:21,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 17:12:21,032 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 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 36 [2022-03-17 17:12:21,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:21,035 INFO L225 Difference]: With dead ends: 72 [2022-03-17 17:12:21,035 INFO L226 Difference]: Without dead ends: 58 [2022-03-17 17:12:21,035 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 37 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-17 17:12:21,037 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 10 mSDsluCounter, 143 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 184 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:21,037 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 184 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:12:21,039 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-03-17 17:12:21,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2022-03-17 17:12:21,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 36 states have (on average 1.1666666666666667) internal successors, (42), 37 states have internal predecessors, (42), 13 states have call successors, (13), 9 states have call predecessors, (13), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-17 17:12:21,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 66 transitions. [2022-03-17 17:12:21,052 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 66 transitions. Word has length 36 [2022-03-17 17:12:21,053 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:21,053 INFO L478 AbstractCegarLoop]: Abstraction has 58 states and 66 transitions. [2022-03-17 17:12:21,053 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 3.0) internal successors, (18), 5 states have internal predecessors, (18), 3 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-03-17 17:12:21,053 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 66 transitions. [2022-03-17 17:12:21,054 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-17 17:12:21,054 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:21,054 INFO L500 BasicCegarLoop]: trace histogram [4, 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, 1, 1] [2022-03-17 17:12:21,076 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:21,254 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-03-17 17:12:21,255 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:21,255 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:21,255 INFO L85 PathProgramCache]: Analyzing trace with hash 1880362404, now seen corresponding path program 1 times [2022-03-17 17:12:21,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:21,255 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [489245293] [2022-03-17 17:12:21,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:21,255 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:21,264 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:21,264 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [174565671] [2022-03-17 17:12:21,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:21,265 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:21,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:21,266 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:21,295 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-17 17:12:21,311 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:21,312 INFO L263 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 17:12:21,314 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:21,391 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 17:12:21,392 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:12:21,491 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 6 proven. 2 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-17 17:12:21,491 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:21,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [489245293] [2022-03-17 17:12:21,491 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:21,491 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [174565671] [2022-03-17 17:12:21,491 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [174565671] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:12:21,491 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:12:21,491 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2022-03-17 17:12:21,492 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1360082026] [2022-03-17 17:12:21,492 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:12:21,492 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-03-17 17:12:21,492 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:21,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-03-17 17:12:21,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2022-03-17 17:12:21,493 INFO L87 Difference]: Start difference. First operand 58 states and 66 transitions. Second operand has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2022-03-17 17:12:21,593 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:21,593 INFO L93 Difference]: Finished difference Result 109 states and 125 transitions. [2022-03-17 17:12:21,594 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 17:12:21,594 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) Word has length 38 [2022-03-17 17:12:21,594 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:21,595 INFO L225 Difference]: With dead ends: 109 [2022-03-17 17:12:21,595 INFO L226 Difference]: Without dead ends: 109 [2022-03-17 17:12:21,595 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=40, Invalid=70, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:12:21,596 INFO L912 BasicCegarLoop]: 51 mSDtfsCounter, 60 mSDsluCounter, 167 mSDsCounter, 0 mSdLazyCounter, 71 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 71 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:21,596 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [60 Valid, 218 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 71 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:12:21,597 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2022-03-17 17:12:21,603 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 103. [2022-03-17 17:12:21,603 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 65 states have (on average 1.1846153846153846) internal successors, (77), 67 states have internal predecessors, (77), 23 states have call successors, (23), 15 states have call predecessors, (23), 14 states have return successors, (20), 20 states have call predecessors, (20), 20 states have call successors, (20) [2022-03-17 17:12:21,605 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 120 transitions. [2022-03-17 17:12:21,605 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 120 transitions. Word has length 38 [2022-03-17 17:12:21,605 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:21,605 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 120 transitions. [2022-03-17 17:12:21,605 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 6 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 4 states have call predecessors, (10), 5 states have call successors, (10) [2022-03-17 17:12:21,605 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 120 transitions. [2022-03-17 17:12:21,606 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-03-17 17:12:21,606 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:21,606 INFO L500 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:21,635 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:21,828 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-03-17 17:12:21,829 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:21,829 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:21,829 INFO L85 PathProgramCache]: Analyzing trace with hash 1525733273, now seen corresponding path program 1 times [2022-03-17 17:12:21,829 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:21,829 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874274639] [2022-03-17 17:12:21,830 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:21,830 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:21,837 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:21,838 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [61899238] [2022-03-17 17:12:21,838 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:21,838 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:21,838 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:21,839 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:21,840 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-17 17:12:21,889 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:21,892 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 16 conjunts are in the unsatisfiable core [2022-03-17 17:12:21,894 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:22,147 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 5 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-17 17:12:22,148 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:12:22,266 INFO L134 CoverageAnalysis]: Checked inductivity of 55 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-17 17:12:22,267 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:22,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [874274639] [2022-03-17 17:12:22,267 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:22,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [61899238] [2022-03-17 17:12:22,267 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [61899238] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 17:12:22,267 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:12:22,267 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-17 17:12:22,267 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [60630830] [2022-03-17 17:12:22,267 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:12:22,268 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:12:22,268 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:22,268 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:12:22,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-17 17:12:22,268 INFO L87 Difference]: Start difference. First operand 103 states and 120 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-03-17 17:12:22,315 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:22,315 INFO L93 Difference]: Finished difference Result 118 states and 137 transitions. [2022-03-17 17:12:22,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 17:12:22,316 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 46 [2022-03-17 17:12:22,316 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:22,317 INFO L225 Difference]: With dead ends: 118 [2022-03-17 17:12:22,317 INFO L226 Difference]: Without dead ends: 118 [2022-03-17 17:12:22,317 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:12:22,318 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 11 mSDsluCounter, 96 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 38 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:22,318 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 136 Invalid, 38 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:12:22,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 118 states. [2022-03-17 17:12:22,326 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 118 to 115. [2022-03-17 17:12:22,326 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 73 states have (on average 1.1643835616438356) internal successors, (85), 76 states have internal predecessors, (85), 25 states have call successors, (25), 17 states have call predecessors, (25), 16 states have return successors, (22), 21 states have call predecessors, (22), 22 states have call successors, (22) [2022-03-17 17:12:22,327 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 132 transitions. [2022-03-17 17:12:22,327 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 132 transitions. Word has length 46 [2022-03-17 17:12:22,327 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:22,328 INFO L478 AbstractCegarLoop]: Abstraction has 115 states and 132 transitions. [2022-03-17 17:12:22,328 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-03-17 17:12:22,328 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 132 transitions. [2022-03-17 17:12:22,329 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-17 17:12:22,329 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:22,329 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:22,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:22,539 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-03-17 17:12:22,539 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:22,540 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:22,540 INFO L85 PathProgramCache]: Analyzing trace with hash 1447419744, now seen corresponding path program 1 times [2022-03-17 17:12:22,540 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:22,540 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1137421756] [2022-03-17 17:12:22,540 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:22,540 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:22,549 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:22,549 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [366952231] [2022-03-17 17:12:22,549 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:22,549 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:22,549 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:22,550 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:22,554 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-17 17:12:22,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:22,612 INFO L263 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 17:12:22,614 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:22,731 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 42 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-17 17:12:22,731 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:12:22,850 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-17 17:12:22,850 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:22,851 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1137421756] [2022-03-17 17:12:22,851 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:22,851 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [366952231] [2022-03-17 17:12:22,851 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [366952231] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:12:22,851 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:12:22,851 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2022-03-17 17:12:22,851 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1513842244] [2022-03-17 17:12:22,852 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:12:22,852 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 17:12:22,852 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:22,853 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 17:12:22,853 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=33, Invalid=57, Unknown=0, NotChecked=0, Total=90 [2022-03-17 17:12:22,853 INFO L87 Difference]: Start difference. First operand 115 states and 132 transitions. Second operand has 10 states, 10 states have (on average 4.2) internal successors, (42), 10 states have internal predecessors, (42), 8 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2022-03-17 17:12:23,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:23,003 INFO L93 Difference]: Finished difference Result 193 states and 224 transitions. [2022-03-17 17:12:23,003 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-17 17:12:23,003 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 10 states have internal predecessors, (42), 8 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) Word has length 54 [2022-03-17 17:12:23,004 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:23,006 INFO L225 Difference]: With dead ends: 193 [2022-03-17 17:12:23,006 INFO L226 Difference]: Without dead ends: 193 [2022-03-17 17:12:23,006 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=52, Invalid=104, Unknown=0, NotChecked=0, Total=156 [2022-03-17 17:12:23,007 INFO L912 BasicCegarLoop]: 63 mSDtfsCounter, 107 mSDsluCounter, 159 mSDsCounter, 0 mSdLazyCounter, 116 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 222 SdHoareTripleChecker+Invalid, 171 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 116 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:23,007 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [107 Valid, 222 Invalid, 171 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 116 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:12:23,007 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 193 states. [2022-03-17 17:12:23,015 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 193 to 186. [2022-03-17 17:12:23,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 118 states have (on average 1.1779661016949152) internal successors, (139), 125 states have internal predecessors, (139), 43 states have call successors, (43), 25 states have call predecessors, (43), 24 states have return successors, (38), 35 states have call predecessors, (38), 38 states have call successors, (38) [2022-03-17 17:12:23,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 220 transitions. [2022-03-17 17:12:23,017 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 220 transitions. Word has length 54 [2022-03-17 17:12:23,017 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:23,018 INFO L478 AbstractCegarLoop]: Abstraction has 186 states and 220 transitions. [2022-03-17 17:12:23,018 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 10 states have internal predecessors, (42), 8 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 6 states have call predecessors, (16), 7 states have call successors, (16) [2022-03-17 17:12:23,018 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 220 transitions. [2022-03-17 17:12:23,019 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-03-17 17:12:23,019 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:23,019 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:12:23,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:23,235 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-03-17 17:12:23,236 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:23,236 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:23,236 INFO L85 PathProgramCache]: Analyzing trace with hash 1448522011, now seen corresponding path program 1 times [2022-03-17 17:12:23,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:23,236 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [974132590] [2022-03-17 17:12:23,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:23,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:23,244 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:23,245 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [225276027] [2022-03-17 17:12:23,245 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:23,245 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:23,245 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:23,249 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:23,250 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-17 17:12:23,286 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:23,287 INFO L263 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-17 17:12:23,291 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:23,672 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-17 17:12:23,672 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:12:23,894 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 12 proven. 6 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-17 17:12:23,894 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:12:23,894 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [974132590] [2022-03-17 17:12:23,894 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:12:23,895 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [225276027] [2022-03-17 17:12:23,895 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [225276027] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:12:23,895 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:12:23,895 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-17 17:12:23,896 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1208220045] [2022-03-17 17:12:23,896 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:12:23,897 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 17:12:23,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:12:23,897 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 17:12:23,897 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-17 17:12:23,898 INFO L87 Difference]: Start difference. First operand 186 states and 220 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, (17), 2 states have call predecessors, (17), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-03-17 17:12:24,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:12:24,131 INFO L93 Difference]: Finished difference Result 266 states and 335 transitions. [2022-03-17 17:12:24,133 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 17:12:24,133 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, (17), 2 states have call predecessors, (17), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 54 [2022-03-17 17:12:24,134 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:12:24,135 INFO L225 Difference]: With dead ends: 266 [2022-03-17 17:12:24,135 INFO L226 Difference]: Without dead ends: 264 [2022-03-17 17:12:24,135 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 98 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2022-03-17 17:12:24,136 INFO L912 BasicCegarLoop]: 59 mSDtfsCounter, 46 mSDsluCounter, 267 mSDsCounter, 0 mSdLazyCounter, 144 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 326 SdHoareTripleChecker+Invalid, 181 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 144 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:12:24,136 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [55 Valid, 326 Invalid, 181 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 144 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 17:12:24,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2022-03-17 17:12:24,153 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 239. [2022-03-17 17:12:24,154 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 155 states have (on average 1.2193548387096773) internal successors, (189), 163 states have internal predecessors, (189), 56 states have call successors, (56), 29 states have call predecessors, (56), 27 states have return successors, (51), 46 states have call predecessors, (51), 51 states have call successors, (51) [2022-03-17 17:12:24,157 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 296 transitions. [2022-03-17 17:12:24,157 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 296 transitions. Word has length 54 [2022-03-17 17:12:24,157 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:12:24,157 INFO L478 AbstractCegarLoop]: Abstraction has 239 states and 296 transitions. [2022-03-17 17:12:24,157 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, (17), 2 states have call predecessors, (17), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-03-17 17:12:24,158 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 296 transitions. [2022-03-17 17:12:24,158 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2022-03-17 17:12:24,159 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:12:24,159 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 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, 1] [2022-03-17 17:12:24,189 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-17 17:12:24,385 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-03-17 17:12:24,385 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:12:24,386 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:12:24,386 INFO L85 PathProgramCache]: Analyzing trace with hash 113245770, now seen corresponding path program 1 times [2022-03-17 17:12:24,386 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:12:24,386 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1593679699] [2022-03-17 17:12:24,386 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:24,386 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:12:24,396 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:12:24,396 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1859891565] [2022-03-17 17:12:24,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:12:24,396 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:12:24,397 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:12:24,398 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:12:24,399 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-03-17 17:12:24,484 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:12:24,485 INFO L263 TraceCheckSpWp]: Trace formula consists of 185 conjuncts, 29 conjunts are in the unsatisfiable core [2022-03-17 17:12:24,488 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:12:25,258 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 36 proven. 10 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2022-03-17 17:12:25,259 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:12:55,825 WARN L232 SmtUtils]: Spent 18.72s on a formula simplification that was a NOOP. DAG size: 53 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 17:14:20,098 WARN L232 SmtUtils]: Spent 19.94s on a formula simplification that was a NOOP. DAG size: 54 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 17:15:38,798 INFO L134 CoverageAnalysis]: Checked inductivity of 137 backedges. 36 proven. 10 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2022-03-17 17:15:38,799 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:15:38,799 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1593679699] [2022-03-17 17:15:38,799 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:15:38,799 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1859891565] [2022-03-17 17:15:38,799 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1859891565] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:15:38,799 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:15:38,799 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 19 [2022-03-17 17:15:38,800 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1809671834] [2022-03-17 17:15:38,800 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:15:38,800 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2022-03-17 17:15:38,800 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:15:38,800 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2022-03-17 17:15:38,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=70, Invalid=272, Unknown=0, NotChecked=0, Total=342 [2022-03-17 17:15:38,801 INFO L87 Difference]: Start difference. First operand 239 states and 296 transitions. Second operand has 19 states, 19 states have (on average 2.263157894736842) internal successors, (43), 16 states have internal predecessors, (43), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (18), 9 states have call predecessors, (18), 7 states have call successors, (18) [2022-03-17 17:15:40,838 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:15:42,971 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:15:54,108 WARN L232 SmtUtils]: Spent 10.53s on a formula simplification. DAG size of input: 57 DAG size of output: 27 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 17:15:59,420 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:16:02,858 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse4 (<= c_main_~d~0 c_main_~r~0)) (.cse0 (mod c_main_~A~0 4294967296)) (.cse2 (mod c_main_~B~0 4294967296))) (and (let ((.cse1 (* 2 c_main_~p~0)) (.cse3 (* 2 c_main_~d~0))) (or (= .cse0 (+ (* (+ c_main_~q~0 (div .cse1 2)) .cse2) (* (- 1) (div .cse3 2)) c_main_~r~0)) (not (= (* .cse1 .cse2) .cse3)) (not .cse4) (<= .cse3 c_main_~r~0))) (or .cse4 (not (= c_main_~d~0 (* c_main_~p~0 .cse2))) (let ((.cse7 (= (mod c_main_~p~0 2) 0)) (.cse13 (div c_main_~p~0 2))) (let ((.cse9 (* (+ c_main_~q~0 .cse13) .cse2)) (.cse10 (not .cse7)) (.cse5 (* (- 1) (div c_main_~d~0 2))) (.cse6 (* (+ c_main_~q~0 .cse13 1) .cse2)) (.cse12 (= (mod c_main_~d~0 2) 0)) (.cse11 (< c_main_~d~0 0))) (and (or (let ((.cse8 (< c_main_~p~0 0))) (and (or (= .cse0 (+ c_main_~r~0 .cse5 .cse6)) .cse7 (not .cse8)) (or (= .cse0 (+ .cse9 c_main_~r~0 .cse5)) (and .cse10 .cse8)))) (and .cse11 (not .cse12))) (or (and (or (= .cse0 (+ (- 1) .cse9 c_main_~r~0 .cse5)) .cse10) (or .cse7 (= .cse0 (+ (- 1) c_main_~r~0 .cse5 .cse6)))) .cse12 (not .cse11)))))))) is different from true [2022-03-17 17:16:06,280 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:16:06,280 INFO L93 Difference]: Finished difference Result 286 states and 355 transitions. [2022-03-17 17:16:06,281 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-17 17:16:06,281 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 2.263157894736842) internal successors, (43), 16 states have internal predecessors, (43), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (18), 9 states have call predecessors, (18), 7 states have call successors, (18) Word has length 68 [2022-03-17 17:16:06,281 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:16:06,282 INFO L225 Difference]: With dead ends: 286 [2022-03-17 17:16:06,283 INFO L226 Difference]: Without dead ends: 286 [2022-03-17 17:16:06,283 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 117 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 116 ImplicationChecksByTransitivity, 57.3s TimeCoverageRelationStatistics Valid=129, Invalid=524, Unknown=1, NotChecked=48, Total=702 [2022-03-17 17:16:06,284 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 77 mSDsluCounter, 371 mSDsCounter, 0 mSdLazyCounter, 500 mSolverCounterSat, 123 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 85 SdHoareTripleChecker+Valid, 412 SdHoareTripleChecker+Invalid, 634 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 123 IncrementalHoareTripleChecker+Valid, 500 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 8 IncrementalHoareTripleChecker+Unchecked, 12.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:16:06,284 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [85 Valid, 412 Invalid, 634 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [123 Valid, 500 Invalid, 3 Unknown, 8 Unchecked, 12.2s Time] [2022-03-17 17:16:06,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 286 states. [2022-03-17 17:16:06,293 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 286 to 252. [2022-03-17 17:16:06,294 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 252 states, 168 states have (on average 1.1904761904761905) internal successors, (200), 176 states have internal predecessors, (200), 53 states have call successors, (53), 31 states have call predecessors, (53), 30 states have return successors, (49), 44 states have call predecessors, (49), 49 states have call successors, (49) [2022-03-17 17:16:06,295 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 252 states to 252 states and 302 transitions. [2022-03-17 17:16:06,295 INFO L78 Accepts]: Start accepts. Automaton has 252 states and 302 transitions. Word has length 68 [2022-03-17 17:16:06,295 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:16:06,295 INFO L478 AbstractCegarLoop]: Abstraction has 252 states and 302 transitions. [2022-03-17 17:16:06,296 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 2.263157894736842) internal successors, (43), 16 states have internal predecessors, (43), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (18), 9 states have call predecessors, (18), 7 states have call successors, (18) [2022-03-17 17:16:06,296 INFO L276 IsEmpty]: Start isEmpty. Operand 252 states and 302 transitions. [2022-03-17 17:16:06,297 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2022-03-17 17:16:06,297 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:16:06,297 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 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-03-17 17:16:06,317 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-03-17 17:16:06,511 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-03-17 17:16:06,511 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:16:06,512 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:16:06,512 INFO L85 PathProgramCache]: Analyzing trace with hash -742748636, now seen corresponding path program 1 times [2022-03-17 17:16:06,512 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:16:06,512 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [83722301] [2022-03-17 17:16:06,512 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:06,512 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:16:06,526 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:16:06,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1082665906] [2022-03-17 17:16:06,527 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:06,527 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:16:06,527 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:16:06,528 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:16:06,529 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-03-17 17:16:06,577 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:16:06,579 INFO L263 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 26 conjunts are in the unsatisfiable core [2022-03-17 17:16:06,581 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:16:07,122 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 25 proven. 33 refuted. 0 times theorem prover too weak. 153 trivial. 0 not checked. [2022-03-17 17:16:07,122 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:16:09,947 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:16:09,947 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [83722301] [2022-03-17 17:16:09,947 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:16:09,947 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1082665906] [2022-03-17 17:16:09,948 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1082665906] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:16:09,948 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:16:09,948 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-17 17:16:09,948 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1081182376] [2022-03-17 17:16:09,948 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:16:09,948 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-17 17:16:09,948 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:16:09,949 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-17 17:16:09,949 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2022-03-17 17:16:09,949 INFO L87 Difference]: Start difference. First operand 252 states and 302 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) [2022-03-17 17:16:10,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:16:10,697 INFO L93 Difference]: Finished difference Result 289 states and 350 transitions. [2022-03-17 17:16:10,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-17 17:16:10,697 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) Word has length 79 [2022-03-17 17:16:10,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:16:10,699 INFO L225 Difference]: With dead ends: 289 [2022-03-17 17:16:10,699 INFO L226 Difference]: Without dead ends: 287 [2022-03-17 17:16:10,699 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 135 GetRequests, 110 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=126, Invalid=474, Unknown=0, NotChecked=0, Total=600 [2022-03-17 17:16:10,700 INFO L912 BasicCegarLoop]: 53 mSDtfsCounter, 32 mSDsluCounter, 357 mSDsCounter, 0 mSdLazyCounter, 360 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 410 SdHoareTripleChecker+Invalid, 408 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 360 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-03-17 17:16:10,700 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 410 Invalid, 408 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 360 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-03-17 17:16:10,701 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 287 states. [2022-03-17 17:16:10,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 287 to 268. [2022-03-17 17:16:10,713 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 268 states, 178 states have (on average 1.1797752808988764) internal successors, (210), 186 states have internal predecessors, (210), 57 states have call successors, (57), 34 states have call predecessors, (57), 32 states have return successors, (53), 47 states have call predecessors, (53), 53 states have call successors, (53) [2022-03-17 17:16:10,718 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 268 states to 268 states and 320 transitions. [2022-03-17 17:16:10,718 INFO L78 Accepts]: Start accepts. Automaton has 268 states and 320 transitions. Word has length 79 [2022-03-17 17:16:10,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:16:10,718 INFO L478 AbstractCegarLoop]: Abstraction has 268 states and 320 transitions. [2022-03-17 17:16:10,719 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 6 states have call predecessors, (12), 5 states have call successors, (12) [2022-03-17 17:16:10,719 INFO L276 IsEmpty]: Start isEmpty. Operand 268 states and 320 transitions. [2022-03-17 17:16:10,719 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 83 [2022-03-17 17:16:10,720 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:16:10,720 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 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] [2022-03-17 17:16:10,746 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-03-17 17:16:10,939 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-03-17 17:16:10,939 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:16:10,940 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:16:10,940 INFO L85 PathProgramCache]: Analyzing trace with hash -911798983, now seen corresponding path program 2 times [2022-03-17 17:16:10,940 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:16:10,940 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [838934778] [2022-03-17 17:16:10,940 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:10,940 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:16:10,948 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:16:10,948 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1523190136] [2022-03-17 17:16:10,948 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 17:16:10,948 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:16:10,949 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:16:10,956 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:16:10,957 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-03-17 17:16:11,005 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 17:16:11,006 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:16:11,006 INFO L263 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 17:16:11,009 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:16:11,135 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-17 17:16:11,136 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:16:11,281 INFO L134 CoverageAnalysis]: Checked inductivity of 218 backedges. 27 proven. 11 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-17 17:16:11,281 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:16:11,282 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [838934778] [2022-03-17 17:16:11,282 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:16:11,282 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1523190136] [2022-03-17 17:16:11,282 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1523190136] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:16:11,282 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:16:11,282 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2022-03-17 17:16:11,282 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1659118125] [2022-03-17 17:16:11,282 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:16:11,282 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:16:11,283 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:16:11,283 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:16:11,283 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:16:11,283 INFO L87 Difference]: Start difference. First operand 268 states and 320 transitions. Second operand has 5 states, 5 states have (on average 7.2) internal successors, (36), 5 states have internal predecessors, (36), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 4 states have call predecessors, (17), 4 states have call successors, (17) [2022-03-17 17:16:11,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:16:11,338 INFO L93 Difference]: Finished difference Result 261 states and 308 transitions. [2022-03-17 17:16:11,338 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-17 17:16:11,338 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 7.2) internal successors, (36), 5 states have internal predecessors, (36), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 4 states have call predecessors, (17), 4 states have call successors, (17) Word has length 82 [2022-03-17 17:16:11,338 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:16:11,339 INFO L225 Difference]: With dead ends: 261 [2022-03-17 17:16:11,339 INFO L226 Difference]: Without dead ends: 259 [2022-03-17 17:16:11,340 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 163 GetRequests, 159 SyntacticMatches, 1 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:16:11,340 INFO L912 BasicCegarLoop]: 59 mSDtfsCounter, 0 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 29 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:16:11,340 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [1 Valid, 141 Invalid, 29 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:16:11,341 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 259 states. [2022-03-17 17:16:11,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 259 to 248. [2022-03-17 17:16:11,347 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 248 states, 166 states have (on average 1.1686746987951808) internal successors, (194), 171 states have internal predecessors, (194), 51 states have call successors, (51), 32 states have call predecessors, (51), 30 states have return successors, (48), 44 states have call predecessors, (48), 48 states have call successors, (48) [2022-03-17 17:16:11,348 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 248 states to 248 states and 293 transitions. [2022-03-17 17:16:11,348 INFO L78 Accepts]: Start accepts. Automaton has 248 states and 293 transitions. Word has length 82 [2022-03-17 17:16:11,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:16:11,348 INFO L478 AbstractCegarLoop]: Abstraction has 248 states and 293 transitions. [2022-03-17 17:16:11,349 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 7.2) internal successors, (36), 5 states have internal predecessors, (36), 5 states have call successors, (19), 2 states have call predecessors, (19), 1 states have return successors, (17), 4 states have call predecessors, (17), 4 states have call successors, (17) [2022-03-17 17:16:11,349 INFO L276 IsEmpty]: Start isEmpty. Operand 248 states and 293 transitions. [2022-03-17 17:16:11,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-03-17 17:16:11,349 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:16:11,349 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 2, 2, 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, 1, 1] [2022-03-17 17:16:11,371 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-17 17:16:11,563 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-03-17 17:16:11,563 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:16:11,564 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:16:11,564 INFO L85 PathProgramCache]: Analyzing trace with hash 1053492757, now seen corresponding path program 1 times [2022-03-17 17:16:11,564 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:16:11,564 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [184770239] [2022-03-17 17:16:11,564 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:11,564 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:16:11,571 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:16:11,571 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [350826564] [2022-03-17 17:16:11,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:11,571 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:16:11,571 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:16:11,572 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:16:11,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-03-17 17:16:11,622 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:16:11,623 INFO L263 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-17 17:16:11,625 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:16:11,855 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-03-17 17:16:11,856 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:16:12,231 INFO L134 CoverageAnalysis]: Checked inductivity of 253 backedges. 22 proven. 11 refuted. 0 times theorem prover too weak. 220 trivial. 0 not checked. [2022-03-17 17:16:12,231 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:16:12,231 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [184770239] [2022-03-17 17:16:12,231 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:16:12,231 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [350826564] [2022-03-17 17:16:12,231 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [350826564] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:16:12,231 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:16:12,232 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2022-03-17 17:16:12,232 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [544402026] [2022-03-17 17:16:12,232 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:16:12,232 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-03-17 17:16:12,232 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:16:12,232 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-03-17 17:16:12,232 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:16:12,233 INFO L87 Difference]: Start difference. First operand 248 states and 293 transitions. Second operand has 11 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 10 states have internal predecessors, (40), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-03-17 17:16:12,504 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:16:12,504 INFO L93 Difference]: Finished difference Result 252 states and 297 transitions. [2022-03-17 17:16:12,504 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 17:16:12,504 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 10 states have internal predecessors, (40), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) Word has length 84 [2022-03-17 17:16:12,505 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:16:12,505 INFO L225 Difference]: With dead ends: 252 [2022-03-17 17:16:12,505 INFO L226 Difference]: Without dead ends: 229 [2022-03-17 17:16:12,506 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 157 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:16:12,506 INFO L912 BasicCegarLoop]: 61 mSDtfsCounter, 12 mSDsluCounter, 193 mSDsCounter, 0 mSdLazyCounter, 70 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 254 SdHoareTripleChecker+Invalid, 84 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 70 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:16:12,506 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 254 Invalid, 84 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 70 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 17:16:12,507 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 229 states. [2022-03-17 17:16:12,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 229 to 229. [2022-03-17 17:16:12,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 229 states, 153 states have (on average 1.1764705882352942) internal successors, (180), 158 states have internal predecessors, (180), 47 states have call successors, (47), 30 states have call predecessors, (47), 28 states have return successors, (44), 40 states have call predecessors, (44), 44 states have call successors, (44) [2022-03-17 17:16:12,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 229 states to 229 states and 271 transitions. [2022-03-17 17:16:12,512 INFO L78 Accepts]: Start accepts. Automaton has 229 states and 271 transitions. Word has length 84 [2022-03-17 17:16:12,512 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:16:12,513 INFO L478 AbstractCegarLoop]: Abstraction has 229 states and 271 transitions. [2022-03-17 17:16:12,513 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 3.6363636363636362) internal successors, (40), 10 states have internal predecessors, (40), 8 states have call successors, (27), 2 states have call predecessors, (27), 1 states have return successors, (24), 8 states have call predecessors, (24), 8 states have call successors, (24) [2022-03-17 17:16:12,513 INFO L276 IsEmpty]: Start isEmpty. Operand 229 states and 271 transitions. [2022-03-17 17:16:12,513 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-17 17:16:12,514 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:16:12,514 INFO L500 BasicCegarLoop]: trace histogram [13, 12, 12, 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, 1, 1, 1, 1, 1, 1] [2022-03-17 17:16:12,536 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-03-17 17:16:12,728 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-03-17 17:16:12,728 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:16:12,728 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:16:12,729 INFO L85 PathProgramCache]: Analyzing trace with hash -883405496, now seen corresponding path program 1 times [2022-03-17 17:16:12,729 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:16:12,729 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1665775313] [2022-03-17 17:16:12,729 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:12,729 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:16:12,736 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:16:12,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1994018836] [2022-03-17 17:16:12,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:12,736 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:16:12,736 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:16:12,737 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:16:12,748 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-03-17 17:16:12,784 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:16:12,785 INFO L263 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-17 17:16:12,787 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:16:12,952 INFO L134 CoverageAnalysis]: Checked inductivity of 306 backedges. 84 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-03-17 17:16:12,953 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:16:12,953 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:16:12,953 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1665775313] [2022-03-17 17:16:12,953 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:16:12,953 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1994018836] [2022-03-17 17:16:12,953 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1994018836] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:16:12,953 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:16:12,953 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 17:16:12,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1813212176] [2022-03-17 17:16:12,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:16:12,954 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:16:12,954 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:16:12,954 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:16:12,954 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:16:12,954 INFO L87 Difference]: Start difference. First operand 229 states and 271 transitions. Second operand has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 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-03-17 17:16:12,999 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:16:12,999 INFO L93 Difference]: Finished difference Result 228 states and 267 transitions. [2022-03-17 17:16:12,999 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 17:16:12,999 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 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 88 [2022-03-17 17:16:13,000 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:16:13,001 INFO L225 Difference]: With dead ends: 228 [2022-03-17 17:16:13,001 INFO L226 Difference]: Without dead ends: 228 [2022-03-17 17:16:13,001 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 84 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-03-17 17:16:13,002 INFO L912 BasicCegarLoop]: 63 mSDtfsCounter, 17 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 135 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:16:13,002 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 135 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:16:13,003 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 228 states. [2022-03-17 17:16:13,008 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 228 to 218. [2022-03-17 17:16:13,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 218 states, 147 states have (on average 1.1360544217687074) internal successors, (167), 150 states have internal predecessors, (167), 43 states have call successors, (43), 28 states have call predecessors, (43), 27 states have return successors, (41), 39 states have call predecessors, (41), 41 states have call successors, (41) [2022-03-17 17:16:13,009 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 218 states to 218 states and 251 transitions. [2022-03-17 17:16:13,009 INFO L78 Accepts]: Start accepts. Automaton has 218 states and 251 transitions. Word has length 88 [2022-03-17 17:16:13,009 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:16:13,009 INFO L478 AbstractCegarLoop]: Abstraction has 218 states and 251 transitions. [2022-03-17 17:16:13,010 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.4) internal successors, (27), 5 states have internal predecessors, (27), 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-03-17 17:16:13,010 INFO L276 IsEmpty]: Start isEmpty. Operand 218 states and 251 transitions. [2022-03-17 17:16:13,011 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 101 [2022-03-17 17:16:13,011 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:16:13,011 INFO L500 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 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-03-17 17:16:13,037 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-03-17 17:16:13,231 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-17 17:16:13,231 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:16:13,232 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:16:13,232 INFO L85 PathProgramCache]: Analyzing trace with hash -873799525, now seen corresponding path program 3 times [2022-03-17 17:16:13,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:16:13,232 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1803409634] [2022-03-17 17:16:13,232 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:16:13,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:16:13,239 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:16:13,239 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [381237125] [2022-03-17 17:16:13,239 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 17:16:13,240 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:16:13,240 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:16:13,245 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:16:13,246 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2022-03-17 17:16:13,357 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-17 17:16:13,357 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:16:13,358 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 47 conjunts are in the unsatisfiable core [2022-03-17 17:16:13,360 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:16:14,071 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 61 proven. 31 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2022-03-17 17:16:14,071 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:16:29,483 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse0 (mod c_main_~B~0 4294967296))) (or (not (= c_main_~d~0 (* c_main_~p~0 .cse0))) (let ((.cse4 (= (mod c_main_~p~0 2) 0)) (.cse10 (div c_main_~p~0 2))) (let ((.cse6 (* (+ c_main_~q~0 .cse10) .cse0)) (.cse7 (not .cse4)) (.cse1 (mod c_main_~A~0 4294967296)) (.cse2 (* (- 1) (div c_main_~d~0 2))) (.cse3 (* (+ c_main_~q~0 .cse10 1) .cse0)) (.cse9 (= (mod c_main_~d~0 2) 0)) (.cse8 (< c_main_~d~0 0))) (and (or (let ((.cse5 (< c_main_~p~0 0))) (and (or (= .cse1 (+ c_main_~r~0 .cse2 .cse3)) .cse4 (not .cse5)) (or (= .cse1 (+ .cse6 c_main_~r~0 .cse2)) (and .cse7 .cse5)))) (and .cse8 (not .cse9))) (or (and (or (= .cse1 (+ (- 1) .cse6 c_main_~r~0 .cse2)) .cse7) (or .cse4 (= .cse1 (+ (- 1) c_main_~r~0 .cse2 .cse3)))) .cse9 (not .cse8))))))) is different from true [2022-03-17 17:17:28,561 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse0 (mod c_main_~B~0 4294967296))) (or (not (= c_main_~d~0 (* c_main_~p~0 .cse0))) (let ((.cse5 (= (mod c_main_~p~0 2) 0)) (.cse11 (div c_main_~p~0 2))) (let ((.cse9 (< c_main_~d~0 0)) (.cse8 (= (mod c_main_~d~0 2) 0)) (.cse4 (* (+ c_main_~q~0 c_main_~p~0 .cse11 1) .cse0)) (.cse1 (mod c_main_~A~0 4294967296)) (.cse6 (* .cse0 (+ c_main_~q~0 c_main_~p~0 .cse11))) (.cse2 (* (- 1) c_main_~d~0)) (.cse3 (* (- 1) (div c_main_~d~0 2))) (.cse7 (not .cse5))) (and (or (and (or (= .cse1 (+ (- 1) .cse2 c_main_~r~0 .cse3 .cse4)) .cse5) (or (= .cse1 (+ (- 1) .cse6 .cse2 c_main_~r~0 .cse3)) .cse7)) .cse8 (not .cse9)) (or (and .cse9 (not .cse8)) (let ((.cse10 (< c_main_~p~0 0))) (and (or (= .cse1 (+ .cse2 c_main_~r~0 .cse3 .cse4)) .cse5 (not .cse10)) (or (= .cse1 (+ .cse6 .cse2 c_main_~r~0 .cse3)) (and .cse7 .cse10)))))))))) is different from true [2022-03-17 17:18:48,651 WARN L232 SmtUtils]: Spent 50.03s on a formula simplification that was a NOOP. DAG size: 116 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 17:25:26,310 WARN L232 SmtUtils]: Spent 22.62s on a formula simplification that was a NOOP. DAG size: 59 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-17 17:26:34,449 INFO L134 CoverageAnalysis]: Checked inductivity of 368 backedges. 61 proven. 23 refuted. 0 times theorem prover too weak. 276 trivial. 8 not checked. [2022-03-17 17:26:34,450 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:26:34,450 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1803409634] [2022-03-17 17:26:34,450 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:26:34,450 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [381237125] [2022-03-17 17:26:34,450 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [381237125] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:26:34,450 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:26:34,450 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 24 [2022-03-17 17:26:34,450 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1154018216] [2022-03-17 17:26:34,450 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:26:34,451 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-17 17:26:34,451 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:26:34,451 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-17 17:26:34,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=84, Invalid=383, Unknown=3, NotChecked=82, Total=552 [2022-03-17 17:26:34,452 INFO L87 Difference]: Start difference. First operand 218 states and 251 transitions. Second operand has 24 states, 24 states have (on average 2.5) internal successors, (60), 21 states have internal predecessors, (60), 11 states have call successors, (31), 2 states have call predecessors, (31), 3 states have return successors, (29), 11 states have call predecessors, (29), 9 states have call successors, (29) [2022-03-17 17:26:36,105 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.65s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:26:38,006 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.90s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:26:40,019 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:26:42,748 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-17 17:26:55,324 WARN L232 SmtUtils]: Spent 12.26s on a formula simplification. DAG size of input: 146 DAG size of output: 43 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate)