/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7968f31 [2022-03-17 17:01:08,099 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-17 17:01:08,100 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-17 17:01:08,125 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-17 17:01:08,126 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-17 17:01:08,127 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-17 17:01:08,129 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-17 17:01:08,133 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-17 17:01:08,134 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-17 17:01:08,137 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-17 17:01:08,137 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-17 17:01:08,138 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-17 17:01:08,138 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-17 17:01:08,139 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-17 17:01:08,139 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-17 17:01:08,140 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-17 17:01:08,140 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-17 17:01:08,141 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-17 17:01:08,141 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-17 17:01:08,142 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-17 17:01:08,143 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-17 17:01:08,145 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-17 17:01:08,146 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-17 17:01:08,148 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-17 17:01:08,149 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-17 17:01:08,150 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-17 17:01:08,150 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-17 17:01:08,150 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-17 17:01:08,151 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-17 17:01:08,151 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-17 17:01:08,152 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-17 17:01:08,152 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-17 17:01:08,152 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-17 17:01:08,153 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-17 17:01:08,153 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-17 17:01:08,153 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-17 17:01:08,154 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-17 17:01:08,154 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-17 17:01:08,154 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-17 17:01:08,154 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-17 17:01:08,155 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-17 17:01:08,156 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-17 17:01:08,157 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-03-17 17:01:08,164 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-17 17:01:08,164 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-17 17:01:08,166 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-17 17:01:08,166 INFO L138 SettingsManager]: * sizeof long=4 [2022-03-17 17:01:08,166 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-17 17:01:08,166 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-03-17 17:01:08,166 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * sizeof long double=12 [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-17 17:01:08,167 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-17 17:01:08,168 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-17 17:01:08,168 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-17 17:01:08,168 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-17 17:01:08,168 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-17 17:01:08,168 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 17:01:08,168 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-17 17:01:08,168 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-17 17:01:08,169 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-17 17:01:08,169 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:01:08,365 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-17 17:01:08,385 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-17 17:01:08,386 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-17 17:01:08,387 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-17 17:01:08,387 INFO L275 PluginConnector]: CDTParser initialized [2022-03-17 17:01:08,388 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c [2022-03-17 17:01:08,436 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ec469829/1009427e719e46aea3211d303115cc63/FLAG4d27f8391 [2022-03-17 17:01:08,780 INFO L306 CDTParser]: Found 1 translation units. [2022-03-17 17:01:08,780 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c [2022-03-17 17:01:08,784 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ec469829/1009427e719e46aea3211d303115cc63/FLAG4d27f8391 [2022-03-17 17:01:08,793 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/2ec469829/1009427e719e46aea3211d303115cc63 [2022-03-17 17:01:08,794 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-17 17:01:08,795 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-17 17:01:08,804 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-17 17:01:08,804 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-17 17:01:08,807 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-17 17:01:08,807 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,808 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7f632b and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08, skipping insertion in model container [2022-03-17 17:01:08,808 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,812 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-17 17:01:08,822 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-17 17:01:08,932 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2022-03-17 17:01:08,946 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 17:01:08,953 INFO L203 MainTranslator]: Completed pre-run [2022-03-17 17:01:08,961 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd2-ll_valuebound2.c[490,503] [2022-03-17 17:01:08,967 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-17 17:01:08,976 INFO L208 MainTranslator]: Completed translation [2022-03-17 17:01:08,976 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08 WrapperNode [2022-03-17 17:01:08,976 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-17 17:01:08,977 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-17 17:01:08,977 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-17 17:01:08,977 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-17 17:01:08,984 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,984 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,990 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,991 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,994 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,996 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,997 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:08,998 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-17 17:01:08,999 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-17 17:01:08,999 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-17 17:01:08,999 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-17 17:01:09,000 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (1/1) ... [2022-03-17 17:01:09,004 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-17 17:01:09,013 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:09,021 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:01:09,030 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:01:09,057 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-17 17:01:09,058 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-17 17:01:09,058 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-17 17:01:09,058 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-17 17:01:09,058 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-17 17:01:09,059 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-17 17:01:09,059 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-17 17:01:09,060 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-17 17:01:09,060 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-17 17:01:09,061 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-17 17:01:09,061 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-17 17:01:09,061 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-17 17:01:09,061 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-17 17:01:09,061 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-17 17:01:09,110 INFO L234 CfgBuilder]: Building ICFG [2022-03-17 17:01:09,111 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-17 17:01:09,225 INFO L275 CfgBuilder]: Performing block encoding [2022-03-17 17:01:09,229 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-17 17:01:09,229 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-17 17:01:09,230 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:01:09 BoogieIcfgContainer [2022-03-17 17:01:09,230 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-17 17:01:09,231 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-17 17:01:09,231 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-17 17:01:09,235 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-17 17:01:09,238 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:01:09" (1/1) ... [2022-03-17 17:01:09,250 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 05:01:09 BasicIcfg [2022-03-17 17:01:09,250 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-17 17:01:09,252 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-17 17:01:09,252 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-17 17:01:09,268 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-17 17:01:09,269 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.03 05:01:08" (1/4) ... [2022-03-17 17:01:09,269 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6aeb2bb9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 05:01:09, skipping insertion in model container [2022-03-17 17:01:09,269 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.03 05:01:08" (2/4) ... [2022-03-17 17:01:09,270 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6aeb2bb9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.03 05:01:09, skipping insertion in model container [2022-03-17 17:01:09,270 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.03 05:01:09" (3/4) ... [2022-03-17 17:01:09,270 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@6aeb2bb9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 05:01:09, skipping insertion in model container [2022-03-17 17:01:09,270 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 17.03 05:01:09" (4/4) ... [2022-03-17 17:01:09,271 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd2-ll_valuebound2.cJordan [2022-03-17 17:01:09,274 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-03-17 17:01:09,275 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-17 17:01:09,324 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-17 17:01:09,339 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:01:09,347 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-17 17:01:09,372 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-17 17:01:09,378 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-03-17 17:01:09,378 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:09,378 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:09,379 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:09,382 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:09,382 INFO L85 PathProgramCache]: Analyzing trace with hash -1630657446, now seen corresponding path program 1 times [2022-03-17 17:01:09,390 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:09,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [735711843] [2022-03-17 17:01:09,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:09,393 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:09,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,533 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-17 17:01:09,542 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,551 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-17 17:01:09,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,572 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-17 17:01:09,574 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,579 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-17 17:01:09,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,586 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-03-17 17:01:09,587 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,594 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 28 [2022-03-17 17:01:09,596 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,601 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 33 [2022-03-17 17:01:09,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,612 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-17 17:01:09,612 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:09,613 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [735711843] [2022-03-17 17:01:09,614 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [735711843] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:01:09,614 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:01:09,614 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-17 17:01:09,615 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1843682757] [2022-03-17 17:01:09,616 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:01:09,620 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-17 17:01:09,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:09,644 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-17 17:01:09,645 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 17:01:09,647 INFO L87 Difference]: Start difference. First operand has 40 states, 20 states have (on average 1.45) internal successors, (29), 22 states have internal predecessors, (29), 14 states have call successors, (14), 4 states have call predecessors, (14), 4 states have return successors, (14), 14 states have call predecessors, (14), 14 states have call successors, (14) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 17:01:09,730 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:09,730 INFO L93 Difference]: Finished difference Result 40 states and 51 transitions. [2022-03-17 17:01:09,731 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-17 17:01:09,732 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-03-17 17:01:09,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:09,740 INFO L225 Difference]: With dead ends: 40 [2022-03-17 17:01:09,740 INFO L226 Difference]: Without dead ends: 35 [2022-03-17 17:01:09,742 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 22 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-17 17:01:09,747 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 42 SdHoareTripleChecker+Invalid, 27 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:09,748 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 42 Invalid, 27 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:09,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-17 17:01:09,771 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-03-17 17:01:09,772 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 19 states have internal predecessors, (20), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-17 17:01:09,773 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 46 transitions. [2022-03-17 17:01:09,774 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 46 transitions. Word has length 43 [2022-03-17 17:01:09,774 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:09,774 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 46 transitions. [2022-03-17 17:01:09,774 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (9), 3 states have call predecessors, (9), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 17:01:09,774 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 46 transitions. [2022-03-17 17:01:09,776 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-03-17 17:01:09,776 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:09,776 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:09,776 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-17 17:01:09,776 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:09,777 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:09,777 INFO L85 PathProgramCache]: Analyzing trace with hash -1790145708, now seen corresponding path program 1 times [2022-03-17 17:01:09,777 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:09,777 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1439523909] [2022-03-17 17:01:09,777 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:09,777 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:09,791 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:09,791 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [290299865] [2022-03-17 17:01:09,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:09,791 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:09,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:09,793 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:01:09,794 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:01:09,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:09,848 INFO L263 TraceCheckSpWp]: Trace formula consists of 133 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-17 17:01:09,852 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:09,976 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-17 17:01:09,977 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:10,087 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-17 17:01:10,087 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:10,087 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1439523909] [2022-03-17 17:01:10,088 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:10,088 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [290299865] [2022-03-17 17:01:10,088 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [290299865] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:10,088 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:10,088 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-03-17 17:01:10,089 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1901748459] [2022-03-17 17:01:10,089 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:10,089 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-17 17:01:10,089 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:10,090 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-17 17:01:10,090 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-17 17:01:10,090 INFO L87 Difference]: Start difference. First operand 35 states and 46 transitions. Second operand has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 17:01:10,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:10,173 INFO L93 Difference]: Finished difference Result 44 states and 60 transitions. [2022-03-17 17:01:10,173 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 17:01:10,173 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) Word has length 44 [2022-03-17 17:01:10,174 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:10,174 INFO L225 Difference]: With dead ends: 44 [2022-03-17 17:01:10,174 INFO L226 Difference]: Without dead ends: 44 [2022-03-17 17:01:10,175 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 81 SyntacticMatches, 1 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2022-03-17 17:01:10,175 INFO L912 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 26 SdHoareTripleChecker+Valid, 124 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:10,176 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [26 Valid, 124 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:01:10,176 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-03-17 17:01:10,189 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-03-17 17:01:10,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 19 states have (on average 1.1578947368421053) internal successors, (22), 20 states have internal predecessors, (22), 14 states have call successors, (14), 4 states have call predecessors, (14), 3 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-17 17:01:10,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 48 transitions. [2022-03-17 17:01:10,190 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 48 transitions. Word has length 44 [2022-03-17 17:01:10,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:10,190 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 48 transitions. [2022-03-17 17:01:10,190 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.5714285714285716) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 3 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-17 17:01:10,191 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 48 transitions. [2022-03-17 17:01:10,191 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-03-17 17:01:10,191 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:10,191 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:10,208 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-17 17:01:10,394 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:10,394 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:10,395 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:10,395 INFO L85 PathProgramCache]: Analyzing trace with hash 375385207, now seen corresponding path program 1 times [2022-03-17 17:01:10,395 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:10,395 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2123993718] [2022-03-17 17:01:10,395 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:10,395 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:10,415 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:10,415 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2071085635] [2022-03-17 17:01:10,415 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:10,415 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:10,416 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:10,423 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:01:10,425 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:01:10,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:10,468 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 17:01:10,474 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:10,589 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 6 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-17 17:01:10,589 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:10,713 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-17 17:01:10,713 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:10,715 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2123993718] [2022-03-17 17:01:10,715 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:10,715 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2071085635] [2022-03-17 17:01:10,715 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2071085635] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:10,715 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:10,715 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-17 17:01:10,716 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1221225539] [2022-03-17 17:01:10,716 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:01:10,716 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:01:10,716 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:10,716 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:01:10,717 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2022-03-17 17:01:10,717 INFO L87 Difference]: Start difference. First operand 37 states and 48 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-03-17 17:01:10,754 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:10,754 INFO L93 Difference]: Finished difference Result 41 states and 51 transitions. [2022-03-17 17:01:10,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-17 17:01:10,755 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) Word has length 45 [2022-03-17 17:01:10,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:10,755 INFO L225 Difference]: With dead ends: 41 [2022-03-17 17:01:10,755 INFO L226 Difference]: Without dead ends: 41 [2022-03-17 17:01:10,756 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:01:10,757 INFO L912 BasicCegarLoop]: 40 mSDtfsCounter, 6 mSDsluCounter, 106 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 146 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:10,757 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 146 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:01:10,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-03-17 17:01:10,761 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 41. [2022-03-17 17:01:10,761 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 14 states have call successors, (14), 5 states have call predecessors, (14), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-17 17:01:10,762 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 51 transitions. [2022-03-17 17:01:10,762 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 51 transitions. Word has length 45 [2022-03-17 17:01:10,762 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:10,762 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 51 transitions. [2022-03-17 17:01:10,762 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 1 states have call predecessors, (7), 1 states have call successors, (7) [2022-03-17 17:01:10,762 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 51 transitions. [2022-03-17 17:01:10,763 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2022-03-17 17:01:10,763 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:10,763 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:10,780 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:01:10,964 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-03-17 17:01:10,964 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:10,965 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:10,965 INFO L85 PathProgramCache]: Analyzing trace with hash -788787523, now seen corresponding path program 1 times [2022-03-17 17:01:10,965 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:10,965 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1180221772] [2022-03-17 17:01:10,965 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:10,965 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:10,975 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:10,976 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1280710826] [2022-03-17 17:01:10,976 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:10,976 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:10,976 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:10,977 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:01:10,978 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:01:11,022 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:11,024 INFO L263 TraceCheckSpWp]: Trace formula consists of 146 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-17 17:01:11,026 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:11,243 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 7 proven. 10 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2022-03-17 17:01:11,243 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:11,303 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:11,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1180221772] [2022-03-17 17:01:11,303 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:11,303 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1280710826] [2022-03-17 17:01:11,303 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1280710826] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:11,304 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:11,304 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10] total 10 [2022-03-17 17:01:11,304 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1507255531] [2022-03-17 17:01:11,304 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:11,304 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-17 17:01:11,304 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:11,305 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-17 17:01:11,305 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:01:11,305 INFO L87 Difference]: Start difference. First operand 41 states and 51 transitions. Second operand has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-17 17:01:11,427 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:11,427 INFO L93 Difference]: Finished difference Result 52 states and 66 transitions. [2022-03-17 17:01:11,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-17 17:01:11,427 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 50 [2022-03-17 17:01:11,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:11,428 INFO L225 Difference]: With dead ends: 52 [2022-03-17 17:01:11,428 INFO L226 Difference]: Without dead ends: 52 [2022-03-17 17:01:11,428 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:01:11,429 INFO L912 BasicCegarLoop]: 30 mSDtfsCounter, 26 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 199 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 207 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 199 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:11,429 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 194 Invalid, 207 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 199 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:11,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-17 17:01:11,433 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-03-17 17:01:11,433 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 27 states have (on average 1.1481481481481481) internal successors, (31), 28 states have internal predecessors, (31), 18 states have call successors, (18), 6 states have call predecessors, (18), 5 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-17 17:01:11,434 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 65 transitions. [2022-03-17 17:01:11,434 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 65 transitions. Word has length 50 [2022-03-17 17:01:11,434 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:11,434 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 65 transitions. [2022-03-17 17:01:11,434 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.0) internal successors, (20), 8 states have internal predecessors, (20), 3 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-17 17:01:11,434 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 65 transitions. [2022-03-17 17:01:11,435 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-03-17 17:01:11,435 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:11,435 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:11,454 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:01:11,651 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:11,652 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:11,652 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:11,652 INFO L85 PathProgramCache]: Analyzing trace with hash -735644649, now seen corresponding path program 1 times [2022-03-17 17:01:11,652 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:11,652 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2024932023] [2022-03-17 17:01:11,652 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:11,652 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:11,664 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:11,664 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1412530735] [2022-03-17 17:01:11,664 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:11,664 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:11,664 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:11,667 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:01:11,668 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:01:11,704 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:11,705 INFO L263 TraceCheckSpWp]: Trace formula consists of 155 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-17 17:01:11,706 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:11,990 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 27 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2022-03-17 17:01:11,990 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:12,123 INFO L134 CoverageAnalysis]: Checked inductivity of 68 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-17 17:01:12,124 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:12,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2024932023] [2022-03-17 17:01:12,124 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:12,124 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1412530735] [2022-03-17 17:01:12,124 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1412530735] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:12,124 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:12,124 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [11] total 13 [2022-03-17 17:01:12,124 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1684423508] [2022-03-17 17:01:12,125 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:01:12,125 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-17 17:01:12,125 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:12,125 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-17 17:01:12,125 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2022-03-17 17:01:12,125 INFO L87 Difference]: Start difference. First operand 51 states and 65 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-17 17:01:12,167 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:12,168 INFO L93 Difference]: Finished difference Result 56 states and 69 transitions. [2022-03-17 17:01:12,168 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 17:01:12,168 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 55 [2022-03-17 17:01:12,168 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:12,169 INFO L225 Difference]: With dead ends: 56 [2022-03-17 17:01:12,169 INFO L226 Difference]: Without dead ends: 56 [2022-03-17 17:01:12,169 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 97 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:01:12,170 INFO L912 BasicCegarLoop]: 46 mSDtfsCounter, 12 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:12,170 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 162 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:01:12,170 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-03-17 17:01:12,173 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 55. [2022-03-17 17:01:12,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 31 states have internal predecessors, (34), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-17 17:01:12,174 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-03-17 17:01:12,174 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 55 [2022-03-17 17:01:12,174 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:12,174 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-03-17 17:01:12,174 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-03-17 17:01:12,174 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-03-17 17:01:12,175 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2022-03-17 17:01:12,175 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:12,175 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:12,197 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:01:12,391 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:12,391 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:12,392 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:12,392 INFO L85 PathProgramCache]: Analyzing trace with hash -1700404515, now seen corresponding path program 1 times [2022-03-17 17:01:12,392 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:12,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1740444619] [2022-03-17 17:01:12,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:12,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:12,401 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:12,401 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [579930450] [2022-03-17 17:01:12,401 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:12,401 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:12,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:12,408 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:01:12,409 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:01:12,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:12,449 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-17 17:01:12,451 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:12,601 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 2 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2022-03-17 17:01:12,602 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:12,666 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:12,667 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1740444619] [2022-03-17 17:01:12,667 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:12,667 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [579930450] [2022-03-17 17:01:12,667 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [579930450] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:12,667 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:12,668 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7] total 7 [2022-03-17 17:01:12,668 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [830852715] [2022-03-17 17:01:12,668 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:12,669 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-17 17:01:12,669 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:12,669 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-17 17:01:12,669 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-03-17 17:01:12,669 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-03-17 17:01:12,746 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:12,747 INFO L93 Difference]: Finished difference Result 60 states and 72 transitions. [2022-03-17 17:01:12,747 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-17 17:01:12,748 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) Word has length 60 [2022-03-17 17:01:12,750 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:12,751 INFO L225 Difference]: With dead ends: 60 [2022-03-17 17:01:12,751 INFO L226 Difference]: Without dead ends: 60 [2022-03-17 17:01:12,751 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 56 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:01:12,753 INFO L912 BasicCegarLoop]: 36 mSDtfsCounter, 11 mSDsluCounter, 145 mSDsCounter, 0 mSdLazyCounter, 111 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 181 SdHoareTripleChecker+Invalid, 113 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 111 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:12,753 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 181 Invalid, 113 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 111 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:12,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2022-03-17 17:01:12,767 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 59. [2022-03-17 17:01:12,767 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 59 states, 33 states have (on average 1.121212121212121) internal successors, (37), 34 states have internal predecessors, (37), 18 states have call successors, (18), 8 states have call predecessors, (18), 7 states have return successors, (16), 16 states have call predecessors, (16), 16 states have call successors, (16) [2022-03-17 17:01:12,767 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 59 states to 59 states and 71 transitions. [2022-03-17 17:01:12,768 INFO L78 Accepts]: Start accepts. Automaton has 59 states and 71 transitions. Word has length 60 [2022-03-17 17:01:12,768 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:12,768 INFO L478 AbstractCegarLoop]: Abstraction has 59 states and 71 transitions. [2022-03-17 17:01:12,768 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.857142857142857) internal successors, (20), 6 states have internal predecessors, (20), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 2 states have call predecessors, (10), 2 states have call successors, (10) [2022-03-17 17:01:12,768 INFO L276 IsEmpty]: Start isEmpty. Operand 59 states and 71 transitions. [2022-03-17 17:01:12,772 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-17 17:01:12,772 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:12,772 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:12,791 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:01:12,985 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:12,990 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:12,991 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:12,991 INFO L85 PathProgramCache]: Analyzing trace with hash 2004479621, now seen corresponding path program 1 times [2022-03-17 17:01:12,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:12,991 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [863278623] [2022-03-17 17:01:12,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:12,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:13,002 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:13,003 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1024991114] [2022-03-17 17:01:13,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:13,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:13,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:13,013 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:01:13,024 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:01:13,080 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:13,080 INFO L263 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-17 17:01:13,088 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:13,181 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-17 17:01:13,181 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:13,296 INFO L134 CoverageAnalysis]: Checked inductivity of 94 backedges. 14 proven. 11 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2022-03-17 17:01:13,296 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:13,296 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [863278623] [2022-03-17 17:01:13,296 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:13,296 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1024991114] [2022-03-17 17:01:13,296 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1024991114] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:13,297 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:13,297 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-03-17 17:01:13,297 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [683903418] [2022-03-17 17:01:13,297 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:13,297 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 17:01:13,297 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:13,297 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 17:01:13,298 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-17 17:01:13,298 INFO L87 Difference]: Start difference. First operand 59 states and 71 transitions. Second operand has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-03-17 17:01:13,411 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:13,411 INFO L93 Difference]: Finished difference Result 98 states and 137 transitions. [2022-03-17 17:01:13,413 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 17:01:13,413 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 69 [2022-03-17 17:01:13,413 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:13,414 INFO L225 Difference]: With dead ends: 98 [2022-03-17 17:01:13,414 INFO L226 Difference]: Without dead ends: 98 [2022-03-17 17:01:13,414 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 142 GetRequests, 129 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:01:13,415 INFO L912 BasicCegarLoop]: 60 mSDtfsCounter, 30 mSDsluCounter, 325 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 53 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 385 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 53 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:13,415 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 385 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [53 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:13,415 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2022-03-17 17:01:13,419 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 89. [2022-03-17 17:01:13,420 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 47 states have (on average 1.1914893617021276) internal successors, (56), 48 states have internal predecessors, (56), 34 states have call successors, (34), 8 states have call predecessors, (34), 7 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2022-03-17 17:01:13,420 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 122 transitions. [2022-03-17 17:01:13,420 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 122 transitions. Word has length 69 [2022-03-17 17:01:13,420 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:13,421 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 122 transitions. [2022-03-17 17:01:13,421 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.888888888888889) internal successors, (26), 8 states have internal predecessors, (26), 5 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2022-03-17 17:01:13,421 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 122 transitions. [2022-03-17 17:01:13,421 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-03-17 17:01:13,421 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:13,421 INFO L500 BasicCegarLoop]: trace histogram [6, 6, 6, 6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:13,440 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:01:13,638 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:13,638 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:13,639 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:13,639 INFO L85 PathProgramCache]: Analyzing trace with hash -966489810, now seen corresponding path program 1 times [2022-03-17 17:01:13,639 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:13,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [100844220] [2022-03-17 17:01:13,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:13,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:13,648 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:13,649 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1010035295] [2022-03-17 17:01:13,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:13,649 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:13,649 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:13,650 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:01:13,651 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:01:13,692 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:13,693 INFO L263 TraceCheckSpWp]: Trace formula consists of 204 conjuncts, 18 conjunts are in the unsatisfiable core [2022-03-17 17:01:13,696 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:13,823 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-17 17:01:13,824 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:13,960 INFO L134 CoverageAnalysis]: Checked inductivity of 115 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2022-03-17 17:01:13,960 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:13,960 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [100844220] [2022-03-17 17:01:13,960 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:13,960 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1010035295] [2022-03-17 17:01:13,960 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1010035295] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:13,960 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:13,960 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-17 17:01:13,960 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [111409860] [2022-03-17 17:01:13,961 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:13,961 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-17 17:01:13,961 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:13,962 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-17 17:01:13,962 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=104, Unknown=0, NotChecked=0, Total=132 [2022-03-17 17:01:13,962 INFO L87 Difference]: Start difference. First operand 89 states and 122 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-03-17 17:01:14,121 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:14,121 INFO L93 Difference]: Finished difference Result 130 states and 185 transitions. [2022-03-17 17:01:14,122 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-03-17 17:01:14,122 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) Word has length 75 [2022-03-17 17:01:14,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:14,125 INFO L225 Difference]: With dead ends: 130 [2022-03-17 17:01:14,125 INFO L226 Difference]: Without dead ends: 128 [2022-03-17 17:01:14,125 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 141 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 32 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-03-17 17:01:14,126 INFO L912 BasicCegarLoop]: 46 mSDtfsCounter, 39 mSDsluCounter, 190 mSDsCounter, 0 mSdLazyCounter, 174 mSolverCounterSat, 55 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 55 IncrementalHoareTripleChecker+Valid, 174 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:14,126 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [45 Valid, 236 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [55 Valid, 174 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:14,126 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2022-03-17 17:01:14,136 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 96. [2022-03-17 17:01:14,137 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 96 states, 51 states have (on average 1.1764705882352942) internal successors, (60), 53 states have internal predecessors, (60), 36 states have call successors, (36), 9 states have call predecessors, (36), 8 states have return successors, (34), 33 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-17 17:01:14,138 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 96 states to 96 states and 130 transitions. [2022-03-17 17:01:14,138 INFO L78 Accepts]: Start accepts. Automaton has 96 states and 130 transitions. Word has length 75 [2022-03-17 17:01:14,138 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:14,138 INFO L478 AbstractCegarLoop]: Abstraction has 96 states and 130 transitions. [2022-03-17 17:01:14,139 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 11 states have internal predecessors, (36), 6 states have call successors, (22), 2 states have call predecessors, (22), 2 states have return successors, (19), 6 states have call predecessors, (19), 6 states have call successors, (19) [2022-03-17 17:01:14,139 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states and 130 transitions. [2022-03-17 17:01:14,139 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-03-17 17:01:14,140 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:14,140 INFO L500 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:14,161 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:01:14,355 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:14,356 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:14,356 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:14,356 INFO L85 PathProgramCache]: Analyzing trace with hash -271689658, now seen corresponding path program 2 times [2022-03-17 17:01:14,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:14,356 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2030969975] [2022-03-17 17:01:14,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:14,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:14,364 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:14,364 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1788544492] [2022-03-17 17:01:14,364 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 17:01:14,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:14,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:14,365 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:01:14,366 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:01:14,410 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 17:01:14,411 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:14,412 INFO L263 TraceCheckSpWp]: Trace formula consists of 213 conjuncts, 37 conjunts are in the unsatisfiable core [2022-03-17 17:01:14,414 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:14,878 INFO L134 CoverageAnalysis]: Checked inductivity of 138 backedges. 18 proven. 24 refuted. 0 times theorem prover too weak. 96 trivial. 0 not checked. [2022-03-17 17:01:14,878 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:14,980 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:14,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2030969975] [2022-03-17 17:01:14,980 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:14,980 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1788544492] [2022-03-17 17:01:14,980 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1788544492] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:14,980 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:14,980 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12] total 12 [2022-03-17 17:01:14,980 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [287927807] [2022-03-17 17:01:14,980 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:14,981 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-17 17:01:14,981 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:14,981 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-17 17:01:14,981 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=168, Unknown=0, NotChecked=0, Total=210 [2022-03-17 17:01:14,981 INFO L87 Difference]: Start difference. First operand 96 states and 130 transitions. Second operand has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-03-17 17:01:15,182 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:15,183 INFO L93 Difference]: Finished difference Result 126 states and 167 transitions. [2022-03-17 17:01:15,183 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-17 17:01:15,183 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 80 [2022-03-17 17:01:15,183 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:15,184 INFO L225 Difference]: With dead ends: 126 [2022-03-17 17:01:15,184 INFO L226 Difference]: Without dead ends: 126 [2022-03-17 17:01:15,184 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 103 GetRequests, 85 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=68, Invalid=274, Unknown=0, NotChecked=0, Total=342 [2022-03-17 17:01:15,185 INFO L912 BasicCegarLoop]: 44 mSDtfsCounter, 35 mSDsluCounter, 264 mSDsCounter, 0 mSdLazyCounter, 248 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 275 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 248 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:15,185 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 308 Invalid, 275 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 248 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:15,185 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2022-03-17 17:01:15,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 123. [2022-03-17 17:01:15,189 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 67 states have (on average 1.164179104477612) internal successors, (78), 69 states have internal predecessors, (78), 44 states have call successors, (44), 12 states have call predecessors, (44), 11 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-17 17:01:15,189 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 164 transitions. [2022-03-17 17:01:15,189 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 164 transitions. Word has length 80 [2022-03-17 17:01:15,189 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:15,190 INFO L478 AbstractCegarLoop]: Abstraction has 123 states and 164 transitions. [2022-03-17 17:01:15,190 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-03-17 17:01:15,190 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 164 transitions. [2022-03-17 17:01:15,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 86 [2022-03-17 17:01:15,190 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:15,190 INFO L500 BasicCegarLoop]: trace histogram [8, 7, 7, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:15,209 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:01:15,403 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-03-17 17:01:15,404 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:15,404 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:15,404 INFO L85 PathProgramCache]: Analyzing trace with hash -1540307954, now seen corresponding path program 3 times [2022-03-17 17:01:15,404 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:15,404 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1311998765] [2022-03-17 17:01:15,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:15,404 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:15,412 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:15,413 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1248548790] [2022-03-17 17:01:15,413 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 17:01:15,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:15,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:15,415 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:01:15,416 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:01:15,451 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-17 17:01:15,452 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:15,453 INFO L263 TraceCheckSpWp]: Trace formula consists of 164 conjuncts, 36 conjunts are in the unsatisfiable core [2022-03-17 17:01:15,454 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:15,793 INFO L134 CoverageAnalysis]: Checked inductivity of 165 backedges. 31 proven. 8 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-03-17 17:01:15,793 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:15,859 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:15,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1311998765] [2022-03-17 17:01:15,859 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:15,859 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1248548790] [2022-03-17 17:01:15,859 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1248548790] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:15,859 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:15,859 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-17 17:01:15,859 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497070766] [2022-03-17 17:01:15,859 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:15,860 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-17 17:01:15,860 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:15,860 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-17 17:01:15,860 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-03-17 17:01:15,860 INFO L87 Difference]: Start difference. First operand 123 states and 164 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-17 17:01:16,011 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:16,012 INFO L93 Difference]: Finished difference Result 130 states and 170 transitions. [2022-03-17 17:01:16,012 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-17 17:01:16,013 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) Word has length 85 [2022-03-17 17:01:16,013 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:16,013 INFO L225 Difference]: With dead ends: 130 [2022-03-17 17:01:16,013 INFO L226 Difference]: Without dead ends: 130 [2022-03-17 17:01:16,014 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:01:16,014 INFO L912 BasicCegarLoop]: 39 mSDtfsCounter, 19 mSDsluCounter, 223 mSDsCounter, 0 mSdLazyCounter, 223 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 262 SdHoareTripleChecker+Invalid, 233 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 223 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:16,014 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 262 Invalid, 233 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 223 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:16,015 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-03-17 17:01:16,018 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 127. [2022-03-17 17:01:16,018 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 127 states, 70 states have (on average 1.1571428571428573) internal successors, (81), 72 states have internal predecessors, (81), 44 states have call successors, (44), 13 states have call predecessors, (44), 12 states have return successors, (42), 41 states have call predecessors, (42), 42 states have call successors, (42) [2022-03-17 17:01:16,018 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 127 states to 127 states and 167 transitions. [2022-03-17 17:01:16,019 INFO L78 Accepts]: Start accepts. Automaton has 127 states and 167 transitions. Word has length 85 [2022-03-17 17:01:16,019 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:16,019 INFO L478 AbstractCegarLoop]: Abstraction has 127 states and 167 transitions. [2022-03-17 17:01:16,019 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 4 states have call predecessors, (14), 4 states have call successors, (14) [2022-03-17 17:01:16,019 INFO L276 IsEmpty]: Start isEmpty. Operand 127 states and 167 transitions. [2022-03-17 17:01:16,020 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-17 17:01:16,020 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:16,020 INFO L500 BasicCegarLoop]: trace histogram [9, 8, 8, 6, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:16,039 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:01:16,235 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-17 17:01:16,235 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:16,236 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:16,236 INFO L85 PathProgramCache]: Analyzing trace with hash -757951041, now seen corresponding path program 1 times [2022-03-17 17:01:16,236 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:16,236 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1623262635] [2022-03-17 17:01:16,236 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:16,236 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:16,244 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:16,244 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [456720534] [2022-03-17 17:01:16,244 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:16,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:16,244 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:16,245 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:01:16,267 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:01:16,304 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:16,305 INFO L263 TraceCheckSpWp]: Trace formula consists of 233 conjuncts, 37 conjunts are in the unsatisfiable core [2022-03-17 17:01:16,307 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:16,686 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-17 17:01:16,686 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:17,029 INFO L134 CoverageAnalysis]: Checked inductivity of 196 backedges. 16 proven. 8 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2022-03-17 17:01:17,029 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:17,029 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1623262635] [2022-03-17 17:01:17,029 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:17,029 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [456720534] [2022-03-17 17:01:17,029 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [456720534] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:17,029 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:17,029 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2022-03-17 17:01:17,030 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [817181326] [2022-03-17 17:01:17,030 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:17,030 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-03-17 17:01:17,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:17,030 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-03-17 17:01:17,030 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-03-17 17:01:17,031 INFO L87 Difference]: Start difference. First operand 127 states and 167 transitions. Second operand has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-03-17 17:01:19,090 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:19,091 INFO L93 Difference]: Finished difference Result 210 states and 297 transitions. [2022-03-17 17:01:19,091 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2022-03-17 17:01:19,091 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) Word has length 91 [2022-03-17 17:01:19,091 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:19,092 INFO L225 Difference]: With dead ends: 210 [2022-03-17 17:01:19,092 INFO L226 Difference]: Without dead ends: 208 [2022-03-17 17:01:19,093 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 197 GetRequests, 168 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=178, Invalid=692, Unknown=0, NotChecked=0, Total=870 [2022-03-17 17:01:19,093 INFO L912 BasicCegarLoop]: 78 mSDtfsCounter, 57 mSDsluCounter, 400 mSDsCounter, 0 mSdLazyCounter, 438 mSolverCounterSat, 142 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 61 SdHoareTripleChecker+Valid, 478 SdHoareTripleChecker+Invalid, 580 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 438 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:19,093 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [61 Valid, 478 Invalid, 580 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 438 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2022-03-17 17:01:19,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 208 states. [2022-03-17 17:01:19,102 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 208 to 204. [2022-03-17 17:01:19,103 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 204 states, 107 states have (on average 1.1962616822429906) internal successors, (128), 108 states have internal predecessors, (128), 81 states have call successors, (81), 16 states have call predecessors, (81), 15 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2022-03-17 17:01:19,104 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 204 states to 204 states and 288 transitions. [2022-03-17 17:01:19,104 INFO L78 Accepts]: Start accepts. Automaton has 204 states and 288 transitions. Word has length 91 [2022-03-17 17:01:19,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:19,105 INFO L478 AbstractCegarLoop]: Abstraction has 204 states and 288 transitions. [2022-03-17 17:01:19,105 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 12 states have (on average 2.75) internal successors, (33), 13 states have internal predecessors, (33), 9 states have call successors, (28), 2 states have call predecessors, (28), 1 states have return successors, (25), 7 states have call predecessors, (25), 7 states have call successors, (25) [2022-03-17 17:01:19,105 INFO L276 IsEmpty]: Start isEmpty. Operand 204 states and 288 transitions. [2022-03-17 17:01:19,106 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-03-17 17:01:19,106 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:19,106 INFO L500 BasicCegarLoop]: trace histogram [11, 10, 10, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:19,123 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:01:19,319 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-17 17:01:19,320 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:19,320 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:19,320 INFO L85 PathProgramCache]: Analyzing trace with hash -1452951817, now seen corresponding path program 4 times [2022-03-17 17:01:19,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:19,320 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1084093081] [2022-03-17 17:01:19,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:19,320 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:19,329 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:19,329 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2015979848] [2022-03-17 17:01:19,329 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-17 17:01:19,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:19,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:19,332 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:01:19,333 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:01:19,373 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-17 17:01:19,373 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:19,374 INFO L263 TraceCheckSpWp]: Trace formula consists of 232 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-17 17:01:19,376 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:19,495 INFO L134 CoverageAnalysis]: Checked inductivity of 281 backedges. 101 proven. 0 refuted. 0 times theorem prover too weak. 180 trivial. 0 not checked. [2022-03-17 17:01:19,495 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-17 17:01:19,495 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:19,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1084093081] [2022-03-17 17:01:19,495 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:19,495 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2015979848] [2022-03-17 17:01:19,495 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2015979848] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-17 17:01:19,495 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-17 17:01:19,496 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-17 17:01:19,496 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2114252814] [2022-03-17 17:01:19,496 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-17 17:01:19,496 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-17 17:01:19,496 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:19,496 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-17 17:01:19,496 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-17 17:01:19,496 INFO L87 Difference]: Start difference. First operand 204 states and 288 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-03-17 17:01:19,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:19,541 INFO L93 Difference]: Finished difference Result 185 states and 250 transitions. [2022-03-17 17:01:19,541 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-17 17:01:19,541 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) Word has length 105 [2022-03-17 17:01:19,542 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:19,542 INFO L225 Difference]: With dead ends: 185 [2022-03-17 17:01:19,542 INFO L226 Difference]: Without dead ends: 185 [2022-03-17 17:01:19,543 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2022-03-17 17:01:19,543 INFO L912 BasicCegarLoop]: 56 mSDtfsCounter, 6 mSDsluCounter, 127 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 47 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:19,543 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 183 Invalid, 47 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-17 17:01:19,543 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 185 states. [2022-03-17 17:01:19,547 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 185 to 171. [2022-03-17 17:01:19,547 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 171 states, 90 states have (on average 1.1444444444444444) internal successors, (103), 91 states have internal predecessors, (103), 65 states have call successors, (65), 16 states have call predecessors, (65), 15 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-03-17 17:01:19,548 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 171 states to 171 states and 231 transitions. [2022-03-17 17:01:19,548 INFO L78 Accepts]: Start accepts. Automaton has 171 states and 231 transitions. Word has length 105 [2022-03-17 17:01:19,548 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:19,548 INFO L478 AbstractCegarLoop]: Abstraction has 171 states and 231 transitions. [2022-03-17 17:01:19,548 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 3 states have call predecessors, (17), 3 states have call successors, (17) [2022-03-17 17:01:19,548 INFO L276 IsEmpty]: Start isEmpty. Operand 171 states and 231 transitions. [2022-03-17 17:01:19,549 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 108 [2022-03-17 17:01:19,549 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:19,549 INFO L500 BasicCegarLoop]: trace histogram [12, 11, 11, 6, 6, 6, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:19,568 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:01:19,763 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2022-03-17 17:01:19,763 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:19,764 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:19,764 INFO L85 PathProgramCache]: Analyzing trace with hash 1708635976, now seen corresponding path program 1 times [2022-03-17 17:01:19,764 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:19,764 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1337811662] [2022-03-17 17:01:19,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:19,764 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:19,771 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:19,771 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1885493195] [2022-03-17 17:01:19,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:19,771 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:19,771 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:19,774 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:01:19,800 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:01:19,819 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-17 17:01:19,820 INFO L263 TraceCheckSpWp]: Trace formula consists of 264 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-17 17:01:19,822 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:20,006 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 122 proven. 23 refuted. 0 times theorem prover too weak. 175 trivial. 0 not checked. [2022-03-17 17:01:20,006 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:20,245 INFO L134 CoverageAnalysis]: Checked inductivity of 320 backedges. 32 proven. 23 refuted. 0 times theorem prover too weak. 265 trivial. 0 not checked. [2022-03-17 17:01:20,245 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:20,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1337811662] [2022-03-17 17:01:20,245 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:20,245 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1885493195] [2022-03-17 17:01:20,245 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1885493195] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:20,245 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:20,245 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2022-03-17 17:01:20,246 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [421340877] [2022-03-17 17:01:20,246 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:20,246 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-17 17:01:20,246 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:20,246 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-17 17:01:20,246 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=29, Invalid=127, Unknown=0, NotChecked=0, Total=156 [2022-03-17 17:01:20,246 INFO L87 Difference]: Start difference. First operand 171 states and 231 transitions. Second operand has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) [2022-03-17 17:01:20,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:20,531 INFO L93 Difference]: Finished difference Result 150 states and 196 transitions. [2022-03-17 17:01:20,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-17 17:01:20,531 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) Word has length 107 [2022-03-17 17:01:20,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:20,532 INFO L225 Difference]: With dead ends: 150 [2022-03-17 17:01:20,532 INFO L226 Difference]: Without dead ends: 144 [2022-03-17 17:01:20,532 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 225 GetRequests, 200 SyntacticMatches, 2 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=144, Invalid=456, Unknown=0, NotChecked=0, Total=600 [2022-03-17 17:01:20,533 INFO L912 BasicCegarLoop]: 53 mSDtfsCounter, 35 mSDsluCounter, 422 mSDsCounter, 0 mSdLazyCounter, 201 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 475 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 201 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:20,533 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 475 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 201 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:20,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2022-03-17 17:01:20,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 142. [2022-03-17 17:01:20,536 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 75 states have (on average 1.12) internal successors, (84), 76 states have internal predecessors, (84), 53 states have call successors, (53), 14 states have call predecessors, (53), 13 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-03-17 17:01:20,537 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 188 transitions. [2022-03-17 17:01:20,537 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 188 transitions. Word has length 107 [2022-03-17 17:01:20,537 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:20,537 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 188 transitions. [2022-03-17 17:01:20,537 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.769230769230769) internal successors, (36), 13 states have internal predecessors, (36), 8 states have call successors, (30), 2 states have call predecessors, (30), 3 states have return successors, (29), 8 states have call predecessors, (29), 8 states have call successors, (29) [2022-03-17 17:01:20,537 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 188 transitions. [2022-03-17 17:01:20,538 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-03-17 17:01:20,538 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:20,538 INFO L500 BasicCegarLoop]: trace histogram [15, 14, 14, 6, 6, 6, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:20,559 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:01:20,748 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-03-17 17:01:20,749 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:20,749 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:20,749 INFO L85 PathProgramCache]: Analyzing trace with hash 259955901, now seen corresponding path program 2 times [2022-03-17 17:01:20,749 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:20,749 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1393093522] [2022-03-17 17:01:20,749 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:20,749 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:20,757 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:20,757 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [714481206] [2022-03-17 17:01:20,757 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 17:01:20,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:20,758 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:20,762 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:01:20,765 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:01:20,814 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 17:01:20,814 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:20,815 INFO L263 TraceCheckSpWp]: Trace formula consists of 313 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-17 17:01:20,816 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:21,033 INFO L134 CoverageAnalysis]: Checked inductivity of 489 backedges. 154 proven. 18 refuted. 0 times theorem prover too weak. 317 trivial. 0 not checked. [2022-03-17 17:01:21,033 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:21,267 INFO L134 CoverageAnalysis]: Checked inductivity of 489 backedges. 48 proven. 32 refuted. 0 times theorem prover too weak. 409 trivial. 0 not checked. [2022-03-17 17:01:21,267 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:21,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1393093522] [2022-03-17 17:01:21,267 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:21,267 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [714481206] [2022-03-17 17:01:21,267 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [714481206] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:21,267 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:21,267 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-17 17:01:21,268 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890195103] [2022-03-17 17:01:21,268 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:21,268 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-17 17:01:21,268 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:21,268 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-17 17:01:21,268 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2022-03-17 17:01:21,269 INFO L87 Difference]: Start difference. First operand 142 states and 188 transitions. Second operand has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2022-03-17 17:01:21,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:21,530 INFO L93 Difference]: Finished difference Result 146 states and 191 transitions. [2022-03-17 17:01:21,530 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-03-17 17:01:21,530 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) Word has length 127 [2022-03-17 17:01:21,530 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:21,531 INFO L225 Difference]: With dead ends: 146 [2022-03-17 17:01:21,531 INFO L226 Difference]: Without dead ends: 146 [2022-03-17 17:01:21,531 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 264 GetRequests, 238 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 90 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=151, Invalid=551, Unknown=0, NotChecked=0, Total=702 [2022-03-17 17:01:21,532 INFO L912 BasicCegarLoop]: 55 mSDtfsCounter, 41 mSDsluCounter, 387 mSDsCounter, 0 mSdLazyCounter, 242 mSolverCounterSat, 81 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 442 SdHoareTripleChecker+Invalid, 323 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 81 IncrementalHoareTripleChecker+Valid, 242 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:21,532 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 442 Invalid, 323 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [81 Valid, 242 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:21,532 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2022-03-17 17:01:21,535 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 142. [2022-03-17 17:01:21,535 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 75 states have (on average 1.0933333333333333) internal successors, (82), 76 states have internal predecessors, (82), 53 states have call successors, (53), 14 states have call predecessors, (53), 13 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-03-17 17:01:21,535 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 186 transitions. [2022-03-17 17:01:21,535 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 186 transitions. Word has length 127 [2022-03-17 17:01:21,536 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:21,536 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 186 transitions. [2022-03-17 17:01:21,536 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.8125) internal successors, (45), 14 states have internal predecessors, (45), 9 states have call successors, (35), 2 states have call predecessors, (35), 3 states have return successors, (34), 9 states have call predecessors, (34), 9 states have call successors, (34) [2022-03-17 17:01:21,536 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 186 transitions. [2022-03-17 17:01:21,537 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 139 [2022-03-17 17:01:21,537 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:21,537 INFO L500 BasicCegarLoop]: trace histogram [17, 16, 16, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:21,555 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:01:21,751 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-03-17 17:01:21,751 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:21,752 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:21,752 INFO L85 PathProgramCache]: Analyzing trace with hash -928796440, now seen corresponding path program 2 times [2022-03-17 17:01:21,752 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:21,752 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1495972846] [2022-03-17 17:01:21,752 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:21,752 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:21,759 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:21,759 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2121073509] [2022-03-17 17:01:21,759 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-17 17:01:21,759 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:21,759 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:21,760 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:01:21,761 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:01:21,820 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-17 17:01:21,821 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:21,822 INFO L263 TraceCheckSpWp]: Trace formula consists of 333 conjuncts, 96 conjunts are in the unsatisfiable core [2022-03-17 17:01:21,825 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:23,066 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 119 proven. 151 refuted. 0 times theorem prover too weak. 345 trivial. 0 not checked. [2022-03-17 17:01:23,066 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:23,756 INFO L134 CoverageAnalysis]: Checked inductivity of 615 backedges. 154 proven. 12 refuted. 0 times theorem prover too weak. 449 trivial. 0 not checked. [2022-03-17 17:01:23,757 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:23,757 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1495972846] [2022-03-17 17:01:23,757 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:23,757 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2121073509] [2022-03-17 17:01:23,757 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2121073509] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:23,757 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:23,757 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 12] total 28 [2022-03-17 17:01:23,757 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1631905668] [2022-03-17 17:01:23,757 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:23,758 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2022-03-17 17:01:23,758 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:23,758 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2022-03-17 17:01:23,758 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=620, Unknown=0, NotChecked=0, Total=756 [2022-03-17 17:01:23,758 INFO L87 Difference]: Start difference. First operand 142 states and 186 transitions. Second operand has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) [2022-03-17 17:01:25,354 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:25,354 INFO L93 Difference]: Finished difference Result 168 states and 215 transitions. [2022-03-17 17:01:25,354 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2022-03-17 17:01:25,354 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) Word has length 138 [2022-03-17 17:01:25,355 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:25,355 INFO L225 Difference]: With dead ends: 168 [2022-03-17 17:01:25,355 INFO L226 Difference]: Without dead ends: 159 [2022-03-17 17:01:25,357 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 289 GetRequests, 246 SyntacticMatches, 3 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 422 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=335, Invalid=1387, Unknown=0, NotChecked=0, Total=1722 [2022-03-17 17:01:25,358 INFO L912 BasicCegarLoop]: 41 mSDtfsCounter, 86 mSDsluCounter, 475 mSDsCounter, 0 mSdLazyCounter, 847 mSolverCounterSat, 190 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 516 SdHoareTripleChecker+Invalid, 1037 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 190 IncrementalHoareTripleChecker+Valid, 847 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:25,358 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [94 Valid, 516 Invalid, 1037 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [190 Valid, 847 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2022-03-17 17:01:25,358 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 159 states. [2022-03-17 17:01:25,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 159 to 146. [2022-03-17 17:01:25,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 78 states have (on average 1.064102564102564) internal successors, (83), 78 states have internal predecessors, (83), 52 states have call successors, (52), 16 states have call predecessors, (52), 15 states have return successors, (51), 51 states have call predecessors, (51), 51 states have call successors, (51) [2022-03-17 17:01:25,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 186 transitions. [2022-03-17 17:01:25,362 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 186 transitions. Word has length 138 [2022-03-17 17:01:25,362 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:25,362 INFO L478 AbstractCegarLoop]: Abstraction has 146 states and 186 transitions. [2022-03-17 17:01:25,362 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 24 states have (on average 2.0416666666666665) internal successors, (49), 21 states have internal predecessors, (49), 14 states have call successors, (37), 2 states have call predecessors, (37), 3 states have return successors, (36), 12 states have call predecessors, (36), 12 states have call successors, (36) [2022-03-17 17:01:25,362 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 186 transitions. [2022-03-17 17:01:25,363 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2022-03-17 17:01:25,363 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:25,363 INFO L500 BasicCegarLoop]: trace histogram [19, 18, 18, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:25,385 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2022-03-17 17:01:25,577 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:25,578 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:25,578 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:25,578 INFO L85 PathProgramCache]: Analyzing trace with hash -1469599656, now seen corresponding path program 3 times [2022-03-17 17:01:25,578 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:25,578 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1799758934] [2022-03-17 17:01:25,578 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:25,578 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:25,585 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:25,585 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [854759682] [2022-03-17 17:01:25,585 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-17 17:01:25,585 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:25,585 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:25,586 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:01:25,587 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2022-03-17 17:01:25,646 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-17 17:01:25,646 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:25,647 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 52 conjunts are in the unsatisfiable core [2022-03-17 17:01:25,650 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:26,455 INFO L134 CoverageAnalysis]: Checked inductivity of 762 backedges. 118 proven. 59 refuted. 0 times theorem prover too weak. 585 trivial. 0 not checked. [2022-03-17 17:01:26,455 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:26,661 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-17 17:01:26,812 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:26,812 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1799758934] [2022-03-17 17:01:26,812 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:26,812 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [854759682] [2022-03-17 17:01:26,812 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [854759682] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-17 17:01:26,812 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-17 17:01:26,812 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2022-03-17 17:01:26,812 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [829927663] [2022-03-17 17:01:26,812 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:26,813 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-17 17:01:26,813 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:26,813 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-17 17:01:26,813 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=252, Unknown=0, NotChecked=0, Total=306 [2022-03-17 17:01:26,813 INFO L87 Difference]: Start difference. First operand 146 states and 186 transitions. Second operand has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-17 17:01:27,065 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:27,065 INFO L93 Difference]: Finished difference Result 180 states and 230 transitions. [2022-03-17 17:01:27,065 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-17 17:01:27,066 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) Word has length 146 [2022-03-17 17:01:27,066 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:27,067 INFO L225 Difference]: With dead ends: 180 [2022-03-17 17:01:27,067 INFO L226 Difference]: Without dead ends: 180 [2022-03-17 17:01:27,067 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 162 SyntacticMatches, 2 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 76 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=80, Invalid=382, Unknown=0, NotChecked=0, Total=462 [2022-03-17 17:01:27,067 INFO L912 BasicCegarLoop]: 29 mSDtfsCounter, 33 mSDsluCounter, 209 mSDsCounter, 0 mSdLazyCounter, 336 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 357 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 336 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:27,067 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 238 Invalid, 357 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 336 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 17:01:27,068 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 180 states. [2022-03-17 17:01:27,070 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 180 to 179. [2022-03-17 17:01:27,071 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 179 states, 96 states have (on average 1.0625) internal successors, (102), 96 states have internal predecessors, (102), 64 states have call successors, (64), 19 states have call predecessors, (64), 18 states have return successors, (63), 63 states have call predecessors, (63), 63 states have call successors, (63) [2022-03-17 17:01:27,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 179 states to 179 states and 229 transitions. [2022-03-17 17:01:27,071 INFO L78 Accepts]: Start accepts. Automaton has 179 states and 229 transitions. Word has length 146 [2022-03-17 17:01:27,072 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:27,072 INFO L478 AbstractCegarLoop]: Abstraction has 179 states and 229 transitions. [2022-03-17 17:01:27,072 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.4166666666666665) internal successors, (29), 11 states have internal predecessors, (29), 6 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 6 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-17 17:01:27,072 INFO L276 IsEmpty]: Start isEmpty. Operand 179 states and 229 transitions. [2022-03-17 17:01:27,073 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 152 [2022-03-17 17:01:27,073 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:27,073 INFO L500 BasicCegarLoop]: trace histogram [20, 19, 19, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:27,089 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2022-03-17 17:01:27,287 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-03-17 17:01:27,287 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:27,287 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:27,287 INFO L85 PathProgramCache]: Analyzing trace with hash -1402624196, now seen corresponding path program 4 times [2022-03-17 17:01:27,287 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:27,287 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1499149563] [2022-03-17 17:01:27,287 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:27,288 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:27,297 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:27,297 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [631874321] [2022-03-17 17:01:27,297 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-03-17 17:01:27,297 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:27,297 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:27,298 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:01:27,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2022-03-17 17:01:27,344 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-03-17 17:01:27,344 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:27,345 INFO L263 TraceCheckSpWp]: Trace formula consists of 309 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-17 17:01:27,347 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:27,576 INFO L134 CoverageAnalysis]: Checked inductivity of 840 backedges. 246 proven. 51 refuted. 0 times theorem prover too weak. 543 trivial. 0 not checked. [2022-03-17 17:01:27,577 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:27,886 INFO L134 CoverageAnalysis]: Checked inductivity of 840 backedges. 60 proven. 51 refuted. 0 times theorem prover too weak. 729 trivial. 0 not checked. [2022-03-17 17:01:27,887 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:27,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1499149563] [2022-03-17 17:01:27,887 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:27,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [631874321] [2022-03-17 17:01:27,887 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [631874321] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:27,887 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:27,887 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2022-03-17 17:01:27,887 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2147124724] [2022-03-17 17:01:27,887 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:27,889 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-17 17:01:27,889 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:27,889 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-17 17:01:27,889 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2022-03-17 17:01:27,889 INFO L87 Difference]: Start difference. First operand 179 states and 229 transitions. Second operand has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) [2022-03-17 17:01:28,086 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:28,087 INFO L93 Difference]: Finished difference Result 150 states and 188 transitions. [2022-03-17 17:01:28,087 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-17 17:01:28,087 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) Word has length 151 [2022-03-17 17:01:28,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:28,088 INFO L225 Difference]: With dead ends: 150 [2022-03-17 17:01:28,088 INFO L226 Difference]: Without dead ends: 124 [2022-03-17 17:01:28,088 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 310 GetRequests, 287 SyntacticMatches, 1 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 43 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=104, Invalid=448, Unknown=0, NotChecked=0, Total=552 [2022-03-17 17:01:28,089 INFO L912 BasicCegarLoop]: 62 mSDtfsCounter, 28 mSDsluCounter, 339 mSDsCounter, 0 mSdLazyCounter, 158 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 401 SdHoareTripleChecker+Invalid, 225 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 158 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:28,089 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [32 Valid, 401 Invalid, 225 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 158 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-17 17:01:28,089 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2022-03-17 17:01:28,091 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 124. [2022-03-17 17:01:28,092 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 69 states have (on average 1.0434782608695652) internal successors, (72), 69 states have internal predecessors, (72), 40 states have call successors, (40), 15 states have call predecessors, (40), 14 states have return successors, (39), 39 states have call predecessors, (39), 39 states have call successors, (39) [2022-03-17 17:01:28,092 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 151 transitions. [2022-03-17 17:01:28,092 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 151 transitions. Word has length 151 [2022-03-17 17:01:28,092 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:28,092 INFO L478 AbstractCegarLoop]: Abstraction has 124 states and 151 transitions. [2022-03-17 17:01:28,093 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.933333333333333) internal successors, (44), 15 states have internal predecessors, (44), 12 states have call successors, (46), 2 states have call predecessors, (46), 3 states have return successors, (45), 12 states have call predecessors, (45), 12 states have call successors, (45) [2022-03-17 17:01:28,093 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 151 transitions. [2022-03-17 17:01:28,093 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 172 [2022-03-17 17:01:28,094 INFO L492 BasicCegarLoop]: Found error trace [2022-03-17 17:01:28,094 INFO L500 BasicCegarLoop]: trace histogram [23, 22, 22, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:28,112 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Ended with exit code 0 [2022-03-17 17:01:28,309 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2022-03-17 17:01:28,309 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-17 17:01:28,310 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-17 17:01:28,310 INFO L85 PathProgramCache]: Analyzing trace with hash 477503177, now seen corresponding path program 5 times [2022-03-17 17:01:28,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-17 17:01:28,310 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [588215518] [2022-03-17 17:01:28,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-17 17:01:28,310 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-17 17:01:28,317 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-17 17:01:28,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [969486874] [2022-03-17 17:01:28,317 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2022-03-17 17:01:28,317 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-17 17:01:28,317 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-17 17:01:28,326 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-17 17:01:28,327 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2022-03-17 17:01:28,383 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2022-03-17 17:01:28,383 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-17 17:01:28,384 INFO L263 TraceCheckSpWp]: Trace formula consists of 331 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-17 17:01:28,386 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-17 17:01:28,677 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 234 proven. 68 refuted. 0 times theorem prover too weak. 813 trivial. 0 not checked. [2022-03-17 17:01:28,677 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-17 17:01:29,120 INFO L134 CoverageAnalysis]: Checked inductivity of 1115 backedges. 84 proven. 62 refuted. 0 times theorem prover too weak. 969 trivial. 0 not checked. [2022-03-17 17:01:29,120 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-17 17:01:29,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [588215518] [2022-03-17 17:01:29,120 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-17 17:01:29,120 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [969486874] [2022-03-17 17:01:29,120 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [969486874] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-17 17:01:29,120 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-17 17:01:29,120 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 12] total 20 [2022-03-17 17:01:29,121 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [999059543] [2022-03-17 17:01:29,121 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-17 17:01:29,121 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-17 17:01:29,121 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-17 17:01:29,121 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-17 17:01:29,121 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=61, Invalid=319, Unknown=0, NotChecked=0, Total=380 [2022-03-17 17:01:29,121 INFO L87 Difference]: Start difference. First operand 124 states and 151 transitions. Second operand has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) [2022-03-17 17:01:29,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-17 17:01:29,429 INFO L93 Difference]: Finished difference Result 93 states and 108 transitions. [2022-03-17 17:01:29,429 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-17 17:01:29,430 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) Word has length 171 [2022-03-17 17:01:29,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-17 17:01:29,430 INFO L225 Difference]: With dead ends: 93 [2022-03-17 17:01:29,430 INFO L226 Difference]: Without dead ends: 0 [2022-03-17 17:01:29,430 INFO L911 BasicCegarLoop]: 0 DeclaredPredicates, 350 GetRequests, 323 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=168, Invalid=644, Unknown=0, NotChecked=0, Total=812 [2022-03-17 17:01:29,431 INFO L912 BasicCegarLoop]: 65 mSDtfsCounter, 27 mSDsluCounter, 493 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 138 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 558 SdHoareTripleChecker+Invalid, 367 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 138 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-17 17:01:29,431 INFO L913 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 558 Invalid, 367 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [138 Valid, 229 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-17 17:01:29,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-03-17 17:01:29,431 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-03-17 17:01:29,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-17 17:01:29,431 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-03-17 17:01:29,431 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 171 [2022-03-17 17:01:29,431 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-17 17:01:29,432 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-03-17 17:01:29,432 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 20 states have (on average 2.8) internal successors, (56), 18 states have internal predecessors, (56), 15 states have call successors, (57), 2 states have call predecessors, (57), 3 states have return successors, (56), 15 states have call predecessors, (56), 15 states have call successors, (56) [2022-03-17 17:01:29,432 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-03-17 17:01:29,432 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-03-17 17:01:29,434 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-17 17:01:29,453 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2022-03-17 17:01:29,639 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2022-03-17 17:01:29,642 INFO L718 BasicCegarLoop]: Path program histogram: [5, 4, 2, 1, 1, 1, 1, 1, 1, 1] [2022-03-17 17:01:29,642 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-17 17:01:29,644 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 17.03 05:01:29 BasicIcfg [2022-03-17 17:01:29,644 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-17 17:01:29,644 INFO L158 Benchmark]: Toolchain (without parser) took 20849.18ms. Allocated memory was 197.1MB in the beginning and 289.4MB in the end (delta: 92.3MB). Free memory was 145.7MB in the beginning and 172.1MB in the end (delta: -26.4MB). Peak memory consumption was 66.4MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,644 INFO L158 Benchmark]: CDTParser took 0.09ms. Allocated memory is still 197.1MB. Free memory was 162.2MB in the beginning and 162.1MB in the end (delta: 68.9kB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-17 17:01:29,645 INFO L158 Benchmark]: CACSL2BoogieTranslator took 172.23ms. Allocated memory was 197.1MB in the beginning and 241.2MB in the end (delta: 44.0MB). Free memory was 145.5MB in the beginning and 215.7MB in the end (delta: -70.1MB). Peak memory consumption was 9.1MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,645 INFO L158 Benchmark]: Boogie Preprocessor took 21.50ms. Allocated memory is still 241.2MB. Free memory was 215.7MB in the beginning and 214.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,645 INFO L158 Benchmark]: RCFGBuilder took 231.71ms. Allocated memory is still 241.2MB. Free memory was 214.1MB in the beginning and 201.5MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,645 INFO L158 Benchmark]: IcfgTransformer took 19.53ms. Allocated memory is still 241.2MB. Free memory was 201.5MB in the beginning and 200.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,645 INFO L158 Benchmark]: TraceAbstraction took 20392.53ms. Allocated memory was 241.2MB in the beginning and 289.4MB in the end (delta: 48.2MB). Free memory was 199.9MB in the beginning and 172.1MB in the end (delta: 27.8MB). Peak memory consumption was 77.6MB. Max. memory is 8.0GB. [2022-03-17 17:01:29,646 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.09ms. Allocated memory is still 197.1MB. Free memory was 162.2MB in the beginning and 162.1MB in the end (delta: 68.9kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 172.23ms. Allocated memory was 197.1MB in the beginning and 241.2MB in the end (delta: 44.0MB). Free memory was 145.5MB in the beginning and 215.7MB in the end (delta: -70.1MB). Peak memory consumption was 9.1MB. Max. memory is 8.0GB. * Boogie Preprocessor took 21.50ms. Allocated memory is still 241.2MB. Free memory was 215.7MB in the beginning and 214.1MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 231.71ms. Allocated memory is still 241.2MB. Free memory was 214.1MB in the beginning and 201.5MB in the end (delta: 12.6MB). Peak memory consumption was 12.6MB. Max. memory is 8.0GB. * IcfgTransformer took 19.53ms. Allocated memory is still 241.2MB. Free memory was 201.5MB in the beginning and 200.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 20392.53ms. Allocated memory was 241.2MB in the beginning and 289.4MB in the end (delta: 48.2MB). Free memory was 199.9MB in the beginning and 172.1MB in the end (delta: 27.8MB). Peak memory consumption was 77.6MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 40 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 20.3s, OverallIterations: 18, TraceHistogramMax: 23, PathProgramHistogramMax: 5, EmptinessCheckTime: 0.0s, AutomataDifference: 6.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 625 SdHoareTripleChecker+Valid, 4.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 532 mSDsluCounter, 5331 SdHoareTripleChecker+Invalid, 4.1s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 4474 mSDsCounter, 888 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3695 IncrementalHoareTripleChecker+Invalid, 4583 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 888 mSolverCounterUnsat, 857 mSDtfsCounter, 3695 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2853 GetRequests, 2538 SyntacticMatches, 19 SemanticMatches, 296 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1023 ImplicationChecksByTransitivity, 3.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=204occurred in iteration=11, InterpolantAutomatonStates: 201, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 18 MinimizatonAttempts, 95 StatesRemovedByMinimization, 14 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 9.1s InterpolantComputationTime, 1642 NumberOfCodeBlocks, 1520 NumberOfCodeBlocksAsserted, 35 NumberOfCheckSat, 2686 ConstructedInterpolants, 0 QuantifiedInterpolants, 9120 SizeOfPredicates, 113 NumberOfNonLiveVariables, 3743 ConjunctsInSsa, 435 ConjunctsInUnsatCore, 29 InterpolantComputations, 4 PerfectInterpolantSequences, 8794/9490 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2022-03-17 17:01:29,663 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...