/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_valuebound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-05ce600 [2022-02-23 18:00:21,855 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-23 18:00:21,856 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-23 18:00:21,890 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-23 18:00:21,890 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-23 18:00:21,908 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-23 18:00:21,909 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-23 18:00:21,910 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-23 18:00:21,911 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-23 18:00:21,911 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-23 18:00:21,912 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-23 18:00:21,923 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-23 18:00:21,924 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-23 18:00:21,925 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-23 18:00:21,925 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-23 18:00:21,926 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-23 18:00:21,926 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-23 18:00:21,927 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-23 18:00:21,928 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-23 18:00:21,929 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-23 18:00:21,930 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-23 18:00:21,931 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-23 18:00:21,932 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-23 18:00:21,932 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-23 18:00:21,934 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-23 18:00:21,934 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-23 18:00:21,934 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-23 18:00:21,935 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-23 18:00:21,935 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-23 18:00:21,935 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-23 18:00:21,936 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-23 18:00:21,936 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-23 18:00:21,936 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-23 18:00:21,937 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-23 18:00:21,938 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-23 18:00:21,938 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-23 18:00:21,938 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-23 18:00:21,938 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-23 18:00:21,938 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-23 18:00:21,939 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-23 18:00:21,939 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-23 18:00:21,944 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/LoopAccelerationJordanC.epf [2022-02-23 18:00:21,951 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-23 18:00:21,951 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-23 18:00:21,952 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-23 18:00:21,952 INFO L138 SettingsManager]: * sizeof long=4 [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * sizeof POINTER=4 [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * sizeof long double=12 [2022-02-23 18:00:21,953 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-23 18:00:21,954 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * To the following directory=./dump/ [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-23 18:00:21,954 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 18:00:21,954 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-23 18:00:21,955 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-23 18:00:21,960 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-23 18:00:21,960 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_JORDAN WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-02-23 18:00:22,174 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-23 18:00:22,191 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-23 18:00:22,193 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-23 18:00:22,193 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-23 18:00:22,207 INFO L275 PluginConnector]: CDTParser initialized [2022-02-23 18:00:22,209 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_valuebound100.c [2022-02-23 18:00:22,257 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/468260e09/ca59313486674b2cbc44aa7898c60b91/FLAG29b4ec36d [2022-02-23 18:00:22,630 INFO L306 CDTParser]: Found 1 translation units. [2022-02-23 18:00:22,630 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/egcd-ll_valuebound100.c [2022-02-23 18:00:22,635 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/468260e09/ca59313486674b2cbc44aa7898c60b91/FLAG29b4ec36d [2022-02-23 18:00:22,655 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/468260e09/ca59313486674b2cbc44aa7898c60b91 [2022-02-23 18:00:22,658 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-23 18:00:22,660 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-23 18:00:22,664 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-23 18:00:22,664 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-23 18:00:22,666 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-23 18:00:22,667 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,668 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a1ebd2f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22, skipping insertion in model container [2022-02-23 18:00:22,668 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,673 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-23 18:00:22,687 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-23 18:00:22,891 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/egcd-ll_valuebound100.c[489,502] [2022-02-23 18:00:22,905 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 18:00:22,910 INFO L203 MainTranslator]: Completed pre-run [2022-02-23 18:00:22,921 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/egcd-ll_valuebound100.c[489,502] [2022-02-23 18:00:22,942 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 18:00:22,952 INFO L208 MainTranslator]: Completed translation [2022-02-23 18:00:22,953 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22 WrapperNode [2022-02-23 18:00:22,953 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-23 18:00:22,955 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-23 18:00:22,955 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-23 18:00:22,955 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-23 18:00:22,963 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,964 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,970 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,970 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,981 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,985 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,991 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:22,995 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-23 18:00:22,996 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-23 18:00:22,996 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-23 18:00:22,996 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-23 18:00:22,997 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (1/1) ... [2022-02-23 18:00:23,002 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 18:00:23,010 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:23,037 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-02-23 18:00:23,044 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-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-23 18:00:23,071 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-02-23 18:00:23,072 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-23 18:00:23,073 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-23 18:00:23,073 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-23 18:00:23,073 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-23 18:00:23,074 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-23 18:00:23,074 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-23 18:00:23,074 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-23 18:00:23,074 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-23 18:00:23,074 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-23 18:00:23,143 INFO L234 CfgBuilder]: Building ICFG [2022-02-23 18:00:23,144 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-23 18:00:23,274 INFO L275 CfgBuilder]: Performing block encoding [2022-02-23 18:00:23,279 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-23 18:00:23,279 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-02-23 18:00:23,280 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 06:00:23 BoogieIcfgContainer [2022-02-23 18:00:23,280 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-23 18:00:23,281 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-23 18:00:23,281 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-23 18:00:23,282 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-23 18:00:23,284 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 06:00:23" (1/1) ... [2022-02-23 18:00:23,297 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 06:00:23 BasicIcfg [2022-02-23 18:00:23,297 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-23 18:00:23,298 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-23 18:00:23,298 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-23 18:00:23,300 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-23 18:00:23,301 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.02 06:00:22" (1/4) ... [2022-02-23 18:00:23,301 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38c4a384 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 06:00:23, skipping insertion in model container [2022-02-23 18:00:23,301 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 06:00:22" (2/4) ... [2022-02-23 18:00:23,302 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38c4a384 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 06:00:23, skipping insertion in model container [2022-02-23 18:00:23,302 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 06:00:23" (3/4) ... [2022-02-23 18:00:23,302 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@38c4a384 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 06:00:23, skipping insertion in model container [2022-02-23 18:00:23,302 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 06:00:23" (4/4) ... [2022-02-23 18:00:23,303 INFO L111 eAbstractionObserver]: Analyzing ICFG egcd-ll_valuebound100.cJordan [2022-02-23 18:00:23,307 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:ForwardPredicates Determinization: PREDICATE_ABSTRACTION [2022-02-23 18:00:23,307 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-23 18:00:23,336 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-23 18:00:23,341 INFO L339 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=ForwardPredicates, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=false, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=All, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mLoopAccelerationTechnique=FAST_UPR [2022-02-23 18:00:23,342 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-23 18:00:23,352 INFO L276 IsEmpty]: Start isEmpty. Operand has 37 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-02-23 18:00:23,359 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-02-23 18:00:23,359 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:23,359 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:23,360 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:23,363 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:23,364 INFO L85 PathProgramCache]: Analyzing trace with hash -1381881312, now seen corresponding path program 1 times [2022-02-23 18:00:23,370 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:23,370 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493988509] [2022-02-23 18:00:23,371 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:23,373 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:23,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,535 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 18:00:23,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,583 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-02-23 18:00:23,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,588 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-02-23 18:00:23,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,609 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 17 [2022-02-23 18:00:23,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,615 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2022-02-23 18:00:23,617 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,624 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 18:00:23,625 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:23,625 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493988509] [2022-02-23 18:00:23,626 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [493988509] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 18:00:23,626 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 18:00:23,626 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-23 18:00:23,627 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2026976406] [2022-02-23 18:00:23,628 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:23,631 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-23 18:00:23,631 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:23,657 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-23 18:00:23,658 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 18:00:23,660 INFO L87 Difference]: Start difference. First operand has 37 states, 18 states have (on average 1.3888888888888888) internal successors, (25), 19 states have internal predecessors, (25), 13 states have call successors, (13), 4 states have call predecessors, (13), 4 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-02-23 18:00:23,721 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:23,721 INFO L93 Difference]: Finished difference Result 37 states and 47 transitions. [2022-02-23 18:00:23,728 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-23 18:00:23,730 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 33 [2022-02-23 18:00:23,730 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:23,735 INFO L225 Difference]: With dead ends: 37 [2022-02-23 18:00:23,735 INFO L226 Difference]: Without dead ends: 32 [2022-02-23 18:00:23,736 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 18:00:23,739 INFO L933 BasicCegarLoop]: 36 mSDtfsCounter, 18 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 39 SdHoareTripleChecker+Invalid, 25 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:23,740 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 39 Invalid, 25 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:23,753 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2022-02-23 18:00:23,764 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2022-02-23 18:00:23,765 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 15 states have (on average 1.2) internal successors, (18), 16 states have internal predecessors, (18), 13 states have call successors, (13), 4 states have call predecessors, (13), 3 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2022-02-23 18:00:23,766 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2022-02-23 18:00:23,767 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 33 [2022-02-23 18:00:23,767 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:23,767 INFO L470 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2022-02-23 18:00:23,768 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-02-23 18:00:23,768 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2022-02-23 18:00:23,769 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 34 [2022-02-23 18:00:23,769 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:23,769 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:23,769 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-02-23 18:00:23,770 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:23,770 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:23,770 INFO L85 PathProgramCache]: Analyzing trace with hash 1975235811, now seen corresponding path program 1 times [2022-02-23 18:00:23,770 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:23,770 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [847912122] [2022-02-23 18:00:23,771 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:23,771 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:23,784 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:23,785 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [456854312] [2022-02-23 18:00:23,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:23,785 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:23,785 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:23,787 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-02-23 18:00:23,788 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-02-23 18:00:23,846 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:23,848 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 18:00:23,852 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:24,017 INFO L134 CoverageAnalysis]: Checked inductivity of 24 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 18:00:24,017 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 18:00:24,017 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:24,018 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [847912122] [2022-02-23 18:00:24,018 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:24,018 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [456854312] [2022-02-23 18:00:24,018 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [456854312] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 18:00:24,018 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 18:00:24,018 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 18:00:24,019 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [133688091] [2022-02-23 18:00:24,019 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:24,020 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:24,020 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:24,020 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:24,020 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 18:00:24,020 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-02-23 18:00:24,079 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:24,079 INFO L93 Difference]: Finished difference Result 46 states and 63 transitions. [2022-02-23 18:00:24,079 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:24,079 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) Word has length 33 [2022-02-23 18:00:24,080 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:24,080 INFO L225 Difference]: With dead ends: 46 [2022-02-23 18:00:24,080 INFO L226 Difference]: Without dead ends: 46 [2022-02-23 18:00:24,081 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 29 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-02-23 18:00:24,082 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 7 mSDsluCounter, 113 mSDsCounter, 0 mSdLazyCounter, 30 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 32 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 30 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:24,082 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 155 Invalid, 32 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 30 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:24,083 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 46 states. [2022-02-23 18:00:24,088 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 46 to 45. [2022-02-23 18:00:24,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 21 states have (on average 1.2380952380952381) internal successors, (26), 23 states have internal predecessors, (26), 19 states have call successors, (19), 5 states have call predecessors, (19), 4 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2022-02-23 18:00:24,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 62 transitions. [2022-02-23 18:00:24,089 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 62 transitions. Word has length 33 [2022-02-23 18:00:24,090 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:24,090 INFO L470 AbstractCegarLoop]: Abstraction has 45 states and 62 transitions. [2022-02-23 18:00:24,090 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 4 states have internal predecessors, (12), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 1 states have call predecessors, (5), 1 states have call successors, (5) [2022-02-23 18:00:24,090 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 62 transitions. [2022-02-23 18:00:24,091 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2022-02-23 18:00:24,091 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:24,091 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:24,130 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-02-23 18:00:24,316 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:24,317 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:24,317 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:24,317 INFO L85 PathProgramCache]: Analyzing trace with hash -759782395, now seen corresponding path program 1 times [2022-02-23 18:00:24,317 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:24,318 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [281430797] [2022-02-23 18:00:24,318 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:24,318 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:24,330 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:24,330 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [911626143] [2022-02-23 18:00:24,330 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:24,330 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:24,331 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:24,332 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-02-23 18:00:24,333 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-02-23 18:00:24,377 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:24,378 INFO L263 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 9 conjunts are in the unsatisfiable core [2022-02-23 18:00:24,380 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:24,489 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2022-02-23 18:00:24,490 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 18:00:24,490 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:24,491 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [281430797] [2022-02-23 18:00:24,492 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:24,492 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [911626143] [2022-02-23 18:00:24,492 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [911626143] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 18:00:24,492 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 18:00:24,492 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 18:00:24,492 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [854842878] [2022-02-23 18:00:24,492 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:24,493 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:24,493 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:24,493 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:24,493 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 18:00:24,494 INFO L87 Difference]: Start difference. First operand 45 states and 62 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-02-23 18:00:24,543 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:24,544 INFO L93 Difference]: Finished difference Result 50 states and 66 transitions. [2022-02-23 18:00:24,544 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:24,544 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 38 [2022-02-23 18:00:24,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:24,547 INFO L225 Difference]: With dead ends: 50 [2022-02-23 18:00:24,547 INFO L226 Difference]: Without dead ends: 50 [2022-02-23 18:00:24,548 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 38 GetRequests, 34 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-02-23 18:00:24,551 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 8 mSDsluCounter, 112 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 156 SdHoareTripleChecker+Invalid, 35 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:24,552 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [13 Valid, 156 Invalid, 35 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:24,553 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-02-23 18:00:24,563 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 49. [2022-02-23 18:00:24,563 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 24 states have (on average 1.2083333333333333) internal successors, (29), 26 states have internal predecessors, (29), 19 states have call successors, (19), 6 states have call predecessors, (19), 5 states have return successors, (17), 16 states have call predecessors, (17), 17 states have call successors, (17) [2022-02-23 18:00:24,567 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 65 transitions. [2022-02-23 18:00:24,568 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 65 transitions. Word has length 38 [2022-02-23 18:00:24,568 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:24,568 INFO L470 AbstractCegarLoop]: Abstraction has 49 states and 65 transitions. [2022-02-23 18:00:24,568 INFO L471 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, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2022-02-23 18:00:24,568 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 65 transitions. [2022-02-23 18:00:24,570 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2022-02-23 18:00:24,570 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:24,570 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:24,592 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-02-23 18:00:24,784 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-02-23 18:00:24,784 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:24,785 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:24,785 INFO L85 PathProgramCache]: Analyzing trace with hash -1840397536, now seen corresponding path program 1 times [2022-02-23 18:00:24,785 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:24,785 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [345680095] [2022-02-23 18:00:24,785 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:24,785 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:24,800 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:24,800 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2117518915] [2022-02-23 18:00:24,800 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:24,800 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:24,801 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:24,805 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-02-23 18:00:24,810 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-02-23 18:00:24,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:24,848 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 19 conjunts are in the unsatisfiable core [2022-02-23 18:00:24,851 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:25,036 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 7 proven. 9 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-02-23 18:00:25,036 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 18:00:25,164 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-02-23 18:00:25,164 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:25,164 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [345680095] [2022-02-23 18:00:25,164 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:25,164 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2117518915] [2022-02-23 18:00:25,164 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2117518915] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 18:00:25,164 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 18:00:25,164 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [9] total 10 [2022-02-23 18:00:25,165 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [606045465] [2022-02-23 18:00:25,165 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:25,165 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:25,165 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:25,165 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:25,166 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2022-02-23 18:00:25,166 INFO L87 Difference]: Start difference. First operand 49 states and 65 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-02-23 18:00:25,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:25,203 INFO L93 Difference]: Finished difference Result 72 states and 103 transitions. [2022-02-23 18:00:25,203 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:25,203 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 43 [2022-02-23 18:00:25,203 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:25,205 INFO L225 Difference]: With dead ends: 72 [2022-02-23 18:00:25,205 INFO L226 Difference]: Without dead ends: 70 [2022-02-23 18:00:25,206 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 86 GetRequests, 76 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2022-02-23 18:00:25,206 INFO L933 BasicCegarLoop]: 44 mSDtfsCounter, 8 mSDsluCounter, 111 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:25,206 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 155 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:25,207 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-02-23 18:00:25,211 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 70. [2022-02-23 18:00:25,212 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 70 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 37 states have internal predecessors, (42), 30 states have call successors, (30), 7 states have call predecessors, (30), 6 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2022-02-23 18:00:25,212 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 70 states to 70 states and 98 transitions. [2022-02-23 18:00:25,213 INFO L78 Accepts]: Start accepts. Automaton has 70 states and 98 transitions. Word has length 43 [2022-02-23 18:00:25,213 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:25,213 INFO L470 AbstractCegarLoop]: Abstraction has 70 states and 98 transitions. [2022-02-23 18:00:25,213 INFO L471 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, (9), 2 states have call predecessors, (9), 1 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2022-02-23 18:00:25,213 INFO L276 IsEmpty]: Start isEmpty. Operand 70 states and 98 transitions. [2022-02-23 18:00:25,214 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2022-02-23 18:00:25,214 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:25,214 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:25,245 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-02-23 18:00:25,446 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:25,446 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:25,446 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:25,447 INFO L85 PathProgramCache]: Analyzing trace with hash -1590647429, now seen corresponding path program 1 times [2022-02-23 18:00:25,447 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:25,447 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1273056621] [2022-02-23 18:00:25,447 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:25,447 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:25,471 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:25,471 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [556763011] [2022-02-23 18:00:25,471 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:25,471 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:25,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:25,481 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-02-23 18:00:25,501 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-02-23 18:00:25,518 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:25,519 INFO L263 TraceCheckSpWp]: Trace formula consists of 134 conjuncts, 5 conjunts are in the unsatisfiable core [2022-02-23 18:00:25,520 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:25,586 INFO L134 CoverageAnalysis]: Checked inductivity of 42 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2022-02-23 18:00:25,586 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 18:00:25,586 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:25,586 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1273056621] [2022-02-23 18:00:25,586 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:25,586 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [556763011] [2022-02-23 18:00:25,586 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [556763011] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 18:00:25,587 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 18:00:25,587 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 18:00:25,587 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2133183304] [2022-02-23 18:00:25,587 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:25,587 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:25,587 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:25,588 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:25,588 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 18:00:25,588 INFO L87 Difference]: Start difference. First operand 70 states and 98 transitions. Second operand has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) [2022-02-23 18:00:25,613 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:25,613 INFO L93 Difference]: Finished difference Result 74 states and 101 transitions. [2022-02-23 18:00:25,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:25,613 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) Word has length 49 [2022-02-23 18:00:25,614 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:25,614 INFO L225 Difference]: With dead ends: 74 [2022-02-23 18:00:25,614 INFO L226 Difference]: Without dead ends: 74 [2022-02-23 18:00:25,615 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 45 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-02-23 18:00:25,615 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 5 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:25,615 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 147 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:25,616 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2022-02-23 18:00:25,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 74. [2022-02-23 18:00:25,620 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 36 states have (on average 1.25) internal successors, (45), 40 states have internal predecessors, (45), 30 states have call successors, (30), 8 states have call predecessors, (30), 7 states have return successors, (26), 25 states have call predecessors, (26), 26 states have call successors, (26) [2022-02-23 18:00:25,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 101 transitions. [2022-02-23 18:00:25,620 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 101 transitions. Word has length 49 [2022-02-23 18:00:25,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:25,621 INFO L470 AbstractCegarLoop]: Abstraction has 74 states and 101 transitions. [2022-02-23 18:00:25,621 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.0) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 1 states have call predecessors, (8), 1 states have call successors, (8) [2022-02-23 18:00:25,621 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 101 transitions. [2022-02-23 18:00:25,622 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2022-02-23 18:00:25,622 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:25,622 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:25,639 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-02-23 18:00:25,839 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:25,839 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:25,840 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:25,840 INFO L85 PathProgramCache]: Analyzing trace with hash 1737902154, now seen corresponding path program 1 times [2022-02-23 18:00:25,840 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:25,840 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2019880830] [2022-02-23 18:00:25,840 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:25,840 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:25,849 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:25,849 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [533638826] [2022-02-23 18:00:25,849 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:25,849 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:25,849 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:25,850 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-02-23 18:00:25,851 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-02-23 18:00:25,887 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:25,888 INFO L263 TraceCheckSpWp]: Trace formula consists of 141 conjuncts, 11 conjunts are in the unsatisfiable core [2022-02-23 18:00:25,889 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:26,006 INFO L134 CoverageAnalysis]: Checked inductivity of 44 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2022-02-23 18:00:26,006 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 18:00:26,006 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:26,006 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2019880830] [2022-02-23 18:00:26,006 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:26,006 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [533638826] [2022-02-23 18:00:26,006 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [533638826] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 18:00:26,007 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 18:00:26,007 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-02-23 18:00:26,007 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1477164710] [2022-02-23 18:00:26,007 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:26,007 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:26,007 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:26,008 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:26,008 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-02-23 18:00:26,008 INFO L87 Difference]: Start difference. First operand 74 states and 101 transitions. Second operand has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-02-23 18:00:26,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:26,033 INFO L93 Difference]: Finished difference Result 82 states and 107 transitions. [2022-02-23 18:00:26,033 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:26,033 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 51 [2022-02-23 18:00:26,034 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:26,034 INFO L225 Difference]: With dead ends: 82 [2022-02-23 18:00:26,034 INFO L226 Difference]: Without dead ends: 81 [2022-02-23 18:00:26,034 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 51 GetRequests, 46 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-02-23 18:00:26,035 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 6 mSDsluCounter, 115 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 158 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:26,035 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 158 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:26,036 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 81 states. [2022-02-23 18:00:26,039 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 81 to 79. [2022-02-23 18:00:26,039 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 79 states, 42 states have (on average 1.2142857142857142) internal successors, (51), 45 states have internal predecessors, (51), 27 states have call successors, (27), 10 states have call predecessors, (27), 9 states have return successors, (24), 23 states have call predecessors, (24), 24 states have call successors, (24) [2022-02-23 18:00:26,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 79 states to 79 states and 102 transitions. [2022-02-23 18:00:26,040 INFO L78 Accepts]: Start accepts. Automaton has 79 states and 102 transitions. Word has length 51 [2022-02-23 18:00:26,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:26,041 INFO L470 AbstractCegarLoop]: Abstraction has 79 states and 102 transitions. [2022-02-23 18:00:26,041 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.4) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-02-23 18:00:26,049 INFO L276 IsEmpty]: Start isEmpty. Operand 79 states and 102 transitions. [2022-02-23 18:00:26,049 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2022-02-23 18:00:26,049 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:26,050 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:26,077 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-02-23 18:00:26,280 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:26,280 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:26,281 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:26,281 INFO L85 PathProgramCache]: Analyzing trace with hash 1046589490, now seen corresponding path program 1 times [2022-02-23 18:00:26,281 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:26,281 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [763748335] [2022-02-23 18:00:26,281 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:26,281 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:26,289 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:26,289 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [439174948] [2022-02-23 18:00:26,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:26,289 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:26,290 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:26,291 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-02-23 18:00:26,308 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-02-23 18:00:26,361 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:26,362 INFO L263 TraceCheckSpWp]: Trace formula consists of 143 conjuncts, 10 conjunts are in the unsatisfiable core [2022-02-23 18:00:26,364 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:26,458 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-02-23 18:00:26,458 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 18:00:26,579 INFO L134 CoverageAnalysis]: Checked inductivity of 56 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2022-02-23 18:00:26,580 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:26,580 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [763748335] [2022-02-23 18:00:26,580 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:26,580 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [439174948] [2022-02-23 18:00:26,580 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [439174948] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 18:00:26,580 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 18:00:26,580 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2022-02-23 18:00:26,580 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [421766106] [2022-02-23 18:00:26,580 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 18:00:26,580 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-02-23 18:00:26,581 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:26,581 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-02-23 18:00:26,581 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2022-02-23 18:00:26,581 INFO L87 Difference]: Start difference. First operand 79 states and 102 transitions. Second operand has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-02-23 18:00:26,671 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:26,671 INFO L93 Difference]: Finished difference Result 86 states and 110 transitions. [2022-02-23 18:00:26,671 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-02-23 18:00:26,671 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 54 [2022-02-23 18:00:26,672 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:26,673 INFO L225 Difference]: With dead ends: 86 [2022-02-23 18:00:26,673 INFO L226 Difference]: Without dead ends: 84 [2022-02-23 18:00:26,673 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 110 GetRequests, 99 SyntacticMatches, 1 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=36, Invalid=96, Unknown=0, NotChecked=0, Total=132 [2022-02-23 18:00:26,674 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 17 mSDsluCounter, 108 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 18 SdHoareTripleChecker+Valid, 139 SdHoareTripleChecker+Invalid, 91 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:26,674 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [18 Valid, 139 Invalid, 91 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 18:00:26,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 84 states. [2022-02-23 18:00:26,685 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 84 to 84. [2022-02-23 18:00:26,685 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 46 states have (on average 1.1521739130434783) internal successors, (53), 49 states have internal predecessors, (53), 27 states have call successors, (27), 11 states have call predecessors, (27), 10 states have return successors, (25), 23 states have call predecessors, (25), 25 states have call successors, (25) [2022-02-23 18:00:26,686 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 105 transitions. [2022-02-23 18:00:26,687 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 105 transitions. Word has length 54 [2022-02-23 18:00:26,687 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:26,687 INFO L470 AbstractCegarLoop]: Abstraction has 84 states and 105 transitions. [2022-02-23 18:00:26,687 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 2.625) internal successors, (21), 7 states have internal predecessors, (21), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2022-02-23 18:00:26,687 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 105 transitions. [2022-02-23 18:00:26,691 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 57 [2022-02-23 18:00:26,691 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:26,692 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:26,735 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-02-23 18:00:26,909 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:26,909 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:26,909 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:26,909 INFO L85 PathProgramCache]: Analyzing trace with hash -2126309122, now seen corresponding path program 2 times [2022-02-23 18:00:26,909 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:26,910 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1929327537] [2022-02-23 18:00:26,910 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:26,910 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:26,924 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:26,924 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1643258777] [2022-02-23 18:00:26,924 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 18:00:26,924 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:26,924 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:26,931 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-02-23 18:00:26,970 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-02-23 18:00:26,982 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 18:00:26,982 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 18:00:26,983 INFO L263 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 23 conjunts are in the unsatisfiable core [2022-02-23 18:00:26,984 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:27,190 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 18:00:27,190 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 18:00:27,293 INFO L134 CoverageAnalysis]: Checked inductivity of 59 backedges. 8 proven. 3 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2022-02-23 18:00:27,294 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:27,294 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1929327537] [2022-02-23 18:00:27,294 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:27,294 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1643258777] [2022-02-23 18:00:27,294 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1643258777] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 18:00:27,294 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 18:00:27,294 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2022-02-23 18:00:27,294 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [271467117] [2022-02-23 18:00:27,294 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 18:00:27,295 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2022-02-23 18:00:27,295 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:27,295 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2022-02-23 18:00:27,295 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-02-23 18:00:27,295 INFO L87 Difference]: Start difference. First operand 84 states and 105 transitions. Second operand has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-02-23 18:00:28,172 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:28,172 INFO L93 Difference]: Finished difference Result 108 states and 139 transitions. [2022-02-23 18:00:28,172 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-02-23 18:00:28,172 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 56 [2022-02-23 18:00:28,173 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:28,173 INFO L225 Difference]: With dead ends: 108 [2022-02-23 18:00:28,173 INFO L226 Difference]: Without dead ends: 103 [2022-02-23 18:00:28,173 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 104 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=79, Unknown=0, NotChecked=0, Total=110 [2022-02-23 18:00:28,174 INFO L933 BasicCegarLoop]: 43 mSDtfsCounter, 12 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 180 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:28,174 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 180 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2022-02-23 18:00:28,174 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2022-02-23 18:00:28,177 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 88. [2022-02-23 18:00:28,178 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 88 states, 52 states have (on average 1.1153846153846154) internal successors, (58), 54 states have internal predecessors, (58), 23 states have call successors, (23), 13 states have call predecessors, (23), 12 states have return successors, (21), 20 states have call predecessors, (21), 21 states have call successors, (21) [2022-02-23 18:00:28,178 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 102 transitions. [2022-02-23 18:00:28,178 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 102 transitions. Word has length 56 [2022-02-23 18:00:28,179 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:28,179 INFO L470 AbstractCegarLoop]: Abstraction has 88 states and 102 transitions. [2022-02-23 18:00:28,179 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 1 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2022-02-23 18:00:28,179 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 102 transitions. [2022-02-23 18:00:28,179 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 70 [2022-02-23 18:00:28,179 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 18:00:28,180 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 4, 4, 4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:28,206 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-02-23 18:00:28,396 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:28,397 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 18:00:28,397 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 18:00:28,397 INFO L85 PathProgramCache]: Analyzing trace with hash -296466288, now seen corresponding path program 1 times [2022-02-23 18:00:28,397 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 18:00:28,397 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1786595380] [2022-02-23 18:00:28,398 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:28,398 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 18:00:28,405 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 18:00:28,406 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [92903959] [2022-02-23 18:00:28,406 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 18:00:28,406 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 18:00:28,406 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 18:00:28,413 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-02-23 18:00:28,419 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-02-23 18:00:28,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 18:00:28,459 INFO L263 TraceCheckSpWp]: Trace formula consists of 177 conjuncts, 19 conjunts are in the unsatisfiable core [2022-02-23 18:00:28,460 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 18:00:28,696 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2022-02-23 18:00:28,696 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 18:00:28,846 INFO L134 CoverageAnalysis]: Checked inductivity of 106 backedges. 12 proven. 0 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2022-02-23 18:00:28,846 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 18:00:28,846 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1786595380] [2022-02-23 18:00:28,846 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 18:00:28,846 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [92903959] [2022-02-23 18:00:28,846 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [92903959] provided 1 perfect and 1 imperfect interpolant sequences [2022-02-23 18:00:28,846 INFO L191 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-02-23 18:00:28,846 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 8 [2022-02-23 18:00:28,847 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1306840130] [2022-02-23 18:00:28,847 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 18:00:28,847 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-02-23 18:00:28,847 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 18:00:28,847 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-02-23 18:00:28,847 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2022-02-23 18:00:28,848 INFO L87 Difference]: Start difference. First operand 88 states and 102 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, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-02-23 18:00:28,877 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 18:00:28,877 INFO L93 Difference]: Finished difference Result 86 states and 100 transitions. [2022-02-23 18:00:28,877 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 18:00:28,878 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, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) Word has length 69 [2022-02-23 18:00:28,878 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 18:00:28,878 INFO L225 Difference]: With dead ends: 86 [2022-02-23 18:00:28,878 INFO L226 Difference]: Without dead ends: 0 [2022-02-23 18:00:28,878 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 138 GetRequests, 128 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2022-02-23 18:00:28,879 INFO L933 BasicCegarLoop]: 33 mSDtfsCounter, 6 mSDsluCounter, 85 mSDsCounter, 0 mSdLazyCounter, 21 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 118 SdHoareTripleChecker+Invalid, 22 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 21 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 18:00:28,879 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 118 Invalid, 22 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 21 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 18:00:28,879 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-02-23 18:00:28,879 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-02-23 18:00:28,879 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-02-23 18:00:28,879 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-02-23 18:00:28,879 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 69 [2022-02-23 18:00:28,880 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 18:00:28,880 INFO L470 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-02-23 18:00:28,880 INFO L471 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, (10), 2 states have call predecessors, (10), 1 states have return successors, (8), 2 states have call predecessors, (8), 2 states have call successors, (8) [2022-02-23 18:00:28,880 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-02-23 18:00:28,880 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-02-23 18:00:28,882 INFO L764 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-02-23 18:00:28,901 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2022-02-23 18:00:29,095 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable8 [2022-02-23 18:00:29,098 INFO L732 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 18:00:29,099 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-02-23 18:00:29,100 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 06:00:29 BasicIcfg [2022-02-23 18:00:29,100 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-02-23 18:00:29,101 INFO L158 Benchmark]: Toolchain (without parser) took 6441.14ms. Allocated memory was 163.6MB in the beginning and 204.5MB in the end (delta: 40.9MB). Free memory was 109.3MB in the beginning and 146.8MB in the end (delta: -37.5MB). Peak memory consumption was 4.9MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,101 INFO L158 Benchmark]: CDTParser took 0.15ms. Allocated memory is still 163.6MB. Free memory is still 125.7MB. There was no memory consumed. Max. memory is 8.0GB. [2022-02-23 18:00:29,101 INFO L158 Benchmark]: CACSL2BoogieTranslator took 289.71ms. Allocated memory was 163.6MB in the beginning and 204.5MB in the end (delta: 40.9MB). Free memory was 109.2MB in the beginning and 177.1MB in the end (delta: -67.9MB). Peak memory consumption was 8.3MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,101 INFO L158 Benchmark]: Boogie Preprocessor took 40.03ms. Allocated memory is still 204.5MB. Free memory was 177.1MB in the beginning and 175.7MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,101 INFO L158 Benchmark]: RCFGBuilder took 284.76ms. Allocated memory is still 204.5MB. Free memory was 175.7MB in the beginning and 165.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,101 INFO L158 Benchmark]: IcfgTransformer took 16.12ms. Allocated memory is still 204.5MB. Free memory was 165.2MB in the beginning and 163.8MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,102 INFO L158 Benchmark]: TraceAbstraction took 5802.06ms. Allocated memory is still 204.5MB. Free memory was 163.1MB in the beginning and 146.8MB in the end (delta: 16.3MB). Peak memory consumption was 16.4MB. Max. memory is 8.0GB. [2022-02-23 18:00:29,103 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.15ms. Allocated memory is still 163.6MB. Free memory is still 125.7MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 289.71ms. Allocated memory was 163.6MB in the beginning and 204.5MB in the end (delta: 40.9MB). Free memory was 109.2MB in the beginning and 177.1MB in the end (delta: -67.9MB). Peak memory consumption was 8.3MB. Max. memory is 8.0GB. * Boogie Preprocessor took 40.03ms. Allocated memory is still 204.5MB. Free memory was 177.1MB in the beginning and 175.7MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 284.76ms. Allocated memory is still 204.5MB. Free memory was 175.7MB in the beginning and 165.2MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 16.12ms. Allocated memory is still 204.5MB. Free memory was 165.2MB in the beginning and 163.8MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 5802.06ms. Allocated memory is still 204.5MB. Free memory was 163.1MB in the beginning and 146.8MB in the end (delta: 16.3MB). Peak memory consumption was 16.4MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 13]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 37 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 5.8s, OverallIterations: 9, TraceHistogramMax: 7, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 1.3s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 121 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 87 mSDsluCounter, 1247 SdHoareTripleChecker+Invalid, 1.0s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 889 mSDsCounter, 69 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 360 IncrementalHoareTripleChecker+Invalid, 429 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 69 mSolverCounterUnsat, 358 mSDtfsCounter, 360 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 635 GetRequests, 576 SyntacticMatches, 7 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=88occurred in iteration=8, InterpolantAutomatonStates: 48, 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, 9 MinimizatonAttempts, 19 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.3s SatisfiabilityAnalysisTime, 1.9s InterpolantComputationTime, 426 NumberOfCodeBlocks, 426 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 635 ConstructedInterpolants, 0 QuantifiedInterpolants, 1676 SizeOfPredicates, 16 NumberOfNonLiveVariables, 1087 ConjunctsInSsa, 105 ConjunctsInUnsatCore, 13 InterpolantComputations, 7 PerfectInterpolantSequences, 627/666 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold RESULT: Ultimate proved your program to be correct! [2022-02-23 18:00:29,136 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...