/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/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 10:22:39,150 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 10:22:39,152 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 10:22:39,192 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 10:22:39,192 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 10:22:39,193 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 10:22:39,194 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 10:22:39,195 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 10:22:39,197 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 10:22:39,198 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 10:22:39,198 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 10:22:39,199 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 10:22:39,200 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 10:22:39,200 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 10:22:39,201 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 10:22:39,202 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 10:22:39,203 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 10:22:39,203 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 10:22:39,205 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 10:22:39,206 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 10:22:39,207 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 10:22:39,208 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 10:22:39,209 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 10:22:39,210 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 10:22:39,211 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 10:22:39,213 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 10:22:39,213 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 10:22:39,213 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 10:22:39,214 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 10:22:39,214 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 10:22:39,215 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 10:22:39,215 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 10:22:39,216 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 10:22:39,216 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 10:22:39,217 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 10:22:39,217 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 10:22:39,218 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 10:22:39,218 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 10:22:39,218 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 10:22:39,219 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 10:22:39,219 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 10:22:39,220 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 10:22:39,221 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-03-20 10:22:39,246 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 10:22:39,247 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 10:22:39,249 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-20 10:22:39,249 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-20 10:22:39,251 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-20 10:22:39,251 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-20 10:22:39,251 INFO L138 SettingsManager]: * Use SBE=true [2022-03-20 10:22:39,251 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 10:22:39,251 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 10:22:39,252 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 10:22:39,252 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 10:22:39,252 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 10:22:39,253 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 10:22:39,253 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 10:22:39,253 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-20 10:22:39,254 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-20 10:22:39,255 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 10:22:39,255 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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-20 10:22:39,407 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 10:22:39,437 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 10:22:39,439 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 10:22:39,440 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 10:22:39,440 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 10:22:39,441 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_valuebound50.c [2022-03-20 10:22:39,494 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aee762185/b6232c8b1d4b4180948ff41b2ae9f991/FLAG5e389cfc2 [2022-03-20 10:22:39,845 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 10:22:39,846 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd3-ll_valuebound50.c [2022-03-20 10:22:39,849 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aee762185/b6232c8b1d4b4180948ff41b2ae9f991/FLAG5e389cfc2 [2022-03-20 10:22:39,859 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/aee762185/b6232c8b1d4b4180948ff41b2ae9f991 [2022-03-20 10:22:39,860 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 10:22:39,861 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 10:22:39,862 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 10:22:39,862 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 10:22:39,873 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 10:22:39,873 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 10:22:39" (1/1) ... [2022-03-20 10:22:39,874 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@57bcdc0f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:39, skipping insertion in model container [2022-03-20 10:22:39,874 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 10:22:39" (1/1) ... [2022-03-20 10:22:39,882 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 10:22:39,894 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 10:22:40,033 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/egcd3-ll_valuebound50.c[490,503] [2022-03-20 10:22:40,051 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 10:22:40,056 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 10:22:40,064 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/egcd3-ll_valuebound50.c[490,503] [2022-03-20 10:22:40,069 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 10:22:40,077 INFO L208 MainTranslator]: Completed translation [2022-03-20 10:22:40,077 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40 WrapperNode [2022-03-20 10:22:40,077 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 10:22:40,078 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 10:22:40,078 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 10:22:40,078 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 10:22:40,085 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,086 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,090 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,090 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,092 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,095 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,096 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,097 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 10:22:40,097 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 10:22:40,097 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 10:22:40,097 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 10:22:40,098 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,103 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 10:22:40,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:40,135 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-20 10:22:40,137 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-20 10:22:40,170 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 10:22:40,170 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 10:22:40,170 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 10:22:40,171 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 10:22:40,171 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 10:22:40,171 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 10:22:40,171 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 10:22:40,172 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 10:22:40,172 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 10:22:40,172 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 10:22:40,172 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-20 10:22:40,172 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 10:22:40,173 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 10:22:40,216 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 10:22:40,217 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 10:22:40,313 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 10:22:40,317 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 10:22:40,317 INFO L299 CfgBuilder]: Removed 3 assume(true) statements. [2022-03-20 10:22:40,318 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:22:40 BoogieIcfgContainer [2022-03-20 10:22:40,319 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 10:22:40,319 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 10:22:40,319 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 10:22:40,320 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 10:22:40,322 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:22:40" (1/1) ... [2022-03-20 10:22:40,323 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-03-20 10:22:40,334 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 10:22:40 BasicIcfg [2022-03-20 10:22:40,334 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 10:22:40,335 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 10:22:40,335 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 10:22:40,337 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 10:22:40,337 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 10:22:39" (1/4) ... [2022-03-20 10:22:40,338 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67323b83 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 10:22:40, skipping insertion in model container [2022-03-20 10:22:40,338 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 10:22:40" (2/4) ... [2022-03-20 10:22:40,338 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67323b83 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 10:22:40, skipping insertion in model container [2022-03-20 10:22:40,338 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 10:22:40" (3/4) ... [2022-03-20 10:22:40,338 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@67323b83 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 10:22:40, skipping insertion in model container [2022-03-20 10:22:40,338 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 10:22:40" (4/4) ... [2022-03-20 10:22:40,339 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd3-ll_valuebound50.cqvasr [2022-03-20 10:22:40,342 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-20 10:22:40,342 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 10:22:40,369 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 10:22:40,374 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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-20 10:22:40,374 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 10:22:40,383 INFO L276 IsEmpty]: Start isEmpty. Operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-03-20 10:22:40,387 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-03-20 10:22:40,387 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:40,387 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:22:40,388 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:40,391 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:40,391 INFO L85 PathProgramCache]: Analyzing trace with hash 958536290, now seen corresponding path program 1 times [2022-03-20 10:22:40,397 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:40,398 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1740176620] [2022-03-20 10:22:40,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:40,398 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:40,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,498 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 10:22:40,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,507 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 10:22:40,509 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,513 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-03-20 10:22:40,515 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,519 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-03-20 10:22:40,520 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,524 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-03-20 10:22:40,525 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,530 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:40,530 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:40,530 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1740176620] [2022-03-20 10:22:40,531 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1740176620] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:40,531 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:40,531 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 10:22:40,532 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2027876145] [2022-03-20 10:22:40,532 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:40,535 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 10:22:40,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:40,553 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 10:22:40,554 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 10:22:40,555 INFO L87 Difference]: Start difference. First operand has 40 states, 23 states have (on average 1.5217391304347827) internal successors, (35), 24 states have internal predecessors, (35), 11 states have call successors, (11), 4 states have call predecessors, (11), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:22:40,611 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:40,611 INFO L93 Difference]: Finished difference Result 73 states and 115 transitions. [2022-03-20 10:22:40,612 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 10:22:40,613 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-03-20 10:22:40,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:40,618 INFO L225 Difference]: With dead ends: 73 [2022-03-20 10:22:40,618 INFO L226 Difference]: Without dead ends: 35 [2022-03-20 10:22:40,620 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 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-20 10:22:40,625 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 24 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 21 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:40,631 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 43 Invalid, 21 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:40,644 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-20 10:22:40,670 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-03-20 10:22:40,671 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 10:22:40,674 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 44 transitions. [2022-03-20 10:22:40,675 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 44 transitions. Word has length 33 [2022-03-20 10:22:40,676 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:40,676 INFO L478 AbstractCegarLoop]: Abstraction has 35 states and 44 transitions. [2022-03-20 10:22:40,677 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, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:22:40,677 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 44 transitions. [2022-03-20 10:22:40,679 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-03-20 10:22:40,679 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:40,679 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:22:40,679 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 10:22:40,680 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:40,684 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:40,684 INFO L85 PathProgramCache]: Analyzing trace with hash 641145651, now seen corresponding path program 1 times [2022-03-20 10:22:40,684 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:40,684 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [483388865] [2022-03-20 10:22:40,685 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:40,685 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:40,725 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:40,725 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1760883629] [2022-03-20 10:22:40,725 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:40,725 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:40,726 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:40,742 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-20 10:22:40,790 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-20 10:22:40,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:40,818 INFO L263 TraceCheckSpWp]: Trace formula consists of 107 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 10:22:40,822 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:40,993 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-20 10:22:40,993 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:22:40,993 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:40,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [483388865] [2022-03-20 10:22:40,994 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:40,994 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1760883629] [2022-03-20 10:22:40,994 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1760883629] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:40,994 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:40,994 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 10:22:40,995 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [605378396] [2022-03-20 10:22:40,995 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:40,995 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 10:22:40,996 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:40,996 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 10:22:40,996 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:22:40,996 INFO L87 Difference]: Start difference. First operand 35 states and 44 transitions. Second operand has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:41,050 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:41,050 INFO L93 Difference]: Finished difference Result 54 states and 69 transitions. [2022-03-20 10:22:41,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 10:22:41,051 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) Word has length 34 [2022-03-20 10:22:41,051 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:41,053 INFO L225 Difference]: With dead ends: 54 [2022-03-20 10:22:41,053 INFO L226 Difference]: Without dead ends: 47 [2022-03-20 10:22:41,053 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 10:22:41,054 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 31 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 54 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 63 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 54 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:41,055 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 155 Invalid, 63 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:41,058 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-03-20 10:22:41,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 37. [2022-03-20 10:22:41,073 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 11 states have call successors, (11), 4 states have call predecessors, (11), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 10:22:41,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-03-20 10:22:41,074 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 34 [2022-03-20 10:22:41,074 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:41,075 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-03-20 10:22:41,075 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 5 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:41,075 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-03-20 10:22:41,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2022-03-20 10:22:41,076 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:41,076 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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-20 10:22:41,094 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-20 10:22:41,291 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-20 10:22:41,292 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:41,293 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:41,293 INFO L85 PathProgramCache]: Analyzing trace with hash 283168444, now seen corresponding path program 1 times [2022-03-20 10:22:41,293 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:41,293 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1789673351] [2022-03-20 10:22:41,293 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:41,293 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:41,304 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:41,305 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1660641362] [2022-03-20 10:22:41,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:41,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:41,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:41,306 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-20 10:22:41,307 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-20 10:22:41,346 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:41,348 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 19 conjunts are in the unsatisfiable core [2022-03-20 10:22:41,349 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:41,545 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:22:41,546 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:41,673 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:41,673 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:41,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1789673351] [2022-03-20 10:22:41,673 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:41,673 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1660641362] [2022-03-20 10:22:41,673 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1660641362] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 10:22:41,673 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 10:22:41,674 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-03-20 10:22:41,674 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [684457807] [2022-03-20 10:22:41,674 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:41,674 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:41,674 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:41,675 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:41,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-03-20 10:22:41,675 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:41,704 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:41,704 INFO L93 Difference]: Finished difference Result 53 states and 67 transitions. [2022-03-20 10:22:41,704 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:22:41,704 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 37 [2022-03-20 10:22:41,705 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:41,705 INFO L225 Difference]: With dead ends: 53 [2022-03-20 10:22:41,705 INFO L226 Difference]: Without dead ends: 51 [2022-03-20 10:22:41,706 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 74 GetRequests, 64 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-03-20 10:22:41,706 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 9 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 26 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 161 SdHoareTripleChecker+Invalid, 26 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 26 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:41,707 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 161 Invalid, 26 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 26 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:41,707 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2022-03-20 10:22:41,712 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 50. [2022-03-20 10:22:41,712 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 50 states, 30 states have (on average 1.2) internal successors, (36), 31 states have internal predecessors, (36), 15 states have call successors, (15), 5 states have call predecessors, (15), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 10:22:41,713 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 50 states to 50 states and 64 transitions. [2022-03-20 10:22:41,713 INFO L78 Accepts]: Start accepts. Automaton has 50 states and 64 transitions. Word has length 37 [2022-03-20 10:22:41,713 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:41,713 INFO L478 AbstractCegarLoop]: Abstraction has 50 states and 64 transitions. [2022-03-20 10:22:41,713 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:41,714 INFO L276 IsEmpty]: Start isEmpty. Operand 50 states and 64 transitions. [2022-03-20 10:22:41,714 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-03-20 10:22:41,714 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:41,714 INFO L499 BasicCegarLoop]: trace histogram [4, 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] [2022-03-20 10:22:41,737 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-03-20 10:22:41,927 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-20 10:22:41,928 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:41,928 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:41,928 INFO L85 PathProgramCache]: Analyzing trace with hash 656144812, now seen corresponding path program 1 times [2022-03-20 10:22:41,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:41,928 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [294835525] [2022-03-20 10:22:41,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:41,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:41,938 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:41,938 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [704319491] [2022-03-20 10:22:41,938 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:41,938 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:41,939 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:41,964 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-20 10:22:41,977 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-20 10:22:42,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:42,011 INFO L263 TraceCheckSpWp]: Trace formula consists of 129 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 10:22:42,012 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:42,102 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-20 10:22:42,102 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:42,212 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 5 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-20 10:22:42,212 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:42,212 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [294835525] [2022-03-20 10:22:42,213 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:42,213 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [704319491] [2022-03-20 10:22:42,213 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [704319491] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:42,213 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:42,213 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-03-20 10:22:42,213 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1355858700] [2022-03-20 10:22:42,213 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:42,214 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 10:22:42,214 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:42,214 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 10:22:42,214 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=17, Invalid=55, Unknown=0, NotChecked=0, Total=72 [2022-03-20 10:22:42,215 INFO L87 Difference]: Start difference. First operand 50 states and 64 transitions. Second operand has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:22:42,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:42,366 INFO L93 Difference]: Finished difference Result 103 states and 143 transitions. [2022-03-20 10:22:42,367 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-03-20 10:22:42,367 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 39 [2022-03-20 10:22:42,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:42,368 INFO L225 Difference]: With dead ends: 103 [2022-03-20 10:22:42,368 INFO L226 Difference]: Without dead ends: 96 [2022-03-20 10:22:42,368 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 69 SyntacticMatches, 1 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2022-03-20 10:22:42,369 INFO L913 BasicCegarLoop]: 52 mSDtfsCounter, 58 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 295 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:42,369 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [62 Valid, 295 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 10:22:42,370 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-03-20 10:22:42,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 71. [2022-03-20 10:22:42,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 47 states have (on average 1.2553191489361701) internal successors, (59), 48 states have internal predecessors, (59), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 10:22:42,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 95 transitions. [2022-03-20 10:22:42,380 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 95 transitions. Word has length 39 [2022-03-20 10:22:42,380 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:42,380 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 95 transitions. [2022-03-20 10:22:42,380 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 8 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 10:22:42,380 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 95 transitions. [2022-03-20 10:22:42,381 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-03-20 10:22:42,381 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:42,381 INFO L499 BasicCegarLoop]: trace histogram [4, 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] [2022-03-20 10:22:42,415 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-20 10:22:42,600 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-20 10:22:42,600 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:42,601 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:42,601 INFO L85 PathProgramCache]: Analyzing trace with hash -2079765955, now seen corresponding path program 1 times [2022-03-20 10:22:42,601 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:42,601 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1812056785] [2022-03-20 10:22:42,601 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:42,602 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:42,611 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:42,611 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [781851313] [2022-03-20 10:22:42,611 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:42,611 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:42,612 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:42,624 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-20 10:22:42,627 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-20 10:22:42,659 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:42,659 INFO L263 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-20 10:22:42,661 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:42,990 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 12 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:22:42,991 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:43,185 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:43,185 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:43,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1812056785] [2022-03-20 10:22:43,185 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:43,185 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [781851313] [2022-03-20 10:22:43,185 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [781851313] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 10:22:43,185 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 10:22:43,186 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [11] total 14 [2022-03-20 10:22:43,186 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1383395338] [2022-03-20 10:22:43,186 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:43,186 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-03-20 10:22:43,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:43,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-03-20 10:22:43,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=139, Unknown=0, NotChecked=0, Total=182 [2022-03-20 10:22:43,187 INFO L87 Difference]: Start difference. First operand 71 states and 95 transitions. Second operand has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 10:22:43,241 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:43,242 INFO L93 Difference]: Finished difference Result 79 states and 102 transitions. [2022-03-20 10:22:43,242 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 10:22:43,242 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 42 [2022-03-20 10:22:43,243 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:43,243 INFO L225 Difference]: With dead ends: 79 [2022-03-20 10:22:43,243 INFO L226 Difference]: Without dead ends: 77 [2022-03-20 10:22:43,244 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 70 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=47, Invalid=163, Unknown=0, NotChecked=0, Total=210 [2022-03-20 10:22:43,244 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 27 mSDsluCounter, 148 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 192 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:43,245 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 192 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:43,245 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 77 states. [2022-03-20 10:22:43,254 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 77 to 75. [2022-03-20 10:22:43,254 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 50 states have (on average 1.24) internal successors, (62), 51 states have internal predecessors, (62), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 10:22:43,255 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 98 transitions. [2022-03-20 10:22:43,255 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 98 transitions. Word has length 42 [2022-03-20 10:22:43,255 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:43,255 INFO L478 AbstractCegarLoop]: Abstraction has 75 states and 98 transitions. [2022-03-20 10:22:43,255 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 2.7142857142857144) internal successors, (19), 6 states have internal predecessors, (19), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-03-20 10:22:43,256 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 98 transitions. [2022-03-20 10:22:43,256 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2022-03-20 10:22:43,256 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:43,257 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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-20 10:22:43,274 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-20 10:22:43,473 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-20 10:22:43,474 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:43,474 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:43,474 INFO L85 PathProgramCache]: Analyzing trace with hash 446575011, now seen corresponding path program 1 times [2022-03-20 10:22:43,474 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:43,474 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [865672048] [2022-03-20 10:22:43,474 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:43,474 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:43,489 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:43,489 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1502217987] [2022-03-20 10:22:43,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:43,493 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:43,493 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:43,495 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-20 10:22:43,529 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-20 10:22:43,578 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:43,596 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 30 conjunts are in the unsatisfiable core [2022-03-20 10:22:43,597 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:43,868 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 10:22:43,868 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:44,017 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:44,017 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:44,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [865672048] [2022-03-20 10:22:44,017 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:44,017 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1502217987] [2022-03-20 10:22:44,017 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1502217987] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:44,018 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:44,018 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 8] total 16 [2022-03-20 10:22:44,018 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1257877781] [2022-03-20 10:22:44,018 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:44,018 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 10:22:44,018 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:44,018 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 10:22:44,019 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2022-03-20 10:22:44,019 INFO L87 Difference]: Start difference. First operand 75 states and 98 transitions. Second operand has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 5 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 10:22:44,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:44,396 INFO L93 Difference]: Finished difference Result 118 states and 159 transitions. [2022-03-20 10:22:44,396 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-03-20 10:22:44,396 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 5 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 42 [2022-03-20 10:22:44,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:44,399 INFO L225 Difference]: With dead ends: 118 [2022-03-20 10:22:44,399 INFO L226 Difference]: Without dead ends: 116 [2022-03-20 10:22:44,400 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 68 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 88 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=132, Invalid=468, Unknown=0, NotChecked=0, Total=600 [2022-03-20 10:22:44,402 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 106 mSDsluCounter, 300 mSDsCounter, 0 mSdLazyCounter, 277 mSolverCounterSat, 109 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 107 SdHoareTripleChecker+Valid, 347 SdHoareTripleChecker+Invalid, 386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 109 IncrementalHoareTripleChecker+Valid, 277 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:44,402 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [107 Valid, 347 Invalid, 386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [109 Valid, 277 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 10:22:44,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 116 states. [2022-03-20 10:22:44,429 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 116 to 105. [2022-03-20 10:22:44,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 71 states have (on average 1.2535211267605635) internal successors, (89), 72 states have internal predecessors, (89), 27 states have call successors, (27), 7 states have call predecessors, (27), 6 states have return successors, (25), 25 states have call predecessors, (25), 25 states have call successors, (25) [2022-03-20 10:22:44,433 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 141 transitions. [2022-03-20 10:22:44,433 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 141 transitions. Word has length 42 [2022-03-20 10:22:44,433 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:44,433 INFO L478 AbstractCegarLoop]: Abstraction has 105 states and 141 transitions. [2022-03-20 10:22:44,434 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.3333333333333335) internal successors, (35), 13 states have internal predecessors, (35), 5 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 10:22:44,435 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 141 transitions. [2022-03-20 10:22:44,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 10:22:44,437 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:44,437 INFO L499 BasicCegarLoop]: trace histogram [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, 1, 1, 1, 1] [2022-03-20 10:22:44,480 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-20 10:22:44,638 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-20 10:22:44,638 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:44,638 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:44,638 INFO L85 PathProgramCache]: Analyzing trace with hash -1977261252, now seen corresponding path program 1 times [2022-03-20 10:22:44,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:44,639 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [410533786] [2022-03-20 10:22:44,639 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:44,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:44,647 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:44,647 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1325636399] [2022-03-20 10:22:44,647 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:44,648 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:44,648 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:44,649 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-20 10:22:44,650 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-20 10:22:44,683 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:44,684 INFO L263 TraceCheckSpWp]: Trace formula consists of 135 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 10:22:44,685 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:44,750 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-03-20 10:22:44,750 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:22:44,750 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:44,750 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [410533786] [2022-03-20 10:22:44,750 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:44,750 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1325636399] [2022-03-20 10:22:44,750 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1325636399] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:44,750 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:44,750 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:22:44,750 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1289528234] [2022-03-20 10:22:44,750 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:44,751 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:44,751 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:44,751 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:44,751 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:22:44,751 INFO L87 Difference]: Start difference. First operand 105 states and 141 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:22:44,788 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:44,788 INFO L93 Difference]: Finished difference Result 151 states and 213 transitions. [2022-03-20 10:22:44,788 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:22:44,788 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 47 [2022-03-20 10:22:44,789 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:44,789 INFO L225 Difference]: With dead ends: 151 [2022-03-20 10:22:44,789 INFO L226 Difference]: Without dead ends: 149 [2022-03-20 10:22:44,790 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 47 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:22:44,790 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 8 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 42 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 151 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 42 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:44,790 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 151 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 42 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:44,791 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2022-03-20 10:22:44,803 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 143. [2022-03-20 10:22:44,804 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 143 states, 88 states have (on average 1.2840909090909092) internal successors, (113), 89 states have internal predecessors, (113), 47 states have call successors, (47), 8 states have call predecessors, (47), 7 states have return successors, (45), 45 states have call predecessors, (45), 45 states have call successors, (45) [2022-03-20 10:22:44,804 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 205 transitions. [2022-03-20 10:22:44,805 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 205 transitions. Word has length 47 [2022-03-20 10:22:44,805 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:44,805 INFO L478 AbstractCegarLoop]: Abstraction has 143 states and 205 transitions. [2022-03-20 10:22:44,805 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-03-20 10:22:44,805 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 205 transitions. [2022-03-20 10:22:44,805 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 10:22:44,805 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:44,805 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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-20 10:22:44,824 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-03-20 10:22:45,024 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-20 10:22:45,024 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:45,024 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:45,024 INFO L85 PathProgramCache]: Analyzing trace with hash -846684234, now seen corresponding path program 1 times [2022-03-20 10:22:45,024 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:45,025 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [9395904] [2022-03-20 10:22:45,025 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:45,025 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:45,050 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:45,051 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1211632366] [2022-03-20 10:22:45,051 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:45,051 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:45,051 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:45,067 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-20 10:22:45,102 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-20 10:22:45,145 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:45,146 INFO L263 TraceCheckSpWp]: Trace formula consists of 148 conjuncts, 35 conjunts are in the unsatisfiable core [2022-03-20 10:22:45,147 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:45,404 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 7 proven. 8 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2022-03-20 10:22:45,404 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:45,598 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:45,598 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:45,598 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [9395904] [2022-03-20 10:22:45,598 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:45,598 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1211632366] [2022-03-20 10:22:45,598 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1211632366] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:45,599 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:45,599 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 8] total 17 [2022-03-20 10:22:45,599 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1824100938] [2022-03-20 10:22:45,599 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:45,599 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-03-20 10:22:45,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:45,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-03-20 10:22:45,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=43, Invalid=229, Unknown=0, NotChecked=0, Total=272 [2022-03-20 10:22:45,600 INFO L87 Difference]: Start difference. First operand 143 states and 205 transitions. Second operand has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 15 states have internal predecessors, (41), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-20 10:22:46,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:46,101 INFO L93 Difference]: Finished difference Result 194 states and 277 transitions. [2022-03-20 10:22:46,102 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2022-03-20 10:22:46,102 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 15 states have internal predecessors, (41), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 47 [2022-03-20 10:22:46,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:46,107 INFO L225 Difference]: With dead ends: 194 [2022-03-20 10:22:46,107 INFO L226 Difference]: Without dead ends: 192 [2022-03-20 10:22:46,107 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 106 GetRequests, 78 SyntacticMatches, 1 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 141 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=138, Invalid=674, Unknown=0, NotChecked=0, Total=812 [2022-03-20 10:22:46,108 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 102 mSDsluCounter, 331 mSDsCounter, 0 mSdLazyCounter, 356 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 370 SdHoareTripleChecker+Invalid, 472 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 356 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 66 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:46,108 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [105 Valid, 370 Invalid, 472 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 356 Invalid, 0 Unknown, 66 Unchecked, 0.2s Time] [2022-03-20 10:22:46,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 192 states. [2022-03-20 10:22:46,134 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 192 to 166. [2022-03-20 10:22:46,135 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 104 states have (on average 1.2692307692307692) internal successors, (132), 108 states have internal predecessors, (132), 53 states have call successors, (53), 9 states have call predecessors, (53), 8 states have return successors, (51), 48 states have call predecessors, (51), 51 states have call successors, (51) [2022-03-20 10:22:46,136 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 236 transitions. [2022-03-20 10:22:46,136 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 236 transitions. Word has length 47 [2022-03-20 10:22:46,137 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:46,137 INFO L478 AbstractCegarLoop]: Abstraction has 166 states and 236 transitions. [2022-03-20 10:22:46,137 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 17 states have (on average 2.411764705882353) internal successors, (41), 15 states have internal predecessors, (41), 4 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2022-03-20 10:22:46,137 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 236 transitions. [2022-03-20 10:22:46,141 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2022-03-20 10:22:46,141 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:46,141 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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-20 10:22:46,157 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-20 10:22:46,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-20 10:22:46,356 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:46,356 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:46,356 INFO L85 PathProgramCache]: Analyzing trace with hash 1679656732, now seen corresponding path program 2 times [2022-03-20 10:22:46,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:46,356 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [781453017] [2022-03-20 10:22:46,356 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:46,356 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:46,364 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:46,364 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [654248208] [2022-03-20 10:22:46,364 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 10:22:46,364 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:46,364 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:46,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-20 10:22:46,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-20 10:22:46,407 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 10:22:46,407 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:22:46,408 INFO L263 TraceCheckSpWp]: Trace formula consists of 161 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-20 10:22:46,409 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:46,458 INFO L134 CoverageAnalysis]: Checked inductivity of 37 backedges. 13 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-03-20 10:22:46,459 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:22:46,459 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:46,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [781453017] [2022-03-20 10:22:46,459 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:46,459 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [654248208] [2022-03-20 10:22:46,459 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [654248208] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:46,459 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:46,459 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:22:46,459 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1642838482] [2022-03-20 10:22:46,459 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:46,459 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:46,460 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:46,460 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:46,460 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:22:46,460 INFO L87 Difference]: Start difference. First operand 166 states and 236 transitions. Second operand has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:46,515 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:46,515 INFO L93 Difference]: Finished difference Result 212 states and 296 transitions. [2022-03-20 10:22:46,516 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 10:22:46,516 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 47 [2022-03-20 10:22:46,516 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:46,516 INFO L225 Difference]: With dead ends: 212 [2022-03-20 10:22:46,517 INFO L226 Difference]: Without dead ends: 136 [2022-03-20 10:22:46,517 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 44 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-20 10:22:46,518 INFO L913 BasicCegarLoop]: 57 mSDtfsCounter, 18 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:46,518 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 180 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:46,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2022-03-20 10:22:46,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 113. [2022-03-20 10:22:46,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 69 states have (on average 1.1884057971014492) internal successors, (82), 72 states have internal predecessors, (82), 35 states have call successors, (35), 9 states have call predecessors, (35), 8 states have return successors, (33), 31 states have call predecessors, (33), 33 states have call successors, (33) [2022-03-20 10:22:46,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 150 transitions. [2022-03-20 10:22:46,529 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 150 transitions. Word has length 47 [2022-03-20 10:22:46,529 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:46,529 INFO L478 AbstractCegarLoop]: Abstraction has 113 states and 150 transitions. [2022-03-20 10:22:46,529 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.2) internal successors, (26), 5 states have internal predecessors, (26), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-03-20 10:22:46,529 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 150 transitions. [2022-03-20 10:22:46,529 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 53 [2022-03-20 10:22:46,530 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:46,530 INFO L499 BasicCegarLoop]: trace histogram [4, 4, 4, 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] [2022-03-20 10:22:46,557 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-20 10:22:46,756 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-20 10:22:46,756 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:46,756 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:46,756 INFO L85 PathProgramCache]: Analyzing trace with hash -1660248707, now seen corresponding path program 1 times [2022-03-20 10:22:46,757 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:46,757 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1894453699] [2022-03-20 10:22:46,757 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:46,757 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:46,767 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:46,767 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1930609958] [2022-03-20 10:22:46,768 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:46,768 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:46,768 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:46,769 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-20 10:22:46,770 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-20 10:22:46,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:46,801 INFO L263 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 10:22:46,802 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:46,887 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-03-20 10:22:46,887 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:22:46,887 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:46,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1894453699] [2022-03-20 10:22:46,887 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:46,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1930609958] [2022-03-20 10:22:46,887 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1930609958] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:46,887 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:46,887 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:22:46,888 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [386554929] [2022-03-20 10:22:46,888 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:46,888 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:46,888 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:46,888 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:46,888 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:22:46,888 INFO L87 Difference]: Start difference. First operand 113 states and 150 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-03-20 10:22:46,931 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:46,932 INFO L93 Difference]: Finished difference Result 163 states and 230 transitions. [2022-03-20 10:22:46,932 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:22:46,932 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 52 [2022-03-20 10:22:46,932 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:46,933 INFO L225 Difference]: With dead ends: 163 [2022-03-20 10:22:46,933 INFO L226 Difference]: Without dead ends: 161 [2022-03-20 10:22:46,933 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 52 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:22:46,933 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 9 mSDsluCounter, 116 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 162 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:46,933 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 162 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:46,934 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2022-03-20 10:22:46,947 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 144. [2022-03-20 10:22:46,948 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 77 states have (on average 1.1688311688311688) internal successors, (90), 85 states have internal predecessors, (90), 57 states have call successors, (57), 10 states have call predecessors, (57), 9 states have return successors, (55), 48 states have call predecessors, (55), 55 states have call successors, (55) [2022-03-20 10:22:46,948 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 202 transitions. [2022-03-20 10:22:46,948 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 202 transitions. Word has length 52 [2022-03-20 10:22:46,949 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:46,949 INFO L478 AbstractCegarLoop]: Abstraction has 144 states and 202 transitions. [2022-03-20 10:22:46,949 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 4 states have internal predecessors, (19), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-03-20 10:22:46,949 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 202 transitions. [2022-03-20 10:22:46,949 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-03-20 10:22:46,949 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:46,949 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1] [2022-03-20 10:22:46,967 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-20 10:22:47,158 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-20 10:22:47,160 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:47,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:47,160 INFO L85 PathProgramCache]: Analyzing trace with hash 1094467600, now seen corresponding path program 1 times [2022-03-20 10:22:47,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:47,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1158039490] [2022-03-20 10:22:47,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:47,160 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:47,168 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:47,168 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1212195927] [2022-03-20 10:22:47,168 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:47,168 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:47,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:47,175 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-20 10:22:47,179 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-20 10:22:47,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:47,228 INFO L263 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 45 conjunts are in the unsatisfiable core [2022-03-20 10:22:47,229 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:47,656 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-20 10:22:47,656 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:47,917 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-03-20 10:22:47,917 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:47,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1158039490] [2022-03-20 10:22:47,918 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:47,918 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1212195927] [2022-03-20 10:22:47,918 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1212195927] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:47,918 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:47,918 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-20 10:22:47,918 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [968021505] [2022-03-20 10:22:47,918 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:47,918 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 10:22:47,918 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:47,919 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 10:22:47,919 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2022-03-20 10:22:47,919 INFO L87 Difference]: Start difference. First operand 144 states and 202 transitions. Second operand has 16 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 15 states have internal predecessors, (39), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2022-03-20 10:22:51,677 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:51,678 INFO L93 Difference]: Finished difference Result 331 states and 487 transitions. [2022-03-20 10:22:51,678 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2022-03-20 10:22:51,678 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 15 states have internal predecessors, (39), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 64 [2022-03-20 10:22:51,678 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:51,680 INFO L225 Difference]: With dead ends: 331 [2022-03-20 10:22:51,680 INFO L226 Difference]: Without dead ends: 326 [2022-03-20 10:22:51,680 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 112 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 234 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=275, Invalid=1057, Unknown=0, NotChecked=0, Total=1332 [2022-03-20 10:22:51,681 INFO L913 BasicCegarLoop]: 79 mSDtfsCounter, 148 mSDsluCounter, 409 mSDsCounter, 0 mSdLazyCounter, 693 mSolverCounterSat, 302 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 160 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 995 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 302 IncrementalHoareTripleChecker+Valid, 693 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:51,681 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [160 Valid, 488 Invalid, 995 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [302 Valid, 693 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2022-03-20 10:22:51,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 326 states. [2022-03-20 10:22:51,748 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 326 to 250. [2022-03-20 10:22:51,749 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 250 states, 146 states have (on average 1.1986301369863013) internal successors, (175), 153 states have internal predecessors, (175), 89 states have call successors, (89), 15 states have call predecessors, (89), 14 states have return successors, (87), 81 states have call predecessors, (87), 87 states have call successors, (87) [2022-03-20 10:22:51,750 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 250 states to 250 states and 351 transitions. [2022-03-20 10:22:51,750 INFO L78 Accepts]: Start accepts. Automaton has 250 states and 351 transitions. Word has length 64 [2022-03-20 10:22:51,750 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:51,750 INFO L478 AbstractCegarLoop]: Abstraction has 250 states and 351 transitions. [2022-03-20 10:22:51,751 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 14 states have (on average 2.7857142857142856) internal successors, (39), 15 states have internal predecessors, (39), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2022-03-20 10:22:51,751 INFO L276 IsEmpty]: Start isEmpty. Operand 250 states and 351 transitions. [2022-03-20 10:22:51,767 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2022-03-20 10:22:51,767 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:51,768 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 4, 4, 4, 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] [2022-03-20 10:22:51,786 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-20 10:22:51,987 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-20 10:22:51,987 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:51,988 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:51,988 INFO L85 PathProgramCache]: Analyzing trace with hash 696944608, now seen corresponding path program 1 times [2022-03-20 10:22:51,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:51,988 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [856242816] [2022-03-20 10:22:51,988 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:51,988 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:51,995 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:51,996 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1053581268] [2022-03-20 10:22:51,996 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:51,996 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:51,996 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:51,999 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-20 10:22:52,027 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-20 10:22:52,037 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:52,037 INFO L263 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 11 conjunts are in the unsatisfiable core [2022-03-20 10:22:52,039 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:52,164 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 5 refuted. 0 times theorem prover too weak. 108 trivial. 0 not checked. [2022-03-20 10:22:52,164 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:52,290 INFO L134 CoverageAnalysis]: Checked inductivity of 127 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2022-03-20 10:22:52,290 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:52,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [856242816] [2022-03-20 10:22:52,290 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:52,290 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1053581268] [2022-03-20 10:22:52,290 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1053581268] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 10:22:52,290 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 10:22:52,290 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 10:22:52,290 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [681541807] [2022-03-20 10:22:52,291 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:52,291 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:52,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:52,291 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:52,291 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 10:22:52,291 INFO L87 Difference]: Start difference. First operand 250 states and 351 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 10:22:52,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:52,359 INFO L93 Difference]: Finished difference Result 256 states and 356 transitions. [2022-03-20 10:22:52,359 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 10:22:52,359 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 74 [2022-03-20 10:22:52,359 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:52,360 INFO L225 Difference]: With dead ends: 256 [2022-03-20 10:22:52,360 INFO L226 Difference]: Without dead ends: 254 [2022-03-20 10:22:52,361 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 140 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-03-20 10:22:52,361 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 9 mSDsluCounter, 103 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:52,361 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 145 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:52,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 254 states. [2022-03-20 10:22:52,402 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 254 to 254. [2022-03-20 10:22:52,402 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 254 states, 149 states have (on average 1.1946308724832215) internal successors, (178), 156 states have internal predecessors, (178), 89 states have call successors, (89), 16 states have call predecessors, (89), 15 states have return successors, (87), 81 states have call predecessors, (87), 87 states have call successors, (87) [2022-03-20 10:22:52,403 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 254 states to 254 states and 354 transitions. [2022-03-20 10:22:52,403 INFO L78 Accepts]: Start accepts. Automaton has 254 states and 354 transitions. Word has length 74 [2022-03-20 10:22:52,403 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:52,403 INFO L478 AbstractCegarLoop]: Abstraction has 254 states and 354 transitions. [2022-03-20 10:22:52,404 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-03-20 10:22:52,404 INFO L276 IsEmpty]: Start isEmpty. Operand 254 states and 354 transitions. [2022-03-20 10:22:52,404 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2022-03-20 10:22:52,404 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:52,404 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 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, 1, 1, 1, 1, 1] [2022-03-20 10:22:52,435 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Ended with exit code 0 [2022-03-20 10:22:52,621 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-20 10:22:52,621 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:52,621 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:52,621 INFO L85 PathProgramCache]: Analyzing trace with hash -2010106522, now seen corresponding path program 1 times [2022-03-20 10:22:52,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:52,621 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1629704989] [2022-03-20 10:22:52,621 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:52,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:52,641 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:52,641 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [228297052] [2022-03-20 10:22:52,641 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:52,641 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:52,641 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:52,656 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-20 10:22:52,658 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-20 10:22:52,696 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:22:52,697 INFO L263 TraceCheckSpWp]: Trace formula consists of 209 conjuncts, 38 conjunts are in the unsatisfiable core [2022-03-20 10:22:52,699 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:52,982 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 10 proven. 26 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2022-03-20 10:22:52,982 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:53,125 INFO L134 CoverageAnalysis]: Checked inductivity of 77 backedges. 25 proven. 9 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2022-03-20 10:22:53,125 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:53,125 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1629704989] [2022-03-20 10:22:53,126 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:53,126 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [228297052] [2022-03-20 10:22:53,126 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [228297052] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:53,126 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:53,126 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 8] total 13 [2022-03-20 10:22:53,126 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1480896767] [2022-03-20 10:22:53,126 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:53,126 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-03-20 10:22:53,126 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:53,126 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-03-20 10:22:53,126 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=125, Unknown=0, NotChecked=0, Total=156 [2022-03-20 10:22:53,127 INFO L87 Difference]: Start difference. First operand 254 states and 354 transitions. Second operand has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 12 states have internal predecessors, (56), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2022-03-20 10:22:53,518 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:53,518 INFO L93 Difference]: Finished difference Result 323 states and 461 transitions. [2022-03-20 10:22:53,519 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-03-20 10:22:53,519 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 12 states have internal predecessors, (56), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) Word has length 72 [2022-03-20 10:22:53,519 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:53,520 INFO L225 Difference]: With dead ends: 323 [2022-03-20 10:22:53,520 INFO L226 Difference]: Without dead ends: 321 [2022-03-20 10:22:53,521 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 136 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 40 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=78, Invalid=302, Unknown=0, NotChecked=0, Total=380 [2022-03-20 10:22:53,521 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 73 mSDsluCounter, 290 mSDsCounter, 0 mSdLazyCounter, 352 mSolverCounterSat, 59 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 332 SdHoareTripleChecker+Invalid, 411 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 59 IncrementalHoareTripleChecker+Valid, 352 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:53,521 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [77 Valid, 332 Invalid, 411 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [59 Valid, 352 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 10:22:53,521 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 321 states. [2022-03-20 10:22:53,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 321 to 258. [2022-03-20 10:22:53,562 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 258 states, 152 states have (on average 1.1907894736842106) internal successors, (181), 159 states have internal predecessors, (181), 89 states have call successors, (89), 17 states have call predecessors, (89), 16 states have return successors, (87), 81 states have call predecessors, (87), 87 states have call successors, (87) [2022-03-20 10:22:53,563 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 258 states to 258 states and 357 transitions. [2022-03-20 10:22:53,563 INFO L78 Accepts]: Start accepts. Automaton has 258 states and 357 transitions. Word has length 72 [2022-03-20 10:22:53,563 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:53,563 INFO L478 AbstractCegarLoop]: Abstraction has 258 states and 357 transitions. [2022-03-20 10:22:53,563 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 4.3076923076923075) internal successors, (56), 12 states have internal predecessors, (56), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (13), 3 states have call predecessors, (13), 3 states have call successors, (13) [2022-03-20 10:22:53,564 INFO L276 IsEmpty]: Start isEmpty. Operand 258 states and 357 transitions. [2022-03-20 10:22:53,568 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-03-20 10:22:53,568 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:53,568 INFO L499 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 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-20 10:22:53,592 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Ended with exit code 0 [2022-03-20 10:22:53,780 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-20 10:22:53,780 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:53,780 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:53,780 INFO L85 PathProgramCache]: Analyzing trace with hash 857620825, now seen corresponding path program 2 times [2022-03-20 10:22:53,781 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:53,781 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777993052] [2022-03-20 10:22:53,781 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:53,781 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:53,802 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:53,802 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2136725546] [2022-03-20 10:22:53,802 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 10:22:53,802 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:53,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:53,807 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-20 10:22:53,808 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-20 10:22:53,865 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 10:22:53,865 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:22:53,865 INFO L263 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-20 10:22:53,866 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:53,998 INFO L134 CoverageAnalysis]: Checked inductivity of 108 backedges. 48 proven. 0 refuted. 0 times theorem prover too weak. 60 trivial. 0 not checked. [2022-03-20 10:22:53,999 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 10:22:53,999 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:53,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [777993052] [2022-03-20 10:22:53,999 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:53,999 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2136725546] [2022-03-20 10:22:53,999 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2136725546] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 10:22:53,999 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 10:22:53,999 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 10:22:53,999 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [178038792] [2022-03-20 10:22:54,000 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 10:22:54,000 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 10:22:54,000 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:54,000 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 10:22:54,000 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 10:22:54,001 INFO L87 Difference]: Start difference. First operand 258 states and 357 transitions. Second operand has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2022-03-20 10:22:54,099 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:22:54,099 INFO L93 Difference]: Finished difference Result 444 states and 610 transitions. [2022-03-20 10:22:54,108 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-03-20 10:22:54,109 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 77 [2022-03-20 10:22:54,109 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:22:54,110 INFO L225 Difference]: With dead ends: 444 [2022-03-20 10:22:54,110 INFO L226 Difference]: Without dead ends: 266 [2022-03-20 10:22:54,123 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2022-03-20 10:22:54,124 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 3 mSDsluCounter, 70 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 10:22:54,124 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [3 Valid, 115 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 10:22:54,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2022-03-20 10:22:54,188 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 257. [2022-03-20 10:22:54,188 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 257 states, 159 states have (on average 1.1761006289308176) internal successors, (187), 161 states have internal predecessors, (187), 81 states have call successors, (81), 17 states have call predecessors, (81), 16 states have return successors, (79), 78 states have call predecessors, (79), 79 states have call successors, (79) [2022-03-20 10:22:54,190 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 257 states to 257 states and 347 transitions. [2022-03-20 10:22:54,190 INFO L78 Accepts]: Start accepts. Automaton has 257 states and 347 transitions. Word has length 77 [2022-03-20 10:22:54,190 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:22:54,190 INFO L478 AbstractCegarLoop]: Abstraction has 257 states and 347 transitions. [2022-03-20 10:22:54,190 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.6) internal successors, (28), 5 states have internal predecessors, (28), 3 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2022-03-20 10:22:54,190 INFO L276 IsEmpty]: Start isEmpty. Operand 257 states and 347 transitions. [2022-03-20 10:22:54,190 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2022-03-20 10:22:54,191 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:22:54,191 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 4, 4, 4, 4, 3, 3, 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-20 10:22:54,209 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-20 10:22:54,406 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-20 10:22:54,406 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:22:54,407 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:22:54,407 INFO L85 PathProgramCache]: Analyzing trace with hash 1988197843, now seen corresponding path program 3 times [2022-03-20 10:22:54,407 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:22:54,407 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1424385864] [2022-03-20 10:22:54,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:22:54,407 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:22:54,413 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:22:54,413 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [831987898] [2022-03-20 10:22:54,413 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 10:22:54,413 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:22:54,413 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:22:54,417 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-20 10:22:54,418 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-20 10:22:54,458 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2022-03-20 10:22:54,458 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 10:22:54,459 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 60 conjunts are in the unsatisfiable core [2022-03-20 10:22:54,460 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:22:55,061 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 10 proven. 22 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-20 10:22:55,061 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:22:56,086 INFO L134 CoverageAnalysis]: Checked inductivity of 96 backedges. 14 proven. 18 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2022-03-20 10:22:56,086 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:22:56,086 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1424385864] [2022-03-20 10:22:56,086 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:22:56,086 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [831987898] [2022-03-20 10:22:56,087 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [831987898] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:22:56,087 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:22:56,087 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 26 [2022-03-20 10:22:56,087 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1413987184] [2022-03-20 10:22:56,087 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:22:56,087 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2022-03-20 10:22:56,087 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:22:56,092 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2022-03-20 10:22:56,093 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=128, Invalid=522, Unknown=0, NotChecked=0, Total=650 [2022-03-20 10:22:56,093 INFO L87 Difference]: Start difference. First operand 257 states and 347 transitions. Second operand has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2022-03-20 10:23:07,636 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:23:20,988 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:23:20,988 INFO L93 Difference]: Finished difference Result 424 states and 583 transitions. [2022-03-20 10:23:20,989 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2022-03-20 10:23:20,989 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) Word has length 77 [2022-03-20 10:23:20,989 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:23:20,997 INFO L225 Difference]: With dead ends: 424 [2022-03-20 10:23:20,997 INFO L226 Difference]: Without dead ends: 422 [2022-03-20 10:23:20,998 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 184 GetRequests, 128 SyntacticMatches, 2 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 745 ImplicationChecksByTransitivity, 15.0s TimeCoverageRelationStatistics Valid=692, Invalid=2388, Unknown=0, NotChecked=0, Total=3080 [2022-03-20 10:23:20,998 INFO L913 BasicCegarLoop]: 75 mSDtfsCounter, 258 mSDsluCounter, 643 mSDsCounter, 0 mSdLazyCounter, 949 mSolverCounterSat, 434 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 258 SdHoareTripleChecker+Valid, 718 SdHoareTripleChecker+Invalid, 1384 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 434 IncrementalHoareTripleChecker+Valid, 949 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.7s IncrementalHoareTripleChecker+Time [2022-03-20 10:23:20,998 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [258 Valid, 718 Invalid, 1384 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [434 Valid, 949 Invalid, 1 Unknown, 0 Unchecked, 10.7s Time] [2022-03-20 10:23:20,999 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 422 states. [2022-03-20 10:23:21,069 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 422 to 359. [2022-03-20 10:23:21,070 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 359 states, 218 states have (on average 1.1926605504587156) internal successors, (260), 219 states have internal predecessors, (260), 119 states have call successors, (119), 22 states have call predecessors, (119), 21 states have return successors, (117), 117 states have call predecessors, (117), 117 states have call successors, (117) [2022-03-20 10:23:21,071 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 359 states to 359 states and 496 transitions. [2022-03-20 10:23:21,071 INFO L78 Accepts]: Start accepts. Automaton has 359 states and 496 transitions. Word has length 77 [2022-03-20 10:23:21,071 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:23:21,071 INFO L478 AbstractCegarLoop]: Abstraction has 359 states and 496 transitions. [2022-03-20 10:23:21,072 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 26 states have (on average 2.1153846153846154) internal successors, (55), 25 states have internal predecessors, (55), 5 states have call successors, (18), 2 states have call predecessors, (18), 1 states have return successors, (15), 5 states have call predecessors, (15), 5 states have call successors, (15) [2022-03-20 10:23:21,072 INFO L276 IsEmpty]: Start isEmpty. Operand 359 states and 496 transitions. [2022-03-20 10:23:21,072 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 92 [2022-03-20 10:23:21,072 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:23:21,072 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:23:21,089 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-20 10:23:21,288 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-20 10:23:21,288 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:23:21,289 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:23:21,289 INFO L85 PathProgramCache]: Analyzing trace with hash -983010836, now seen corresponding path program 1 times [2022-03-20 10:23:21,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:23:21,289 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1249162361] [2022-03-20 10:23:21,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:21,289 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:23:21,295 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:23:21,295 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [73955313] [2022-03-20 10:23:21,295 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:21,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:23:21,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:23:21,296 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-20 10:23:21,297 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-20 10:23:21,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:23:21,347 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 94 conjunts are in the unsatisfiable core [2022-03-20 10:23:21,348 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:23:22,158 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 56 proven. 24 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2022-03-20 10:23:22,158 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:23:34,867 INFO L134 CoverageAnalysis]: Checked inductivity of 171 backedges. 73 proven. 4 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2022-03-20 10:23:34,867 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:23:34,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1249162361] [2022-03-20 10:23:34,867 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:23:34,867 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [73955313] [2022-03-20 10:23:34,867 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [73955313] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:23:34,867 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:23:34,867 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 24 [2022-03-20 10:23:34,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1379121948] [2022-03-20 10:23:34,868 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:23:34,868 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 24 states [2022-03-20 10:23:34,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:23:34,868 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2022-03-20 10:23:34,868 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=104, Invalid=448, Unknown=0, NotChecked=0, Total=552 [2022-03-20 10:23:34,868 INFO L87 Difference]: Start difference. First operand 359 states and 496 transitions. Second operand has 24 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 20 states have internal predecessors, (54), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 7 states have call successors, (21) [2022-03-20 10:23:43,364 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:23:44,291 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:23:44,291 INFO L93 Difference]: Finished difference Result 468 states and 639 transitions. [2022-03-20 10:23:44,292 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2022-03-20 10:23:44,292 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 20 states have internal predecessors, (54), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 7 states have call successors, (21) Word has length 91 [2022-03-20 10:23:44,292 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:23:44,294 INFO L225 Difference]: With dead ends: 468 [2022-03-20 10:23:44,294 INFO L226 Difference]: Without dead ends: 464 [2022-03-20 10:23:44,294 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 222 GetRequests, 171 SyntacticMatches, 2 SemanticMatches, 49 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 512 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=503, Invalid=2047, Unknown=0, NotChecked=0, Total=2550 [2022-03-20 10:23:44,296 INFO L913 BasicCegarLoop]: 56 mSDtfsCounter, 140 mSDsluCounter, 420 mSDsCounter, 0 mSdLazyCounter, 985 mSolverCounterSat, 271 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 147 SdHoareTripleChecker+Valid, 476 SdHoareTripleChecker+Invalid, 1257 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 271 IncrementalHoareTripleChecker+Valid, 985 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.5s IncrementalHoareTripleChecker+Time [2022-03-20 10:23:44,296 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [147 Valid, 476 Invalid, 1257 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [271 Valid, 985 Invalid, 1 Unknown, 0 Unchecked, 6.5s Time] [2022-03-20 10:23:44,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 464 states. [2022-03-20 10:23:44,412 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 464 to 370. [2022-03-20 10:23:44,413 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 370 states, 213 states have (on average 1.192488262910798) internal successors, (254), 213 states have internal predecessors, (254), 130 states have call successors, (130), 27 states have call predecessors, (130), 26 states have return successors, (129), 129 states have call predecessors, (129), 129 states have call successors, (129) [2022-03-20 10:23:44,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 370 states to 370 states and 513 transitions. [2022-03-20 10:23:44,415 INFO L78 Accepts]: Start accepts. Automaton has 370 states and 513 transitions. Word has length 91 [2022-03-20 10:23:44,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:23:44,415 INFO L478 AbstractCegarLoop]: Abstraction has 370 states and 513 transitions. [2022-03-20 10:23:44,415 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 24 states, 19 states have (on average 2.8421052631578947) internal successors, (54), 20 states have internal predecessors, (54), 9 states have call successors, (23), 2 states have call predecessors, (23), 2 states have return successors, (21), 8 states have call predecessors, (21), 7 states have call successors, (21) [2022-03-20 10:23:44,415 INFO L276 IsEmpty]: Start isEmpty. Operand 370 states and 513 transitions. [2022-03-20 10:23:44,416 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-20 10:23:44,416 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:23:44,416 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 4, 4, 4, 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, 1] [2022-03-20 10:23:44,432 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-20 10:23:44,631 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-20 10:23:44,631 INFO L403 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:23:44,632 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:23:44,632 INFO L85 PathProgramCache]: Analyzing trace with hash 736682115, now seen corresponding path program 1 times [2022-03-20 10:23:44,632 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:23:44,632 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [383088507] [2022-03-20 10:23:44,632 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:44,632 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:23:44,637 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:23:44,637 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [13364543] [2022-03-20 10:23:44,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:44,638 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:23:44,638 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:23:44,641 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-20 10:23:44,642 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-20 10:23:44,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:23:44,685 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 10:23:44,687 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:23:44,925 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 20 proven. 16 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2022-03-20 10:23:44,925 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:23:45,759 INFO L134 CoverageAnalysis]: Checked inductivity of 240 backedges. 22 proven. 14 refuted. 0 times theorem prover too weak. 204 trivial. 0 not checked. [2022-03-20 10:23:45,759 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:23:45,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [383088507] [2022-03-20 10:23:45,759 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:23:45,759 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [13364543] [2022-03-20 10:23:45,760 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [13364543] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:23:45,760 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:23:45,760 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-20 10:23:45,760 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2082201311] [2022-03-20 10:23:45,760 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:23:45,760 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 10:23:45,760 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:23:45,760 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 10:23:45,760 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=171, Unknown=0, NotChecked=0, Total=240 [2022-03-20 10:23:45,761 INFO L87 Difference]: Start difference. First operand 370 states and 513 transitions. Second operand has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 7 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-20 10:23:47,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:23:47,133 INFO L93 Difference]: Finished difference Result 897 states and 1392 transitions. [2022-03-20 10:23:47,133 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-03-20 10:23:47,133 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 7 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 94 [2022-03-20 10:23:47,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:23:47,136 INFO L225 Difference]: With dead ends: 897 [2022-03-20 10:23:47,136 INFO L226 Difference]: Without dead ends: 895 [2022-03-20 10:23:47,137 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 199 GetRequests, 172 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=222, Invalid=534, Unknown=0, NotChecked=0, Total=756 [2022-03-20 10:23:47,137 INFO L913 BasicCegarLoop]: 85 mSDtfsCounter, 91 mSDsluCounter, 430 mSDsCounter, 0 mSdLazyCounter, 475 mSolverCounterSat, 157 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 97 SdHoareTripleChecker+Valid, 515 SdHoareTripleChecker+Invalid, 632 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 157 IncrementalHoareTripleChecker+Valid, 475 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-20 10:23:47,137 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [97 Valid, 515 Invalid, 632 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [157 Valid, 475 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-03-20 10:23:47,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 895 states. [2022-03-20 10:23:47,430 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 895 to 823. [2022-03-20 10:23:47,431 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 823 states, 395 states have (on average 1.3063291139240507) internal successors, (516), 395 states have internal predecessors, (516), 398 states have call successors, (398), 30 states have call predecessors, (398), 29 states have return successors, (397), 397 states have call predecessors, (397), 397 states have call successors, (397) [2022-03-20 10:23:47,436 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 823 states to 823 states and 1311 transitions. [2022-03-20 10:23:47,436 INFO L78 Accepts]: Start accepts. Automaton has 823 states and 1311 transitions. Word has length 94 [2022-03-20 10:23:47,436 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:23:47,436 INFO L478 AbstractCegarLoop]: Abstraction has 823 states and 1311 transitions. [2022-03-20 10:23:47,436 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.3125) internal successors, (37), 15 states have internal predecessors, (37), 7 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-20 10:23:47,436 INFO L276 IsEmpty]: Start isEmpty. Operand 823 states and 1311 transitions. [2022-03-20 10:23:47,437 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-03-20 10:23:47,437 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 10:23:47,437 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 4, 4, 4, 3, 3, 3, 3, 3, 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] [2022-03-20 10:23:47,454 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2022-03-20 10:23:47,653 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-20 10:23:47,653 INFO L403 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 10:23:47,653 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 10:23:47,654 INFO L85 PathProgramCache]: Analyzing trace with hash 1867259133, now seen corresponding path program 1 times [2022-03-20 10:23:47,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 10:23:47,654 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1800635] [2022-03-20 10:23:47,654 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:47,654 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 10:23:47,659 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 10:23:47,659 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1608682531] [2022-03-20 10:23:47,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 10:23:47,659 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 10:23:47,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 10:23:47,660 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-20 10:23:47,666 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-20 10:23:47,708 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 10:23:47,709 INFO L263 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 53 conjunts are in the unsatisfiable core [2022-03-20 10:23:47,710 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 10:23:48,206 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 43 proven. 37 refuted. 0 times theorem prover too weak. 126 trivial. 0 not checked. [2022-03-20 10:23:48,206 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 10:23:48,728 INFO L134 CoverageAnalysis]: Checked inductivity of 206 backedges. 38 proven. 24 refuted. 0 times theorem prover too weak. 144 trivial. 0 not checked. [2022-03-20 10:23:48,728 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 10:23:48,728 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1800635] [2022-03-20 10:23:48,728 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 10:23:48,728 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1608682531] [2022-03-20 10:23:48,728 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1608682531] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 10:23:48,728 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 10:23:48,729 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 21 [2022-03-20 10:23:48,729 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [330262856] [2022-03-20 10:23:48,729 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 10:23:48,729 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2022-03-20 10:23:48,729 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 10:23:48,729 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2022-03-20 10:23:48,729 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=348, Unknown=0, NotChecked=0, Total=420 [2022-03-20 10:23:48,730 INFO L87 Difference]: Start difference. First operand 823 states and 1311 transitions. Second operand has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 7 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 7 states have call successors, (23) [2022-03-20 10:23:51,601 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.53s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:23:54,462 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:23:55,811 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.29s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-03-20 10:24:00,635 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 10:24:00,635 INFO L93 Difference]: Finished difference Result 929 states and 1490 transitions. [2022-03-20 10:24:00,635 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 10:24:00,636 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 7 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 7 states have call successors, (23) Word has length 94 [2022-03-20 10:24:00,636 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 10:24:00,636 INFO L225 Difference]: With dead ends: 929 [2022-03-20 10:24:00,636 INFO L226 Difference]: Without dead ends: 0 [2022-03-20 10:24:00,641 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 165 SyntacticMatches, 4 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 187 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=230, Invalid=892, Unknown=0, NotChecked=0, Total=1122 [2022-03-20 10:24:00,642 INFO L913 BasicCegarLoop]: 47 mSDtfsCounter, 69 mSDsluCounter, 528 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 180 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 9.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 69 SdHoareTripleChecker+Valid, 575 SdHoareTripleChecker+Invalid, 803 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 180 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 9.7s IncrementalHoareTripleChecker+Time [2022-03-20 10:24:00,642 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [69 Valid, 575 Invalid, 803 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [180 Valid, 622 Invalid, 1 Unknown, 0 Unchecked, 9.7s Time] [2022-03-20 10:24:00,642 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-03-20 10:24:00,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-03-20 10:24:00,642 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-20 10:24:00,642 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-03-20 10:24:00,643 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 94 [2022-03-20 10:24:00,643 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 10:24:00,643 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-03-20 10:24:00,643 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 2.5714285714285716) internal successors, (54), 20 states have internal predecessors, (54), 7 states have call successors, (26), 2 states have call predecessors, (26), 2 states have return successors, (23), 9 states have call predecessors, (23), 7 states have call successors, (23) [2022-03-20 10:24:00,643 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-03-20 10:24:00,643 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-03-20 10:24:00,648 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-20 10:24:00,665 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-20 10:24:00,859 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-20 10:24:00,862 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-03-20 10:24:06,493 WARN L232 SmtUtils]: Spent 5.28s on a formula simplification. DAG size of input: 459 DAG size of output: 464 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:24:11,887 WARN L232 SmtUtils]: Spent 5.32s on a formula simplification. DAG size of input: 463 DAG size of output: 460 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:24:21,866 WARN L232 SmtUtils]: Spent 9.98s on a formula simplification. DAG size of input: 406 DAG size of output: 401 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:24:27,082 WARN L232 SmtUtils]: Spent 5.21s on a formula simplification. DAG size of input: 464 DAG size of output: 463 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:24:34,503 WARN L232 SmtUtils]: Spent 7.42s on a formula simplification. DAG size of input: 480 DAG size of output: 468 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:24:41,948 WARN L232 SmtUtils]: Spent 7.44s on a formula simplification. DAG size of input: 480 DAG size of output: 468 (called from [L 182] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.or) [2022-03-20 10:25:41,565 WARN L232 SmtUtils]: Spent 53.89s on a formula simplification. DAG size of input: 387 DAG size of output: 52 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:27:16,726 WARN L232 SmtUtils]: Spent 1.59m on a formula simplification. DAG size of input: 383 DAG size of output: 65 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:27:40,153 WARN L232 SmtUtils]: Spent 23.42s on a formula simplification. DAG size of input: 327 DAG size of output: 58 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:28:46,545 WARN L232 SmtUtils]: Spent 1.11m on a formula simplification. DAG size of input: 386 DAG size of output: 52 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:29:39,613 WARN L232 SmtUtils]: Spent 53.06s on a formula simplification. DAG size of input: 396 DAG size of output: 53 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:30:44,345 WARN L232 SmtUtils]: Spent 1.08m on a formula simplification. DAG size of input: 396 DAG size of output: 53 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 10:30:44,348 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-03-20 10:30:44,348 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 7 9) the Hoare annotation is: true [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point L8(line 8) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point L8-2(lines 7 9) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 7 9) no Hoare annotation was computed. [2022-03-20 10:30:44,348 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 18 76) the Hoare annotation is: true [2022-03-20 10:30:44,348 INFO L885 garLoopResultBuilder]: At program point L22(line 22) the Hoare annotation is: true [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L22-1(line 22) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L885 garLoopResultBuilder]: At program point L24(line 24) the Hoare annotation is: true [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L24-1(line 24) the Hoare annotation is: (and (<= 0 main_~y~0) (<= main_~y~0 50)) [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: (and (<= 0 main_~y~0) (<= 1 main_~x~0) (<= main_~y~0 50)) [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L26(line 26) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L35-2(lines 35 73) the Hoare annotation is: (let ((.cse1 (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0)))) (let ((.cse0 (= main_~a~0 .cse1)) (.cse2 (<= 1 main_~y~0)) (.cse3 (<= main_~y~0 50))) (or (and (< main_~b~0 main_~a~0) (or (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (not (<= (* main_~b~0 3) main_~c~0)) (<= (* main_~b~0 4) main_~c~0)) (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0))) (<= 1 main_~x~0) .cse0 (or (= .cse1 (+ (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0))) (<= main_~b~0 main_~c~0)) .cse2 .cse3) (and (= main_~s~0 1) .cse0 (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse2 (= main_~a~0 main_~x~0) .cse3 (= main_~p~0 1))))) [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L35-3(lines 35 73) the Hoare annotation is: (let ((.cse0 (* main_~q~0 main_~x~0)) (.cse1 (* main_~y~0 main_~s~0))) (let ((.cse2 (= main_~b~0 (+ .cse0 .cse1)))) (and (< main_~b~0 main_~a~0) (<= 1 main_~x~0) (= (+ .cse0 main_~a~0 .cse1) (+ (* main_~y~0 main_~r~0) (* main_~p~0 main_~x~0))) (or .cse2 (= main_~b~0 0)) (or .cse2 (<= main_~b~0 main_~c~0)) (<= 1 main_~y~0) (<= main_~y~0 50)))) [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L36(lines 36 37) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L74(line 74) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L42-2(lines 42 62) the Hoare annotation is: (let ((.cse14 (* main_~y~0 main_~r~0)) (.cse15 (* main_~p~0 main_~x~0))) (let ((.cse11 (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0)))) (.cse12 (<= 1 main_~x~0)) (.cse0 (= main_~k~0 0)) (.cse10 (= main_~v~0 (* main_~d~0 main_~b~0))) (.cse1 (= main_~s~0 1)) (.cse2 (= main_~a~0 (+ .cse14 .cse15))) (.cse13 (= (+ (* main_~d~0 main_~y~0 main_~s~0) (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0) (* main_~d~0 main_~q~0 main_~x~0)) (+ .cse14 main_~v~0 .cse15))) (.cse3 (<= 1 main_~a~0)) (.cse4 (= main_~b~0 main_~y~0)) (.cse5 (= main_~q~0 0)) (.cse6 (<= 1 main_~y~0)) (.cse7 (= main_~a~0 main_~x~0)) (.cse8 (<= main_~y~0 50)) (.cse9 (= main_~p~0 1))) (or (and .cse0 .cse1 .cse2 .cse3 .cse4 .cse5 .cse6 .cse7 (= main_~c~0 main_~x~0) .cse8 .cse9) (and (< main_~b~0 main_~a~0) .cse10 .cse11 .cse12 .cse2 .cse13 .cse6 .cse8) (and (= main_~c~0 main_~a~0) .cse11 .cse12 .cse0 .cse2 (< main_~b~0 main_~c~0) .cse6 .cse8) (and .cse10 .cse1 .cse2 .cse13 .cse3 .cse4 .cse5 .cse6 .cse7 .cse8 .cse9)))) [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 18 76) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L42-3(lines 42 62) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L43(lines 43 44) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 18 76) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L49-2(lines 49 59) the Hoare annotation is: (let ((.cse4 (* main_~y~0 main_~r~0)) (.cse5 (* main_~p~0 main_~x~0))) (let ((.cse0 (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0)))) (.cse1 (= main_~a~0 (+ .cse4 .cse5))) (.cse2 (<= 1 main_~y~0)) (.cse3 (<= main_~y~0 50))) (or (and (< main_~b~0 main_~a~0) (= main_~v~0 (* main_~d~0 main_~b~0)) .cse0 (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0))) (<= 1 main_~x~0) .cse1 .cse2 .cse3) (and .cse0 (= main_~s~0 1) .cse1 (= (+ (* main_~d~0 main_~y~0 main_~s~0) (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0) (* main_~d~0 main_~q~0 main_~x~0)) (+ .cse4 main_~v~0 .cse5)) (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse2 (= main_~a~0 main_~x~0) .cse3 (= main_~p~0 1))))) [2022-03-20 10:30:44,349 INFO L882 garLoopResultBuilder]: For program point L49-3(lines 49 59) no Hoare annotation was computed. [2022-03-20 10:30:44,349 INFO L878 garLoopResultBuilder]: At program point L50(line 50) the Hoare annotation is: (let ((.cse4 (* main_~y~0 main_~r~0)) (.cse5 (* main_~p~0 main_~x~0))) (let ((.cse0 (= main_~a~0 (+ .cse4 .cse5))) (.cse1 (= (+ (* main_~d~0 main_~y~0 main_~s~0) (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0) (* main_~d~0 main_~q~0 main_~x~0)) (+ .cse4 main_~v~0 .cse5))) (.cse2 (<= 1 main_~y~0)) (.cse3 (<= main_~y~0 50))) (or (and (< main_~b~0 main_~a~0) (= main_~v~0 (* main_~d~0 main_~b~0)) (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0))) (<= 1 main_~x~0) .cse0 .cse1 .cse2 .cse3) (and (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (= main_~s~0 1) .cse0 .cse1 (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse2 (= main_~a~0 main_~x~0) .cse3 (= main_~p~0 1))))) [2022-03-20 10:30:44,350 INFO L878 garLoopResultBuilder]: At program point L50-1(line 50) the Hoare annotation is: (let ((.cse4 (* main_~y~0 main_~r~0)) (.cse5 (* main_~p~0 main_~x~0))) (let ((.cse0 (= main_~a~0 (+ .cse4 .cse5))) (.cse1 (= (+ (* main_~d~0 main_~y~0 main_~s~0) (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0) (* main_~d~0 main_~q~0 main_~x~0)) (+ .cse4 main_~v~0 .cse5))) (.cse2 (<= 1 main_~y~0)) (.cse3 (<= main_~y~0 50))) (or (and (< main_~b~0 main_~a~0) (= main_~v~0 (* main_~d~0 main_~b~0)) (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0))) (<= 1 main_~x~0) .cse0 .cse1 .cse2 .cse3) (and (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (= main_~s~0 1) .cse0 .cse1 (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse2 (= main_~a~0 main_~x~0) .cse3 (= main_~p~0 1))))) [2022-03-20 10:30:44,350 INFO L878 garLoopResultBuilder]: At program point L51(line 51) the Hoare annotation is: (let ((.cse4 (* main_~y~0 main_~r~0)) (.cse5 (* main_~p~0 main_~x~0))) (let ((.cse0 (= main_~a~0 (+ .cse4 .cse5))) (.cse1 (= (+ (* main_~d~0 main_~y~0 main_~s~0) (* main_~k~0 main_~y~0 main_~s~0) main_~c~0 (* main_~q~0 main_~k~0 main_~x~0) (* main_~d~0 main_~q~0 main_~x~0)) (+ .cse4 main_~v~0 .cse5))) (.cse2 (<= 1 main_~y~0)) (.cse3 (<= main_~y~0 50))) (or (and (< main_~b~0 main_~a~0) (= main_~v~0 (* main_~d~0 main_~b~0)) (= main_~b~0 (+ (* main_~q~0 main_~x~0) (* main_~y~0 main_~s~0))) (<= 1 main_~x~0) .cse0 .cse1 .cse2 .cse3) (and (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (= main_~s~0 1) .cse0 .cse1 (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse2 (= main_~a~0 main_~x~0) .cse3 (= main_~p~0 1))))) [2022-03-20 10:30:44,350 INFO L878 garLoopResultBuilder]: At program point L52(line 52) the Hoare annotation is: (let ((.cse4 (* main_~y~0 main_~r~0)) (.cse5 (* main_~p~0 main_~x~0))) (let ((.cse6 (= main_~a~0 (+ .cse4 .cse5))) (.cse7 (* main_~d~0 main_~y~0 main_~s~0)) (.cse2 (* main_~k~0 main_~y~0 main_~s~0)) (.cse3 (* main_~q~0 main_~k~0 main_~x~0)) (.cse8 (* main_~d~0 main_~q~0 main_~x~0)) (.cse9 (<= 1 main_~y~0)) (.cse10 (<= main_~y~0 50))) (or (let ((.cse1 (* main_~q~0 main_~x~0)) (.cse0 (* main_~y~0 main_~s~0))) (and (< main_~b~0 main_~a~0) (= main_~v~0 (* main_~d~0 main_~b~0)) (= (+ (* 2 .cse0) (* .cse1 2) .cse2 main_~c~0 .cse3) (+ .cse4 .cse5 (* main_~b~0 2))) (= main_~b~0 (+ .cse1 .cse0)) (<= 1 main_~x~0) .cse6 (or (not (= main_~c~0 main_~v~0)) (= (+ .cse4 main_~b~0 .cse5) (+ .cse1 .cse7 .cse2 .cse3 .cse0 .cse8))) .cse9 .cse10)) (and (= main_~a~0 (+ main_~c~0 (* main_~b~0 main_~k~0))) (= main_~s~0 1) .cse6 (= (+ .cse7 .cse2 main_~c~0 .cse3 .cse8) (+ .cse4 main_~v~0 .cse5)) (<= 1 main_~a~0) (= main_~b~0 main_~y~0) (= main_~q~0 0) .cse9 (= main_~a~0 main_~x~0) .cse10 (= main_~p~0 1))))) [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point L53(lines 49 59) no Hoare annotation was computed. [2022-03-20 10:30:44,350 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 10 16) the Hoare annotation is: true [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point L11(lines 11 14) no Hoare annotation was computed. [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point L12(lines 12 13) no Hoare annotation was computed. [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point L11-2(lines 10 16) no Hoare annotation was computed. [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 13) no Hoare annotation was computed. [2022-03-20 10:30:44,350 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 10 16) no Hoare annotation was computed. [2022-03-20 10:30:44,352 INFO L719 BasicCegarLoop]: Path program histogram: [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 10:30:44,353 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-20 10:30:44,383 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 10:30:44 BasicIcfg [2022-03-20 10:30:44,383 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-20 10:30:44,383 INFO L158 Benchmark]: Toolchain (without parser) took 484522.16ms. Allocated memory was 221.2MB in the beginning and 502.3MB in the end (delta: 281.0MB). Free memory was 170.1MB in the beginning and 284.1MB in the end (delta: -114.0MB). Peak memory consumption was 279.2MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,383 INFO L158 Benchmark]: CDTParser took 0.08ms. Allocated memory is still 221.2MB. Free memory is still 186.5MB. There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 10:30:44,384 INFO L158 Benchmark]: CACSL2BoogieTranslator took 215.55ms. Allocated memory is still 221.2MB. Free memory was 170.0MB in the beginning and 198.3MB in the end (delta: -28.4MB). Peak memory consumption was 12.7MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,384 INFO L158 Benchmark]: Boogie Preprocessor took 18.65ms. Allocated memory is still 221.2MB. Free memory was 198.3MB in the beginning and 196.8MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,384 INFO L158 Benchmark]: RCFGBuilder took 221.35ms. Allocated memory is still 221.2MB. Free memory was 196.8MB in the beginning and 185.5MB in the end (delta: 11.3MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,384 INFO L158 Benchmark]: IcfgTransformer took 15.02ms. Allocated memory is still 221.2MB. Free memory was 185.5MB in the beginning and 183.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,384 INFO L158 Benchmark]: TraceAbstraction took 484047.98ms. Allocated memory was 221.2MB in the beginning and 502.3MB in the end (delta: 281.0MB). Free memory was 183.7MB in the beginning and 284.1MB in the end (delta: -100.5MB). Peak memory consumption was 292.8MB. Max. memory is 8.0GB. [2022-03-20 10:30:44,385 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.08ms. Allocated memory is still 221.2MB. Free memory is still 186.5MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 215.55ms. Allocated memory is still 221.2MB. Free memory was 170.0MB in the beginning and 198.3MB in the end (delta: -28.4MB). Peak memory consumption was 12.7MB. Max. memory is 8.0GB. * Boogie Preprocessor took 18.65ms. Allocated memory is still 221.2MB. Free memory was 198.3MB in the beginning and 196.8MB in the end (delta: 1.6MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 221.35ms. Allocated memory is still 221.2MB. Free memory was 196.8MB in the beginning and 185.5MB in the end (delta: 11.3MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * IcfgTransformer took 15.02ms. Allocated memory is still 221.2MB. Free memory was 185.5MB in the beginning and 183.9MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * TraceAbstraction took 484047.98ms. Allocated memory was 221.2MB in the beginning and 502.3MB in the end (delta: 281.0MB). Free memory was 183.7MB in the beginning and 284.1MB in the end (delta: -100.5MB). Peak memory consumption was 292.8MB. 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: 484.0s, OverallIterations: 18, TraceHistogramMax: 11, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 53.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 403.5s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 3 mSolverCounterUnknown, 1247 SdHoareTripleChecker+Valid, 31.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 1183 mSDsluCounter, 5420 SdHoareTripleChecker+Invalid, 31.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 66 IncrementalHoareTripleChecker+Unchecked, 4501 mSDsCounter, 1650 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 5174 IncrementalHoareTripleChecker+Invalid, 6893 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 1650 mSolverCounterUnsat, 919 mSDtfsCounter, 5174 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1972 GetRequests, 1626 SyntacticMatches, 18 SemanticMatches, 328 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2182 ImplicationChecksByTransitivity, 23.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=823occurred in iteration=17, InterpolantAutomatonStates: 252, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.9s AutomataMinimizationTime, 18 MinimizatonAttempts, 498 StatesRemovedByMinimization, 15 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 18 LocationsWithAnnotation, 565 PreInvPairs, 1178 NumberOfFragments, 1081 HoareAnnotationTreeSize, 565 FomulaSimplifications, 410915 FormulaSimplificationTreeSizeReduction, 41.1s HoareSimplificationTime, 18 FomulaSimplificationsInter, 765880 FormulaSimplificationTreeSizeReductionInter, 362.4s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 21.1s InterpolantComputationTime, 1063 NumberOfCodeBlocks, 1042 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 1806 ConstructedInterpolants, 3 QuantifiedInterpolants, 9337 SizeOfPredicates, 100 NumberOfNonLiveVariables, 2865 ConjunctsInSsa, 472 ConjunctsInUnsatCore, 30 InterpolantComputations, 9 PerfectInterpolantSequences, 2231/2489 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 - InvariantResult [Line: 49]: Loop Invariant Derived loop invariant: (((((((b < a && v == d * b) && a == c + b * k) && b == q * x + y * s) && 1 <= x) && a == y * r + p * x) && 1 <= y) && y <= 50) || ((((((((((a == c + b * k && s == 1) && a == y * r + p * x) && d * y * s + k * y * s + c + q * k * x + d * q * x == y * r + v + p * x) && 1 <= a) && b == y) && q == 0) && 1 <= y) && a == x) && y <= 50) && p == 1) - InvariantResult [Line: 35]: Loop Invariant Derived loop invariant: (((((((b < a && ((a == c + b * k || !(b * 3 <= c)) || b * 4 <= c)) && b == q * x + y * s) && 1 <= x) && a == y * r + p * x) && (y * r + p * x == k * y * s + c + q * k * x || b <= c)) && 1 <= y) && y <= 50) || ((((((((s == 1 && a == y * r + p * x) && 1 <= a) && b == y) && q == 0) && 1 <= y) && a == x) && y <= 50) && p == 1) - InvariantResult [Line: 42]: Loop Invariant Derived loop invariant: ((((((((((((k == 0 && s == 1) && a == y * r + p * x) && 1 <= a) && b == y) && q == 0) && 1 <= y) && a == x) && c == x) && y <= 50) && p == 1) || (((((((b < a && v == d * b) && b == q * x + y * s) && 1 <= x) && a == y * r + p * x) && d * y * s + k * y * s + c + q * k * x + d * q * x == y * r + v + p * x) && 1 <= y) && y <= 50)) || (((((((c == a && b == q * x + y * s) && 1 <= x) && k == 0) && a == y * r + p * x) && b < c) && 1 <= y) && y <= 50)) || ((((((((((v == d * b && s == 1) && a == y * r + p * x) && d * y * s + k * y * s + c + q * k * x + d * q * x == y * r + v + p * x) && 1 <= a) && b == y) && q == 0) && 1 <= y) && a == x) && y <= 50) && p == 1) RESULT: Ultimate proved your program to be correct! [2022-03-20 10:30:44,470 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...