/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/AutomizerC.xml -s ../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound2.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 23:01:03,055 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 23:01:03,057 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 23:01:03,104 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 23:01:03,104 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 23:01:03,106 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 23:01:03,108 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 23:01:03,110 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 23:01:03,112 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 23:01:03,116 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 23:01:03,117 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 23:01:03,119 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 23:01:03,119 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 23:01:03,121 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 23:01:03,122 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 23:01:03,125 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 23:01:03,126 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 23:01:03,127 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 23:01:03,129 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 23:01:03,135 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 23:01:03,137 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 23:01:03,140 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 23:01:03,141 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 23:01:03,141 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 23:01:03,143 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 23:01:03,145 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 23:01:03,145 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 23:01:03,145 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 23:01:03,146 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 23:01:03,146 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 23:01:03,147 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 23:01:03,148 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 23:01:03,149 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 23:01:03,150 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 23:01:03,150 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 23:01:03,151 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 23:01:03,151 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 23:01:03,151 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 23:01:03,152 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 23:01:03,152 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 23:01:03,152 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 23:01:03,154 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 23:01:03,155 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-04-06 23:01:03,165 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 23:01:03,166 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 23:01:03,167 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 23:01:03,167 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 23:01:03,168 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 23:01:03,168 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 23:01:03,168 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:01:03,169 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-04-06 23:01:03,169 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 23:01:03,170 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-04-06 23:01:03,170 INFO L138 SettingsManager]: * Use separate solver for trace checks=false WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-04-06 23:01:03,399 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 23:01:03,421 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 23:01:03,423 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 23:01:03,424 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 23:01:03,426 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 23:01:03,427 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound2.c [2022-04-06 23:01:03,487 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0566792e9/647d6183a91d400589cf084ab4bdb884/FLAGd1c258a52 [2022-04-06 23:01:03,903 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 23:01:03,904 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound2.c [2022-04-06 23:01:03,912 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0566792e9/647d6183a91d400589cf084ab4bdb884/FLAGd1c258a52 [2022-04-06 23:01:03,928 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/0566792e9/647d6183a91d400589cf084ab4bdb884 [2022-04-06 23:01:03,931 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 23:01:03,933 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-04-06 23:01:03,936 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 23:01:03,936 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 23:01:03,940 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 23:01:03,941 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:01:03" (1/1) ... [2022-04-06 23:01:03,942 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@468763f8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:03, skipping insertion in model container [2022-04-06 23:01:03,942 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:01:03" (1/1) ... [2022-04-06 23:01:03,949 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 23:01:03,963 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 23:01:04,195 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound2.c[538,551] [2022-04-06 23:01:04,221 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:01:04,231 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 23:01:04,244 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_valuebound2.c[538,551] [2022-04-06 23:01:04,262 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 23:01:04,274 INFO L208 MainTranslator]: Completed translation [2022-04-06 23:01:04,274 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04 WrapperNode [2022-04-06 23:01:04,275 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 23:01:04,277 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 23:01:04,278 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 23:01:04,278 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 23:01:04,288 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,288 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,294 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,295 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,306 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,312 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,320 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,322 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 23:01:04,323 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 23:01:04,323 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 23:01:04,323 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 23:01:04,325 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (1/1) ... [2022-04-06 23:01:04,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 23:01:04,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:04,357 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-04-06 23:01:04,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-04-06 23:01:04,394 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 23:01:04,394 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 23:01:04,394 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 23:01:04,394 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 23:01:04,395 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 23:01:04,395 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 23:01:04,395 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 23:01:04,396 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 23:01:04,396 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 23:01:04,397 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 23:01:04,397 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-04-06 23:01:04,397 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 23:01:04,397 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 23:01:04,398 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 23:01:04,398 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 23:01:04,403 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 23:01:04,404 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 23:01:04,404 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 23:01:04,404 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 23:01:04,404 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 23:01:04,458 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 23:01:04,460 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 23:01:04,562 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 23:01:04,567 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 23:01:04,568 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-06 23:01:04,569 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:01:04 BoogieIcfgContainer [2022-04-06 23:01:04,570 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 23:01:04,571 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 23:01:04,571 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 23:01:04,574 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 23:01:04,575 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:01:03" (1/3) ... [2022-04-06 23:01:04,575 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12fe8698 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:01:04, skipping insertion in model container [2022-04-06 23:01:04,575 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:04" (2/3) ... [2022-04-06 23:01:04,576 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@12fe8698 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:01:04, skipping insertion in model container [2022-04-06 23:01:04,576 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:01:04" (3/3) ... [2022-04-06 23:01:04,577 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_valuebound2.c [2022-04-06 23:01:04,581 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-04-06 23:01:04,582 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 23:01:04,617 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 23:01:04,623 INFO L340 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=Craig_NestedInterpolation, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP [2022-04-06 23:01:04,623 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 23:01:04,636 INFO L276 IsEmpty]: Start isEmpty. Operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2022-04-06 23:01:04,642 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 23:01:04,643 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:04,643 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:04,644 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:04,648 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:04,648 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 1 times [2022-04-06 23:01:04,655 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:04,655 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1239085565] [2022-04-06 23:01:04,665 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:04,665 INFO L85 PathProgramCache]: Analyzing trace with hash -1784424332, now seen corresponding path program 2 times [2022-04-06 23:01:04,667 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:04,667 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [23389545] [2022-04-06 23:01:04,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:04,668 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:04,754 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:04,835 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:01:04,839 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:04,847 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:01:04,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:04,854 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:01:04,857 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:04,862 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:01:04,865 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:04,870 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:01:04,871 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:04,871 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [23389545] [2022-04-06 23:01:04,872 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [23389545] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:04,872 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:04,873 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:01:04,875 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:04,875 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1239085565] [2022-04-06 23:01:04,876 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1239085565] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:04,876 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:04,876 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 23:01:04,876 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [973766420] [2022-04-06 23:01:04,877 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:04,881 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 23:01:04,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:04,908 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 23:01:04,909 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 23:01:04,911 INFO L87 Difference]: Start difference. First operand has 38 states, 20 states have (on average 1.5) internal successors, (30), 21 states have internal predecessors, (30), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:01:05,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:05,037 INFO L93 Difference]: Finished difference Result 69 states and 110 transitions. [2022-04-06 23:01:05,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 23:01:05,040 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-04-06 23:01:05,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:05,046 INFO L225 Difference]: With dead ends: 69 [2022-04-06 23:01:05,046 INFO L226 Difference]: Without dead ends: 33 [2022-04-06 23:01:05,051 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 23:01:05,058 INFO L913 BasicCegarLoop]: 38 mSDtfsCounter, 21 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 12 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 23 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 12 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:05,060 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 41 Invalid, 23 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 12 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:05,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-04-06 23:01:05,100 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 33. [2022-04-06 23:01:05,101 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 33 states, 17 states have (on average 1.2352941176470589) internal successors, (21), 18 states have internal predecessors, (21), 12 states have call successors, (12), 4 states have call predecessors, (12), 3 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:01:05,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 33 states to 33 states and 43 transitions. [2022-04-06 23:01:05,108 INFO L78 Accepts]: Start accepts. Automaton has 33 states and 43 transitions. Word has length 28 [2022-04-06 23:01:05,108 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:05,108 INFO L478 AbstractCegarLoop]: Abstraction has 33 states and 43 transitions. [2022-04-06 23:01:05,108 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-06 23:01:05,108 INFO L276 IsEmpty]: Start isEmpty. Operand 33 states and 43 transitions. [2022-04-06 23:01:05,110 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-04-06 23:01:05,110 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:05,111 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:05,111 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 23:01:05,112 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:05,115 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:05,116 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 1 times [2022-04-06 23:01:05,116 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:05,117 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1825303357] [2022-04-06 23:01:05,118 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:05,119 INFO L85 PathProgramCache]: Analyzing trace with hash 1361835634, now seen corresponding path program 2 times [2022-04-06 23:01:05,119 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:05,119 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1141049481] [2022-04-06 23:01:05,119 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:05,120 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:05,144 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,208 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:01:05,211 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,216 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:01:05,218 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,223 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:01:05,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,229 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:01:05,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,235 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:01:05,236 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:05,236 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1141049481] [2022-04-06 23:01:05,236 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1141049481] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:05,236 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:05,237 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:05,237 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:05,237 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1825303357] [2022-04-06 23:01:05,237 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1825303357] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:05,237 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:05,238 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:05,238 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1296125908] [2022-04-06 23:01:05,238 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:05,239 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:01:05,239 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:05,239 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:01:05,240 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:05,240 INFO L87 Difference]: Start difference. First operand 33 states and 43 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 23:01:05,418 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:05,418 INFO L93 Difference]: Finished difference Result 46 states and 60 transitions. [2022-04-06 23:01:05,419 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 23:01:05,420 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) Word has length 28 [2022-04-06 23:01:05,420 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:05,423 INFO L225 Difference]: With dead ends: 46 [2022-04-06 23:01:05,423 INFO L226 Difference]: Without dead ends: 44 [2022-04-06 23:01:05,424 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 9 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-04-06 23:01:05,426 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 38 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 155 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:05,427 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 48 Invalid, 155 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:05,428 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-04-06 23:01:05,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 37. [2022-04-06 23:01:05,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 20 states have (on average 1.2) internal successors, (24), 21 states have internal predecessors, (24), 12 states have call successors, (12), 5 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:01:05,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 46 transitions. [2022-04-06 23:01:05,438 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 46 transitions. Word has length 28 [2022-04-06 23:01:05,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:05,439 INFO L478 AbstractCegarLoop]: Abstraction has 37 states and 46 transitions. [2022-04-06 23:01:05,439 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (6), 3 states have call predecessors, (6), 1 states have return successors, (4), 1 states have call predecessors, (4), 1 states have call successors, (4) [2022-04-06 23:01:05,439 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 46 transitions. [2022-04-06 23:01:05,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-04-06 23:01:05,440 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:05,440 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:05,440 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-06 23:01:05,441 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:05,441 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:05,441 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 1 times [2022-04-06 23:01:05,441 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:05,442 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [481909022] [2022-04-06 23:01:05,442 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:05,442 INFO L85 PathProgramCache]: Analyzing trace with hash 1382067636, now seen corresponding path program 2 times [2022-04-06 23:01:05,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:05,443 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [617505989] [2022-04-06 23:01:05,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:05,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:05,465 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,527 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 23:01:05,533 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,556 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 23:01:05,558 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,564 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 23:01:05,565 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,568 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-04-06 23:01:05,570 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,573 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2022-04-06 23:01:05,576 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 23:01:05,580 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-06 23:01:05,581 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:05,581 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [617505989] [2022-04-06 23:01:05,581 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [617505989] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:05,581 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:05,581 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:05,582 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:05,582 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [481909022] [2022-04-06 23:01:05,582 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [481909022] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:05,583 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:05,583 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:05,583 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [762787096] [2022-04-06 23:01:05,583 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:05,584 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:01:05,584 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:05,584 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:01:05,584 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:05,585 INFO L87 Difference]: Start difference. First operand 37 states and 46 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 23:01:05,789 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:05,789 INFO L93 Difference]: Finished difference Result 50 states and 63 transitions. [2022-04-06 23:01:05,790 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-06 23:01:05,790 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-04-06 23:01:05,791 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:05,793 INFO L225 Difference]: With dead ends: 50 [2022-04-06 23:01:05,793 INFO L226 Difference]: Without dead ends: 48 [2022-04-06 23:01:05,794 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-06 23:01:05,797 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 33 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 48 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:05,802 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 48 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:05,804 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states. [2022-04-06 23:01:05,823 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 41. [2022-04-06 23:01:05,823 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 23 states have (on average 1.173913043478261) internal successors, (27), 24 states have internal predecessors, (27), 12 states have call successors, (12), 6 states have call predecessors, (12), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-06 23:01:05,824 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 49 transitions. [2022-04-06 23:01:05,824 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 49 transitions. Word has length 33 [2022-04-06 23:01:05,826 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:05,827 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 49 transitions. [2022-04-06 23:01:05,827 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 3 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-06 23:01:05,827 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 49 transitions. [2022-04-06 23:01:05,828 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-04-06 23:01:05,828 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:05,829 INFO L499 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:05,829 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-06 23:01:05,830 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:05,831 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:05,831 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 1 times [2022-04-06 23:01:05,831 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:05,834 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1831576481] [2022-04-06 23:01:05,834 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:05,834 INFO L85 PathProgramCache]: Analyzing trace with hash -1455208590, now seen corresponding path program 2 times [2022-04-06 23:01:05,835 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:05,835 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1629814381] [2022-04-06 23:01:05,835 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:05,835 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:05,854 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:05,855 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1609893489] [2022-04-06 23:01:05,864 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:05,864 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:05,864 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:05,871 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:05,878 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-04-06 23:01:05,945 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:05,946 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:05,948 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 23:01:05,953 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:06,305 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2022-04-06 23:01:06,305 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:01:06,305 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:06,306 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1629814381] [2022-04-06 23:01:06,306 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:06,306 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1609893489] [2022-04-06 23:01:06,306 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1609893489] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:06,307 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:06,307 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 23:01:06,308 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:06,308 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1831576481] [2022-04-06 23:01:06,308 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1831576481] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:06,308 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:06,308 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 23:01:06,309 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1240204604] [2022-04-06 23:01:06,309 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:06,310 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 23:01:06,312 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:06,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 23:01:06,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2022-04-06 23:01:06,316 INFO L87 Difference]: Start difference. First operand 41 states and 49 transitions. Second operand has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-06 23:01:06,475 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:06,475 INFO L93 Difference]: Finished difference Result 69 states and 89 transitions. [2022-04-06 23:01:06,476 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 23:01:06,476 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) Word has length 38 [2022-04-06 23:01:06,476 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:06,478 INFO L225 Difference]: With dead ends: 69 [2022-04-06 23:01:06,478 INFO L226 Difference]: Without dead ends: 55 [2022-04-06 23:01:06,479 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 39 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:01:06,481 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 23 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 129 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 194 SdHoareTripleChecker+Invalid, 139 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 129 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:06,481 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 194 Invalid, 139 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 129 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:06,482 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2022-04-06 23:01:06,504 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 55. [2022-04-06 23:01:06,505 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 55 states, 30 states have (on average 1.1666666666666667) internal successors, (35), 32 states have internal predecessors, (35), 18 states have call successors, (18), 7 states have call predecessors, (18), 6 states have return successors, (15), 15 states have call predecessors, (15), 15 states have call successors, (15) [2022-04-06 23:01:06,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 55 states to 55 states and 68 transitions. [2022-04-06 23:01:06,512 INFO L78 Accepts]: Start accepts. Automaton has 55 states and 68 transitions. Word has length 38 [2022-04-06 23:01:06,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:06,513 INFO L478 AbstractCegarLoop]: Abstraction has 55 states and 68 transitions. [2022-04-06 23:01:06,513 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.25) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (6), 4 states have call predecessors, (6), 3 states have call successors, (6) [2022-04-06 23:01:06,513 INFO L276 IsEmpty]: Start isEmpty. Operand 55 states and 68 transitions. [2022-04-06 23:01:06,515 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2022-04-06 23:01:06,515 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:06,515 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:06,543 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:06,739 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:06,739 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:06,740 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:06,740 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 1 times [2022-04-06 23:01:06,740 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:06,740 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [236245318] [2022-04-06 23:01:06,741 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:06,741 INFO L85 PathProgramCache]: Analyzing trace with hash -1688067263, now seen corresponding path program 2 times [2022-04-06 23:01:06,741 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:06,741 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986315060] [2022-04-06 23:01:06,741 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:06,741 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:06,756 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:06,756 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1240152121] [2022-04-06 23:01:06,756 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:06,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:06,757 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:06,765 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:06,767 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-04-06 23:01:06,814 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:06,814 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:06,818 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-06 23:01:06,821 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:07,082 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 3 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2022-04-06 23:01:07,082 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:07,271 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-04-06 23:01:07,272 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:07,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986315060] [2022-04-06 23:01:07,272 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:07,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1240152121] [2022-04-06 23:01:07,272 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1240152121] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 23:01:07,272 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:01:07,272 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [9] total 11 [2022-04-06 23:01:07,273 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:07,273 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [236245318] [2022-04-06 23:01:07,273 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [236245318] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:07,273 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:07,273 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 23:01:07,273 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1056209009] [2022-04-06 23:01:07,273 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:07,274 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 23:01:07,274 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:07,274 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 23:01:07,275 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:01:07,275 INFO L87 Difference]: Start difference. First operand 55 states and 68 transitions. Second operand has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:07,352 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:07,352 INFO L93 Difference]: Finished difference Result 68 states and 85 transitions. [2022-04-06 23:01:07,352 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:07,352 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 45 [2022-04-06 23:01:07,353 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:07,353 INFO L225 Difference]: With dead ends: 68 [2022-04-06 23:01:07,354 INFO L226 Difference]: Without dead ends: 66 [2022-04-06 23:01:07,354 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 90 GetRequests, 79 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 23:01:07,355 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 16 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 52 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 52 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:07,355 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [22 Valid, 128 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 52 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:07,355 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-04-06 23:01:07,367 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 64. [2022-04-06 23:01:07,367 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 36 states have (on average 1.1944444444444444) internal successors, (43), 38 states have internal predecessors, (43), 20 states have call successors, (20), 8 states have call predecessors, (20), 7 states have return successors, (17), 17 states have call predecessors, (17), 17 states have call successors, (17) [2022-04-06 23:01:07,368 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 80 transitions. [2022-04-06 23:01:07,368 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 80 transitions. Word has length 45 [2022-04-06 23:01:07,369 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:07,369 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 80 transitions. [2022-04-06 23:01:07,369 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.8333333333333335) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:07,369 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 80 transitions. [2022-04-06 23:01:07,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2022-04-06 23:01:07,370 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:07,370 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:07,399 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:07,591 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:07,592 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:07,592 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:07,592 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 1 times [2022-04-06 23:01:07,592 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:07,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1723937411] [2022-04-06 23:01:07,593 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:07,593 INFO L85 PathProgramCache]: Analyzing trace with hash -1471734606, now seen corresponding path program 2 times [2022-04-06 23:01:07,593 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:07,593 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1265983483] [2022-04-06 23:01:07,593 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:07,594 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:07,606 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:07,607 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [340634703] [2022-04-06 23:01:07,607 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:07,607 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:07,607 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:07,615 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:07,616 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-04-06 23:01:07,657 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:07,657 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:07,658 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-06 23:01:07,661 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:07,970 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 16 proven. 4 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2022-04-06 23:01:07,970 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:08,134 INFO L134 CoverageAnalysis]: Checked inductivity of 66 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 56 trivial. 0 not checked. [2022-04-06 23:01:08,134 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:08,134 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1265983483] [2022-04-06 23:01:08,134 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:08,134 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [340634703] [2022-04-06 23:01:08,135 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [340634703] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-06 23:01:08,135 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:01:08,135 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [10] total 11 [2022-04-06 23:01:08,135 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:08,135 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1723937411] [2022-04-06 23:01:08,135 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1723937411] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:08,135 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:08,136 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:08,136 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [123198590] [2022-04-06 23:01:08,136 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:08,136 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:01:08,136 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:08,136 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:01:08,137 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=26, Invalid=84, Unknown=0, NotChecked=0, Total=110 [2022-04-06 23:01:08,137 INFO L87 Difference]: Start difference. First operand 64 states and 80 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:08,208 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:08,208 INFO L93 Difference]: Finished difference Result 76 states and 95 transitions. [2022-04-06 23:01:08,208 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:08,209 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 55 [2022-04-06 23:01:08,209 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:08,210 INFO L225 Difference]: With dead ends: 76 [2022-04-06 23:01:08,210 INFO L226 Difference]: Without dead ends: 74 [2022-04-06 23:01:08,210 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 98 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=30, Invalid=102, Unknown=0, NotChecked=0, Total=132 [2022-04-06 23:01:08,211 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 51 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:08,211 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 129 Invalid, 51 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 23:01:08,212 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-04-06 23:01:08,225 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 71. [2022-04-06 23:01:08,225 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 40 states have (on average 1.175) internal successors, (47), 43 states have internal predecessors, (47), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-04-06 23:01:08,226 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 88 transitions. [2022-04-06 23:01:08,226 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 88 transitions. Word has length 55 [2022-04-06 23:01:08,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:08,226 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 88 transitions. [2022-04-06 23:01:08,226 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-04-06 23:01:08,227 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 88 transitions. [2022-04-06 23:01:08,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-04-06 23:01:08,227 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:08,228 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:08,253 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-04-06 23:01:08,451 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:08,452 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:08,452 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:08,452 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 1 times [2022-04-06 23:01:08,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:08,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [481452117] [2022-04-06 23:01:08,453 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:08,453 INFO L85 PathProgramCache]: Analyzing trace with hash -682689219, now seen corresponding path program 2 times [2022-04-06 23:01:08,453 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:08,453 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [44150735] [2022-04-06 23:01:08,453 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:08,453 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:08,463 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:08,464 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [629705820] [2022-04-06 23:01:08,464 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:08,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:08,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:08,465 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:08,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-04-06 23:01:08,513 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:08,513 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:08,514 INFO L263 TraceCheckSpWp]: Trace formula consists of 137 conjuncts, 7 conjunts are in the unsatisfiable core [2022-04-06 23:01:08,516 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:08,630 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2022-04-06 23:01:08,631 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 23:01:08,631 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:08,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [44150735] [2022-04-06 23:01:08,631 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:08,631 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [629705820] [2022-04-06 23:01:08,631 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [629705820] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:08,632 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:08,632 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:08,632 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:08,632 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [481452117] [2022-04-06 23:01:08,632 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [481452117] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:08,632 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:08,632 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-06 23:01:08,632 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1485332393] [2022-04-06 23:01:08,632 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:08,633 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-06 23:01:08,634 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:08,634 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-06 23:01:08,634 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-06 23:01:08,634 INFO L87 Difference]: Start difference. First operand 71 states and 88 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 23:01:08,689 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:08,689 INFO L93 Difference]: Finished difference Result 79 states and 96 transitions. [2022-04-06 23:01:08,690 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-06 23:01:08,690 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) Word has length 56 [2022-04-06 23:01:08,692 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:08,694 INFO L225 Difference]: With dead ends: 79 [2022-04-06 23:01:08,694 INFO L226 Difference]: Without dead ends: 72 [2022-04-06 23:01:08,694 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-06 23:01:08,695 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 87 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 9 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:08,695 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [9 Valid, 123 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 23:01:08,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-06 23:01:08,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 71. [2022-04-06 23:01:08,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 41 states have (on average 1.146341463414634) internal successors, (47), 44 states have internal predecessors, (47), 20 states have call successors, (20), 10 states have call predecessors, (20), 9 states have return successors, (18), 16 states have call predecessors, (18), 18 states have call successors, (18) [2022-04-06 23:01:08,710 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 85 transitions. [2022-04-06 23:01:08,710 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 85 transitions. Word has length 56 [2022-04-06 23:01:08,710 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:08,710 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 85 transitions. [2022-04-06 23:01:08,710 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 2 states have call predecessors, (9), 2 states have call successors, (9) [2022-04-06 23:01:08,710 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 85 transitions. [2022-04-06 23:01:08,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-06 23:01:08,711 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:08,712 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:08,737 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-04-06 23:01:08,931 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:08,931 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:08,932 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:08,932 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 1 times [2022-04-06 23:01:08,932 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:08,932 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1409339740] [2022-04-06 23:01:08,933 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:08,933 INFO L85 PathProgramCache]: Analyzing trace with hash 680531353, now seen corresponding path program 2 times [2022-04-06 23:01:08,933 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:08,933 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1107577951] [2022-04-06 23:01:08,933 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:08,933 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:08,944 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:08,945 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [40037482] [2022-04-06 23:01:08,945 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:08,945 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:08,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:08,949 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:08,950 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-04-06 23:01:09,015 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:09,015 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:09,016 INFO L263 TraceCheckSpWp]: Trace formula consists of 179 conjuncts, 30 conjunts are in the unsatisfiable core [2022-04-06 23:01:09,019 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:09,717 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 19 proven. 10 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2022-04-06 23:01:09,717 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:11,126 INFO L134 CoverageAnalysis]: Checked inductivity of 147 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2022-04-06 23:01:11,127 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:11,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1107577951] [2022-04-06 23:01:11,127 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:11,127 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [40037482] [2022-04-06 23:01:11,127 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [40037482] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:11,127 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:11,127 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 17 [2022-04-06 23:01:11,128 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:11,128 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1409339740] [2022-04-06 23:01:11,128 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1409339740] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:11,128 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:11,128 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 23:01:11,128 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1313214569] [2022-04-06 23:01:11,128 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:11,129 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 23:01:11,129 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:11,129 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 23:01:11,129 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=214, Unknown=0, NotChecked=0, Total=272 [2022-04-06 23:01:11,129 INFO L87 Difference]: Start difference. First operand 71 states and 85 transitions. Second operand has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2022-04-06 23:01:11,431 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:11,431 INFO L93 Difference]: Finished difference Result 135 states and 165 transitions. [2022-04-06 23:01:11,432 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 23:01:11,432 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) Word has length 75 [2022-04-06 23:01:11,432 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:11,434 INFO L225 Difference]: With dead ends: 135 [2022-04-06 23:01:11,434 INFO L226 Difference]: Without dead ends: 108 [2022-04-06 23:01:11,435 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 133 SyntacticMatches, 1 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 69 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=66, Invalid=276, Unknown=0, NotChecked=0, Total=342 [2022-04-06 23:01:11,435 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 28 mSDsluCounter, 133 mSDsCounter, 0 mSdLazyCounter, 316 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 175 SdHoareTripleChecker+Invalid, 345 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 316 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:11,435 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [37 Valid, 175 Invalid, 345 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 316 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 23:01:11,436 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 108 states. [2022-04-06 23:01:11,451 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 108 to 106. [2022-04-06 23:01:11,452 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 106 states, 64 states have (on average 1.140625) internal successors, (73), 67 states have internal predecessors, (73), 27 states have call successors, (27), 15 states have call predecessors, (27), 14 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 23:01:11,453 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 106 states to 106 states and 125 transitions. [2022-04-06 23:01:11,453 INFO L78 Accepts]: Start accepts. Automaton has 106 states and 125 transitions. Word has length 75 [2022-04-06 23:01:11,453 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:11,453 INFO L478 AbstractCegarLoop]: Abstraction has 106 states and 125 transitions. [2022-04-06 23:01:11,453 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.0833333333333335) internal successors, (25), 10 states have internal predecessors, (25), 6 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 5 states have call predecessors, (12), 5 states have call successors, (12) [2022-04-06 23:01:11,453 INFO L276 IsEmpty]: Start isEmpty. Operand 106 states and 125 transitions. [2022-04-06 23:01:11,454 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2022-04-06 23:01:11,454 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:11,455 INFO L499 BasicCegarLoop]: trace histogram [10, 9, 9, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:11,478 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:11,673 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:11,674 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:11,674 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:11,674 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 3 times [2022-04-06 23:01:11,674 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:11,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [516150413] [2022-04-06 23:01:11,675 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:11,675 INFO L85 PathProgramCache]: Analyzing trace with hash -1566820819, now seen corresponding path program 4 times [2022-04-06 23:01:11,675 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:11,675 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1194412835] [2022-04-06 23:01:11,676 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:11,676 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:11,687 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:11,687 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [548192439] [2022-04-06 23:01:11,687 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:01:11,688 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:11,688 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:11,689 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:11,690 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-04-06 23:01:11,741 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:01:11,741 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:11,742 INFO L263 TraceCheckSpWp]: Trace formula consists of 188 conjuncts, 22 conjunts are in the unsatisfiable core [2022-04-06 23:01:11,744 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:12,100 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 21 proven. 11 refuted. 0 times theorem prover too weak. 150 trivial. 0 not checked. [2022-04-06 23:01:12,100 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:14,505 INFO L134 CoverageAnalysis]: Checked inductivity of 182 backedges. 18 proven. 8 refuted. 0 times theorem prover too weak. 156 trivial. 0 not checked. [2022-04-06 23:01:14,505 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:14,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1194412835] [2022-04-06 23:01:14,506 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:14,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [548192439] [2022-04-06 23:01:14,506 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [548192439] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:14,506 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:14,506 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 8] total 15 [2022-04-06 23:01:14,506 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:14,506 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [516150413] [2022-04-06 23:01:14,506 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [516150413] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:14,506 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:14,506 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 23:01:14,506 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1594505828] [2022-04-06 23:01:14,507 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:14,507 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 23:01:14,507 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:14,507 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 23:01:14,507 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=164, Unknown=0, NotChecked=0, Total=210 [2022-04-06 23:01:14,507 INFO L87 Difference]: Start difference. First operand 106 states and 125 transitions. Second operand has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-04-06 23:01:14,867 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:14,867 INFO L93 Difference]: Finished difference Result 133 states and 159 transitions. [2022-04-06 23:01:14,867 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 23:01:14,868 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) Word has length 80 [2022-04-06 23:01:14,868 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:14,869 INFO L225 Difference]: With dead ends: 133 [2022-04-06 23:01:14,869 INFO L226 Difference]: Without dead ends: 110 [2022-04-06 23:01:14,870 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 145 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=63, Invalid=243, Unknown=0, NotChecked=0, Total=306 [2022-04-06 23:01:14,870 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 26 mSDsluCounter, 179 mSDsCounter, 0 mSdLazyCounter, 233 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 227 SdHoareTripleChecker+Invalid, 254 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 233 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:14,870 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 227 Invalid, 254 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 233 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-04-06 23:01:14,871 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2022-04-06 23:01:14,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 110. [2022-04-06 23:01:14,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 110 states, 66 states have (on average 1.106060606060606) internal successors, (73), 70 states have internal predecessors, (73), 28 states have call successors, (28), 16 states have call predecessors, (28), 15 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-04-06 23:01:14,885 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 110 states to 110 states and 126 transitions. [2022-04-06 23:01:14,885 INFO L78 Accepts]: Start accepts. Automaton has 110 states and 126 transitions. Word has length 80 [2022-04-06 23:01:14,886 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:14,886 INFO L478 AbstractCegarLoop]: Abstraction has 110 states and 126 transitions. [2022-04-06 23:01:14,886 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.272727272727273) internal successors, (25), 9 states have internal predecessors, (25), 6 states have call successors, (15), 2 states have call predecessors, (15), 2 states have return successors, (13), 6 states have call predecessors, (13), 6 states have call successors, (13) [2022-04-06 23:01:14,886 INFO L276 IsEmpty]: Start isEmpty. Operand 110 states and 126 transitions. [2022-04-06 23:01:14,887 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 87 [2022-04-06 23:01:14,887 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:14,887 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:14,915 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-06 23:01:15,100 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:15,101 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:15,101 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:15,101 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 1 times [2022-04-06 23:01:15,101 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:15,101 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [505325231] [2022-04-06 23:01:15,102 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:15,102 INFO L85 PathProgramCache]: Analyzing trace with hash -815356955, now seen corresponding path program 2 times [2022-04-06 23:01:15,102 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:15,102 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1503946762] [2022-04-06 23:01:15,102 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:15,102 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:15,112 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:15,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [284295683] [2022-04-06 23:01:15,113 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:01:15,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:15,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:15,114 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:15,143 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-04-06 23:01:15,172 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:01:15,172 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:15,173 INFO L263 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 21 conjunts are in the unsatisfiable core [2022-04-06 23:01:15,175 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:15,728 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-04-06 23:01:15,729 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:01:17,535 INFO L134 CoverageAnalysis]: Checked inductivity of 221 backedges. 20 proven. 9 refuted. 0 times theorem prover too weak. 192 trivial. 0 not checked. [2022-04-06 23:01:17,535 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:01:17,535 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1503946762] [2022-04-06 23:01:17,535 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:01:17,536 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [284295683] [2022-04-06 23:01:17,536 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [284295683] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:01:17,536 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:01:17,536 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 15 [2022-04-06 23:01:17,536 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:01:17,536 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [505325231] [2022-04-06 23:01:17,536 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [505325231] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:01:17,536 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:01:17,536 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [] total 10 [2022-04-06 23:01:17,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2131042893] [2022-04-06 23:01:17,537 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:01:17,537 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-06 23:01:17,537 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:17,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-06 23:01:17,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=57, Invalid=153, Unknown=0, NotChecked=0, Total=210 [2022-04-06 23:01:17,538 INFO L87 Difference]: Start difference. First operand 110 states and 126 transitions. Second operand has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-06 23:01:18,134 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:01:18,135 INFO L93 Difference]: Finished difference Result 145 states and 170 transitions. [2022-04-06 23:01:18,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-06 23:01:18,135 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 86 [2022-04-06 23:01:18,135 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:01:18,136 INFO L225 Difference]: With dead ends: 145 [2022-04-06 23:01:18,136 INFO L226 Difference]: Without dead ends: 96 [2022-04-06 23:01:18,137 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 173 GetRequests, 156 SyntacticMatches, 2 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=68, Invalid=204, Unknown=0, NotChecked=0, Total=272 [2022-04-06 23:01:18,138 INFO L913 BasicCegarLoop]: 48 mSDtfsCounter, 10 mSDsluCounter, 188 mSDsCounter, 0 mSdLazyCounter, 250 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 236 SdHoareTripleChecker+Invalid, 264 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 250 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:01:18,138 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 236 Invalid, 264 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 250 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-06 23:01:18,138 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 96 states. [2022-04-06 23:01:18,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 96 to 89. [2022-04-06 23:01:18,149 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 53 states have (on average 1.1132075471698113) internal successors, (59), 55 states have internal predecessors, (59), 23 states have call successors, (23), 13 states have call predecessors, (23), 12 states have return successors, (21), 20 states have call predecessors, (21), 21 states have call successors, (21) [2022-04-06 23:01:18,149 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 103 transitions. [2022-04-06 23:01:18,149 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 103 transitions. Word has length 86 [2022-04-06 23:01:18,150 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:01:18,150 INFO L478 AbstractCegarLoop]: Abstraction has 89 states and 103 transitions. [2022-04-06 23:01:18,150 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.5555555555555554) internal successors, (23), 9 states have internal predecessors, (23), 6 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-06 23:01:18,150 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 103 transitions. [2022-04-06 23:01:18,151 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 93 [2022-04-06 23:01:18,151 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:01:18,151 INFO L499 BasicCegarLoop]: trace histogram [12, 11, 11, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:01:18,175 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2022-04-06 23:01:18,373 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:18,374 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:01:18,374 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:01:18,374 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 5 times [2022-04-06 23:01:18,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:01:18,375 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1703027080] [2022-04-06 23:01:18,375 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:01:18,375 INFO L85 PathProgramCache]: Analyzing trace with hash 1885636697, now seen corresponding path program 6 times [2022-04-06 23:01:18,375 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:01:18,376 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [855638653] [2022-04-06 23:01:18,376 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:01:18,376 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:01:18,383 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:01:18,383 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1772228242] [2022-04-06 23:01:18,383 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:01:18,384 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:01:18,384 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:01:18,393 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:01:18,395 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-06 23:01:18,441 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2022-04-06 23:01:18,441 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:01:18,442 INFO L263 TraceCheckSpWp]: Trace formula consists of 139 conjuncts, 26 conjunts are in the unsatisfiable core [2022-04-06 23:01:18,445 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:01:35,397 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 55 proven. 9 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-04-06 23:01:35,397 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:02:12,450 WARN L232 SmtUtils]: Spent 19.56s on a formula simplification that was a NOOP. DAG size: 51 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 23:02:58,539 INFO L134 CoverageAnalysis]: Checked inductivity of 271 backedges. 45 proven. 19 refuted. 0 times theorem prover too weak. 207 trivial. 0 not checked. [2022-04-06 23:02:58,539 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:02:58,540 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [855638653] [2022-04-06 23:02:58,540 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:02:58,540 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1772228242] [2022-04-06 23:02:58,540 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1772228242] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:02:58,540 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:02:58,540 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 15 [2022-04-06 23:02:58,540 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:02:58,540 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1703027080] [2022-04-06 23:02:58,541 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1703027080] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:02:58,541 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:02:58,541 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2022-04-06 23:02:58,541 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1303828366] [2022-04-06 23:02:58,541 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:02:58,541 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 23:02:58,541 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:02:58,542 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 23:02:58,542 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=161, Unknown=3, NotChecked=0, Total=210 [2022-04-06 23:02:58,542 INFO L87 Difference]: Start difference. First operand 89 states and 103 transitions. Second operand has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:02:59,375 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:02:59,375 INFO L93 Difference]: Finished difference Result 107 states and 121 transitions. [2022-04-06 23:02:59,375 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 23:02:59,376 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 92 [2022-04-06 23:02:59,376 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:02:59,376 INFO L225 Difference]: With dead ends: 107 [2022-04-06 23:02:59,377 INFO L226 Difference]: Without dead ends: 95 [2022-04-06 23:02:59,377 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 185 GetRequests, 167 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 30.2s TimeCoverageRelationStatistics Valid=59, Invalid=210, Unknown=3, NotChecked=0, Total=272 [2022-04-06 23:02:59,378 INFO L913 BasicCegarLoop]: 33 mSDtfsCounter, 25 mSDsluCounter, 84 mSDsCounter, 0 mSdLazyCounter, 136 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 173 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 136 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:02:59,378 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [33 Valid, 117 Invalid, 173 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 136 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-06 23:02:59,378 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-04-06 23:02:59,390 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 95. [2022-04-06 23:02:59,390 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 57 states have (on average 1.087719298245614) internal successors, (62), 60 states have internal predecessors, (62), 24 states have call successors, (24), 14 states have call predecessors, (24), 13 states have return successors, (22), 20 states have call predecessors, (22), 22 states have call successors, (22) [2022-04-06 23:02:59,391 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 108 transitions. [2022-04-06 23:02:59,391 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 108 transitions. Word has length 92 [2022-04-06 23:02:59,391 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:02:59,391 INFO L478 AbstractCegarLoop]: Abstraction has 95 states and 108 transitions. [2022-04-06 23:02:59,391 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 2.3636363636363638) internal successors, (26), 10 states have internal predecessors, (26), 5 states have call successors, (14), 2 states have call predecessors, (14), 2 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2022-04-06 23:02:59,392 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 108 transitions. [2022-04-06 23:02:59,392 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 98 [2022-04-06 23:02:59,392 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:02:59,392 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:02:59,417 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-06 23:02:59,614 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-06 23:02:59,615 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:02:59,615 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:02:59,615 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 7 times [2022-04-06 23:02:59,615 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:02:59,616 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1085510151] [2022-04-06 23:02:59,616 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:02:59,616 INFO L85 PathProgramCache]: Analyzing trace with hash -278824083, now seen corresponding path program 8 times [2022-04-06 23:02:59,616 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:02:59,616 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1485555003] [2022-04-06 23:02:59,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:02:59,617 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:02:59,630 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:02:59,630 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1128938730] [2022-04-06 23:02:59,630 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:02:59,631 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:02:59,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:02:59,632 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:02:59,633 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-06 23:02:59,731 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:02:59,731 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:02:59,732 INFO L263 TraceCheckSpWp]: Trace formula consists of 221 conjuncts, 38 conjunts are in the unsatisfiable core [2022-04-06 23:02:59,734 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:03:00,418 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 28 proven. 80 refuted. 0 times theorem prover too weak. 210 trivial. 0 not checked. [2022-04-06 23:03:00,418 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:03:03,614 INFO L134 CoverageAnalysis]: Checked inductivity of 318 backedges. 37 proven. 38 refuted. 0 times theorem prover too weak. 243 trivial. 0 not checked. [2022-04-06 23:03:03,614 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:03:03,614 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1485555003] [2022-04-06 23:03:03,614 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:03:03,614 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1128938730] [2022-04-06 23:03:03,614 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1128938730] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:03:03,614 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:03:03,614 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 11] total 21 [2022-04-06 23:03:03,615 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:03:03,615 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1085510151] [2022-04-06 23:03:03,615 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1085510151] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:03:03,615 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:03:03,615 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15] imperfect sequences [] total 15 [2022-04-06 23:03:03,615 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1821909372] [2022-04-06 23:03:03,615 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:03:03,615 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-06 23:03:03,615 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:03,616 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-06 23:03:03,616 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=74, Invalid=346, Unknown=0, NotChecked=0, Total=420 [2022-04-06 23:03:03,616 INFO L87 Difference]: Start difference. First operand 95 states and 108 transitions. Second operand has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2022-04-06 23:03:04,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:03:04,753 INFO L93 Difference]: Finished difference Result 154 states and 184 transitions. [2022-04-06 23:03:04,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 23:03:04,754 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) Word has length 97 [2022-04-06 23:03:04,755 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:03:04,755 INFO L225 Difference]: With dead ends: 154 [2022-04-06 23:03:04,755 INFO L226 Difference]: Without dead ends: 129 [2022-04-06 23:03:04,756 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 172 SyntacticMatches, 2 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=139, Invalid=673, Unknown=0, NotChecked=0, Total=812 [2022-04-06 23:03:04,756 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 36 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 687 mSolverCounterSat, 47 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 277 SdHoareTripleChecker+Invalid, 734 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 47 IncrementalHoareTripleChecker+Valid, 687 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-04-06 23:03:04,757 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [44 Valid, 277 Invalid, 734 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [47 Valid, 687 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-04-06 23:03:04,757 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2022-04-06 23:03:04,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 129. [2022-04-06 23:03:04,776 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 77 states have (on average 1.0909090909090908) internal successors, (84), 82 states have internal predecessors, (84), 35 states have call successors, (35), 17 states have call predecessors, (35), 16 states have return successors, (32), 29 states have call predecessors, (32), 32 states have call successors, (32) [2022-04-06 23:03:04,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 151 transitions. [2022-04-06 23:03:04,777 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 151 transitions. Word has length 97 [2022-04-06 23:03:04,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:03:04,777 INFO L478 AbstractCegarLoop]: Abstraction has 129 states and 151 transitions. [2022-04-06 23:03:04,777 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 15 states have (on average 2.0) internal successors, (30), 13 states have internal predecessors, (30), 8 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (16), 8 states have call predecessors, (16), 8 states have call successors, (16) [2022-04-06 23:03:04,777 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 151 transitions. [2022-04-06 23:03:04,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2022-04-06 23:03:04,778 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:03:04,778 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:03:04,803 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-06 23:03:04,993 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:04,993 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:03:04,993 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:03:04,994 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 9 times [2022-04-06 23:03:04,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:04,994 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [124678104] [2022-04-06 23:03:04,994 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:03:04,994 INFO L85 PathProgramCache]: Analyzing trace with hash -367001023, now seen corresponding path program 10 times [2022-04-06 23:03:04,994 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:03:04,994 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2052922178] [2022-04-06 23:03:04,995 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:03:04,995 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:03:05,002 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:03:05,002 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [512453237] [2022-04-06 23:03:05,002 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2022-04-06 23:03:05,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:05,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:03:05,004 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:03:05,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-06 23:03:05,058 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2022-04-06 23:03:05,059 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:03:05,060 INFO L263 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 19 conjunts are in the unsatisfiable core [2022-04-06 23:03:05,062 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:03:05,865 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 45 proven. 11 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2022-04-06 23:03:05,865 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:03:06,482 INFO L134 CoverageAnalysis]: Checked inductivity of 374 backedges. 30 proven. 26 refuted. 0 times theorem prover too weak. 318 trivial. 0 not checked. [2022-04-06 23:03:06,483 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:03:06,483 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2052922178] [2022-04-06 23:03:06,483 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:03:06,483 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [512453237] [2022-04-06 23:03:06,483 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [512453237] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:03:06,483 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:03:06,483 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 20 [2022-04-06 23:03:06,484 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:03:06,484 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [124678104] [2022-04-06 23:03:06,484 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [124678104] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:03:06,484 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:03:06,484 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2022-04-06 23:03:06,484 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2112795956] [2022-04-06 23:03:06,484 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:03:06,484 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 23:03:06,484 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:06,485 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 23:03:06,485 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=83, Invalid=297, Unknown=0, NotChecked=0, Total=380 [2022-04-06 23:03:06,485 INFO L87 Difference]: Start difference. First operand 129 states and 151 transitions. Second operand has 12 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-06 23:03:07,530 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:03:07,530 INFO L93 Difference]: Finished difference Result 176 states and 217 transitions. [2022-04-06 23:03:07,531 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 23:03:07,531 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) Word has length 105 [2022-04-06 23:03:07,531 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:03:07,532 INFO L225 Difference]: With dead ends: 176 [2022-04-06 23:03:07,532 INFO L226 Difference]: Without dead ends: 148 [2022-04-06 23:03:07,532 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 217 GetRequests, 190 SyntacticMatches, 1 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 113 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=165, Invalid=591, Unknown=0, NotChecked=0, Total=756 [2022-04-06 23:03:07,533 INFO L913 BasicCegarLoop]: 68 mSDtfsCounter, 32 mSDsluCounter, 207 mSDsCounter, 0 mSdLazyCounter, 271 mSolverCounterSat, 43 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 275 SdHoareTripleChecker+Invalid, 314 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 43 IncrementalHoareTripleChecker+Valid, 271 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-04-06 23:03:07,533 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 275 Invalid, 314 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [43 Valid, 271 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-04-06 23:03:07,534 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2022-04-06 23:03:07,558 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 142. [2022-04-06 23:03:07,558 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 85 states have (on average 1.1176470588235294) internal successors, (95), 89 states have internal predecessors, (95), 40 states have call successors, (40), 17 states have call predecessors, (40), 16 states have return successors, (37), 35 states have call predecessors, (37), 37 states have call successors, (37) [2022-04-06 23:03:07,559 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 172 transitions. [2022-04-06 23:03:07,559 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 172 transitions. Word has length 105 [2022-04-06 23:03:07,559 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:03:07,560 INFO L478 AbstractCegarLoop]: Abstraction has 142 states and 172 transitions. [2022-04-06 23:03:07,560 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 2.5) internal successors, (30), 12 states have internal predecessors, (30), 8 states have call successors, (19), 2 states have call predecessors, (19), 2 states have return successors, (17), 7 states have call predecessors, (17), 7 states have call successors, (17) [2022-04-06 23:03:07,560 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 172 transitions. [2022-04-06 23:03:07,561 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2022-04-06 23:03:07,561 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:03:07,561 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:03:07,579 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-06 23:03:07,767 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-06 23:03:07,767 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:03:07,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:03:07,768 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 11 times [2022-04-06 23:03:07,768 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:07,768 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1930456106] [2022-04-06 23:03:07,769 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:03:07,769 INFO L85 PathProgramCache]: Analyzing trace with hash -1683530195, now seen corresponding path program 12 times [2022-04-06 23:03:07,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:03:07,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [252847275] [2022-04-06 23:03:07,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:03:07,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:03:07,775 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:03:07,776 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [805613500] [2022-04-06 23:03:07,776 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2022-04-06 23:03:07,776 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:03:07,776 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:03:07,777 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:03:07,792 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-06 23:03:07,853 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2022-04-06 23:03:07,853 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:03:07,854 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 33 conjunts are in the unsatisfiable core [2022-04-06 23:03:07,856 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:03:08,217 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 23:03:19,975 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 116 proven. 20 refuted. 0 times theorem prover too weak. 359 trivial. 0 not checked. [2022-04-06 23:03:19,975 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:03:29,819 INFO L134 CoverageAnalysis]: Checked inductivity of 495 backedges. 107 proven. 21 refuted. 0 times theorem prover too weak. 367 trivial. 0 not checked. [2022-04-06 23:03:29,820 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:03:29,820 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [252847275] [2022-04-06 23:03:29,820 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:03:29,820 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [805613500] [2022-04-06 23:03:29,820 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [805613500] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:03:29,820 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:03:29,821 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 10] total 18 [2022-04-06 23:03:29,821 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:03:29,821 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1930456106] [2022-04-06 23:03:29,821 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1930456106] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:03:29,821 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:03:29,821 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [] total 13 [2022-04-06 23:03:29,821 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1296184481] [2022-04-06 23:03:29,821 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:03:29,821 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2022-04-06 23:03:29,822 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:03:29,822 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2022-04-06 23:03:29,822 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=228, Unknown=3, NotChecked=0, Total=306 [2022-04-06 23:03:29,822 INFO L87 Difference]: Start difference. First operand 142 states and 172 transitions. Second operand has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 10 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 23:03:32,085 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-04-06 23:03:34,092 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-04-06 23:03:36,110 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-04-06 23:03:38,123 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-04-06 23:03:40,143 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-04-06 23:03:42,215 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-04-06 23:03:44,956 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-04-06 23:03:46,719 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.74s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 23:03:48,722 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-04-06 23:03:50,725 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-04-06 23:03:52,731 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-04-06 23:04:00,350 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-04-06 23:04:02,214 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.52s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 23:04:04,215 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-04-06 23:04:05,773 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.25s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 23:04:05,870 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:05,870 INFO L93 Difference]: Finished difference Result 159 states and 187 transitions. [2022-04-06 23:04:05,871 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2022-04-06 23:04:05,871 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 10 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) Word has length 114 [2022-04-06 23:04:05,871 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:05,872 INFO L225 Difference]: With dead ends: 159 [2022-04-06 23:04:05,872 INFO L226 Difference]: Without dead ends: 147 [2022-04-06 23:04:05,873 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 209 SyntacticMatches, 3 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 99 ImplicationChecksByTransitivity, 19.3s TimeCoverageRelationStatistics Valid=88, Invalid=289, Unknown=3, NotChecked=0, Total=380 [2022-04-06 23:04:05,873 INFO L913 BasicCegarLoop]: 41 mSDtfsCounter, 22 mSDsluCounter, 180 mSDsCounter, 0 mSdLazyCounter, 306 mSolverCounterSat, 17 mSolverCounterUnsat, 12 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 30.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 221 SdHoareTripleChecker+Invalid, 335 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 306 IncrementalHoareTripleChecker+Invalid, 12 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 30.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:05,873 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 221 Invalid, 335 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 306 Invalid, 12 Unknown, 0 Unchecked, 30.6s Time] [2022-04-06 23:04:05,874 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 147 states. [2022-04-06 23:04:05,900 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 147 to 145. [2022-04-06 23:04:05,901 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 88 states have (on average 1.1022727272727273) internal successors, (97), 91 states have internal predecessors, (97), 39 states have call successors, (39), 18 states have call predecessors, (39), 17 states have return successors, (36), 35 states have call predecessors, (36), 36 states have call successors, (36) [2022-04-06 23:04:05,902 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 172 transitions. [2022-04-06 23:04:05,902 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 172 transitions. Word has length 114 [2022-04-06 23:04:05,902 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:05,902 INFO L478 AbstractCegarLoop]: Abstraction has 145 states and 172 transitions. [2022-04-06 23:04:05,903 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 2.3333333333333335) internal successors, (28), 10 states have internal predecessors, (28), 6 states have call successors, (18), 2 states have call predecessors, (18), 2 states have return successors, (16), 6 states have call predecessors, (16), 5 states have call successors, (16) [2022-04-06 23:04:05,903 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 172 transitions. [2022-04-06 23:04:05,904 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2022-04-06 23:04:05,904 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:05,904 INFO L499 BasicCegarLoop]: trace histogram [16, 15, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:05,923 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-06 23:04:06,104 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-06 23:04:06,105 INFO L403 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:06,105 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:06,105 INFO L85 PathProgramCache]: Analyzing trace with hash 1087601215, now seen corresponding path program 1 times [2022-04-06 23:04:06,105 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:06,105 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [229935281] [2022-04-06 23:04:06,106 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:06,106 INFO L85 PathProgramCache]: Analyzing trace with hash 1087601215, now seen corresponding path program 2 times [2022-04-06 23:04:06,106 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:06,106 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [822482387] [2022-04-06 23:04:06,106 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:06,106 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:06,113 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:06,113 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [854014410] [2022-04-06 23:04:06,113 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:04:06,113 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:06,113 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:06,114 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:04:06,121 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2022-04-06 23:04:06,166 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:04:06,167 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:06,168 INFO L263 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 41 conjunts are in the unsatisfiable core [2022-04-06 23:04:06,170 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:11,677 WARN L855 $PredicateComparison]: unable to prove that (let ((.cse0 (mod c_main_~A~0 4294967296))) (and (= c_main_~q~0 2) (<= .cse0 2) (= c_main_~d~0 (div (+ .cse0 (* (- 1) c_main_~r~0)) 2)) (<= (div (+ (* 2 c_main_~r~0) (* (- 2) .cse0)) (- 4)) (div .cse0 2)) (< c_main_~r~0 c_main_~d~0))) is different from true [2022-04-06 23:04:11,954 INFO L134 CoverageAnalysis]: Checked inductivity of 490 backedges. 30 proven. 34 refuted. 0 times theorem prover too weak. 426 trivial. 0 not checked. [2022-04-06 23:04:11,954 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:04:15,403 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:15,403 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [822482387] [2022-04-06 23:04:15,403 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:15,403 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [854014410] [2022-04-06 23:04:15,403 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [854014410] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-06 23:04:15,403 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-06 23:04:15,403 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16] total 16 [2022-04-06 23:04:15,403 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:15,403 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [229935281] [2022-04-06 23:04:15,404 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [229935281] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:15,404 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:15,404 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [16] imperfect sequences [] total 16 [2022-04-06 23:04:15,404 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [769772429] [2022-04-06 23:04:15,404 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:15,404 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-06 23:04:15,404 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:15,404 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-06 23:04:15,405 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=361, Unknown=2, NotChecked=40, Total=506 [2022-04-06 23:04:15,405 INFO L87 Difference]: Start difference. First operand 145 states and 172 transitions. Second operand has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) [2022-04-06 23:04:17,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:17,106 INFO L93 Difference]: Finished difference Result 149 states and 176 transitions. [2022-04-06 23:04:17,107 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2022-04-06 23:04:17,107 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) Word has length 116 [2022-04-06 23:04:17,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:17,108 INFO L225 Difference]: With dead ends: 149 [2022-04-06 23:04:17,108 INFO L226 Difference]: Without dead ends: 122 [2022-04-06 23:04:17,109 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 126 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 1 IntricatePredicates, 1 DeprecatedPredicates, 130 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=112, Invalid=442, Unknown=2, NotChecked=44, Total=600 [2022-04-06 23:04:17,109 INFO L913 BasicCegarLoop]: 61 mSDtfsCounter, 24 mSDsluCounter, 254 mSDsCounter, 0 mSdLazyCounter, 391 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 315 SdHoareTripleChecker+Invalid, 531 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 391 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 117 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:17,109 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [30 Valid, 315 Invalid, 531 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 391 Invalid, 0 Unknown, 117 Unchecked, 1.6s Time] [2022-04-06 23:04:17,110 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 122 states. [2022-04-06 23:04:17,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 122 to 122. [2022-04-06 23:04:17,129 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 122 states, 74 states have (on average 1.1081081081081081) internal successors, (82), 76 states have internal predecessors, (82), 32 states have call successors, (32), 16 states have call predecessors, (32), 15 states have return successors, (30), 29 states have call predecessors, (30), 30 states have call successors, (30) [2022-04-06 23:04:17,130 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 122 states to 122 states and 144 transitions. [2022-04-06 23:04:17,130 INFO L78 Accepts]: Start accepts. Automaton has 122 states and 144 transitions. Word has length 116 [2022-04-06 23:04:17,132 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:17,132 INFO L478 AbstractCegarLoop]: Abstraction has 122 states and 144 transitions. [2022-04-06 23:04:17,132 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 2.066666666666667) internal successors, (31), 15 states have internal predecessors, (31), 9 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 8 states have call predecessors, (19), 8 states have call successors, (19) [2022-04-06 23:04:17,132 INFO L276 IsEmpty]: Start isEmpty. Operand 122 states and 144 transitions. [2022-04-06 23:04:17,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-04-06 23:04:17,133 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 23:04:17,133 INFO L499 BasicCegarLoop]: trace histogram [18, 17, 17, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 23:04:17,156 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2022-04-06 23:04:17,355 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2022-04-06 23:04:17,356 INFO L403 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 23:04:17,356 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 23:04:17,356 INFO L85 PathProgramCache]: Analyzing trace with hash -523768505, now seen corresponding path program 1 times [2022-04-06 23:04:17,356 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:17,356 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1738755902] [2022-04-06 23:04:17,356 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-04-06 23:04:17,357 INFO L85 PathProgramCache]: Analyzing trace with hash -523768505, now seen corresponding path program 2 times [2022-04-06 23:04:17,357 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 23:04:17,357 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1071302409] [2022-04-06 23:04:17,357 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 23:04:17,357 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 23:04:17,364 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 23:04:17,364 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1497928931] [2022-04-06 23:04:17,364 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 23:04:17,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 23:04:17,365 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 23:04:17,366 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-06 23:04:17,372 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2022-04-06 23:04:17,412 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 23:04:17,412 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 23:04:17,413 INFO L263 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 15 conjunts are in the unsatisfiable core [2022-04-06 23:04:17,415 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 23:04:18,092 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 264 proven. 36 refuted. 0 times theorem prover too weak. 331 trivial. 0 not checked. [2022-04-06 23:04:18,092 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 23:04:18,566 INFO L134 CoverageAnalysis]: Checked inductivity of 631 backedges. 34 proven. 36 refuted. 0 times theorem prover too weak. 561 trivial. 0 not checked. [2022-04-06 23:04:18,566 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 23:04:18,566 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1071302409] [2022-04-06 23:04:18,566 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 23:04:18,566 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1497928931] [2022-04-06 23:04:18,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1497928931] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 23:04:18,567 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 23:04:18,567 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 15 [2022-04-06 23:04:18,567 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-04-06 23:04:18,567 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1738755902] [2022-04-06 23:04:18,567 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1738755902] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 23:04:18,567 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 23:04:18,567 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2022-04-06 23:04:18,567 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [908386090] [2022-04-06 23:04:18,568 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 23:04:18,568 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-06 23:04:18,568 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-04-06 23:04:18,568 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-06 23:04:18,568 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2022-04-06 23:04:18,569 INFO L87 Difference]: Start difference. First operand 122 states and 144 transitions. Second operand has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 9 states have internal predecessors, (31), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) [2022-04-06 23:04:19,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 23:04:19,206 INFO L93 Difference]: Finished difference Result 126 states and 147 transitions. [2022-04-06 23:04:19,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2022-04-06 23:04:19,207 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 9 states have internal predecessors, (31), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) Word has length 127 [2022-04-06 23:04:19,207 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 23:04:19,207 INFO L225 Difference]: With dead ends: 126 [2022-04-06 23:04:19,207 INFO L226 Difference]: Without dead ends: 0 [2022-04-06 23:04:19,207 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 258 GetRequests, 240 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=87, Invalid=293, Unknown=0, NotChecked=0, Total=380 [2022-04-06 23:04:19,208 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 4 mSDsluCounter, 154 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 4 SdHoareTripleChecker+Valid, 197 SdHoareTripleChecker+Invalid, 149 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-04-06 23:04:19,208 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [4 Valid, 197 Invalid, 149 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2022-04-06 23:04:19,208 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-06 23:04:19,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-06 23:04:19,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-04-06 23:04:19,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-06 23:04:19,209 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 127 [2022-04-06 23:04:19,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 23:04:19,209 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-06 23:04:19,209 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 3.4444444444444446) internal successors, (31), 9 states have internal predecessors, (31), 7 states have call successors, (19), 2 states have call predecessors, (19), 3 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18) [2022-04-06 23:04:19,209 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-06 23:04:19,209 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-06 23:04:19,211 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 23:04:19,230 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2022-04-06 23:04:19,423 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2022-04-06 23:04:19,425 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-06 23:04:53,551 WARN L232 SmtUtils]: Spent 33.95s on a formula simplification. DAG size of input: 157 DAG size of output: 83 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:05:42,737 WARN L232 SmtUtils]: Spent 49.17s on a formula simplification. DAG size of input: 154 DAG size of output: 80 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:06:25,229 WARN L232 SmtUtils]: Spent 38.79s on a formula simplification. DAG size of input: 154 DAG size of output: 82 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:06:51,943 WARN L232 SmtUtils]: Spent 26.71s on a formula simplification. DAG size of input: 125 DAG size of output: 70 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:08:04,192 WARN L232 SmtUtils]: Spent 1.18m on a formula simplification. DAG size of input: 154 DAG size of output: 80 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:08:27,781 WARN L232 SmtUtils]: Spent 23.59s on a formula simplification. DAG size of input: 86 DAG size of output: 42 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 23:08:27,851 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 8) no Hoare annotation was computed. [2022-04-06 23:08:27,851 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 8) no Hoare annotation was computed. [2022-04-06 23:08:27,851 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 8) no Hoare annotation was computed. [2022-04-06 23:08:27,852 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point L12(line 12) the Hoare annotation is: (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|) [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 11 13) the Hoare annotation is: (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point L29(line 29) the Hoare annotation is: (let ((.cse0 (mod main_~B~0 4294967296))) (and (<= .cse0 2) (<= 1 .cse0) (<= (mod main_~A~0 4294967296) 2))) [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point L60(line 60) the Hoare annotation is: (let ((.cse0 (mod main_~B~0 4294967296))) (and (= main_~d~0 .cse0) (<= .cse0 2) (<= 1 .cse0) (= main_~p~0 1))) [2022-04-06 23:08:27,852 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 22 63) the Hoare annotation is: true [2022-04-06 23:08:27,852 INFO L878 garLoopResultBuilder]: At program point L54(lines 54 57) the Hoare annotation is: (let ((.cse6 (mod main_~A~0 4294967296)) (.cse1 (mod main_~B~0 4294967296))) (let ((.cse0 (= main_~d~0 .cse1)) (.cse5 (= main_~p~0 1)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse1)) .cse6)) (.cse3 (< main_~r~0 (* main_~d~0 2))) (.cse4 (= main_~q~0 0)) (.cse7 (* (- 1) main_~r~0)) (.cse8 (* (- 1) main_~d~0))) (or (and .cse0 (<= .cse1 2) .cse2 .cse3 .cse4 (<= .cse1 main_~r~0) .cse5) (and .cse0 (<= (div (+ (* (- 2) .cse6) (* main_~r~0 2)) (- 4)) (div .cse6 2)) (= main_~d~0 (div (+ .cse6 .cse7) 2)) .cse2 (<= .cse6 2) (< (div (+ .cse8 (div (+ (- 1) .cse7) 2)) (- 2)) (+ main_~d~0 1)) .cse5) (let ((.cse10 (* main_~p~0 2)) (.cse9 (* 4 (div (div .cse8 (- 2)) .cse1)))) (and (= (mod (div (- main_~d~0) (- 2)) .cse1) 0) (< main_~d~0 (+ main_~r~0 1)) .cse2 (< .cse9 (+ .cse10 2)) (not (= .cse1 0)) .cse3 (<= .cse10 .cse9) (= (mod main_~d~0 2) 0) .cse4 (< (div (+ 2 .cse7) (- 4294967296)) 1)))))) [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L54-2(lines 22 63) the Hoare annotation is: (let ((.cse3 (mod main_~B~0 4294967296)) (.cse4 (mod main_~A~0 4294967296))) (let ((.cse8 (= main_~p~0 1)) (.cse10 (= (+ main_~d~0 main_~r~0) .cse4)) (.cse0 (<= 1 .cse3)) (.cse7 (* (- 1) main_~d~0)) (.cse6 (<= .cse4 2)) (.cse11 (< main_~d~0 (+ .cse4 1))) (.cse9 (<= .cse3 2)) (.cse12 (= main_~d~0 (* main_~p~0 .cse3))) (.cse13 (= main_~p~0 2)) (.cse1 (= (+ main_~r~0 (* main_~q~0 .cse3)) .cse4)) (.cse2 (= main_~q~0 0))) (or (and (<= (div main_~d~0 2) main_~r~0) .cse0 .cse1 .cse2 (= main_~p~0 4) (= main_~d~0 (* (* .cse3 (div main_~p~0 2)) 2)) (<= (mod main_~r~0 4294967296) 2)) (let ((.cse5 (* (- 1) main_~r~0))) (and (= main_~d~0 .cse3) (<= (div (+ (* (- 2) .cse4) (* main_~r~0 2)) (- 4)) (div .cse4 2)) (= main_~d~0 (div (+ .cse4 .cse5) 2)) .cse1 .cse6 (< (div (+ .cse7 (div (+ (- 1) .cse5) 2)) (- 2)) (+ main_~d~0 1)) .cse8)) (and (= .cse4 (+ main_~r~0 .cse3)) .cse9 .cse10 (= main_~q~0 1) (< .cse4 (* 2 .cse3)) .cse11 .cse8) (and .cse9 .cse12 .cse0 .cse1 .cse2 .cse8) (and .cse13 .cse10 .cse0 .cse1 (<= (* main_~p~0 2) (* 4 (div (div .cse7 (- 2)) .cse3))) (= (mod main_~d~0 2) 0) .cse6 .cse11) (and .cse9 (< main_~r~0 main_~d~0) .cse12 .cse13 .cse1 .cse2 (<= .cse3 main_~r~0))))) [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L48(lines 46 58) the Hoare annotation is: (let ((.cse1 (mod main_~A~0 4294967296)) (.cse0 (mod main_~B~0 4294967296))) (let ((.cse6 (= main_~p~0 1)) (.cse9 (* 2 .cse0)) (.cse13 (= main_~p~0 2)) (.cse8 (= (+ main_~d~0 main_~r~0) .cse1)) (.cse5 (* (- 1) main_~d~0)) (.cse4 (<= .cse1 2)) (.cse10 (< main_~d~0 (+ .cse1 1))) (.cse7 (<= .cse0 2)) (.cse11 (<= 1 .cse0)) (.cse3 (= (+ main_~r~0 (* main_~q~0 .cse0)) .cse1)) (.cse12 (= main_~q~0 0))) (or (let ((.cse2 (* (- 1) main_~r~0))) (and (= main_~d~0 .cse0) (<= (div (+ (* (- 2) .cse1) (* main_~r~0 2)) (- 4)) (div .cse1 2)) (= main_~d~0 (div (+ .cse1 .cse2) 2)) .cse3 .cse4 (< (div (+ .cse5 (div (+ (- 1) .cse2) 2)) (- 2)) (+ main_~d~0 1)) .cse6)) (and (= .cse1 (+ main_~r~0 .cse0)) .cse7 .cse8 (= main_~q~0 1) (< .cse1 .cse9) .cse10 .cse6) (and .cse7 (= main_~d~0 (* main_~p~0 .cse0)) .cse11 .cse3 .cse12 .cse6) (and .cse7 (= .cse1 main_~r~0) (= main_~d~0 .cse9) (< main_~r~0 main_~d~0) .cse13 .cse11 .cse3 (<= .cse0 main_~r~0)) (and .cse13 .cse8 .cse11 .cse3 (<= (* main_~p~0 2) (* 4 (div (div .cse5 (- 2)) .cse0))) (= (mod main_~d~0 2) 0) .cse4 .cse10) (and .cse7 (<= (div main_~d~0 2) main_~r~0) .cse11 .cse3 .cse12 (= main_~p~0 4) (= main_~d~0 (* (* .cse0 (div main_~p~0 2)) 2)) (<= (mod main_~r~0 4294967296) 2))))) [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L46-1(lines 46 58) the Hoare annotation is: (let ((.cse2 (mod main_~A~0 4294967296)) (.cse5 (mod main_~B~0 4294967296))) (let ((.cse0 (= main_~d~0 .cse5)) (.cse1 (<= .cse5 2)) (.cse3 (<= 1 .cse5)) (.cse6 (= (+ main_~r~0 (* main_~q~0 .cse5)) .cse2)) (.cse4 (= main_~p~0 1))) (or (and .cse0 .cse1 (< .cse2 (* main_~d~0 2)) (= (+ main_~d~0 main_~r~0) .cse2) .cse3 (= main_~q~0 1) (< main_~d~0 (+ .cse2 1)) .cse4) (and .cse1 (= main_~d~0 (* main_~p~0 .cse5)) .cse3 .cse6 (= main_~q~0 0) .cse4) (and .cse0 .cse1 .cse3 (= main_~d~0 (div (+ .cse2 (* (- 1) main_~r~0)) 2)) .cse6 (<= .cse2 2) (<= (mod main_~r~0 4294967296) 2) .cse4)))) [2022-04-06 23:08:27,853 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 22 63) the Hoare annotation is: true [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L38(line 38) the Hoare annotation is: (let ((.cse4 (mod main_~B~0 4294967296))) (let ((.cse0 (<= .cse4 2)) (.cse1 (<= 1 .cse4)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse4)) (mod main_~A~0 4294967296))) (.cse3 (= main_~q~0 0)) (.cse5 (< (div (+ 2 (* (- 1) main_~r~0)) (- 4294967296)) 1))) (or (and .cse0 (<= (div main_~d~0 2) main_~r~0) (<= 0 main_~d~0) .cse1 .cse2 .cse3 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse4 (div main_~p~0 2)) 2)) .cse5) (and .cse0 (= main_~d~0 (* main_~p~0 .cse4)) .cse1 .cse2 .cse3 .cse5 (= main_~p~0 1))))) [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L36-2(lines 36 44) the Hoare annotation is: (let ((.cse4 (mod main_~B~0 4294967296))) (let ((.cse0 (<= .cse4 2)) (.cse1 (<= 1 .cse4)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse4)) (mod main_~A~0 4294967296))) (.cse3 (= main_~q~0 0)) (.cse5 (< (div (+ 2 (* (- 1) main_~r~0)) (- 4294967296)) 1))) (or (and .cse0 (<= (div main_~d~0 2) main_~r~0) (<= 0 main_~d~0) .cse1 .cse2 .cse3 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse4 (div main_~p~0 2)) 2)) .cse5) (and .cse0 (= main_~d~0 (* main_~p~0 .cse4)) .cse1 .cse2 .cse3 .cse5 (= main_~p~0 1))))) [2022-04-06 23:08:27,853 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 22 63) the Hoare annotation is: true [2022-04-06 23:08:27,853 INFO L885 garLoopResultBuilder]: At program point L61(line 61) the Hoare annotation is: true [2022-04-06 23:08:27,853 INFO L878 garLoopResultBuilder]: At program point L28(line 28) the Hoare annotation is: (<= (mod main_~A~0 4294967296) 2) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L28-1(line 28) the Hoare annotation is: (and (<= (mod main_~B~0 4294967296) 2) (<= (mod main_~A~0 4294967296) 2)) [2022-04-06 23:08:27,854 INFO L885 garLoopResultBuilder]: At program point L26(line 26) the Hoare annotation is: true [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L26-1(line 26) the Hoare annotation is: (<= (mod main_~A~0 4294967296) 2) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L47(line 47) the Hoare annotation is: (let ((.cse3 (mod main_~B~0 4294967296)) (.cse4 (mod main_~A~0 4294967296))) (let ((.cse8 (= main_~p~0 1)) (.cse10 (= (+ main_~d~0 main_~r~0) .cse4)) (.cse0 (<= 1 .cse3)) (.cse7 (* (- 1) main_~d~0)) (.cse6 (<= .cse4 2)) (.cse11 (< main_~d~0 (+ .cse4 1))) (.cse9 (<= .cse3 2)) (.cse12 (= main_~d~0 (* main_~p~0 .cse3))) (.cse13 (= main_~p~0 2)) (.cse1 (= (+ main_~r~0 (* main_~q~0 .cse3)) .cse4)) (.cse2 (= main_~q~0 0))) (or (and (<= (div main_~d~0 2) main_~r~0) .cse0 .cse1 .cse2 (= main_~p~0 4) (= main_~d~0 (* (* .cse3 (div main_~p~0 2)) 2)) (<= (mod main_~r~0 4294967296) 2)) (let ((.cse5 (* (- 1) main_~r~0))) (and (= main_~d~0 .cse3) (<= (div (+ (* (- 2) .cse4) (* main_~r~0 2)) (- 4)) (div .cse4 2)) (= main_~d~0 (div (+ .cse4 .cse5) 2)) .cse1 .cse6 (< (div (+ .cse7 (div (+ (- 1) .cse5) 2)) (- 2)) (+ main_~d~0 1)) .cse8)) (and (= .cse4 (+ main_~r~0 .cse3)) .cse9 .cse10 (= main_~q~0 1) (< .cse4 (* 2 .cse3)) .cse11 .cse8) (and .cse9 .cse12 .cse0 .cse1 .cse2 .cse8) (and .cse13 .cse10 .cse0 .cse1 (<= (* main_~p~0 2) (* 4 (div (div .cse7 (- 2)) .cse3))) (= (mod main_~d~0 2) 0) .cse6 .cse11) (and .cse9 (< main_~r~0 main_~d~0) .cse12 .cse13 .cse1 .cse2 (<= .cse3 main_~r~0))))) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L47-1(line 47) the Hoare annotation is: (let ((.cse0 (mod main_~B~0 4294967296)) (.cse1 (mod main_~A~0 4294967296))) (let ((.cse6 (= main_~p~0 1)) (.cse8 (= (+ main_~d~0 main_~r~0) .cse1)) (.cse5 (* (- 1) main_~d~0)) (.cse4 (<= .cse1 2)) (.cse9 (< main_~d~0 (+ .cse1 1))) (.cse11 (<= 1 .cse0)) (.cse2 (* (- 1) main_~r~0)) (.cse7 (<= .cse0 2)) (.cse10 (= main_~d~0 (* main_~p~0 .cse0))) (.cse13 (= main_~p~0 2)) (.cse3 (= (+ main_~r~0 (* main_~q~0 .cse0)) .cse1)) (.cse12 (= main_~q~0 0))) (or (and (= main_~d~0 .cse0) (<= (div (+ (* (- 2) .cse1) (* main_~r~0 2)) (- 4)) (div .cse1 2)) (= main_~d~0 (div (+ .cse1 .cse2) 2)) .cse3 .cse4 (< (div (+ .cse5 (div (+ (- 1) .cse2) 2)) (- 2)) (+ main_~d~0 1)) .cse6) (and (= .cse1 (+ main_~r~0 .cse0)) .cse7 .cse8 (= main_~q~0 1) (< .cse1 (* 2 .cse0)) .cse9 .cse6) (and .cse7 .cse10 .cse11 .cse3 .cse12 .cse6) (and .cse13 .cse8 .cse11 .cse3 (<= (* main_~p~0 2) (* 4 (div (div .cse5 (- 2)) .cse0))) (= (mod main_~d~0 2) 0) .cse4 .cse9) (and (<= (div main_~d~0 2) main_~r~0) .cse11 .cse3 .cse12 (= main_~p~0 4) (= main_~d~0 (* (* .cse0 (div main_~p~0 2)) 2)) (< (div (+ 2 .cse2) (- 4294967296)) 1)) (and .cse7 (< main_~r~0 main_~d~0) .cse10 .cse13 .cse3 .cse12 (<= .cse0 main_~r~0))))) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L39(lines 36 44) the Hoare annotation is: (let ((.cse4 (mod main_~B~0 4294967296))) (let ((.cse0 (<= .cse4 2)) (.cse1 (<= 1 .cse4)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse4)) (mod main_~A~0 4294967296))) (.cse3 (= main_~q~0 0)) (.cse5 (< (div (+ 2 (* (- 1) main_~r~0)) (- 4294967296)) 1))) (or (and .cse0 (<= (div main_~d~0 2) main_~r~0) (<= 0 main_~d~0) .cse1 .cse2 .cse3 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse4 (div main_~p~0 2)) 2)) .cse5) (and .cse0 (= main_~d~0 (* main_~p~0 .cse4)) .cse1 .cse2 .cse3 .cse5 (= main_~p~0 1))))) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L37(line 37) the Hoare annotation is: (let ((.cse4 (mod main_~B~0 4294967296))) (let ((.cse0 (<= .cse4 2)) (.cse1 (<= 1 .cse4)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse4)) (mod main_~A~0 4294967296))) (.cse3 (= main_~q~0 0)) (.cse5 (< (div (+ 2 (* (- 1) main_~r~0)) (- 4294967296)) 1))) (or (and .cse0 (<= (div main_~d~0 2) main_~r~0) (<= 0 main_~d~0) .cse1 .cse2 .cse3 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse4 (div main_~p~0 2)) 2)) .cse5) (and .cse0 (= main_~d~0 (* main_~p~0 .cse4)) .cse1 .cse2 .cse3 .cse5 (= main_~p~0 1))))) [2022-04-06 23:08:27,854 INFO L878 garLoopResultBuilder]: At program point L37-1(line 37) the Hoare annotation is: (let ((.cse4 (mod main_~B~0 4294967296))) (let ((.cse0 (<= .cse4 2)) (.cse1 (<= 1 .cse4)) (.cse2 (= (+ main_~r~0 (* main_~q~0 .cse4)) (mod main_~A~0 4294967296))) (.cse3 (= main_~q~0 0)) (.cse5 (< (div (+ 2 (* (- 1) main_~r~0)) (- 4294967296)) 1))) (or (and .cse0 (<= (div main_~d~0 2) main_~r~0) (<= 0 main_~d~0) .cse1 .cse2 .cse3 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse4 (div main_~p~0 2)) 2)) .cse5) (and .cse0 (= main_~d~0 (* main_~p~0 .cse4)) .cse1 .cse2 .cse3 .cse5 (= main_~p~0 1))))) [2022-04-06 23:08:27,854 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 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-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L878 garLoopResultBuilder]: At program point L16(lines 16 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-06 23:08:27,855 INFO L878 garLoopResultBuilder]: At program point L15(lines 15 18) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 23:08:27,855 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-04-06 23:08:27,855 INFO L878 garLoopResultBuilder]: At program point L15-2(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 23:08:27,855 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 14 20) the Hoare annotation is: (or (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond) (not (<= 1 |__VERIFIER_assert_#in~cond|))) [2022-04-06 23:08:27,855 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-04-06 23:08:27,858 INFO L719 BasicCegarLoop]: Path program histogram: [12, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2] [2022-04-06 23:08:27,859 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 23:08:27,875 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 11:08:27 BoogieIcfgContainer [2022-04-06 23:08:27,875 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 23:08:27,876 INFO L158 Benchmark]: Toolchain (without parser) took 443942.61ms. Allocated memory was 172.0MB in the beginning and 289.4MB in the end (delta: 117.4MB). Free memory was 120.4MB in the beginning and 141.9MB in the end (delta: -21.5MB). Peak memory consumption was 145.7MB. Max. memory is 8.0GB. [2022-04-06 23:08:27,876 INFO L158 Benchmark]: CDTParser took 0.25ms. Allocated memory is still 172.0MB. Free memory is still 137.4MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 23:08:27,877 INFO L158 Benchmark]: CACSL2BoogieTranslator took 339.41ms. Allocated memory was 172.0MB in the beginning and 241.2MB in the end (delta: 69.2MB). Free memory was 120.3MB in the beginning and 217.2MB in the end (delta: -96.9MB). Peak memory consumption was 11.7MB. Max. memory is 8.0GB. [2022-04-06 23:08:27,877 INFO L158 Benchmark]: Boogie Preprocessor took 44.53ms. Allocated memory is still 241.2MB. Free memory was 217.2MB in the beginning and 215.6MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 23:08:27,877 INFO L158 Benchmark]: RCFGBuilder took 246.98ms. Allocated memory is still 241.2MB. Free memory was 215.6MB in the beginning and 204.6MB in the end (delta: 11.0MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 23:08:27,878 INFO L158 Benchmark]: TraceAbstraction took 443303.83ms. Allocated memory was 241.2MB in the beginning and 289.4MB in the end (delta: 48.2MB). Free memory was 204.1MB in the beginning and 141.9MB in the end (delta: 62.2MB). Peak memory consumption was 160.2MB. Max. memory is 8.0GB. [2022-04-06 23:08:27,879 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.25ms. Allocated memory is still 172.0MB. Free memory is still 137.4MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 339.41ms. Allocated memory was 172.0MB in the beginning and 241.2MB in the end (delta: 69.2MB). Free memory was 120.3MB in the beginning and 217.2MB in the end (delta: -96.9MB). Peak memory consumption was 11.7MB. Max. memory is 8.0GB. * Boogie Preprocessor took 44.53ms. Allocated memory is still 241.2MB. Free memory was 217.2MB in the beginning and 215.6MB in the end (delta: 1.5MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 246.98ms. Allocated memory is still 241.2MB. Free memory was 215.6MB in the beginning and 204.6MB in the end (delta: 11.0MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 443303.83ms. Allocated memory was 241.2MB in the beginning and 289.4MB in the end (delta: 48.2MB). Free memory was 204.1MB in the beginning and 141.9MB in the end (delta: 62.2MB). Peak memory consumption was 160.2MB. 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 6 procedures, 41 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 443.2s, OverallIterations: 16, TraceHistogramMax: 18, PathProgramHistogramMax: 12, EmptinessCheckTime: 0.0s, AutomataDifference: 43.7s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 248.4s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 12 mSolverCounterUnknown, 442 SdHoareTripleChecker+Valid, 36.7s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 354 mSDsluCounter, 2751 SdHoareTripleChecker+Invalid, 36.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 117 IncrementalHoareTripleChecker+Unchecked, 2069 mSDsCounter, 331 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 3275 IncrementalHoareTripleChecker+Invalid, 3735 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 331 mSolverCounterUnsat, 682 mSDtfsCounter, 3275 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 2071 GetRequests, 1829 SyntacticMatches, 17 SemanticMatches, 225 ConstructedPredicates, 1 IntricatePredicates, 1 DeprecatedPredicates, 718 ImplicationChecksByTransitivity, 59.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=145occurred in iteration=14, InterpolantAutomatonStates: 147, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.3s AutomataMinimizationTime, 16 MinimizatonAttempts, 37 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 38 LocationsWithAnnotation, 612 PreInvPairs, 804 NumberOfFragments, 2148 HoareAnnotationTreeSize, 612 FomulaSimplifications, 758 FormulaSimplificationTreeSizeReduction, 0.2s HoareSimplificationTime, 38 FomulaSimplificationsInter, 6637 FormulaSimplificationTreeSizeReductionInter, 248.2s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: No data available, 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: 36]: Loop Invariant Derived loop invariant: ((((((((B % 4294967296 <= 2 && d / 2 <= r) && 0 <= d) && 1 <= B % 4294967296) && r + q * (B % 4294967296) == A % 4294967296) && q == 0) && p % 2 == 0) && d == B % 4294967296 * (p / 2) * 2) && (2 + -1 * r) / -4294967296 < 1) || ((((((B % 4294967296 <= 2 && d == p * (B % 4294967296)) && 1 <= B % 4294967296) && r + q * (B % 4294967296) == A % 4294967296) && q == 0) && (2 + -1 * r) / -4294967296 < 1) && p == 1) - ProcedureContractResult [Line: 11]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: !(\old(cond) == 0) && cond == \old(cond) - ProcedureContractResult [Line: 22]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert: \old(cond) == cond || !(1 <= \old(cond)) RESULT: Ultimate proved your program to be correct! [2022-04-06 23:08:27,965 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...