/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/hard2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 09:10:47,191 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 09:10:47,192 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 09:10:47,221 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 09:10:47,222 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 09:10:47,223 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 09:10:47,226 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 09:10:47,230 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 09:10:47,232 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 09:10:47,235 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 09:10:47,236 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 09:10:47,237 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 09:10:47,237 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 09:10:47,239 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 09:10:47,239 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 09:10:47,240 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 09:10:47,240 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 09:10:47,241 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 09:10:47,244 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 09:10:47,248 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 09:10:47,249 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 09:10:47,250 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 09:10:47,250 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 09:10:47,251 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 09:10:47,252 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 09:10:47,256 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 09:10:47,256 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 09:10:47,257 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 09:10:47,257 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 09:10:47,257 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 09:10:47,258 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 09:10:47,259 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 09:10:47,260 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 09:10:47,260 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 09:10:47,261 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 09:10:47,261 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 09:10:47,261 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 09:10:47,262 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 09:10:47,262 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 09:10:47,262 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 09:10:47,263 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 09:10:47,264 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 09:10:47,264 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 09:10:47,284 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 09:10:47,284 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 09:10:47,285 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-03-20 09:10:47,285 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-03-20 09:10:47,286 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-03-20 09:10:47,286 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-03-20 09:10:47,286 INFO L138 SettingsManager]: * Use SBE=true [2022-03-20 09:10:47,286 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 09:10:47,286 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 09:10:47,287 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 09:10:47,288 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 09:10:47,288 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-03-20 09:10:47,288 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-03-20 09:10:47,289 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 09:10:47,289 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-03-20 09:10:47,289 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-03-20 09:10:47,289 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-03-20 09:10:47,290 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 09:10:47,466 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 09:10:47,495 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 09:10:47,497 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 09:10:47,498 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 09:10:47,498 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 09:10:47,499 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench/hard2.c [2022-03-20 09:10:47,553 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3058bd842/2bee0a4ff058486eaa683a9f8fc7c253/FLAGda718ee05 [2022-03-20 09:10:47,900 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 09:10:47,900 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench/hard2.c [2022-03-20 09:10:47,904 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3058bd842/2bee0a4ff058486eaa683a9f8fc7c253/FLAGda718ee05 [2022-03-20 09:10:47,912 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3058bd842/2bee0a4ff058486eaa683a9f8fc7c253 [2022-03-20 09:10:47,914 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 09:10:47,915 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-03-20 09:10:47,916 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 09:10:47,916 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 09:10:47,918 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 09:10:47,919 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 09:10:47" (1/1) ... [2022-03-20 09:10:47,919 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6890f311 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:47, skipping insertion in model container [2022-03-20 09:10:47,920 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 09:10:47" (1/1) ... [2022-03-20 09:10:47,924 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 09:10:47,961 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 09:10:48,058 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/hard2.c[526,539] [2022-03-20 09:10:48,087 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 09:10:48,092 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 09:10:48,101 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/hard2.c[526,539] [2022-03-20 09:10:48,109 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 09:10:48,122 INFO L208 MainTranslator]: Completed translation [2022-03-20 09:10:48,122 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48 WrapperNode [2022-03-20 09:10:48,122 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 09:10:48,132 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 09:10:48,132 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 09:10:48,132 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 09:10:48,139 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,139 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,148 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,148 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,151 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,154 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,160 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,162 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 09:10:48,163 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 09:10:48,163 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 09:10:48,163 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 09:10:48,163 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 09:10:48,179 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:48,189 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 09:10:48,192 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 09:10:48,221 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 09:10:48,221 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 09:10:48,221 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 09:10:48,222 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 09:10:48,222 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 09:10:48,222 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 09:10:48,222 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 09:10:48,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 09:10:48,223 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 09:10:48,223 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 09:10:48,223 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 09:10:48,270 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 09:10:48,271 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 09:10:48,363 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 09:10:48,367 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 09:10:48,368 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 09:10:48,369 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 09:10:48 BoogieIcfgContainer [2022-03-20 09:10:48,369 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 09:10:48,370 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-03-20 09:10:48,370 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-03-20 09:10:48,371 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-03-20 09:10:48,373 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 09:10:48" (1/1) ... [2022-03-20 09:10:48,375 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-03-20 09:10:48,386 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 09:10:48 BasicIcfg [2022-03-20 09:10:48,386 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-03-20 09:10:48,388 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 09:10:48,388 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 09:10:48,390 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 09:10:48,390 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 09:10:47" (1/4) ... [2022-03-20 09:10:48,390 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34d8a2cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 09:10:48, skipping insertion in model container [2022-03-20 09:10:48,390 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:10:48" (2/4) ... [2022-03-20 09:10:48,391 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34d8a2cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 09:10:48, skipping insertion in model container [2022-03-20 09:10:48,391 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 09:10:48" (3/4) ... [2022-03-20 09:10:48,391 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34d8a2cc and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 09:10:48, skipping insertion in model container [2022-03-20 09:10:48,391 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 20.03 09:10:48" (4/4) ... [2022-03-20 09:10:48,392 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2.cqvasr [2022-03-20 09:10:48,396 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-03-20 09:10:48,396 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 09:10:48,429 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 09:10:48,441 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 09:10:48,441 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 09:10:48,453 INFO L276 IsEmpty]: Start isEmpty. Operand has 29 states, 15 states have (on average 1.6) internal successors, (24), 16 states have internal predecessors, (24), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 09:10:48,457 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 12 [2022-03-20 09:10:48,457 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:48,458 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:48,458 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:48,462 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:48,462 INFO L85 PathProgramCache]: Analyzing trace with hash -1059151250, now seen corresponding path program 1 times [2022-03-20 09:10:48,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:48,469 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1977364011] [2022-03-20 09:10:48,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:48,470 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:48,536 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:48,608 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 09:10:48,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:48,617 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 09:10:48,618 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:48,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1977364011] [2022-03-20 09:10:48,618 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1977364011] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 09:10:48,619 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 09:10:48,619 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 09:10:48,620 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [684727159] [2022-03-20 09:10:48,620 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:48,623 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 09:10:48,624 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:48,642 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 09:10:48,642 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 09:10:48,644 INFO L87 Difference]: Start difference. First operand has 29 states, 15 states have (on average 1.6) internal successors, (24), 16 states have internal predecessors, (24), 9 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 09:10:48,874 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:48,874 INFO L93 Difference]: Finished difference Result 66 states and 111 transitions. [2022-03-20 09:10:48,876 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 09:10:48,876 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 11 [2022-03-20 09:10:48,877 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:48,881 INFO L225 Difference]: With dead ends: 66 [2022-03-20 09:10:48,881 INFO L226 Difference]: Without dead ends: 35 [2022-03-20 09:10:48,884 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 09:10:48,886 INFO L913 BasicCegarLoop]: 27 mSDtfsCounter, 39 mSDsluCounter, 21 mSDsCounter, 0 mSdLazyCounter, 107 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 135 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 107 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:48,886 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [43 Valid, 48 Invalid, 135 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 107 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 09:10:48,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-03-20 09:10:48,938 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 28. [2022-03-20 09:10:48,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 28 states, 15 states have (on average 1.2666666666666666) internal successors, (19), 16 states have internal predecessors, (19), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 09:10:48,942 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 28 states to 28 states and 35 transitions. [2022-03-20 09:10:48,944 INFO L78 Accepts]: Start accepts. Automaton has 28 states and 35 transitions. Word has length 11 [2022-03-20 09:10:48,944 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:48,944 INFO L478 AbstractCegarLoop]: Abstraction has 28 states and 35 transitions. [2022-03-20 09:10:48,944 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 4 states have internal predecessors, (7), 2 states have call successors, (3), 3 states have call predecessors, (3), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2022-03-20 09:10:48,945 INFO L276 IsEmpty]: Start isEmpty. Operand 28 states and 35 transitions. [2022-03-20 09:10:48,945 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 17 [2022-03-20 09:10:48,945 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:48,946 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:48,946 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 09:10:48,946 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:48,949 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:48,949 INFO L85 PathProgramCache]: Analyzing trace with hash -2043934920, now seen corresponding path program 1 times [2022-03-20 09:10:48,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:48,950 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1200943223] [2022-03-20 09:10:48,950 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:48,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:48,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:49,040 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 09:10:49,043 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:49,048 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2022-03-20 09:10:49,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:49,054 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 09:10:49,055 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:49,055 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1200943223] [2022-03-20 09:10:49,055 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1200943223] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 09:10:49,055 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 09:10:49,055 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 09:10:49,056 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1736868923] [2022-03-20 09:10:49,057 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:49,059 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 09:10:49,060 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:49,063 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 09:10:49,064 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 09:10:49,065 INFO L87 Difference]: Start difference. First operand 28 states and 35 transitions. Second operand has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 09:10:49,197 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:49,198 INFO L93 Difference]: Finished difference Result 41 states and 52 transitions. [2022-03-20 09:10:49,198 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 09:10:49,198 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 16 [2022-03-20 09:10:49,199 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:49,200 INFO L225 Difference]: With dead ends: 41 [2022-03-20 09:10:49,200 INFO L226 Difference]: Without dead ends: 39 [2022-03-20 09:10:49,200 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 09:10:49,201 INFO L913 BasicCegarLoop]: 23 mSDtfsCounter, 28 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 25 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 40 SdHoareTripleChecker+Invalid, 121 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 25 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:49,201 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 40 Invalid, 121 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [25 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 09:10:49,202 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 39 states. [2022-03-20 09:10:49,206 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 39 to 32. [2022-03-20 09:10:49,207 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.2222222222222223) internal successors, (22), 19 states have internal predecessors, (22), 9 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-03-20 09:10:49,207 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2022-03-20 09:10:49,208 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 38 transitions. Word has length 16 [2022-03-20 09:10:49,208 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:49,208 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 38 transitions. [2022-03-20 09:10:49,208 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 09:10:49,208 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 38 transitions. [2022-03-20 09:10:49,208 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2022-03-20 09:10:49,209 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:49,209 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:49,209 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 09:10:49,209 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:49,210 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:49,210 INFO L85 PathProgramCache]: Analyzing trace with hash 106953131, now seen corresponding path program 1 times [2022-03-20 09:10:49,210 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:49,210 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1472324847] [2022-03-20 09:10:49,210 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:49,211 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:49,222 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:49,222 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [453401490] [2022-03-20 09:10:49,223 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:49,223 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:49,223 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:49,264 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 09:10:49,265 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 09:10:49,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:49,321 INFO L263 TraceCheckSpWp]: Trace formula consists of 81 conjuncts, 9 conjunts are in the unsatisfiable core [2022-03-20 09:10:49,325 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:49,425 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 09:10:49,425 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 09:10:49,425 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:49,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1472324847] [2022-03-20 09:10:49,426 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:49,426 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [453401490] [2022-03-20 09:10:49,426 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [453401490] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 09:10:49,426 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 09:10:49,426 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 09:10:49,426 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1396040315] [2022-03-20 09:10:49,426 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:49,427 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 09:10:49,427 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:49,427 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 09:10:49,427 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 09:10:49,427 INFO L87 Difference]: Start difference. First operand 32 states and 38 transitions. Second operand has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 09:10:49,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:49,466 INFO L93 Difference]: Finished difference Result 60 states and 78 transitions. [2022-03-20 09:10:49,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 09:10:49,467 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 21 [2022-03-20 09:10:49,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:49,467 INFO L225 Difference]: With dead ends: 60 [2022-03-20 09:10:49,467 INFO L226 Difference]: Without dead ends: 46 [2022-03-20 09:10:49,468 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 17 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 09:10:49,469 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 8 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 115 SdHoareTripleChecker+Invalid, 39 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:49,469 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 115 Invalid, 39 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:10:49,470 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-03-20 09:10:49,475 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 46. [2022-03-20 09:10:49,475 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 25 states have (on average 1.2) internal successors, (30), 27 states have internal predecessors, (30), 15 states have call successors, (15), 6 states have call predecessors, (15), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-03-20 09:10:49,476 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 57 transitions. [2022-03-20 09:10:49,476 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 57 transitions. Word has length 21 [2022-03-20 09:10:49,476 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:49,477 INFO L478 AbstractCegarLoop]: Abstraction has 46 states and 57 transitions. [2022-03-20 09:10:49,477 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.0) internal successors, (10), 4 states have internal predecessors, (10), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 09:10:49,477 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 57 transitions. [2022-03-20 09:10:49,477 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 09:10:49,477 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:49,478 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:49,502 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-03-20 09:10:49,702 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:49,702 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:49,703 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:49,703 INFO L85 PathProgramCache]: Analyzing trace with hash 606156080, now seen corresponding path program 1 times [2022-03-20 09:10:49,703 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:49,703 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1146826088] [2022-03-20 09:10:49,703 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:49,703 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:49,720 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:49,720 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [933658103] [2022-03-20 09:10:49,720 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:49,720 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:49,721 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:49,727 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 09:10:49,756 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 09:10:49,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:49,762 INFO L263 TraceCheckSpWp]: Trace formula consists of 92 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 09:10:49,763 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:49,856 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 09:10:49,857 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 09:10:49,857 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:49,857 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1146826088] [2022-03-20 09:10:49,857 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:49,857 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [933658103] [2022-03-20 09:10:49,865 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [933658103] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 09:10:49,867 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 09:10:49,867 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 09:10:49,868 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [845294737] [2022-03-20 09:10:49,868 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:49,868 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 09:10:49,868 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:49,869 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 09:10:49,869 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 09:10:49,870 INFO L87 Difference]: Start difference. First operand 46 states and 57 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 09:10:49,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:49,910 INFO L93 Difference]: Finished difference Result 59 states and 74 transitions. [2022-03-20 09:10:49,910 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 09:10:49,911 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-03-20 09:10:49,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:49,913 INFO L225 Difference]: With dead ends: 59 [2022-03-20 09:10:49,913 INFO L226 Difference]: Without dead ends: 52 [2022-03-20 09:10:49,913 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 09:10:49,916 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 9 mSDsluCounter, 64 mSDsCounter, 0 mSdLazyCounter, 39 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 39 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:49,916 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 89 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 39 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:10:49,918 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-03-20 09:10:49,927 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 51. [2022-03-20 09:10:49,928 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 29 states have (on average 1.206896551724138) internal successors, (35), 31 states have internal predecessors, (35), 15 states have call successors, (15), 7 states have call predecessors, (15), 6 states have return successors, (13), 12 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 09:10:49,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 63 transitions. [2022-03-20 09:10:49,932 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 63 transitions. Word has length 28 [2022-03-20 09:10:49,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:49,933 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 63 transitions. [2022-03-20 09:10:49,933 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 09:10:49,933 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 63 transitions. [2022-03-20 09:10:49,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-03-20 09:10:49,934 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:49,934 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:49,951 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 09:10:50,147 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2022-03-20 09:10:50,149 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:50,150 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:50,150 INFO L85 PathProgramCache]: Analyzing trace with hash 312970699, now seen corresponding path program 1 times [2022-03-20 09:10:50,150 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:50,150 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1093167732] [2022-03-20 09:10:50,150 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:50,150 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:50,157 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:50,157 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1401259327] [2022-03-20 09:10:50,157 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:50,157 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:50,157 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:50,165 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 09:10:50,166 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 09:10:50,215 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:50,216 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 09:10:50,218 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:50,361 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-03-20 09:10:50,361 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:10:50,446 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-03-20 09:10:50,447 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:50,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1093167732] [2022-03-20 09:10:50,447 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:50,447 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1401259327] [2022-03-20 09:10:50,447 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1401259327] provided 1 perfect and 1 imperfect interpolant sequences [2022-03-20 09:10:50,447 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-03-20 09:10:50,447 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-03-20 09:10:50,447 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [717682056] [2022-03-20 09:10:50,447 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:50,448 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 09:10:50,448 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:50,448 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 09:10:50,448 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-03-20 09:10:50,448 INFO L87 Difference]: Start difference. First operand 51 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 09:10:50,497 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:50,497 INFO L93 Difference]: Finished difference Result 63 states and 78 transitions. [2022-03-20 09:10:50,498 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 09:10:50,498 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 38 [2022-03-20 09:10:50,498 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:50,500 INFO L225 Difference]: With dead ends: 63 [2022-03-20 09:10:50,500 INFO L226 Difference]: Without dead ends: 61 [2022-03-20 09:10:50,501 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 76 GetRequests, 68 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 09:10:50,501 INFO L913 BasicCegarLoop]: 30 mSDtfsCounter, 8 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 99 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:50,502 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 99 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:10:50,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2022-03-20 09:10:50,517 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 58. [2022-03-20 09:10:50,517 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 36 states have internal predecessors, (39), 17 states have call successors, (17), 8 states have call predecessors, (17), 7 states have return successors, (15), 13 states have call predecessors, (15), 15 states have call successors, (15) [2022-03-20 09:10:50,518 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 71 transitions. [2022-03-20 09:10:50,518 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 71 transitions. Word has length 38 [2022-03-20 09:10:50,518 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:50,519 INFO L478 AbstractCegarLoop]: Abstraction has 58 states and 71 transitions. [2022-03-20 09:10:50,519 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 09:10:50,519 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 71 transitions. [2022-03-20 09:10:50,520 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2022-03-20 09:10:50,520 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:50,520 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:50,540 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 09:10:50,735 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:50,736 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:50,736 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:50,736 INFO L85 PathProgramCache]: Analyzing trace with hash 1500982750, now seen corresponding path program 1 times [2022-03-20 09:10:50,736 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:50,736 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1960466097] [2022-03-20 09:10:50,736 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:50,737 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:50,745 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:50,745 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1760388193] [2022-03-20 09:10:50,745 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:50,745 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:50,745 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:50,752 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 09:10:50,753 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 09:10:50,791 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:50,793 INFO L263 TraceCheckSpWp]: Trace formula consists of 154 conjuncts, 25 conjunts are in the unsatisfiable core [2022-03-20 09:10:50,795 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:51,105 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 09:10:51,105 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:10:51,871 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-03-20 09:10:51,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:51,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1960466097] [2022-03-20 09:10:51,871 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:51,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1760388193] [2022-03-20 09:10:51,871 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1760388193] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:10:51,871 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:10:51,871 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-20 09:10:51,871 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [552507117] [2022-03-20 09:10:51,872 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:10:51,872 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 09:10:51,872 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:51,872 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 09:10:51,872 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-03-20 09:10:51,873 INFO L87 Difference]: Start difference. First operand 58 states and 71 transitions. Second operand has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-20 09:10:56,547 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:56,547 INFO L93 Difference]: Finished difference Result 148 states and 204 transitions. [2022-03-20 09:10:56,548 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-03-20 09:10:56,548 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) Word has length 58 [2022-03-20 09:10:56,548 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:56,550 INFO L225 Difference]: With dead ends: 148 [2022-03-20 09:10:56,550 INFO L226 Difference]: Without dead ends: 119 [2022-03-20 09:10:56,550 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 104 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-03-20 09:10:56,551 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 34 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 226 mSolverCounterSat, 67 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 40 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 293 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 67 IncrementalHoareTripleChecker+Valid, 226 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:56,551 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [40 Valid, 283 Invalid, 293 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [67 Valid, 226 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2022-03-20 09:10:56,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 119 states. [2022-03-20 09:10:56,562 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 119 to 107. [2022-03-20 09:10:56,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 63 states have (on average 1.2380952380952381) internal successors, (78), 67 states have internal predecessors, (78), 32 states have call successors, (32), 12 states have call predecessors, (32), 11 states have return successors, (30), 27 states have call predecessors, (30), 30 states have call successors, (30) [2022-03-20 09:10:56,564 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 140 transitions. [2022-03-20 09:10:56,564 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 140 transitions. Word has length 58 [2022-03-20 09:10:56,564 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:56,564 INFO L478 AbstractCegarLoop]: Abstraction has 107 states and 140 transitions. [2022-03-20 09:10:56,564 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.6) internal successors, (26), 9 states have internal predecessors, (26), 7 states have call successors, (20), 2 states have call predecessors, (20), 1 states have return successors, (17), 5 states have call predecessors, (17), 5 states have call successors, (17) [2022-03-20 09:10:56,565 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 140 transitions. [2022-03-20 09:10:56,575 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-03-20 09:10:56,575 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:56,575 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:56,610 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 09:10:56,794 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:56,794 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:56,794 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:56,795 INFO L85 PathProgramCache]: Analyzing trace with hash -781577916, now seen corresponding path program 1 times [2022-03-20 09:10:56,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:56,795 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1585440596] [2022-03-20 09:10:56,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:56,795 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:56,802 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:56,802 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2063679343] [2022-03-20 09:10:56,802 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:56,802 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:56,802 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:56,803 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 09:10:56,805 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 09:10:56,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:56,842 INFO L263 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 37 conjunts are in the unsatisfiable core [2022-03-20 09:10:56,844 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:57,208 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 66 proven. 11 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-03-20 09:10:57,208 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:10:57,430 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-03-20 09:10:57,431 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:57,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1585440596] [2022-03-20 09:10:57,431 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:57,431 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2063679343] [2022-03-20 09:10:57,431 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2063679343] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:10:57,431 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:10:57,431 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2022-03-20 09:10:57,431 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1637318677] [2022-03-20 09:10:57,431 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:10:57,432 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-03-20 09:10:57,432 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:57,432 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-03-20 09:10:57,432 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2022-03-20 09:10:57,432 INFO L87 Difference]: Start difference. First operand 107 states and 140 transitions. Second operand has 15 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2022-03-20 09:10:57,729 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:57,729 INFO L93 Difference]: Finished difference Result 163 states and 213 transitions. [2022-03-20 09:10:57,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-03-20 09:10:57,730 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) Word has length 69 [2022-03-20 09:10:57,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:57,731 INFO L225 Difference]: With dead ends: 163 [2022-03-20 09:10:57,731 INFO L226 Difference]: Without dead ends: 109 [2022-03-20 09:10:57,732 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 121 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2022-03-20 09:10:57,732 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 38 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 254 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 306 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 254 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:57,732 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [51 Valid, 141 Invalid, 306 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 254 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 09:10:57,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2022-03-20 09:10:57,742 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 95. [2022-03-20 09:10:57,742 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 57 states have (on average 1.1754385964912282) internal successors, (67), 60 states have internal predecessors, (67), 25 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (23), 21 states have call predecessors, (23), 23 states have call successors, (23) [2022-03-20 09:10:57,743 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 115 transitions. [2022-03-20 09:10:57,743 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 115 transitions. Word has length 69 [2022-03-20 09:10:57,743 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:57,743 INFO L478 AbstractCegarLoop]: Abstraction has 95 states and 115 transitions. [2022-03-20 09:10:57,743 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 2.5833333333333335) internal successors, (31), 11 states have internal predecessors, (31), 7 states have call successors, (20), 2 states have call predecessors, (20), 2 states have return successors, (18), 7 states have call predecessors, (18), 5 states have call successors, (18) [2022-03-20 09:10:57,743 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 115 transitions. [2022-03-20 09:10:57,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2022-03-20 09:10:57,744 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:57,744 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:57,763 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 09:10:57,957 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:57,957 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:57,957 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:57,958 INFO L85 PathProgramCache]: Analyzing trace with hash -1979995209, now seen corresponding path program 1 times [2022-03-20 09:10:57,958 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:57,958 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [90898529] [2022-03-20 09:10:57,958 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:57,958 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:57,964 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:57,964 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1160804041] [2022-03-20 09:10:57,964 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:57,964 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:57,964 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:57,966 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 09:10:57,967 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 09:10:58,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:10:58,004 INFO L263 TraceCheckSpWp]: Trace formula consists of 187 conjuncts, 4 conjunts are in the unsatisfiable core [2022-03-20 09:10:58,005 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:58,142 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-03-20 09:10:58,142 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 09:10:58,142 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:10:58,142 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [90898529] [2022-03-20 09:10:58,142 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:10:58,142 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1160804041] [2022-03-20 09:10:58,142 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1160804041] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 09:10:58,142 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 09:10:58,143 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 09:10:58,143 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [215101250] [2022-03-20 09:10:58,143 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 09:10:58,143 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 09:10:58,143 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:10:58,143 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 09:10:58,144 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 09:10:58,144 INFO L87 Difference]: Start difference. First operand 95 states and 115 transitions. Second operand has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 09:10:58,180 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:10:58,181 INFO L93 Difference]: Finished difference Result 109 states and 130 transitions. [2022-03-20 09:10:58,181 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 09:10:58,181 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 78 [2022-03-20 09:10:58,182 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:10:58,182 INFO L225 Difference]: With dead ends: 109 [2022-03-20 09:10:58,182 INFO L226 Difference]: Without dead ends: 97 [2022-03-20 09:10:58,183 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-03-20 09:10:58,183 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 9 mSDsluCounter, 52 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 7 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 31 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 7 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:10:58,183 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 98 Invalid, 31 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [7 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:10:58,184 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 97 states. [2022-03-20 09:10:58,192 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 97 to 97. [2022-03-20 09:10:58,192 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 97 states, 59 states have (on average 1.152542372881356) internal successors, (68), 60 states have internal predecessors, (68), 25 states have call successors, (25), 13 states have call predecessors, (25), 12 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2022-03-20 09:10:58,193 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 97 states to 97 states and 116 transitions. [2022-03-20 09:10:58,193 INFO L78 Accepts]: Start accepts. Automaton has 97 states and 116 transitions. Word has length 78 [2022-03-20 09:10:58,193 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:10:58,193 INFO L478 AbstractCegarLoop]: Abstraction has 97 states and 116 transitions. [2022-03-20 09:10:58,194 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.8) internal successors, (19), 5 states have internal predecessors, (19), 5 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-03-20 09:10:58,194 INFO L276 IsEmpty]: Start isEmpty. Operand 97 states and 116 transitions. [2022-03-20 09:10:58,195 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 89 [2022-03-20 09:10:58,195 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:10:58,195 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:10:58,214 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 09:10:58,413 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:58,413 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:10:58,414 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:10:58,414 INFO L85 PathProgramCache]: Analyzing trace with hash -1650636816, now seen corresponding path program 2 times [2022-03-20 09:10:58,414 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:10:58,414 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1695506342] [2022-03-20 09:10:58,414 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:10:58,414 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:10:58,421 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:10:58,421 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1026749472] [2022-03-20 09:10:58,421 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 09:10:58,421 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:10:58,421 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:10:58,422 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 09:10:58,424 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 09:10:58,466 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 09:10:58,466 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 09:10:58,468 INFO L263 TraceCheckSpWp]: Trace formula consists of 216 conjuncts, 39 conjunts are in the unsatisfiable core [2022-03-20 09:10:58,470 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:10:58,953 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 09:10:58,953 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:11:21,076 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-03-20 09:11:21,076 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:11:21,077 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1695506342] [2022-03-20 09:11:21,077 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:11:21,077 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1026749472] [2022-03-20 09:11:21,077 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1026749472] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:11:21,077 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:11:21,077 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-03-20 09:11:21,077 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [615711387] [2022-03-20 09:11:21,077 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:11:21,078 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-03-20 09:11:21,078 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:11:21,078 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-03-20 09:11:21,078 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=179, Unknown=1, NotChecked=0, Total=240 [2022-03-20 09:11:21,078 INFO L87 Difference]: Start difference. First operand 97 states and 116 transitions. Second operand has 16 states, 16 states have (on average 2.25) internal successors, (36), 15 states have internal predecessors, (36), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-20 09:11:35,328 WARN L232 SmtUtils]: Spent 14.04s on a formula simplification. DAG size of input: 192 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-03-20 09:11:42,294 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 09:11:42,844 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:11:42,845 INFO L93 Difference]: Finished difference Result 222 states and 299 transitions. [2022-03-20 09:11:42,845 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-03-20 09:11:42,846 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.25) internal successors, (36), 15 states have internal predecessors, (36), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) Word has length 88 [2022-03-20 09:11:42,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:11:42,847 INFO L225 Difference]: With dead ends: 222 [2022-03-20 09:11:42,847 INFO L226 Difference]: Without dead ends: 171 [2022-03-20 09:11:42,848 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 180 GetRequests, 158 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 21.1s TimeCoverageRelationStatistics Valid=114, Invalid=305, Unknown=1, NotChecked=0, Total=420 [2022-03-20 09:11:42,848 INFO L913 BasicCegarLoop]: 55 mSDtfsCounter, 85 mSDsluCounter, 443 mSDsCounter, 0 mSdLazyCounter, 520 mSolverCounterSat, 191 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 96 SdHoareTripleChecker+Valid, 498 SdHoareTripleChecker+Invalid, 712 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 191 IncrementalHoareTripleChecker+Valid, 520 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.2s IncrementalHoareTripleChecker+Time [2022-03-20 09:11:42,848 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [96 Valid, 498 Invalid, 712 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [191 Valid, 520 Invalid, 1 Unknown, 0 Unchecked, 6.2s Time] [2022-03-20 09:11:42,849 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2022-03-20 09:11:42,864 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 160. [2022-03-20 09:11:42,864 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 160 states, 96 states have (on average 1.21875) internal successors, (117), 100 states have internal predecessors, (117), 48 states have call successors, (48), 16 states have call predecessors, (48), 15 states have return successors, (46), 43 states have call predecessors, (46), 46 states have call successors, (46) [2022-03-20 09:11:42,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 160 states to 160 states and 211 transitions. [2022-03-20 09:11:42,865 INFO L78 Accepts]: Start accepts. Automaton has 160 states and 211 transitions. Word has length 88 [2022-03-20 09:11:42,865 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:11:42,865 INFO L478 AbstractCegarLoop]: Abstraction has 160 states and 211 transitions. [2022-03-20 09:11:42,866 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.25) internal successors, (36), 15 states have internal predecessors, (36), 11 states have call successors, (30), 2 states have call predecessors, (30), 1 states have return successors, (27), 9 states have call predecessors, (27), 9 states have call successors, (27) [2022-03-20 09:11:42,866 INFO L276 IsEmpty]: Start isEmpty. Operand 160 states and 211 transitions. [2022-03-20 09:11:42,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 105 [2022-03-20 09:11:42,867 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:11:42,867 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:11:42,891 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 09:11:43,087 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:43,087 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:11:43,088 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:11:43,088 INFO L85 PathProgramCache]: Analyzing trace with hash 1538097783, now seen corresponding path program 1 times [2022-03-20 09:11:43,088 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:11:43,088 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1685203180] [2022-03-20 09:11:43,088 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:11:43,088 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:11:43,098 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:11:43,099 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [385261652] [2022-03-20 09:11:43,099 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:11:43,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:43,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:11:43,104 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 09:11:43,105 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 09:11:43,154 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 09:11:43,156 INFO L263 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 14 conjunts are in the unsatisfiable core [2022-03-20 09:11:43,158 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:11:43,416 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-20 09:11:43,416 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:11:44,106 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-03-20 09:11:44,106 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:11:44,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1685203180] [2022-03-20 09:11:44,106 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:11:44,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [385261652] [2022-03-20 09:11:44,107 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [385261652] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:11:44,107 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:11:44,107 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-03-20 09:11:44,107 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [462760868] [2022-03-20 09:11:44,107 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:11:44,107 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-03-20 09:11:44,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:11:44,108 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-03-20 09:11:44,108 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-03-20 09:11:44,108 INFO L87 Difference]: Start difference. First operand 160 states and 211 transitions. Second operand has 10 states, 10 states have (on average 3.8) internal successors, (38), 9 states have internal predecessors, (38), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-03-20 09:11:44,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:11:44,350 INFO L93 Difference]: Finished difference Result 176 states and 233 transitions. [2022-03-20 09:11:44,351 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 09:11:44,351 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.8) internal successors, (38), 9 states have internal predecessors, (38), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) Word has length 104 [2022-03-20 09:11:44,351 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:11:44,352 INFO L225 Difference]: With dead ends: 176 [2022-03-20 09:11:44,352 INFO L226 Difference]: Without dead ends: 168 [2022-03-20 09:11:44,352 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 208 GetRequests, 195 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-03-20 09:11:44,353 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 7 mSDsluCounter, 290 mSDsCounter, 0 mSdLazyCounter, 160 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 348 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 160 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-03-20 09:11:44,353 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 348 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 160 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-03-20 09:11:44,353 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 168 states. [2022-03-20 09:11:44,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 168 to 168. [2022-03-20 09:11:44,368 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 168 states, 100 states have (on average 1.21) internal successors, (121), 104 states have internal predecessors, (121), 52 states have call successors, (52), 16 states have call predecessors, (52), 15 states have return successors, (50), 47 states have call predecessors, (50), 50 states have call successors, (50) [2022-03-20 09:11:44,369 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 168 states to 168 states and 223 transitions. [2022-03-20 09:11:44,369 INFO L78 Accepts]: Start accepts. Automaton has 168 states and 223 transitions. Word has length 104 [2022-03-20 09:11:44,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:11:44,369 INFO L478 AbstractCegarLoop]: Abstraction has 168 states and 223 transitions. [2022-03-20 09:11:44,369 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.8) internal successors, (38), 9 states have internal predecessors, (38), 7 states have call successors, (36), 2 states have call predecessors, (36), 1 states have return successors, (33), 7 states have call predecessors, (33), 7 states have call successors, (33) [2022-03-20 09:11:44,369 INFO L276 IsEmpty]: Start isEmpty. Operand 168 states and 223 transitions. [2022-03-20 09:11:44,371 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 118 [2022-03-20 09:11:44,371 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:11:44,371 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:11:44,402 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 09:11:44,589 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2022-03-20 09:11:44,589 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:11:44,590 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:11:44,590 INFO L85 PathProgramCache]: Analyzing trace with hash -191386235, now seen corresponding path program 2 times [2022-03-20 09:11:44,590 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:11:44,590 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894973752] [2022-03-20 09:11:44,590 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:11:44,590 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:11:44,598 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:11:44,598 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1437283577] [2022-03-20 09:11:44,598 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 09:11:44,598 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:44,598 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:11:44,599 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 09:11:44,623 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 09:11:44,653 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 09:11:44,653 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 09:11:44,654 INFO L263 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 09:11:44,658 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:11:44,828 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 102 proven. 42 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-03-20 09:11:44,829 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:11:45,157 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 63 proven. 15 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-03-20 09:11:45,157 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:11:45,157 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894973752] [2022-03-20 09:11:45,158 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:11:45,158 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1437283577] [2022-03-20 09:11:45,158 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1437283577] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:11:45,158 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:11:45,158 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-03-20 09:11:45,158 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1112308324] [2022-03-20 09:11:45,158 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:11:45,158 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 09:11:45,159 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:11:45,159 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 09:11:45,159 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-03-20 09:11:45,159 INFO L87 Difference]: Start difference. First operand 168 states and 223 transitions. Second operand has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-03-20 09:11:45,224 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:11:45,225 INFO L93 Difference]: Finished difference Result 197 states and 260 transitions. [2022-03-20 09:11:45,225 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 09:11:45,225 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) Word has length 117 [2022-03-20 09:11:45,225 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:11:45,226 INFO L225 Difference]: With dead ends: 197 [2022-03-20 09:11:45,226 INFO L226 Difference]: Without dead ends: 130 [2022-03-20 09:11:45,227 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 233 GetRequests, 223 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-03-20 09:11:45,227 INFO L913 BasicCegarLoop]: 58 mSDtfsCounter, 4 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 89 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:11:45,227 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 149 Invalid, 89 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:11:45,228 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2022-03-20 09:11:45,237 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 130. [2022-03-20 09:11:45,238 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 78 states have (on average 1.1666666666666667) internal successors, (91), 82 states have internal predecessors, (91), 36 states have call successors, (36), 16 states have call predecessors, (36), 15 states have return successors, (34), 31 states have call predecessors, (34), 34 states have call successors, (34) [2022-03-20 09:11:45,239 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 161 transitions. [2022-03-20 09:11:45,239 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 161 transitions. Word has length 117 [2022-03-20 09:11:45,239 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:11:45,239 INFO L478 AbstractCegarLoop]: Abstraction has 130 states and 161 transitions. [2022-03-20 09:11:45,239 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 4.777777777777778) internal successors, (43), 9 states have internal predecessors, (43), 9 states have call successors, (37), 2 states have call predecessors, (37), 2 states have return successors, (35), 9 states have call predecessors, (35), 9 states have call successors, (35) [2022-03-20 09:11:45,239 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 161 transitions. [2022-03-20 09:11:45,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2022-03-20 09:11:45,240 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:11:45,240 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:11:45,258 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 09:11:45,458 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:45,459 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:11:45,459 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:11:45,459 INFO L85 PathProgramCache]: Analyzing trace with hash 525706014, now seen corresponding path program 3 times [2022-03-20 09:11:45,459 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:11:45,459 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1146882317] [2022-03-20 09:11:45,459 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:11:45,459 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:11:45,465 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:11:45,466 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1312376082] [2022-03-20 09:11:45,466 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 09:11:45,466 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:45,466 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:11:45,471 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 09:11:45,500 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 09:11:45,525 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 09:11:45,526 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 09:11:45,527 INFO L263 TraceCheckSpWp]: Trace formula consists of 169 conjuncts, 23 conjunts are in the unsatisfiable core [2022-03-20 09:11:45,529 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:11:45,787 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 09:11:45,820 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 09:11:45,852 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 09:11:45,902 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-03-20 09:11:45,974 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 142 proven. 2 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2022-03-20 09:11:45,974 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:11:50,905 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:11:50,905 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1146882317] [2022-03-20 09:11:50,906 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:11:50,906 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1312376082] [2022-03-20 09:11:50,906 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1312376082] provided 0 perfect and 1 imperfect interpolant sequences [2022-03-20 09:11:50,906 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-03-20 09:11:50,906 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-03-20 09:11:50,906 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [758281207] [2022-03-20 09:11:50,906 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-03-20 09:11:50,906 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-03-20 09:11:50,906 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:11:50,907 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-03-20 09:11:50,907 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-03-20 09:11:50,907 INFO L87 Difference]: Start difference. First operand 130 states and 161 transitions. Second operand has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 09:11:50,981 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:11:50,981 INFO L93 Difference]: Finished difference Result 136 states and 166 transitions. [2022-03-20 09:11:50,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-03-20 09:11:50,981 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) Word has length 118 [2022-03-20 09:11:50,982 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:11:50,982 INFO L225 Difference]: With dead ends: 136 [2022-03-20 09:11:50,982 INFO L226 Difference]: Without dead ends: 132 [2022-03-20 09:11:50,983 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 127 GetRequests, 111 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-03-20 09:11:50,983 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 20 mSDsluCounter, 60 mSDsCounter, 0 mSdLazyCounter, 91 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 79 SdHoareTripleChecker+Invalid, 106 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 91 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 09:11:50,983 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [25 Valid, 79 Invalid, 106 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 91 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 09:11:50,984 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2022-03-20 09:11:50,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 112. [2022-03-20 09:11:50,998 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 112 states, 69 states have (on average 1.1159420289855073) internal successors, (77), 69 states have internal predecessors, (77), 28 states have call successors, (28), 16 states have call predecessors, (28), 14 states have return successors, (26), 26 states have call predecessors, (26), 26 states have call successors, (26) [2022-03-20 09:11:50,999 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 112 states to 112 states and 131 transitions. [2022-03-20 09:11:50,999 INFO L78 Accepts]: Start accepts. Automaton has 112 states and 131 transitions. Word has length 118 [2022-03-20 09:11:51,007 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:11:51,007 INFO L478 AbstractCegarLoop]: Abstraction has 112 states and 131 transitions. [2022-03-20 09:11:51,008 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.3333333333333335) internal successors, (21), 8 states have internal predecessors, (21), 3 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 4 states have call predecessors, (8), 3 states have call successors, (8) [2022-03-20 09:11:51,008 INFO L276 IsEmpty]: Start isEmpty. Operand 112 states and 131 transitions. [2022-03-20 09:11:51,010 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2022-03-20 09:11:51,010 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 09:11:51,010 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:11:51,027 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 09:11:51,223 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,SelfDestructingSolverStorable11 [2022-03-20 09:11:51,224 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 09:11:51,224 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 09:11:51,224 INFO L85 PathProgramCache]: Analyzing trace with hash -1635698089, now seen corresponding path program 3 times [2022-03-20 09:11:51,224 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 09:11:51,224 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1257996734] [2022-03-20 09:11:51,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 09:11:51,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 09:11:51,230 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 09:11:51,230 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [116542939] [2022-03-20 09:11:51,230 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-03-20 09:11:51,230 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 09:11:51,230 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 09:11:51,244 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 09:11:51,245 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 09:11:51,279 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-03-20 09:11:51,279 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 09:11:51,280 INFO L263 TraceCheckSpWp]: Trace formula consists of 149 conjuncts, 12 conjunts are in the unsatisfiable core [2022-03-20 09:11:51,281 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 09:11:51,483 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-03-20 09:11:51,483 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-03-20 09:11:51,672 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-03-20 09:11:51,672 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 09:11:51,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1257996734] [2022-03-20 09:11:51,672 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 09:11:51,672 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [116542939] [2022-03-20 09:11:51,672 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [116542939] provided 0 perfect and 2 imperfect interpolant sequences [2022-03-20 09:11:51,672 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-03-20 09:11:51,672 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-03-20 09:11:51,672 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1347115978] [2022-03-20 09:11:51,672 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-03-20 09:11:51,673 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-03-20 09:11:51,673 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-03-20 09:11:51,673 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-03-20 09:11:51,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-03-20 09:11:51,673 INFO L87 Difference]: Start difference. First operand 112 states and 131 transitions. Second operand has 12 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-03-20 09:11:51,761 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 09:11:51,762 INFO L93 Difference]: Finished difference Result 120 states and 137 transitions. [2022-03-20 09:11:51,762 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 09:11:51,762 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) Word has length 121 [2022-03-20 09:11:51,762 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 09:11:51,762 INFO L225 Difference]: With dead ends: 120 [2022-03-20 09:11:51,762 INFO L226 Difference]: Without dead ends: 0 [2022-03-20 09:11:51,763 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 245 GetRequests, 231 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-03-20 09:11:51,763 INFO L913 BasicCegarLoop]: 18 mSDtfsCounter, 18 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 104 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 85 SdHoareTripleChecker+Invalid, 128 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 104 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 09:11:51,763 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 85 Invalid, 128 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 104 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 09:11:51,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-03-20 09:11:51,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-03-20 09:11:51,764 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 09:11:51,764 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-03-20 09:11:51,764 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 121 [2022-03-20 09:11:51,764 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 09:11:51,764 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-03-20 09:11:51,764 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 2.9) internal successors, (29), 9 states have internal predecessors, (29), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 6 states have call predecessors, (15), 4 states have call successors, (15) [2022-03-20 09:11:51,764 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-03-20 09:11:51,764 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-03-20 09:11:51,766 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-20 09:11:51,784 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-03-20 09:11:51,979 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,SelfDestructingSolverStorable12 [2022-03-20 09:11:51,981 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-03-20 09:12:02,938 WARN L232 SmtUtils]: Spent 5.42s on a formula simplification. DAG size of input: 146 DAG size of output: 32 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-03-20 09:12:02,941 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 09:12:02,941 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-03-20 09:12:02,941 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-03-20 09:12:02,941 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-03-20 09:12:02,941 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-03-20 09:12:02,941 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-03-20 09:12:02,941 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-03-20 09:12:02,941 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 22 60) the Hoare annotation is: true [2022-03-20 09:12:02,941 INFO L878 garLoopResultBuilder]: At program point L33-2(lines 33 41) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-03-20 09:12:02,941 INFO L882 garLoopResultBuilder]: For program point L51-2(lines 22 60) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L34(line 34) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L43-1(lines 43 55) the Hoare annotation is: (and (<= 1 main_~B~0) (= (+ (* main_~d~0 main_~q~0) main_~r~0) main_~A~0) (<= 1 main_~p~0) (= main_~B~0 main_~d~0)) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L44(line 44) the Hoare annotation is: (and (= (* main_~B~0 main_~p~0) main_~d~0) (<= 1 main_~p~0) (= main_~B~0 1) (= (+ (* main_~B~0 main_~q~0) main_~r~0) main_~A~0)) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L34-1(line 34) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L57(line 57) the Hoare annotation is: (let ((.cse0 (= main_~B~0 main_~d~0))) (or (and (= main_~B~0 1) .cse0 (= main_~p~0 1)) (and (<= 1 main_~B~0) (= (+ (* main_~d~0 main_~q~0) main_~r~0) main_~A~0) (<= 1 main_~p~0) .cse0))) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L44-1(line 44) the Hoare annotation is: (let ((.cse1 (* main_~B~0 main_~q~0))) (let ((.cse0 (div main_~p~0 2)) (.cse2 (= (+ .cse1 main_~r~0) main_~A~0))) (or (and (<= 1 .cse0) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse1 main_~r~0)) (= main_~B~0 1) .cse2) (and (= (let ((.cse3 (div main_~d~0 2))) (+ (div .cse3 2) main_~A~0 .cse3)) (+ .cse1 main_~r~0 (* main_~B~0 (div .cse0 2)) (* main_~B~0 .cse0))) (<= 1 main_~B~0) .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1))))) [2022-03-20 09:12:02,942 INFO L878 garLoopResultBuilder]: At program point L35(line 35) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L58(line 58) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L45(lines 43 55) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L36(lines 33 41) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 22 60) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L51(lines 51 54) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 22 60) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L15(lines 15 18) no Hoare annotation was computed. [2022-03-20 09:12:02,942 INFO L882 garLoopResultBuilder]: For program point L16(lines 16 17) no Hoare annotation was computed. [2022-03-20 09:12:02,943 INFO L882 garLoopResultBuilder]: For program point L15-2(lines 14 20) no Hoare annotation was computed. [2022-03-20 09:12:02,943 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) no Hoare annotation was computed. [2022-03-20 09:12:02,943 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 14 20) no Hoare annotation was computed. [2022-03-20 09:12:02,945 INFO L719 BasicCegarLoop]: Path program histogram: [3, 3, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 09:12:02,945 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-20 09:12:02,955 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 09:12:02 BasicIcfg [2022-03-20 09:12:02,955 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-20 09:12:02,956 INFO L158 Benchmark]: Toolchain (without parser) took 75040.65ms. Allocated memory was 203.4MB in the beginning and 390.1MB in the end (delta: 186.6MB). Free memory was 147.1MB in the beginning and 150.2MB in the end (delta: -3.1MB). Peak memory consumption was 209.2MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,956 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 203.4MB. Free memory was 163.5MB in the beginning and 163.4MB in the end (delta: 72.1kB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 09:12:02,956 INFO L158 Benchmark]: CACSL2BoogieTranslator took 206.27ms. Allocated memory was 203.4MB in the beginning and 325.1MB in the end (delta: 121.6MB). Free memory was 146.9MB in the beginning and 298.6MB in the end (delta: -151.7MB). Peak memory consumption was 5.9MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,956 INFO L158 Benchmark]: Boogie Preprocessor took 30.15ms. Allocated memory is still 325.1MB. Free memory was 298.6MB in the beginning and 297.1MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,956 INFO L158 Benchmark]: RCFGBuilder took 206.55ms. Allocated memory is still 325.1MB. Free memory was 297.1MB in the beginning and 286.8MB in the end (delta: 10.3MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,956 INFO L158 Benchmark]: IcfgTransformer took 16.77ms. Allocated memory is still 325.1MB. Free memory was 286.6MB in the beginning and 285.3MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,957 INFO L158 Benchmark]: TraceAbstraction took 74567.70ms. Allocated memory was 325.1MB in the beginning and 390.1MB in the end (delta: 65.0MB). Free memory was 285.0MB in the beginning and 150.2MB in the end (delta: 134.8MB). Peak memory consumption was 225.0MB. Max. memory is 8.0GB. [2022-03-20 09:12:02,957 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.10ms. Allocated memory is still 203.4MB. Free memory was 163.5MB in the beginning and 163.4MB in the end (delta: 72.1kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 206.27ms. Allocated memory was 203.4MB in the beginning and 325.1MB in the end (delta: 121.6MB). Free memory was 146.9MB in the beginning and 298.6MB in the end (delta: -151.7MB). Peak memory consumption was 5.9MB. Max. memory is 8.0GB. * Boogie Preprocessor took 30.15ms. Allocated memory is still 325.1MB. Free memory was 298.6MB in the beginning and 297.1MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 206.55ms. Allocated memory is still 325.1MB. Free memory was 297.1MB in the beginning and 286.8MB in the end (delta: 10.3MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 16.77ms. Allocated memory is still 325.1MB. Free memory was 286.6MB in the beginning and 285.3MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * TraceAbstraction took 74567.70ms. Allocated memory was 325.1MB in the beginning and 390.1MB in the end (delta: 65.0MB). Free memory was 285.0MB in the beginning and 150.2MB in the end (delta: 134.8MB). Peak memory consumption was 225.0MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 17]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 29 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 74.5s, OverallIterations: 13, TraceHistogramMax: 20, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 27.8s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 11.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 1 mSolverCounterUnknown, 369 SdHoareTripleChecker+Valid, 7.8s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 307 mSDsluCounter, 2072 SdHoareTripleChecker+Invalid, 7.6s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1611 mSDsCounter, 428 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1770 IncrementalHoareTripleChecker+Invalid, 2199 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 428 mSolverCounterUnsat, 461 mSDtfsCounter, 1770 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1477 GetRequests, 1334 SyntacticMatches, 22 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 26.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=168occurred in iteration=10, InterpolantAutomatonStates: 97, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 13 MinimizatonAttempts, 75 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 13 LocationsWithAnnotation, 126 PreInvPairs, 186 NumberOfFragments, 453 HoareAnnotationTreeSize, 126 FomulaSimplifications, 538 FormulaSimplificationTreeSizeReduction, 0.7s HoareSimplificationTime, 13 FomulaSimplificationsInter, 13266 FormulaSimplificationTreeSizeReductionInter, 10.3s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 32.2s InterpolantComputationTime, 867 NumberOfCodeBlocks, 745 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 1442 ConstructedInterpolants, 0 QuantifiedInterpolants, 15863 SizeOfPredicates, 26 NumberOfNonLiveVariables, 1855 ConjunctsInSsa, 195 ConjunctsInUnsatCore, 20 InterpolantComputations, 6 PerfectInterpolantSequences, 6338/6540 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 33]: Loop Invariant Derived loop invariant: (((((q == 0 && B == 1) && B * q + r == A) && B == d) && p == 1) || ((((B * 2 == d && p == 2) && q == 0) && B == 1) && B * q + r == A)) || ((((1 <= p / 2 / 2 && A + d == B * p + B * q + r) && q == 0) && B == 1) && B * q + r == A) RESULT: Ultimate proved your program to be correct! [2022-03-20 09:12:02,994 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...