/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_unwindbound5.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-b030c9e [2022-03-20 21:29:54,474 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-03-20 21:29:54,475 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-03-20 21:29:54,507 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-03-20 21:29:54,507 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-03-20 21:29:54,508 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-03-20 21:29:54,510 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-03-20 21:29:54,512 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-03-20 21:29:54,513 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-03-20 21:29:54,516 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-03-20 21:29:54,517 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-03-20 21:29:54,518 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-03-20 21:29:54,518 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-03-20 21:29:54,519 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-03-20 21:29:54,520 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-03-20 21:29:54,522 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-03-20 21:29:54,523 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-03-20 21:29:54,523 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-03-20 21:29:54,525 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-03-20 21:29:54,527 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-03-20 21:29:54,528 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-03-20 21:29:54,530 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-03-20 21:29:54,531 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-03-20 21:29:54,531 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-03-20 21:29:54,532 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-03-20 21:29:54,533 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-03-20 21:29:54,533 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-03-20 21:29:54,534 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-03-20 21:29:54,534 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-03-20 21:29:54,534 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-03-20 21:29:54,535 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-03-20 21:29:54,535 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-03-20 21:29:54,535 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-03-20 21:29:54,536 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-03-20 21:29:54,536 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-03-20 21:29:54,537 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-03-20 21:29:54,537 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-03-20 21:29:54,537 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-03-20 21:29:54,538 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-03-20 21:29:54,538 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-03-20 21:29:54,538 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-03-20 21:29:54,539 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-03-20 21:29:54,539 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/acceleratedInterpolation/acceleratedInterpolationQvasr_64.epf [2022-03-20 21:29:54,544 INFO L113 SettingsManager]: Loading preferences was successful [2022-03-20 21:29:54,544 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-03-20 21:29:54,545 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-03-20 21:29:54,545 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-03-20 21:29:54,545 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * Use constant arrays=true [2022-03-20 21:29:54,546 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-03-20 21:29:54,546 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 21:29:54,547 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=Craig_NestedInterpolation [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * Trace refinement strategy=ACCELERATED_INTERPOLATION [2022-03-20 21:29:54,547 INFO L138 SettingsManager]: * Trace refinement strategy used in Accelerated Interpolation=CAMEL [2022-03-20 21:29:54,548 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-03-20 21:29:54,548 INFO L138 SettingsManager]: * Loop acceleration method that is used by accelerated interpolation=QVASR [2022-03-20 21:29:54,548 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-03-20 21:29:54,697 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-03-20 21:29:54,713 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-03-20 21:29:54,715 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-03-20 21:29:54,716 INFO L271 PluginConnector]: Initializing CDTParser... [2022-03-20 21:29:54,716 INFO L275 PluginConnector]: CDTParser initialized [2022-03-20 21:29:54,717 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound5.c [2022-03-20 21:29:54,760 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1f0fb4c0c/9f76cf6842254961b83dae2f7c2997cc/FLAG871d0ab5e [2022-03-20 21:29:55,089 INFO L306 CDTParser]: Found 1 translation units. [2022-03-20 21:29:55,089 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard-ll_unwindbound5.c [2022-03-20 21:29:55,093 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1f0fb4c0c/9f76cf6842254961b83dae2f7c2997cc/FLAG871d0ab5e [2022-03-20 21:29:55,533 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/1f0fb4c0c/9f76cf6842254961b83dae2f7c2997cc [2022-03-20 21:29:55,535 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-03-20 21:29:55,536 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2022-03-20 21:29:55,537 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-03-20 21:29:55,537 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-03-20 21:29:55,542 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-03-20 21:29:55,542 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,543 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2a4584be and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55, skipping insertion in model container [2022-03-20 21:29:55,543 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,547 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-03-20 21:29:55,556 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-03-20 21:29:55,675 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_unwindbound5.c[538,551] [2022-03-20 21:29:55,702 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 21:29:55,707 INFO L203 MainTranslator]: Completed pre-run [2022-03-20 21:29:55,713 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_unwindbound5.c[538,551] [2022-03-20 21:29:55,726 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-03-20 21:29:55,734 INFO L208 MainTranslator]: Completed translation [2022-03-20 21:29:55,734 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55 WrapperNode [2022-03-20 21:29:55,734 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-03-20 21:29:55,735 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-03-20 21:29:55,735 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-03-20 21:29:55,735 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-03-20 21:29:55,741 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,741 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,745 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,745 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,748 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,750 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,750 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,751 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-03-20 21:29:55,752 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-03-20 21:29:55,752 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-03-20 21:29:55,752 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-03-20 21:29:55,753 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (1/1) ... [2022-03-20 21:29:55,757 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-03-20 21:29:55,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:55,771 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2022-03-20 21:29:55,794 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2022-03-20 21:29:55,831 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-03-20 21:29:55,831 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-03-20 21:29:55,840 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-03-20 21:29:55,840 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-03-20 21:29:55,840 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-03-20 21:29:55,841 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-03-20 21:29:55,841 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-03-20 21:29:55,841 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-03-20 21:29:55,841 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-03-20 21:29:55,841 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-03-20 21:29:55,842 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_uint [2022-03-20 21:29:55,842 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-03-20 21:29:55,842 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-03-20 21:29:55,842 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-03-20 21:29:55,843 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-03-20 21:29:55,844 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-03-20 21:29:55,844 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-03-20 21:29:55,845 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-03-20 21:29:55,845 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-03-20 21:29:55,845 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-03-20 21:29:55,890 INFO L234 CfgBuilder]: Building ICFG [2022-03-20 21:29:55,891 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-03-20 21:29:56,023 INFO L275 CfgBuilder]: Performing block encoding [2022-03-20 21:29:56,032 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-03-20 21:29:56,032 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-03-20 21:29:56,034 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 09:29:56 BoogieIcfgContainer [2022-03-20 21:29:56,034 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-03-20 21:29:56,045 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-03-20 21:29:56,045 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-03-20 21:29:56,048 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-03-20 21:29:56,048 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 20.03 09:29:55" (1/3) ... [2022-03-20 21:29:56,049 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bed985c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 09:29:56, skipping insertion in model container [2022-03-20 21:29:56,049 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 20.03 09:29:55" (2/3) ... [2022-03-20 21:29:56,049 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4bed985c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 20.03 09:29:56, skipping insertion in model container [2022-03-20 21:29:56,049 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 20.03 09:29:56" (3/3) ... [2022-03-20 21:29:56,050 INFO L111 eAbstractionObserver]: Analyzing ICFG hard-ll_unwindbound5.c [2022-03-20 21:29:56,053 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:Craig_NestedInterpolation Determinization: PREDICATE_ABSTRACTION [2022-03-20 21:29:56,053 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-03-20 21:29:56,084 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-03-20 21:29:56,089 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-03-20 21:29:56,089 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-03-20 21:29:56,098 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-03-20 21:29:56,104 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 21:29:56,104 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:56,104 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:56,105 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:56,108 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:56,108 INFO L85 PathProgramCache]: Analyzing trace with hash 1191571617, now seen corresponding path program 1 times [2022-03-20 21:29:56,120 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,120 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [190571023] [2022-03-20 21:29:56,127 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:56,128 INFO L85 PathProgramCache]: Analyzing trace with hash 1191571617, now seen corresponding path program 2 times [2022-03-20 21:29:56,129 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:56,129 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1365135289] [2022-03-20 21:29:56,130 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:56,130 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:56,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,226 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 21:29:56,229 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,235 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 21:29:56,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,240 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 21:29:56,240 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:56,240 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1365135289] [2022-03-20 21:29:56,241 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1365135289] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,241 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,241 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 21:29:56,243 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:56,243 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [190571023] [2022-03-20 21:29:56,243 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [190571023] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,243 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,243 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-03-20 21:29:56,244 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [522779023] [2022-03-20 21:29:56,244 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:56,247 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-03-20 21:29:56,247 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,263 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-03-20 21:29:56,263 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 21:29:56,265 INFO L87 Difference]: Start difference. First operand has 37 states, 21 states have (on average 1.4761904761904763) internal successors, (31), 22 states have internal predecessors, (31), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 21:29:56,325 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:56,325 INFO L93 Difference]: Finished difference Result 66 states and 101 transitions. [2022-03-20 21:29:56,326 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-03-20 21:29:56,327 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-03-20 21:29:56,327 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:56,331 INFO L225 Difference]: With dead ends: 66 [2022-03-20 21:29:56,332 INFO L226 Difference]: Without dead ends: 33 [2022-03-20 21:29:56,334 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-03-20 21:29:56,336 INFO L913 BasicCegarLoop]: 45 mSDtfsCounter, 10 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 24 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 49 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 24 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:56,336 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 49 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 24 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 21:29:56,346 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 33 states. [2022-03-20 21:29:56,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 33 to 32. [2022-03-20 21:29:56,361 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 18 states have (on average 1.3333333333333333) internal successors, (24), 19 states have internal predecessors, (24), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 21:29:56,362 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-03-20 21:29:56,363 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 18 [2022-03-20 21:29:56,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:56,363 INFO L478 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-03-20 21:29:56,364 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 21:29:56,364 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-03-20 21:29:56,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2022-03-20 21:29:56,364 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:56,364 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:56,365 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-03-20 21:29:56,365 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:56,365 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:56,365 INFO L85 PathProgramCache]: Analyzing trace with hash 336486197, now seen corresponding path program 1 times [2022-03-20 21:29:56,366 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,366 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1115867126] [2022-03-20 21:29:56,366 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:56,366 INFO L85 PathProgramCache]: Analyzing trace with hash 336486197, now seen corresponding path program 2 times [2022-03-20 21:29:56,367 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:56,367 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1382150994] [2022-03-20 21:29:56,367 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:56,367 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:56,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,461 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 21:29:56,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,467 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 21:29:56,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:56,471 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 21:29:56,471 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:56,471 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1382150994] [2022-03-20 21:29:56,472 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1382150994] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,472 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,472 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 21:29:56,472 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:56,472 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1115867126] [2022-03-20 21:29:56,472 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1115867126] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,472 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,473 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 21:29:56,473 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [78663191] [2022-03-20 21:29:56,473 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:56,473 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 21:29:56,473 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,474 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 21:29:56,474 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 21:29:56,474 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 21:29:56,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:56,607 INFO L93 Difference]: Finished difference Result 47 states and 62 transitions. [2022-03-20 21:29:56,607 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 21:29:56,607 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 18 [2022-03-20 21:29:56,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:56,608 INFO L225 Difference]: With dead ends: 47 [2022-03-20 21:29:56,608 INFO L226 Difference]: Without dead ends: 45 [2022-03-20 21:29:56,609 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-03-20 21:29:56,610 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 28 mSDsluCounter, 57 mSDsCounter, 0 mSdLazyCounter, 93 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 35 SdHoareTripleChecker+Valid, 96 SdHoareTripleChecker+Invalid, 107 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 93 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:56,610 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [35 Valid, 96 Invalid, 107 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 93 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 21:29:56,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-03-20 21:29:56,625 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 36. [2022-03-20 21:29:56,625 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 21 states have (on average 1.2857142857142858) internal successors, (27), 22 states have internal predecessors, (27), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 21:29:56,626 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 45 transitions. [2022-03-20 21:29:56,626 INFO L78 Accepts]: Start accepts. Automaton has 36 states and 45 transitions. Word has length 18 [2022-03-20 21:29:56,627 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:56,627 INFO L478 AbstractCegarLoop]: Abstraction has 36 states and 45 transitions. [2022-03-20 21:29:56,627 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.0) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-03-20 21:29:56,627 INFO L276 IsEmpty]: Start isEmpty. Operand 36 states and 45 transitions. [2022-03-20 21:29:56,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2022-03-20 21:29:56,627 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:56,627 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:56,628 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-03-20 21:29:56,628 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:56,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:56,628 INFO L85 PathProgramCache]: Analyzing trace with hash -1819267188, now seen corresponding path program 1 times [2022-03-20 21:29:56,628 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,628 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1077184159] [2022-03-20 21:29:56,629 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:56,629 INFO L85 PathProgramCache]: Analyzing trace with hash -1819267188, now seen corresponding path program 2 times [2022-03-20 21:29:56,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:56,629 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2006866395] [2022-03-20 21:29:56,629 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:56,629 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:56,638 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:29:56,638 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [988068097] [2022-03-20 21:29:56,639 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 21:29:56,639 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:56,639 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:56,640 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:29:56,641 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-03-20 21:29:56,675 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2022-03-20 21:29:56,675 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 21:29:56,676 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 5 conjunts are in the unsatisfiable core [2022-03-20 21:29:56,679 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:29:56,771 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 21:29:56,771 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:29:56,771 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:56,771 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2006866395] [2022-03-20 21:29:56,772 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:29:56,772 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [988068097] [2022-03-20 21:29:56,772 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [988068097] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,772 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,772 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 21:29:56,773 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:56,773 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1077184159] [2022-03-20 21:29:56,773 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1077184159] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:56,773 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:56,774 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2022-03-20 21:29:56,774 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [315710163] [2022-03-20 21:29:56,774 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:56,774 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2022-03-20 21:29:56,774 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:56,775 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2022-03-20 21:29:56,775 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-20 21:29:56,775 INFO L87 Difference]: Start difference. First operand 36 states and 45 transitions. Second operand has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 21:29:56,797 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:56,797 INFO L93 Difference]: Finished difference Result 52 states and 67 transitions. [2022-03-20 21:29:56,798 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2022-03-20 21:29:56,798 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) Word has length 20 [2022-03-20 21:29:56,798 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:56,799 INFO L225 Difference]: With dead ends: 52 [2022-03-20 21:29:56,799 INFO L226 Difference]: Without dead ends: 38 [2022-03-20 21:29:56,800 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2022-03-20 21:29:56,802 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 0 mSDsluCounter, 67 mSDsCounter, 0 mSdLazyCounter, 8 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 107 SdHoareTripleChecker+Invalid, 8 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 8 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:56,802 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 107 Invalid, 8 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 8 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 21:29:56,803 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 38 states. [2022-03-20 21:29:56,807 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 38 to 38. [2022-03-20 21:29:56,807 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 23 states have (on average 1.2608695652173914) internal successors, (29), 24 states have internal predecessors, (29), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 21:29:56,808 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 47 transitions. [2022-03-20 21:29:56,808 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 47 transitions. Word has length 20 [2022-03-20 21:29:56,808 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:56,808 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 47 transitions. [2022-03-20 21:29:56,808 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 3.5) internal successors, (14), 3 states have internal predecessors, (14), 3 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 2 states have call successors, (2) [2022-03-20 21:29:56,808 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 47 transitions. [2022-03-20 21:29:56,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-03-20 21:29:56,809 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:56,809 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:56,827 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2022-03-20 21:29:57,009 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:57,010 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:57,010 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:57,010 INFO L85 PathProgramCache]: Analyzing trace with hash -784889968, now seen corresponding path program 1 times [2022-03-20 21:29:57,010 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,011 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [498478929] [2022-03-20 21:29:57,011 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:57,011 INFO L85 PathProgramCache]: Analyzing trace with hash -784889968, now seen corresponding path program 2 times [2022-03-20 21:29:57,011 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:57,011 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1240811967] [2022-03-20 21:29:57,012 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:57,012 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:57,020 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:57,103 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-03-20 21:29:57,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:57,109 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-03-20 21:29:57,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:57,112 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2022-03-20 21:29:57,114 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:57,118 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-03-20 21:29:57,118 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:57,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1240811967] [2022-03-20 21:29:57,118 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1240811967] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,118 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,118 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 21:29:57,118 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:57,118 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [498478929] [2022-03-20 21:29:57,118 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [498478929] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,118 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,118 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-03-20 21:29:57,119 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1645215672] [2022-03-20 21:29:57,119 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:57,119 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-03-20 21:29:57,119 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,119 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-03-20 21:29:57,119 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-03-20 21:29:57,119 INFO L87 Difference]: Start difference. First operand 38 states and 47 transitions. Second operand has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 21:29:57,228 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:57,228 INFO L93 Difference]: Finished difference Result 52 states and 66 transitions. [2022-03-20 21:29:57,228 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-03-20 21:29:57,228 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-03-20 21:29:57,228 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:57,229 INFO L225 Difference]: With dead ends: 52 [2022-03-20 21:29:57,229 INFO L226 Difference]: Without dead ends: 50 [2022-03-20 21:29:57,229 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 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-03-20 21:29:57,230 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 23 mSDsluCounter, 50 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 89 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:57,230 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 89 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 21:29:57,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-03-20 21:29:57,236 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 42. [2022-03-20 21:29:57,237 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 26 states have (on average 1.2307692307692308) internal successors, (32), 27 states have internal predecessors, (32), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-03-20 21:29:57,237 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 50 transitions. [2022-03-20 21:29:57,237 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 50 transitions. Word has length 23 [2022-03-20 21:29:57,238 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:57,238 INFO L478 AbstractCegarLoop]: Abstraction has 42 states and 50 transitions. [2022-03-20 21:29:57,238 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.5) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-03-20 21:29:57,238 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 50 transitions. [2022-03-20 21:29:57,238 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2022-03-20 21:29:57,238 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:57,239 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:57,239 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2022-03-20 21:29:57,239 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:57,239 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:57,239 INFO L85 PathProgramCache]: Analyzing trace with hash -1024624683, now seen corresponding path program 1 times [2022-03-20 21:29:57,239 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,239 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1581886553] [2022-03-20 21:29:57,240 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:57,240 INFO L85 PathProgramCache]: Analyzing trace with hash -1024624683, now seen corresponding path program 2 times [2022-03-20 21:29:57,240 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:57,240 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1835988080] [2022-03-20 21:29:57,240 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:57,240 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:57,248 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:29:57,248 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2082634339] [2022-03-20 21:29:57,248 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 21:29:57,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:57,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:57,259 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:29:57,260 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-03-20 21:29:57,301 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 21:29:57,301 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 21:29:57,302 INFO L263 TraceCheckSpWp]: Trace formula consists of 100 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 21:29:57,303 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:29:57,388 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 21:29:57,388 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:29:57,388 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:57,388 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1835988080] [2022-03-20 21:29:57,388 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:29:57,389 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2082634339] [2022-03-20 21:29:57,389 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2082634339] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,389 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,389 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:57,389 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:57,389 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1581886553] [2022-03-20 21:29:57,389 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1581886553] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,389 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,389 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:57,389 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1177923406] [2022-03-20 21:29:57,389 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:57,390 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 21:29:57,390 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,390 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 21:29:57,390 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 21:29:57,390 INFO L87 Difference]: Start difference. First operand 42 states and 50 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 21:29:57,428 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:57,428 INFO L93 Difference]: Finished difference Result 71 states and 93 transitions. [2022-03-20 21:29:57,428 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 21:29:57,428 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2022-03-20 21:29:57,428 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:57,429 INFO L225 Difference]: With dead ends: 71 [2022-03-20 21:29:57,429 INFO L226 Difference]: Without dead ends: 56 [2022-03-20 21:29:57,429 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 21:29:57,430 INFO L913 BasicCegarLoop]: 44 mSDtfsCounter, 10 mSDsluCounter, 110 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 40 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:57,430 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 154 Invalid, 40 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 21:29:57,431 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 56 states. [2022-03-20 21:29:57,437 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 56 to 56. [2022-03-20 21:29:57,437 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 33 states have (on average 1.2424242424242424) internal successors, (41), 35 states have internal predecessors, (41), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 21:29:57,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 70 transitions. [2022-03-20 21:29:57,438 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 70 transitions. Word has length 28 [2022-03-20 21:29:57,438 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:57,438 INFO L478 AbstractCegarLoop]: Abstraction has 56 states and 70 transitions. [2022-03-20 21:29:57,439 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-03-20 21:29:57,439 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 70 transitions. [2022-03-20 21:29:57,439 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-03-20 21:29:57,439 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:57,439 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:57,472 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-03-20 21:29:57,656 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:57,656 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:57,657 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:57,657 INFO L85 PathProgramCache]: Analyzing trace with hash 1301357193, now seen corresponding path program 1 times [2022-03-20 21:29:57,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,657 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [487627470] [2022-03-20 21:29:57,657 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:57,657 INFO L85 PathProgramCache]: Analyzing trace with hash 1301357193, now seen corresponding path program 2 times [2022-03-20 21:29:57,657 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:57,658 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [62174702] [2022-03-20 21:29:57,658 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:57,658 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:57,665 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:29:57,665 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1850505895] [2022-03-20 21:29:57,665 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 21:29:57,665 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:57,666 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:57,666 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:29:57,667 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-03-20 21:29:57,705 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 21:29:57,705 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 21:29:57,705 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 21:29:57,707 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:29:57,776 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 21:29:57,777 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:29:57,777 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:57,777 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [62174702] [2022-03-20 21:29:57,777 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:29:57,777 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1850505895] [2022-03-20 21:29:57,777 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1850505895] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,777 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,777 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:57,777 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:57,778 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [487627470] [2022-03-20 21:29:57,778 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [487627470] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:57,778 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:57,778 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:57,778 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [639342457] [2022-03-20 21:29:57,778 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:57,778 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 21:29:57,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:57,779 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 21:29:57,779 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 21:29:57,779 INFO L87 Difference]: Start difference. First operand 56 states and 70 transitions. Second operand has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-03-20 21:29:57,802 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:57,802 INFO L93 Difference]: Finished difference Result 76 states and 86 transitions. [2022-03-20 21:29:57,803 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 21:29:57,803 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) Word has length 36 [2022-03-20 21:29:57,803 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:57,804 INFO L225 Difference]: With dead ends: 76 [2022-03-20 21:29:57,804 INFO L226 Difference]: Without dead ends: 69 [2022-03-20 21:29:57,804 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 35 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2022-03-20 21:29:57,805 INFO L913 BasicCegarLoop]: 42 mSDtfsCounter, 7 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 117 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:57,805 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 117 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 21:29:57,805 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2022-03-20 21:29:57,813 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 68. [2022-03-20 21:29:57,813 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-03-20 21:29:57,814 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 78 transitions. [2022-03-20 21:29:57,814 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 78 transitions. Word has length 36 [2022-03-20 21:29:57,814 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:57,814 INFO L478 AbstractCegarLoop]: Abstraction has 68 states and 78 transitions. [2022-03-20 21:29:57,814 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.6) internal successors, (18), 4 states have internal predecessors, (18), 4 states have call successors, (7), 4 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 3 states have call successors, (5) [2022-03-20 21:29:57,814 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 78 transitions. [2022-03-20 21:29:57,815 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2022-03-20 21:29:57,815 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:57,815 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:57,837 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-03-20 21:29:58,031 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:58,032 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:58,032 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:58,032 INFO L85 PathProgramCache]: Analyzing trace with hash 1303085071, now seen corresponding path program 1 times [2022-03-20 21:29:58,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:58,032 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [811018973] [2022-03-20 21:29:58,033 INFO L202 tedInterpolationCore]: No loops in this trace, falling back to nested interpolation [2022-03-20 21:29:58,033 INFO L85 PathProgramCache]: Analyzing trace with hash 1303085071, now seen corresponding path program 2 times [2022-03-20 21:29:58,033 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:58,033 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2147276874] [2022-03-20 21:29:58,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:58,033 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:58,040 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:29:58,040 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [58756138] [2022-03-20 21:29:58,041 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-03-20 21:29:58,041 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:58,041 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:58,042 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:29:58,043 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-03-20 21:29:58,077 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-03-20 21:29:58,077 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-03-20 21:29:58,078 INFO L263 TraceCheckSpWp]: Trace formula consists of 115 conjuncts, 7 conjunts are in the unsatisfiable core [2022-03-20 21:29:58,079 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:29:58,178 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-03-20 21:29:58,179 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:29:58,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:58,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2147276874] [2022-03-20 21:29:58,179 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:29:58,179 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [58756138] [2022-03-20 21:29:58,179 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [58756138] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:58,179 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:58,179 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:58,179 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:58,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [811018973] [2022-03-20 21:29:58,180 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [811018973] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:58,180 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:58,180 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:58,180 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [789827412] [2022-03-20 21:29:58,180 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:58,180 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-03-20 21:29:58,180 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:58,180 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-03-20 21:29:58,181 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-03-20 21:29:58,181 INFO L87 Difference]: Start difference. First operand 68 states and 78 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 21:29:58,249 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:58,249 INFO L93 Difference]: Finished difference Result 82 states and 97 transitions. [2022-03-20 21:29:58,250 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-03-20 21:29:58,250 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 36 [2022-03-20 21:29:58,250 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:58,250 INFO L225 Difference]: With dead ends: 82 [2022-03-20 21:29:58,250 INFO L226 Difference]: Without dead ends: 70 [2022-03-20 21:29:58,251 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 36 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-03-20 21:29:58,253 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 11 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 40 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 40 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:58,253 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 126 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 40 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-03-20 21:29:58,254 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-03-20 21:29:58,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 69. [2022-03-20 21:29:58,261 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 69 states, 43 states have (on average 1.2093023255813953) internal successors, (52), 45 states have internal predecessors, (52), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 21:29:58,261 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 69 states to 69 states and 82 transitions. [2022-03-20 21:29:58,261 INFO L78 Accepts]: Start accepts. Automaton has 69 states and 82 transitions. Word has length 36 [2022-03-20 21:29:58,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:58,262 INFO L478 AbstractCegarLoop]: Abstraction has 69 states and 82 transitions. [2022-03-20 21:29:58,262 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, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-03-20 21:29:58,262 INFO L276 IsEmpty]: Start isEmpty. Operand 69 states and 82 transitions. [2022-03-20 21:29:58,262 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-03-20 21:29:58,263 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:58,263 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:58,303 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-03-20 21:29:58,463 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:58,463 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:58,464 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:58,464 INFO L85 PathProgramCache]: Analyzing trace with hash 817878903, now seen corresponding path program 1 times [2022-03-20 21:29:58,464 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:58,464 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [241233283] [2022-03-20 21:29:58,987 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-20 21:29:58,988 INFO L85 PathProgramCache]: Analyzing trace with hash 119537629, now seen corresponding path program 1 times [2022-03-20 21:29:58,988 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:29:58,988 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1032776877] [2022-03-20 21:29:58,988 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:58,988 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:29:58,993 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:29:58,993 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [117419128] [2022-03-20 21:29:58,993 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:29:58,993 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:58,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:29:58,995 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:29:59,015 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-03-20 21:29:59,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:29:59,042 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-20 21:29:59,043 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:29:59,086 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 21:29:59,086 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:29:59,086 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:29:59,086 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1032776877] [2022-03-20 21:29:59,086 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:29:59,087 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [117419128] [2022-03-20 21:29:59,087 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [117419128] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:59,087 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:59,087 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:29:59,369 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:29:59,369 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [241233283] [2022-03-20 21:29:59,369 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [241233283] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:29:59,369 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:29:59,369 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [20] imperfect sequences [] total 20 [2022-03-20 21:29:59,369 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2086119324] [2022-03-20 21:29:59,369 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:29:59,369 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-20 21:29:59,369 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:59,370 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-20 21:29:59,370 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2022-03-20 21:29:59,370 INFO L87 Difference]: Start difference. First operand 69 states and 82 transitions. Second operand has 20 states, 17 states have (on average 1.6470588235294117) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 21:29:59,560 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:29:59,560 INFO L93 Difference]: Finished difference Result 96 states and 120 transitions. [2022-03-20 21:29:59,560 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-03-20 21:29:59,561 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 1.6470588235294117) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) Word has length 43 [2022-03-20 21:29:59,561 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:29:59,562 INFO L225 Difference]: With dead ends: 96 [2022-03-20 21:29:59,562 INFO L226 Difference]: Without dead ends: 71 [2022-03-20 21:29:59,563 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 39 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 148 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=101, Invalid=499, Unknown=0, NotChecked=0, Total=600 [2022-03-20 21:29:59,563 INFO L913 BasicCegarLoop]: 39 mSDtfsCounter, 16 mSDsluCounter, 245 mSDsCounter, 0 mSdLazyCounter, 275 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 284 SdHoareTripleChecker+Invalid, 299 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 275 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-03-20 21:29:59,563 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 284 Invalid, 299 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 275 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-03-20 21:29:59,564 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 71 states. [2022-03-20 21:29:59,571 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 71 to 71. [2022-03-20 21:29:59,571 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 45 states have (on average 1.2) internal successors, (54), 47 states have internal predecessors, (54), 16 states have call successors, (16), 10 states have call predecessors, (16), 9 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-03-20 21:29:59,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 84 transitions. [2022-03-20 21:29:59,583 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 84 transitions. Word has length 43 [2022-03-20 21:29:59,584 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:29:59,584 INFO L478 AbstractCegarLoop]: Abstraction has 71 states and 84 transitions. [2022-03-20 21:29:59,584 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 1.6470588235294117) internal successors, (28), 13 states have internal predecessors, (28), 6 states have call successors, (8), 6 states have call predecessors, (8), 5 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2022-03-20 21:29:59,584 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 84 transitions. [2022-03-20 21:29:59,584 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2022-03-20 21:29:59,584 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:29:59,584 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:29:59,604 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-03-20 21:29:59,804 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:29:59,805 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:29:59,805 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:29:59,805 INFO L85 PathProgramCache]: Analyzing trace with hash 1861890039, now seen corresponding path program 1 times [2022-03-20 21:29:59,805 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:29:59,805 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1611013506] [2022-03-20 21:31:19,031 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-20 21:31:19,032 INFO L85 PathProgramCache]: Analyzing trace with hash -210838127, now seen corresponding path program 1 times [2022-03-20 21:31:19,032 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:31:19,033 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2017293744] [2022-03-20 21:31:19,033 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:31:19,033 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:31:19,038 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:31:19,038 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [692660334] [2022-03-20 21:31:19,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:31:19,038 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:31:19,038 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:31:19,049 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:31:19,067 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-03-20 21:31:19,110 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:31:19,111 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-20 21:31:19,113 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:31:19,179 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 21:31:19,179 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:31:19,179 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:31:19,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2017293744] [2022-03-20 21:31:19,180 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:31:19,180 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [692660334] [2022-03-20 21:31:19,180 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [692660334] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:31:19,180 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:31:19,180 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:31:19,471 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:31:19,471 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1611013506] [2022-03-20 21:31:19,472 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1611013506] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:31:19,472 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:31:19,472 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [20] imperfect sequences [] total 20 [2022-03-20 21:31:19,472 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [547520412] [2022-03-20 21:31:19,472 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:31:19,472 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 20 states [2022-03-20 21:31:19,472 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:31:19,473 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 20 interpolants. [2022-03-20 21:31:19,473 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=82, Invalid=338, Unknown=0, NotChecked=0, Total=420 [2022-03-20 21:31:19,473 INFO L87 Difference]: Start difference. First operand 71 states and 84 transitions. Second operand has 20 states, 17 states have (on average 1.588235294117647) internal successors, (27), 13 states have internal predecessors, (27), 5 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 21:31:19,839 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:31:19,839 INFO L93 Difference]: Finished difference Result 111 states and 143 transitions. [2022-03-20 21:31:19,839 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2022-03-20 21:31:19,840 INFO L78 Accepts]: Start accepts. Automaton has has 20 states, 17 states have (on average 1.588235294117647) internal successors, (27), 13 states have internal predecessors, (27), 5 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) Word has length 46 [2022-03-20 21:31:19,840 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:31:19,840 INFO L225 Difference]: With dead ends: 111 [2022-03-20 21:31:19,840 INFO L226 Difference]: Without dead ends: 79 [2022-03-20 21:31:19,841 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 56 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 140 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=116, Invalid=534, Unknown=0, NotChecked=0, Total=650 [2022-03-20 21:31:19,842 INFO L913 BasicCegarLoop]: 43 mSDtfsCounter, 34 mSDsluCounter, 336 mSDsCounter, 0 mSdLazyCounter, 288 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 379 SdHoareTripleChecker+Invalid, 305 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 288 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2022-03-20 21:31:19,842 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [39 Valid, 379 Invalid, 305 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 288 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2022-03-20 21:31:19,843 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 79 states. [2022-03-20 21:31:19,850 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 79 to 79. [2022-03-20 21:31:19,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 49 states have (on average 1.183673469387755) internal successors, (58), 51 states have internal predecessors, (58), 19 states have call successors, (19), 11 states have call predecessors, (19), 10 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2022-03-20 21:31:19,851 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 94 transitions. [2022-03-20 21:31:19,851 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 94 transitions. Word has length 46 [2022-03-20 21:31:19,851 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:31:19,851 INFO L478 AbstractCegarLoop]: Abstraction has 79 states and 94 transitions. [2022-03-20 21:31:19,851 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 20 states, 17 states have (on average 1.588235294117647) internal successors, (27), 13 states have internal predecessors, (27), 5 states have call successors, (9), 5 states have call predecessors, (9), 4 states have return successors, (7), 5 states have call predecessors, (7), 5 states have call successors, (7) [2022-03-20 21:31:19,851 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 94 transitions. [2022-03-20 21:31:19,852 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 62 [2022-03-20 21:31:19,852 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:31:19,852 INFO L499 BasicCegarLoop]: trace histogram [8, 7, 7, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:31:19,871 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-03-20 21:31:20,069 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:31:20,069 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:31:20,070 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:31:20,070 INFO L85 PathProgramCache]: Analyzing trace with hash 940283669, now seen corresponding path program 2 times [2022-03-20 21:31:20,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:31:20,070 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [2102750246] [2022-03-20 21:31:29,402 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-20 21:31:29,402 INFO L85 PathProgramCache]: Analyzing trace with hash 1218658397, now seen corresponding path program 1 times [2022-03-20 21:31:29,402 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:31:29,403 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1485507606] [2022-03-20 21:31:29,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:31:29,403 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:31:29,407 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:31:29,407 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2000747434] [2022-03-20 21:31:29,407 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:31:29,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:31:29,408 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:31:29,408 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:31:29,409 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-03-20 21:31:29,437 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:31:29,437 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 8 conjunts are in the unsatisfiable core [2022-03-20 21:31:29,438 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:31:29,497 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2022-03-20 21:31:29,497 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:31:29,497 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:31:29,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1485507606] [2022-03-20 21:31:29,497 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:31:29,497 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2000747434] [2022-03-20 21:31:29,497 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2000747434] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:31:29,497 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:31:29,497 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-03-20 21:31:34,317 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:31:34,317 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [2102750246] [2022-03-20 21:31:34,317 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [2102750246] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:31:34,317 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:31:34,317 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [34] imperfect sequences [] total 34 [2022-03-20 21:31:34,317 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1537759707] [2022-03-20 21:31:34,318 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:31:34,318 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 34 states [2022-03-20 21:31:34,318 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:31:34,318 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2022-03-20 21:31:34,319 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=167, Invalid=1093, Unknown=0, NotChecked=0, Total=1260 [2022-03-20 21:31:34,319 INFO L87 Difference]: Start difference. First operand 79 states and 94 transitions. Second operand has 34 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 21 states have internal predecessors, (40), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 21:31:35,391 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:31:35,391 INFO L93 Difference]: Finished difference Result 120 states and 150 transitions. [2022-03-20 21:31:35,392 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-03-20 21:31:35,392 INFO L78 Accepts]: Start accepts. Automaton has has 34 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 21 states have internal predecessors, (40), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) Word has length 61 [2022-03-20 21:31:35,392 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:31:35,393 INFO L225 Difference]: With dead ends: 120 [2022-03-20 21:31:35,393 INFO L226 Difference]: Without dead ends: 95 [2022-03-20 21:31:35,394 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 44 SyntacticMatches, 1 SemanticMatches, 41 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 613 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=242, Invalid=1564, Unknown=0, NotChecked=0, Total=1806 [2022-03-20 21:31:35,394 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 45 mSDsluCounter, 249 mSDsCounter, 0 mSdLazyCounter, 637 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 45 SdHoareTripleChecker+Valid, 285 SdHoareTripleChecker+Invalid, 712 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 637 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-03-20 21:31:35,394 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [45 Valid, 285 Invalid, 712 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 637 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-03-20 21:31:35,395 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2022-03-20 21:31:35,408 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 88. [2022-03-20 21:31:35,408 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 55 states have (on average 1.1818181818181819) internal successors, (65), 57 states have internal predecessors, (65), 21 states have call successors, (21), 12 states have call predecessors, (21), 11 states have return successors, (19), 18 states have call predecessors, (19), 19 states have call successors, (19) [2022-03-20 21:31:35,409 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 105 transitions. [2022-03-20 21:31:35,409 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 105 transitions. Word has length 61 [2022-03-20 21:31:35,409 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:31:35,409 INFO L478 AbstractCegarLoop]: Abstraction has 88 states and 105 transitions. [2022-03-20 21:31:35,409 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 34 states, 29 states have (on average 1.3793103448275863) internal successors, (40), 21 states have internal predecessors, (40), 9 states have call successors, (11), 9 states have call predecessors, (11), 8 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2022-03-20 21:31:35,409 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 105 transitions. [2022-03-20 21:31:35,410 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-03-20 21:31:35,410 INFO L491 BasicCegarLoop]: Found error trace [2022-03-20 21:31:35,410 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-03-20 21:31:35,431 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-03-20 21:31:35,629 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:31:35,629 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-03-20 21:31:35,629 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-03-20 21:31:35,629 INFO L85 PathProgramCache]: Analyzing trace with hash 1995039641, now seen corresponding path program 2 times [2022-03-20 21:31:35,629 INFO L118 FreeRefinementEngine]: Executing refinement strategy ACCELERATED_INTERPOLATION [2022-03-20 21:31:35,629 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleAcceleratedInterpolation [1612899805] [2022-03-20 21:32:30,950 INFO L271 tedInterpolationCore]: Starting analysis with loop acceleration approximation PRECISE [2022-03-20 21:32:30,951 INFO L85 PathProgramCache]: Analyzing trace with hash -1134703343, now seen corresponding path program 1 times [2022-03-20 21:32:30,951 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-03-20 21:32:30,951 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [655503349] [2022-03-20 21:32:30,951 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:32:30,951 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-03-20 21:32:30,958 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-03-20 21:32:30,959 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [901819239] [2022-03-20 21:32:30,959 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-03-20 21:32:30,959 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-03-20 21:32:30,959 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-03-20 21:32:30,969 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-03-20 21:32:30,970 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-03-20 21:32:31,001 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-03-20 21:32:31,001 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 13 conjunts are in the unsatisfiable core [2022-03-20 21:32:31,002 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-03-20 21:32:31,095 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-03-20 21:32:31,095 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-03-20 21:32:31,096 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-03-20 21:32:31,096 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [655503349] [2022-03-20 21:32:31,096 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-03-20 21:32:31,096 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [901819239] [2022-03-20 21:32:31,096 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [901819239] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:32:31,096 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:32:31,096 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2022-03-20 21:32:36,884 INFO L136 FreeRefinementEngine]: Strategy ACCELERATED_INTERPOLATION found an infeasible trace [2022-03-20 21:32:36,884 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleAcceleratedInterpolation [1612899805] [2022-03-20 21:32:36,884 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleAcceleratedInterpolation [1612899805] provided 1 perfect and 0 imperfect interpolant sequences [2022-03-20 21:32:36,884 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-03-20 21:32:36,884 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [27] imperfect sequences [] total 27 [2022-03-20 21:32:36,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1224386182] [2022-03-20 21:32:36,884 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-03-20 21:32:36,884 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2022-03-20 21:32:36,884 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy ACCELERATED_INTERPOLATION [2022-03-20 21:32:36,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2022-03-20 21:32:36,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=640, Unknown=0, NotChecked=0, Total=756 [2022-03-20 21:32:36,885 INFO L87 Difference]: Start difference. First operand 88 states and 105 transitions. Second operand has 27 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 18 states have internal predecessors, (32), 6 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-03-20 21:32:37,882 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-03-20 21:32:37,882 INFO L93 Difference]: Finished difference Result 88 states and 105 transitions. [2022-03-20 21:32:37,882 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2022-03-20 21:32:37,882 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 18 states have internal predecessors, (32), 6 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 64 [2022-03-20 21:32:37,882 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-03-20 21:32:37,883 INFO L225 Difference]: With dead ends: 88 [2022-03-20 21:32:37,883 INFO L226 Difference]: Without dead ends: 0 [2022-03-20 21:32:37,883 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 78 GetRequests, 44 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 255 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=150, Invalid=906, Unknown=0, NotChecked=0, Total=1056 [2022-03-20 21:32:37,884 INFO L913 BasicCegarLoop]: 16 mSDtfsCounter, 33 mSDsluCounter, 126 mSDsCounter, 0 mSdLazyCounter, 207 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 207 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2022-03-20 21:32:37,884 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [34 Valid, 142 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 207 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2022-03-20 21:32:37,884 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-03-20 21:32:37,884 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-03-20 21:32:37,884 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-03-20 21:32:37,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-03-20 21:32:37,884 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 64 [2022-03-20 21:32:37,884 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-03-20 21:32:37,884 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-03-20 21:32:37,884 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 24 states have (on average 1.3333333333333333) internal successors, (32), 18 states have internal predecessors, (32), 6 states have call successors, (10), 6 states have call predecessors, (10), 6 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2022-03-20 21:32:37,884 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-03-20 21:32:37,884 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-03-20 21:32:37,886 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-03-20 21:32:37,906 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-03-20 21:32:38,099 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-03-20 21:32:38,101 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-03-20 21:32:39,744 INFO L882 garLoopResultBuilder]: For program point reach_errorEXIT(line 8) no Hoare annotation was computed. [2022-03-20 21:32:39,744 INFO L882 garLoopResultBuilder]: For program point reach_errorENTRY(line 8) no Hoare annotation was computed. [2022-03-20 21:32:39,745 INFO L882 garLoopResultBuilder]: For program point reach_errorFINAL(line 8) no Hoare annotation was computed. [2022-03-20 21:32:39,745 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L12(line 12) the Hoare annotation is: (or (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|) (not (<= ~counter~0 0))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L12-2(lines 11 13) the Hoare annotation is: (or (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) (not (<= ~counter~0 0))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point assume_abort_if_notEXIT(lines 11 13) the Hoare annotation is: (or (and (not (= |assume_abort_if_not_#in~cond| 0)) (= assume_abort_if_not_~cond |assume_abort_if_not_#in~cond|)) (not (<= ~counter~0 0))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L35-3(lines 35 43) the Hoare annotation is: (let ((.cse0 (mod main_~B~0 4294967296))) (let ((.cse1 (<= 1 .cse0)) (.cse2 (= main_~q~0 0))) (or (and (= ~counter~0 |old(~counter~0)|) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~d~0 (* main_~p~0 .cse0)) .cse1 .cse2 (= main_~p~0 1)) (not (<= |old(~counter~0)| 0)) (and (= main_~A~0 (+ main_~r~0 (* (div main_~A~0 4294967296) 4294967296))) (<= ~counter~0 1) (<= (* (div (* (- 1) main_~p~0) (- 2)) .cse0) main_~r~0) .cse1 .cse2 (= (mod main_~p~0 2) 0) (= main_~d~0 (* (* .cse0 (div main_~p~0 2)) 2)))))) [2022-03-20 21:32:39,745 INFO L885 garLoopResultBuilder]: At program point L60(line 60) the Hoare annotation is: true [2022-03-20 21:32:39,745 INFO L885 garLoopResultBuilder]: At program point mainEXIT(lines 23 62) the Hoare annotation is: true [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L46(line 46) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L46-1(line 46) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,745 INFO L885 garLoopResultBuilder]: At program point mainFINAL(lines 23 62) the Hoare annotation is: true [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L38(lines 35 43) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (let ((.cse0 (mod main_~B~0 4294967296))) (and (= (mod main_~A~0 4294967296) main_~r~0) (<= ~counter~0 1) (= main_~d~0 (* main_~p~0 .cse0)) (<= 1 .cse0) (= main_~q~0 0) (= main_~p~0 1)))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L36(line 36) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (let ((.cse0 (mod main_~B~0 4294967296))) (and (= (mod main_~A~0 4294967296) main_~r~0) (<= ~counter~0 1) (= main_~d~0 (* main_~p~0 .cse0)) (<= 1 .cse0) (= main_~q~0 0) (= main_~p~0 1)))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L36-1(line 36) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (let ((.cse0 (mod main_~B~0 4294967296))) (and (= (mod main_~A~0 4294967296) main_~r~0) (<= ~counter~0 1) (= main_~d~0 (* main_~p~0 .cse0)) (<= 1 .cse0) (= main_~q~0 0) (= main_~p~0 1)))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point mainENTRY(lines 23 62) the Hoare annotation is: (or (= ~counter~0 |old(~counter~0)|) (not (<= |old(~counter~0)| 0))) [2022-03-20 21:32:39,745 INFO L878 garLoopResultBuilder]: At program point L28(line 28) the Hoare annotation is: (or (= ~counter~0 |old(~counter~0)|) (not (<= |old(~counter~0)| 0))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L28-1(line 28) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= ~counter~0 |old(~counter~0)|) (<= 1 (mod main_~B~0 4294967296)))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L59(line 59) the Hoare annotation is: (or (and (= main_~d~0 (mod main_~B~0 4294967296)) (= main_~p~0 1)) (not (<= |old(~counter~0)| 0))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L53(lines 53 56) the Hoare annotation is: (not (<= |old(~counter~0)| 0)) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L53-2(lines 23 62) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L47(lines 45 57) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L45(lines 45 57) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L45-2(lines 45 57) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (and (= main_~d~0 (mod main_~B~0 4294967296)) (= (mod main_~A~0 4294967296) main_~r~0) (= main_~q~0 0) (= main_~p~0 1))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L37(line 37) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (let ((.cse0 (mod main_~B~0 4294967296))) (and (= (mod main_~A~0 4294967296) main_~r~0) (<= ~counter~0 1) (= main_~d~0 (* main_~p~0 .cse0)) (<= 1 .cse0) (= main_~q~0 0) (= main_~p~0 1)))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L35-1(lines 35 43) the Hoare annotation is: (or (not (<= |old(~counter~0)| 0)) (let ((.cse0 (mod main_~B~0 4294967296))) (and (= (mod main_~A~0 4294967296) main_~r~0) (= main_~d~0 (* main_~p~0 .cse0)) (<= |main_#t~post6| 0) (<= 1 .cse0) (= main_~q~0 0) (= ~counter~0 (+ |main_#t~post6| 1)) (= main_~p~0 1)))) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initFINAL(line -1) the Hoare annotation is: (<= ~counter~0 0) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= ~counter~0 |old(~counter~0)|) (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initEXIT(line -1) the Hoare annotation is: (<= ~counter~0 0) [2022-03-20 21:32:39,746 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startEXIT(line -1) the Hoare annotation is: true [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: (<= ~counter~0 0) [2022-03-20 21:32:39,746 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-03-20 21:32:39,746 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startFINAL(line -1) the Hoare annotation is: true [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L16(lines 16 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L15(lines 15 18) the Hoare annotation is: (let ((.cse0 (not (= |__VERIFIER_assert_#in~cond| 1))) (.cse2 (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)) (.cse3 (not (<= ~counter~0 1)))) (and (or (not (<= 1 |__VERIFIER_assert_#in~cond|)) (<= 1 __VERIFIER_assert_~cond)) (let ((.cse1 (mod main_~B~0 4294967296))) (or .cse0 (not (= main_~d~0 .cse1)) .cse2 .cse3 (not (= main_~p~0 1)) (not (<= 1 .cse1)))) (or .cse0 (not (= main_~q~0 0)) .cse2 .cse3) (or (not (= (mod main_~A~0 4294967296) main_~r~0)) .cse0 .cse2 .cse3))) [2022-03-20 21:32:39,746 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-03-20 21:32:39,746 INFO L878 garLoopResultBuilder]: At program point L15-2(lines 14 20) the Hoare annotation is: (let ((.cse0 (not (= |__VERIFIER_assert_#in~cond| 1))) (.cse2 (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)) (.cse3 (not (<= ~counter~0 1)))) (and (or (not (<= 1 |__VERIFIER_assert_#in~cond|)) (<= 1 __VERIFIER_assert_~cond)) (let ((.cse1 (mod main_~B~0 4294967296))) (or .cse0 (not (= main_~d~0 .cse1)) .cse2 .cse3 (not (= main_~p~0 1)) (not (<= 1 .cse1)))) (or .cse0 (not (= main_~q~0 0)) .cse2 .cse3) (or (not (= (mod main_~A~0 4294967296) main_~r~0)) .cse0 .cse2 .cse3))) [2022-03-20 21:32:39,747 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertEXIT(lines 14 20) the Hoare annotation is: (let ((.cse0 (not (= |__VERIFIER_assert_#in~cond| 1))) (.cse2 (= |__VERIFIER_assert_#in~cond| __VERIFIER_assert_~cond)) (.cse3 (not (<= ~counter~0 1)))) (and (or (not (<= 1 |__VERIFIER_assert_#in~cond|)) (<= 1 __VERIFIER_assert_~cond)) (let ((.cse1 (mod main_~B~0 4294967296))) (or .cse0 (not (= main_~d~0 .cse1)) .cse2 .cse3 (not (= main_~p~0 1)) (not (<= 1 .cse1)))) (or .cse0 (not (= main_~q~0 0)) .cse2 .cse3) (or (not (= (mod main_~A~0 4294967296) main_~r~0)) .cse0 .cse2 .cse3))) [2022-03-20 21:32:39,747 INFO L878 garLoopResultBuilder]: At program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) the Hoare annotation is: (not (<= 1 |__VERIFIER_assert_#in~cond|)) [2022-03-20 21:32:39,749 INFO L719 BasicCegarLoop]: Path program histogram: [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2022-03-20 21:32:39,749 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-03-20 21:32:39,759 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 20.03 09:32:39 BoogieIcfgContainer [2022-03-20 21:32:39,759 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-03-20 21:32:39,759 INFO L158 Benchmark]: Toolchain (without parser) took 164223.53ms. Allocated memory was 205.5MB in the beginning and 363.9MB in the end (delta: 158.3MB). Free memory was 153.5MB in the beginning and 269.8MB in the end (delta: -116.3MB). Peak memory consumption was 41.1MB. Max. memory is 8.0GB. [2022-03-20 21:32:39,759 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 205.5MB. Free memory was 169.6MB in the beginning and 169.5MB in the end (delta: 81.1kB). There was no memory consumed. Max. memory is 8.0GB. [2022-03-20 21:32:39,760 INFO L158 Benchmark]: CACSL2BoogieTranslator took 197.70ms. Allocated memory was 205.5MB in the beginning and 303.0MB in the end (delta: 97.5MB). Free memory was 153.3MB in the beginning and 275.5MB in the end (delta: -122.1MB). Peak memory consumption was 11.7MB. Max. memory is 8.0GB. [2022-03-20 21:32:39,760 INFO L158 Benchmark]: Boogie Preprocessor took 16.73ms. Allocated memory is still 303.0MB. Free memory was 275.5MB in the beginning and 274.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-03-20 21:32:39,760 INFO L158 Benchmark]: RCFGBuilder took 281.96ms. Allocated memory is still 303.0MB. Free memory was 274.1MB in the beginning and 262.9MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-03-20 21:32:39,760 INFO L158 Benchmark]: TraceAbstraction took 163714.06ms. Allocated memory was 303.0MB in the beginning and 363.9MB in the end (delta: 60.8MB). Free memory was 262.5MB in the beginning and 269.8MB in the end (delta: -7.3MB). Peak memory consumption was 54.5MB. Max. memory is 8.0GB. [2022-03-20 21:32:39,761 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.11ms. Allocated memory is still 205.5MB. Free memory was 169.6MB in the beginning and 169.5MB in the end (delta: 81.1kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 197.70ms. Allocated memory was 205.5MB in the beginning and 303.0MB in the end (delta: 97.5MB). Free memory was 153.3MB in the beginning and 275.5MB in the end (delta: -122.1MB). Peak memory consumption was 11.7MB. Max. memory is 8.0GB. * Boogie Preprocessor took 16.73ms. Allocated memory is still 303.0MB. Free memory was 275.5MB in the beginning and 274.1MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 281.96ms. Allocated memory is still 303.0MB. Free memory was 274.1MB in the beginning and 262.9MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * TraceAbstraction took 163714.06ms. Allocated memory was 303.0MB in the beginning and 363.9MB in the end (delta: 60.8MB). Free memory was 262.5MB in the beginning and 269.8MB in the end (delta: -7.3MB). Peak memory consumption was 54.5MB. 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, 40 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 163.7s, OverallIterations: 11, TraceHistogramMax: 9, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 3.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 1.6s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 244 SdHoareTripleChecker+Valid, 2.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 217 mSDsluCounter, 1828 SdHoareTripleChecker+Invalid, 2.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1410 mSDsCounter, 186 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1732 IncrementalHoareTripleChecker+Invalid, 1918 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 186 mSolverCounterUnsat, 418 mSDtfsCounter, 1732 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 435 GetRequests, 282 SyntacticMatches, 4 SemanticMatches, 149 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1166 ImplicationChecksByTransitivity, 11.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=88occurred in iteration=10, InterpolantAutomatonStates: 115, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 11 MinimizatonAttempts, 27 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 37 LocationsWithAnnotation, 409 PreInvPairs, 491 NumberOfFragments, 707 HoareAnnotationTreeSize, 409 FomulaSimplifications, 289 FormulaSimplificationTreeSizeReduction, 0.0s HoareSimplificationTime, 37 FomulaSimplificationsInter, 893 FormulaSimplificationTreeSizeReductionInter, 1.6s 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: 35]: Loop Invariant Derived loop invariant: ((((((counter == \old(counter) && A % 4294967296 == r) && d == p * (B % 4294967296)) && 1 <= B % 4294967296) && q == 0) && p == 1) || !(\old(counter) <= 0)) || ((((((A == r + A / 4294967296 * 4294967296 && counter <= 1) && -1 * p / -2 * (B % 4294967296) <= r) && 1 <= B % 4294967296) && q == 0) && p % 2 == 0) && d == B % 4294967296 * (p / 2) * 2) - ProcedureContractResult [Line: 11]: Procedure Contract for assume_abort_if_not Derived contract for procedure assume_abort_if_not: (!(\old(cond) == 0) && cond == \old(cond)) || !(counter <= 0) - ProcedureContractResult [Line: 23]: Procedure Contract for main Derived contract for procedure main: 1 - ProcedureContractResult [Line: 14]: Procedure Contract for __VERIFIER_assert Derived contract for procedure __VERIFIER_assert: (((!(1 <= \old(cond)) || 1 <= cond) && (((((!(\old(cond) == 1) || !(d == B % 4294967296)) || \old(cond) == cond) || !(counter <= 1)) || !(p == 1)) || !(1 <= B % 4294967296))) && (((!(\old(cond) == 1) || !(q == 0)) || \old(cond) == cond) || !(counter <= 1))) && (((!(A % 4294967296 == r) || !(\old(cond) == 1)) || \old(cond) == cond) || !(counter <= 1)) RESULT: Ultimate proved your program to be correct! [2022-03-20 21:32:39,782 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...